Note: This exam is easier than previous exams, and uses quantum
memory to illustrate evaluation of resources, NOT to test an
understanding of quantum computing.


Computer Architecture
---------------------

1.    ( 5) Define a RISC and a superscalar computer architecture.

2. a. (10) List the steps in the instruction execution cycle.
   b. (15) Explain what occurs in each step.



3.    (70 total) Memory Hierarchy and Pipeline Design

Situation
---------

The memory hierarchy describes the components of storage used in 
digital computer systems. At the lowest end are the scarcest and 
fastest resources, registers in the CPU.  At the highest end are 
the largest and slowest resources, such as disk and tape arrays.

Advances in technology have caused the access times at each level 
of the memory hierarchy to differ by tens of nanoseconds instead 
of hundreds or thousands of nanoseconds, although cost is still a 
factor.  For example, available space on a VLSI chip limits the 
number of registers or the size of the cache that can be 
manufactured.

This question examines the access times to the levels of the 
memory hierarchy, and ignores limits due to chip space and costs. 
Instead, a new limit is introduced that is a factor in the design 
of quantum computers, which is the ability to read an arbitrarily 
large array of memory locations in a fixed time, but with an 
associated probability that the value returned from any single 
location will be incorrect in one bit.

Assume that the probability that any one word returned from memory 
has a one-bit error that is proportional to the number of words in 
the storage array.  The probability of error increases as the size 
of the array increases. Where N is the number of words in the 
storage array, the probability of error, Pe, is:

     0 if N = 1, else log2(N-1)/log2(N) if N > 1

This means that storage arrays of size 1 word and 2 words can be 
read with certainty, but the probability of error approaches, but 
will never reach, 1 (certainty), for large storage arrays.

Assume that the access time of a quantum memory array of any size 
is fixed at 1 nanosecond to read one word (32 bits).


Problems
--------

3. a. (5)

Compute the probability of error, Pe, in reading a word from 
storage arrays where N is equal to:

	   1   (a register)
	  64   (a register file)
	4096   (a cache)
	2^64   (main memory)

3. b. (5)

Compute the access time to read one word from each of the arrays 
in part (a). The value may be incorrect.

3. c. (20)

Digital memory that is NOT error-correcting has a probability that 
the value retrieved will be correct, Pr, that is close to 
certainty. Typically this value is on the order of 1 - 10^(-12). 

Assume that the quantum memory will produce the correct value 
after an arbitrary number of reads, M, with probability that the 
correct value will be retrieved, Pr, given by:

     1 - Pe^M

For each of the storage arrays in (a), compute the number of reads 
needed to produce Pr greater than 1 - 10^(-12).

3. d. (5)

Compute the access time needed to read one word from each array in 
(a) with a probability of retrieval, Pr, equal to or better than 
digital memory.

3. e. (10)

Compute the speedup, if any, of the quantum memory over today's 
digital RAM, assuming that all memory on a VLSI CPU can be 
accessed in five (5) nanoseconds, and that main memory can be 
accessed in 50 nanoseconds. Do this for each of the storage arrays 
in (a).

3. f. (25)

Does the quantum memory provide any improvement for the design of 
a pipelined CPU?  Address only the construction of a pipeline 
using registers between stages in the CPU.  Explain your answer, 
that is, why there is or is not an improvement. If there is an 
improvement, compute the speedup obtained by using the quantum 
memory.