Problem

Consider the simultaneous execution of the three programs on the three processors shown in Answer the following questions with reasoning or supported by computer simulation results:

(a) List the 90 execution interleaving orders of the six instructions (o. b, c. d. e, f which will preserve the individual program orders. The corresponding output patterns (6-tuples) should be listed accordingly.

(b) Can all 6-tuple combinations be generated out of the 720 non-program-order inter leavings? Justify the answer with reasoning and examples.

(c) We have assumed atomic memory access in this example. Explain why the output 011001 is not possible in an atomic memory multiprocessor system if individual program orders are preserved.

(d) Suppose non-atomic memory access is allowed in the above multiprocessor. For example, an invalidation does not reach all private caches at the same time. Prove that 011001 is possible even if all instructions were executed in program order but other processors did not observe them in program order.