Quiz 9

This quiz covers Chapter 8 of Tanenbaum. Please allow yourself up to 1 hour to take the quiz, and return it to me by 10:00 AM, Thursday, December 11, if you would like for me to mark it. I will post my answers via the course homepage later that day.

Solutions appear in italics.

A certain RISC architecture uses overlapping register windows for passing parameters between procedures. The machine has 520 registers, and each window has 32 registers, of which 16 are global variables and 8 are local variables.
1. How many registers would be available for use by input parameters?
  4.
2. How many registers would be available for use by output parameters?
  4.
3. By how much would the Current Window Poiner (CWP) be incremented at each procedure call?
  12.
4. How many call frames may be present in the register file?
  (520-16)/12=42. Actually, the 42nd frame would not have room for its output parameters.
The following acronyms are used by Flynn in his taxonomy of computer architectures. For each of the following, say what each acronym stands for and give a brief description and example.
- SISD
  Single instruction stream, single data stream. This is a typical non-pipelined, single processor, single memory processor. The Mic-1 would be an example.
- SIMD
  Single instruction stream, multiple data stream. Here, there are a number of processors, each executing the same instructions in lockstep, each on a different data set. Array processors such as the ILLIAC IV and vector computers are good examples.
- MISD
  Multiple instruction stream, single data stream. There is some debate about whether these exist or not, but one might consider a pipelined processor to be one of these. In this case, multiple instructions are being executed simultaneously in stages on a single data set.
- MIMD
  Multiple instruction stream, multiple data stream. These are computers with shared memory in which each processor may be executing a different program.
16 Pentium 200Mhz computers, each with 2Gbytes of hard disk, 16Mbytes of RAM, and 5 Fast Ethernet ports (100Mbps), are running Linux and are arranged in a hypercube connection scheme. One of the Ethernet ports on each machine is used to connect it to the local area network and from there to the internet, while the other ports are used for interconnection between the machines.
1. Of what degree is the hypercube?
  4.
2. How much communication bandwidth is available between the 16 machines of the system?
  There are 32 dedicated, two-node ethernet segments, and one 16-node ethernet segement. 33 * 100 = 3300Mbps.
3. Assuming that most packets are 256 bytes, how much time (minimum) would a typical packet require to traverse the hypercube from one "corner" to its opposite "corner"?
  Since there are 4 hops from corner to corner, that would be 4 hops * 256 bytes per hop * 8 bits per byte * 1 second per 100,000,000 bits = 81.2 microseconds.
4. How many "hops" is each node from every other node?
  Only one. If you use the shared ethernet segment. At most 4 if you use the hypercube.
5. How many instructions per second are possible (maximum)?
  Assuming 1 instruction per Hz, that's 200 Mhz * 16 processors = 3200 MIPS.