Answer all parts of each question.

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

A superscalar architecture uses multiple functional units at each
stage of the processor pipeline.  For example, multiple instructions
may be fetched into multiple instruction registers, there may be
several ALUs in the execution stage of the pipeline instead of one,
several possible execution paths through a program may be in progress
at the same time even though only one may be the correct one (known as
'speculative execution'), and there may be multiple outputs waiting to
be returned to the user (and some may be due to unwanted speculative
execution). 

1.  Define a superscalar machine in terms of the Flynn category of
parallel computers.

2.  Discuss the types of data and control hazards that can occur in a
superscalar machine.  Can these hazards be prevented by reorganizing
the program outside the superscalar CPU?  Explain.

3.  Compare a superscalar machine to a fine-grained parallel computer
such as the Masspar or the Connection Machine 2 (CM-2).  Are there
classes of problems or computational tasks that are better suited for
one than the other (eg, ray tracing versus an O/S kernel)?  Explain.

Operating Systems
-----------------

Consider the following four synchronization mechanisms (you choose the
fourth one)

	(A) test-and-set
	(B) semaphores
	(C) message passing
	(D) Your choice, but may not be A, B, or C

1.  Explain each of the mechanisms in detail.  In particular, describe
briefly how each mechanism works and specify an appropriate set of
operations for each mechanism.  Where appropriate, discuss both
multi-processor and multi-tasking implementations.

2.  Using sufficiently detailed pseudo-code for each synchronization
mechanism, write a simple program whose execution will deadlock (or
may deadlock if deadlock is possible but not inevitable).

3.  For each of the four mechanisms, explain how a system using that
mechanism, possibly modified, would address deadlock avoidance and/or
deadlock recovery.

Distributed Computing
---------------------

Often distributed systems require that a unique process, called a
coordinator, be designated to perform certain services.  Should the
coordinator fail, an election algorithm is required to choose a new
coordinator.

1.  List several services for which a coordinator might be required.

2.  How might coordinator failure be detected?

3.  In an appropriate pseudo-code, clearly specify an election
algorithms and briefly argue its correctness.  If you know of other
election algorithm, mention them briefly.

Parallel Computing
------------------

1.  What is the "cache coherence" problem in shared memory
multiprocessors?  Describe two standard solutions to the problem.

2.  We would like to execute the program loop below in parallel by
scheduling the iterations on different processors.

	for i := 0 to N do
	         access_shared_data(i);
		 do_work(i);
	end;

Assume that the function do_work() is such that do_work(i) and
do_work(j) can be executed in parallel if i!=j.  Also each invocation
of do_work() requires 29 seconds of cpu time.  However, the function
access_shared_data() has a critical section and requires 3+2p seconds
to execute if p-1 other processors are currently executing it.  As a
function of N, what is the number of processors to use to execute the
loop in the shortest amount of time?