CMPEN 431 flow dependences

Question-1 (20 points):

While anti and output dependences can be handled through renaming, true dependences (also called flow dependences) cannot. Observing this, researchers at ABC (a hardware company), which implements MIPS ISA, proposed a strategy named WNM (Who Needs Memory?). In this strategy, the goal is to predict the value that would be returned by a load operation and continue with the predicted value, i.e., the pipeline proceeds with the value predicted by WNM but the load operation is still executed in the background. If, later in execution, the value read from memory (ground truth) is different from the one predicted, the pipeline is flushed and the execution re-starts using the value read from the memory.

(a) Since WNM reads the value from the memory in the background, wouldn’t its performance be bounded by memory latency anyway, that is, why do these researchers think WNM will bring any performance benefits in practice?

(b)Explain the changes in MIPS architecture, using a detailed diagram that shows all relevant components (e.g., pipeline registers, control signals, etc), to implement WNM.   In your diagram, show the “ prediction logic” of WNM as a “ black box”, and include the logic needed to handle mis- predictions as well.

(c) Discuss three different strategies to implement the “ black box” (prediction logic) in (b).

(d) Focusing on one of the strategies you came up in (c), suggest a metric to quantify the effectiveness of WNM, and explain (using your metric) how well your strategy would work for the load instructions in this high-level program code, assuming that both A and B are initialized to all 0s (note that loop body contains 3 assignment statements):

K=0;

DO i = 1 to 100

{ K = K + A(i) + B(i);  A(i) = A(i) +1;     B(i) = B(i) + A(i) }

(e) In general, what types of programs would benefit most from WNM? (f) Why do you think they named this approach as WNM?

Question-2 (20 points):

Consider the complete memory hierarchy. You have a paged memory system. The processor has 256 MB of memory and an 2GB virtual address space with 2 KB pages. The L1 cache is a 128 KB, 4- way set associative cache with 64-byte cache lines. The L2 cache is a 2 MB, 16-way set associative cache with 128-byte lines. Address translation is supported by a 4 entry TLB. Each page table entry is 32 bits. Both the caches in the system employ the LRU policy for page replacement.

(a) Show the breakdown of the fields of virtual address and physical address. Also show the physical address as interpreted by the L1 cache, and the physical address as interpreted by the L2 cache. Clearly mark the number of bits in each address and the number of bits in each field.

(b) What is the number of L2 cache lines per page? What is the number of entries in the page table? What is the page table size in terms of pages?

(c) If a program has a cache line access pattern (in decimal) :

0, 512, 2048, 2560, 3072, 3584, 4096, 1024, 3072, 4096, 3584, 2048,

indicate, for each access, whether it is an L1 hit/miss or L2 hit/miss (note that the addresses in the sequence are cache line addresses. They do not comprise the bits of offsets within a cache line).

(d) Is it possible for this system to address the L1 cache concurrently with the address translation provided by the TLB? Justify your answer using the address breakdowns shown in part (a). What would be the benefit of doing so?

Question-3 (20 points):

Consider a superscalar architecture with two pipelined units, one for load/store and one for ALU instructions (including branches and jumps). The following two tables indicate the order of execution of two threads, A and B, and the latencies mandated by dependences between instructions. For example, A2 and A3 should execute after A1 and there should be at least four cycles between the execution of A3 and A5 and at least two cycles between A4 and A5. In other words, the tables indicate the schedule if the instructions of each of the threads are executed with no multithreading.

Show the execution schedule for the two threads on the two pipelines assuming the following multithreaded architectures:

(a) Fine grain multithreading (start from thread A, switch between threads A and B in every cycle)

(b) Simultaneous multithreading (with priority always given to thread A)

Question-4 (20 points):

A pipelined architecture has the following characteristics:

* The pipeline has 18 stages, each stage normally taking 1 cycle.

* The address of the branch target is computed in stage 9.

* The branch decision is made in stage 13.

* There is only an L1 cache; consequently, all L1 misses go directly to off-chip DRAM.