ELEG 652 Principles of Parallel Computer Architectures

Homework #5

Issued: Wednesday, November 2th, 2005

Due: Wednesday, November 16th, 2005

Please begin your answer to every problem on a new sheet of paper. Be as concise and clear as you can. Make an effort to be legible. To avoid misplacement of the various components of your assignment, make sure that all the sheets are stapled together. You may discuss problems with your classmates, but all solutions must be written up independently.

  1. Consider the following conditions proposed as sufficient conditions for SC:
  2. Every processor issues memory requests in the order specified by the program.
  3. After a read or write operation is issued, the issuing processor waits for the operation to complete before issue its next operation.
  4. Before a processor Pj can return a value written by another processor Pi,, all operations that were performed with respect to Pi before it issued the store must also be performed with respect to Pj. (In other words, All operations “visible” to Pi must also be “visible” to Pj)

Are these conditions indeed sufficient to guarantee SC executions? If so, say why? If not, construct a counter example, and say why the conditions that were listed in the chapter are indeed sufficient (Culler, 289) in this case.

  1. Below is a multiprocessor system M with:
  • Two processor P1 and P2;
  • Memory location x;
  • Registers R1, R2 in P2;
  • Initial Conditions: x = 0;
  • The following program P is executing on M:

P1P2

x  1R1  x

x  2R2 x

Below is a list of all potential combinations of values that R1 and R2 may have after the program P finish its execution:

R1: 000111222

R2: 012012012

But of course not every combination in the list is legal under a specific memory architecture/model.

  1. Assuming that multiprocessor M follows SC model, Mr. Y makes the following claim:

R1: 000111222

R2: 012012012

A : oxooxoxoo

Where “o” is possible and “x” is impossible

  1. Do you agree? Why or Why not?
  2. Can you outline your claim? (give the cases that are possible and impossible under SC model)
  1. The Multiprocessor M and the program P are the same for this part. However, the memory model description is different. Please list all the possible cases under the following conditions:
  • The network between processor and memory is such that two write operation from the same processor can not arrive out of order
  • The network between processor and memory is such that two read operations from the same processor can not arrive out of order.
  1. Do the same as question 3, but now assume that the reads can arrive out of order

5. The MESI question: A multiprocessor system is executing the following code:

Processor 1 will execute 6 instructions and Processor 2 will execute 7 instructions at the same time. The following assumptions about the system are given:

  1. All loads and stores have no delay so they execute in one cycle each.
  2. Processor 1 and 2 executes instructions at the same frequency with no interruption from OS or other programs. Thus, instructions in processor 1 will execute in the same cycle as processor 2. For example, the load instruction (LD) from Processor 1 will execute at the same time as the move instruction (MOV) from Processor 2 in cycle 1.
  3. Operations in registers DO NOT change the state of cache only load and stores can do that.
  4. Load and stores (and pretty much all operations in these codes) are considered atomic with respect to each other.
  5. All cache lines and blocks are initially in an invalid state (I).

Your job in this question is to fill the following table with the correct information about the state of the cache in Processor 1 and Processor 2 during the execution of these codes.

In this table, “Pn” (where n is either 1 or 2) represent the processor. The “Curr OP” and “Next OP” are the current instruction and next instruction respectively. The “Status” column is the state of the cache line housing the variable AFTER the current instruction has finished. The “Flush?” Column is a simple no or yes column that tells us if the cache line value has been sent to the main memory and who sent this copy (either P1 or P2). An “add R”, “mul R” or “inc R” relates to instructions that operate on registers. The “ld mem” and “st mem” are load and store instructions operating on address _a. You need to fill out the “Status” columns and the “Flush?” column assuming that this machine is using an implementation of the MESI protocol.