CSE 240A -- Principles in Computer Architecture

Readings. I will cover the text (H&P) in pretty much this order. So if you know where I am, you should be able to stay ahead of me on the reading.1-1.7 (skim), 1.8-1.10, 1.11 (okay, just always read fallacies and pitfalls, and always at least skim the historical perspective, but I’ll quit typing them in). B.1-B.11 (skim B.8). A.1-A.10 (skim A.7), 2.1-2.11,3.1-3.9 (skim 3.4, 3.6), C.1-C.8 (skim C.5),  5.1-5.8 (skim 5.4). 4.1-4.2 (skim 4.2).

Homework should be typed. Please put your name only on the first page.

• Homework 1 -- Due October 8.
  • P1, P2, P3, P4, P5, P6, P7, P8
  • P1: Program A runs 20 billion instructions on a 2 GHz processor, and achieves a CPI of 1.5. Introduction of a new instruction to the ISA (and recompiling the code) would allow a reduction in the instruction count to 19 billion instructions, resulting in a speedup of 1.2. What is the CPI for the new code on the improved processor?
  • P2: Machine B runs at 2 GHz and has a CPI of 1.3 for a particular program. Machine C runs at 5 GHz and has a CPI of 2.4 for that program, while executing 20% more instructions. Which machine is faster? What is the speedup over the slower machine?
  • P3: You have an optimization that speeds up floating point operations by a factor of 2, but does not help other instructions. You have another optimization that only speeds up non-FP instructions by 10% (that is, it speeds up those instructions by a factor of 1.1), and you want to decide which to use. Suppose your favorite program has 10% of its instructions FP operations. Further, assume FP operations have a CPI of 3.0, while non-FP instructions have a CPI of 1.0.
  • P4: (Amdahl's law backwards) You improve your memory subsystem so that memory latencies are sped up by a factor of 2.4. After applying the optimization, you observe that you now spend half your time on waiting for memory. What percentage of the original execution (before the optimization) was spent waiting for memory?
  • P5: Give me the code for D = (A + B) / C in an accumulator, stack, GPR, and load-store ISA. For each give me the total size (in bits) of the code, assuming (a) fixed-length instructions, and then (b) variable-length instructions. Assume opcodes are 6 bits, memory addresses are 32 bits, and register specifiers are 4 bits. You'll probably make other assumptions -- just tell me what they are.
  • P6: Suppose we wanted to add the auto-increment addressing mode to the MIPS ISA -- e.g., lw R1, 1000(R2++). This saves an instruction every time we observe a load followed by an increment of the address register. Is this a good idea? Consider only performance, and assume that we have to increase cycle time by 5% to accommodate the new instruction, that 20% of our instructions are loads, that we can apply this change to 40% of all loads, and that the CPI doesn't change.
  • P7: For the following code:

    for (i=0; i<= 100; i++)

        {A[i] = B[i] + C;}

    give the assembly in MIPS code. Assume i is in register R1, that the starting address of Array A is in R2, the address of array B is in R3, that the address of C is in R4. What is the dynamic instruction count of this code?

  • P8: Assume we are executing MIPS code where 15% of instructions are conditional branches, 20% are load instructions, 5% are stores, and the rest are arithmetic. For this code, (a) what percentage of all memory accesses are for data? (b) what percentage of all data accesses are reads? (c) what percentage of all memory accesses are reads? [minor hint -- what do we access memory for besides loads and stores to data memory?]
• Homework 2 -- Due October 20
  • P1, P2, P3, P4, P5, P6, W1
  • P1 -- Show forwarding and stalls for the following code, assuming the pipelined machine from figure A.24 (including all reasonable forwarding logic). Show it the way we did in class, with IF ID EX M WB, and arrows and bubbles.

    lw R3, 100(R5)
    add R6, R3, R2
    sub R9, R3, R8
    lw R1, 2000(R9)
    add R5, R4, R3
    addi R7, R1, #8

  • P2 -- What is the steady-state CPI (ie, assume the branch is taken very many times) of the following code, if we assume the 5-stage MIPS pipeline, but with no support for forwarding (except reg-file forwarding). Also assume no branch delay slot, but rather the "assume branch not taken" approach. Assume the pipeline in figure A.24 for branch hazards.

  loop: lw R1, 100(R2)
  addi R1, R1, #1
  sw R1, 0(R2)
  addi R2, R2, #4
  sub R4, R3, R2
  bnez R4, loop

  • P3 -- What is the steady-state CPI for the same code, but assuming normal forwarding logic. Also, assume a branch delay slot. You may move an instruction into the branch delay slot if possible, but assume no other code reordering. (hint -- you have to make some assumptions about the R4 dependence -- what assumptions make the most sense?)
  • P4 -- Assume code where 20% of instruction are conditional branches and 5% are jumps and procedure calls. Assume an alternate scalar pipeline where the branch target is resolved at the end of the second pipeline stage, and the branch condition is resolved at the end of the third cycle. Also, assume branches are taken 60% of the time, and that we have a useful instruction in the branch delay slot 75% of the time. What is the CPI of this code if we only experience stalls for branch hazards? Assume the ISA uses branch delay slots for jumps/procedure calls as well as conditional branches. Also, assume the architecture takes an "assume branch taken" strategy.
  • P5 -- Repeat problem P1, but this time assume a 6-stage pipeline, with memory access requiring two stages (IF ID EX M1 M2 WB). The result of the memory access is not available until the end of M2.
  • P6 -- Circle all of the instructions in the following code that could safely be moved into the branch delay slot (replacing the nop). Assume other instructions cannot be reordered or changed. Assume you know nothing about the missing code (the ...). Assume no direct path from the fall through code to the taken path.

  add R1, R2, R3
  sub R5, R2, R3
  and R7, R5, R2
  lw R8, 1000(R5)
  beq R7, R15, label:
  nop
  add R6, R7, R5
  sub R5, R7, R5
  lw R9, 2000(R2)
  ...
  label: add R9, R7, R5
  addi R5, R0, #0
  ...

  • W1 -- Using the web, find the number of pipeline stages for the following processors: Intel Nehalem, Intel Core 2 Duo, AMD Opteron, AMD Phenom.
• Homework 3 -- Due November 3.
  • H&P 2.2, P1, P2, P3, P4 (replaces 2.12)
  • P1 -- Consider 2 branch predictors, a 2-level local history predictor (local history table indexed by PC, branch history table of predictors indexed by local history table entry), and a correlating predictor (branch history table indexed by only the global history register). In each case the BHT is the same size (indexed by the same number of bits). We also discover that for the following code, the 2-level local predictor predicts the loop back branch B perfectly (after it gets warmed up), while the correlating predictor does not. What do we know about the size of the BHT? Assume the branches do not conflict with each other in the prediction tables.

        for (j=0;j<10,000;j++) {
              for (i=0;i<7;i++) { // seven iterations
                   ...
                   if (A[i] = = 0) {  // branch A
                       ...
                   }
               }  // loop back branch B
           } // loop back branch C  

  • P2 -- Increasing the size of a branch predictor typically reduces the chances of "aliasing" -- two branches sharing the same predictor. Usually, sharing results in negative interference (decreased prediction accuracy), but sometimes it can result in positive interference. Assuming a PC-indexed table of 2-bit predictors,
    (a) Give an example of two branches (eg, show the T, N patterns for each, and how they are interleaved) that would result in positive interference (increased overall prediction accuracy).
    (b) Give an example of two branches that would result in negative interference.
    (c) Explain why most of the time you would expect to see negative interference with real code.
  • P3 -- Consider a scalar processor. I'll define latency as the number of cycles between the start of execution of one instruction and the potential start of execution of a dependent instruction. Loads have a latency of 2, other integer instructions have a latency of 1, and fp adds have a latency of 5. For the following code, what is the expected speedup of an out-of-order processor vs an in-order processor? Assume the loop is executed many times. Assume branch prediction eliminates all branch hazards. Assume an in-order processor where consecutive, independent instructions can issue on consecutive cycles (even if it results in out-of-order completion). Assume plenty of functional units.

    loop:l.d F2, 1000(r2)     
         add.d F6, F2, F4     
         add.d F10, F6, F8     
         addi r2, r2, #8     
         add.d F12, F2, F14     
         lw r3, 2000(r5)     
         beqz r3, loop  

  • P4 -- Consider the code of Figure 2.35, running on two scalar Tomasulo dynamic scheduling machines with the latencies of Figure 2.35. The first is similar to the one described in class. The second, designed by architects who did not take this class, uses the actual register name (e.g. R2 or F2) rather than the reservation station name, to identify the value on the Common Data Bus. The result of this design is that no ambiguous register names can be in RS's at once (ie, we lose register renaming). For that machine, then, assume that we cannot issue an instruction with a WAW hazard until the prior instruction has cleared the CDB. (a) Do we have to worry about WAR hazards? (b) For the handicapped machine, show me what cycle each instruction Issues to a RS, begins execution, and writes the CDB. Assume, for example, the first LD issues in cycle 0, executes cycle 1, and writes the CDB in cycle 4 (c) Show me the same for the normal Tomasulo machine. (d) What is the performance gain (in cycles) for register renaming? (Hint -- to get a latency of +n over single-cycle, which we would call a latency of n+1, you can assume the instruction spends n+1 cycles in execution, writing the CDB on the last of those cycles. That means the integer add with a latency of +0 (1) would execute in one cycle, writing the CDB that cycle). Assume unlimited RSs and functional units, but make sure you could also solve it if you had limited resources.
• Homework 4 -- Due November 24
  • H&P 2.3 (translation -> 2-way in-order superscalar), 2.5, 5.1a,b,c, P1, P2
  • P1 -- repeat 2.3, but this time assume out-of-order (e.g., Tomasulo) -- watch for CDB conflicts (although there will be two CDBs)
  • P2 is here. (see email update)
• Homework 5 -- Due December 3
  • H&P 5.7*, 5.18a,b,c, P6, P7, P8, W2
  • *assume a prefetch access is initiated the cycle following the access (either hit or miss) that generates the prefetch.
  • P6-8 are here.
  • W2. Give me size, associativity, and block size of all caches on the Intel Core i7 (Nehalem).