CSE 240A -- Principles in Computer Architecture

Homework Assignments

Homework 1, due Thursday, October 10

H&P 1.2b,c [yes, these are different questions], 1.5, 1.7, 1.16, 2.4a,c, 2.9, 2.11, 2.12, P1

P1: On a 1 GHz processor, a program runs in 30 seconds, executing 20 billion instructions:

(a) CPI = ??
(b) If we reduce CPI to 1.2, ET = ??
(c) A new compiler reduces IC to .8 billion, but increases CPI to 1.3: good or bad?
(d) For a particular program, a 1 GHz pentium 4 has CPI of .9, 2 GHz pentium 4 has a CPI of 1.1 (why?): What's the speedup?

Homework 2, due Thursday, October 17

H&P 2.19, A.1, A.3*, A.6**a,b,c, A.7, P2, W1

* Replace the last sentence of A.3 with just "How much faster would the machine be without any branch hazards." Please disregard the answer in the book -- I don't like the way they solve it, anyway.
** Assume the new format only applies to source operands, not destination operands.
P2: Consider the hyper-pipelined processor, with a 30-stage, in-order, scalar pipeline. Instructions are fetched in the 3rd stage, executed in the 22nd stage, and memory is accessed in the 25th stage. Branch target and condition are computed in the 20th stage, in a special branch-execute stage.

What is the steady-state CPI of the following loop, assuming the loop is taken many times, perfect branch prediction (ie, the correct instruction is always fetched the cycle after the branch), and full forwarding support.

Loop: LW    R5, 100(R2)
       SUB   R1, R3, R5
       ADDI R7, R5, #12
       LW    R8, 0(R7)
       ADD   R2, R2, #1
       ADD   R8, R8, #8
       BNEZ R2, Loop:

W1: Use the web, or other resources, to find the integer pipeline length for the following processors: Pentium 4, Pentium III, Itanium, Alpha 21264.

Homework 3, due Thursday, October 31

P3, H&P A.11, 3.1a,c, 3.3, 3.6a,c, P4, P5

P3 -- show all cases (using simple figures, like A.41, but with arrows) of stage-to-stage forwarding for the R4000 integer pipeline. Assume the only interesting instructions are LD, DADD, SD. Assume SD needs the data to be stored to memory at the beginning of the DF stage.
P4 -- If necessary, assume a 2K-entry PHT, indexed by either an 11-bit GHR (correlating predictor), 11 bits of the PC (non-correlating), or the two xor'd (gshare).

(a) Show some code where a correlating predictor would outperform a simple non-correlating predictor that uses the PC to index the PHT. Give the mispredict rate for both predictors.
(b) Show some code where the non-correlating predictor would outperform a correlating predictor. Give the mispredict rate for both predictors.
(c) Give the mispredict rate, for the code in both (a) and (b) for a gshare predictor.

P5 -- When two branches use the same PHT entry, it is not always clear whether that helps or hurts prediction (usually hurts, but not always). Give an example of code where two branches (for whatever reason) compete for a single PHT entry, and the mispredict rate gets worse. Give another example where the mispredict rate consistently improves (ie, not just one or two more correct). Assume a PC-indexed PHT, for example.

Homework 4, due Thursday, November 14

H&P 3.8*, 3.16a,b,e,3.21**, W2

3.8 -- deal with the specific case of a PC-indexed table of predictors. Show what can go wrong when instead of using bits 12-2 of the PC (for a 2K-entry table, 0 being the least significant bit), you use bits 14-4.
3.21 -- do not look at the answer in the back. The figure referred to should be Fig 3.29. Also, change the code to:

W2: For the following processors:

Alpha 21164, 21264, Intel Itanium, Pentium 4, UltraSparc III, AMD Athlon

is is dynamically scheduled (out-of-order) or statically scheduled?
if dynamically scheduled, how many reservation stations or instruction queue entries are supported?

Homework 5 , due Thursday, December 5