Please Note:  All homework assignments must be typed, unless otherwise specified.

Please make sure you understand the class integrity poliy before you begin doing any of the homeworks!

Homework Assignments:

• Homework #1 -- Due Tuesday, October 9
  • P&H 2.3, 2.4, 2.6, 2.8, 2.29, 2.32, 2.37 (only do rows 1, 2, 4, 7, 10)
• Homework #2 -- Due Thursday, October 18
  • P&H 2.57, 4.1, 4.7, 4.10, 4.11, 4.17, 4.22, P1, 3.3, 3.6, 3.10, 3.30
  • P1: Machine B runs at 2 GHz and has a CPI of 1.3 for a particular program. Machine C, which runs at 5 GHz, 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?
• Homework #3 -- Due Thursday, November 1
  • P&H 3.34, 5.3a,b,c,f, 5.8, 5.9, 5.12, 5.20, P2, P3, (5.29***a,b,c,f, 5.36*, 5.41)**
  • * use the following frequencies (loads 28%, stores 10%, reg-reg ALU 43%, branch 16%, jump 3%). Use the following frequencies M1: 4GHz, M2: 3.2GHz, M3:2.8 GHz.
  • ** in the newest, revised versions of the text, these problems appear as 5.27, 5.34 "Two important parameters...", and 5.39 (implement jal).
  • *** in the older version of the text, it refers to Fig 5.27 -- this should be Fig 5.28.
  • P2 -- Give an example of one Intel IA32 instruction that could not be implemented on a single-cycle processor, assuming reg file and memory elements similar to what we used in class.
  • P3 -- This is the same as 5.32, except solve it for the instruction "subi". Show changes, if necessary, to the datapath and control FSM.
  • these might be useful, fig 5.17, fig 5.28, and fig 5.38.
• Homework #4 -- Due Tuesday, November 20
  • P&H 6.1*, 6.2b,c, 6.4, 6.13***, 6.14**, P4, P5, W1
  • *as in the example in the book, just assume all lw instructions, for simplicity.
  • **use figure 6.32, not 6.30, but also refer to 6.27 for the control signals
  • ***use this figure instead (fixed).
  • P4 -- using figure 6.41 as a template, highlight all data paths active (active means carrying data that will actually be used to complete the instruction) for the following code, in the cycle that the lw is in the wb stage:
    • lw $5, 1000($4)
    • add $1, $3, $5
    • sw $10, 1004($4)
    • sub $3, $10, $1
  • P5 -- Show forwarding and stalls for the following code, assuming the pipelined machine from figure 6.36. 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

  • W1 -- Using the web, find the number of pipeline stages for the following processors: Intel Pentium 4, Intel Core 2 Duo, AMD Opteron, Intel Itanium 2.
• Homework #5 -- Due November 29
  • P&H 6.18, 6.19, 6.21, 6.35, 6.36, 6.47 (note 1), P6, P7, 7.4, 7.9*
  • 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 ...).

    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
    ...

  • note 1 -- assume the machine has a branch delay slot that needs to be filled (ie, assume the original code has a nop after the branch). So you need to assume a pipeline similar to 6.36, but with a branch delay slot. In such an architecture, then, we would still need to squash two instructions after the BDS instruction on a taken branch.
  • P7 -- Assume the same code as P5, but running on a different pipeline. In this case, the machine has the following stages: IF ID X1 X2 M1 M2 WB. That is, ALU computation takes two cycles/stages, as does data memory access (the data needed for the alu or memory must be available at the beginning of X1 or M1, and the results are not available until the end of X2 or M2, respectively). Show forwarding and stalls for the code.
  • *To be consistent with our discussions in class, multiply all addresses in the problem by 4 to get the byte addresses. Thus, addresses are 8, 12, 44, ... (this will not change the answers).
• Homework #6 -- Due December 6
  • P&H 7.12**, 7.24, 7.25*, 7.28, 7.32, 7.35, P8, P9, P10, W2.
  • * see (*) from HW#5. Solve for a 2-way associative cache with block size of four words (16 bytes) instead of 1 word.
  • **solve instead for a 256 KB, 4-way set-associative cache with 64-byte blocks. Also include LRU bits.
  • P8 -- Program P running on Processor C achieves an instruction cache miss rate of 6% and a data cache miss rate of 9%. Assume a miss penalty of 25 cycles, that 20% of all instructions are loads, and that we never stall for stores. If the base CPI (ignoring the effect of cache misses) is 1.3, what is the total CPI?
  • P9 -- The equation for MCPI in class assumed a single level memory hierarchy. Derive the MCPI equation for a 2-level cache configuration with separate data and instruction L1 caches, backed up by a unified L2 cache. Use the terms L1DMR, L1IMR, L2MR, L1MP, L2MP, etc.
  • P10 -- For an S KB, n-way set-associative cache with block size of B bytes, what is the size of a tag if memory addresses are 64 bits.
  • W2 -- Using the web, find the on-chip cache configuration (as much detail as you can find) for the following processors: Intel Pentium 4 E, AMD Opteron 850, Intel Core Duo.

Note, the homework may include some problems on the CD and not in the book, and even include some problems ("For More Practice" from the CD) for which they make the solutions readily available. For those ("for more practice") problems only, you may consult the answers, but please do so only after solving them (then you can go back and correct).

Very approximate Reading and Exam Schedule:
 

Date	Topic	Critical	Important	Informative
Sept 27	Introduction	1.2	-	1.1, 1.3, 1.4
Oct 2	ISA	2.1-2.6,2.9	2.13,2.15,2.16	2.7,2.8,2.10-2.12
Oct 4	ISA	-	-	-
Oct 9	Performance	4.1-4.3,4.5	4.4	-
Oct 11	Computer Arithmetic	3.1-3.4,B.5		B.6
Oct 16		3.5-3.6	3.8	3.7
Oct 18	Single-Cycle CPU	5.1,5.3,5.4	5.2
Oct 23	Single-Cycle CPU Control, Multi-cycle CPU	5.5		C.3
Oct 25	Microprogramming and Exceptions	5.6		5.7
Oct 30		6.1,6.2
Nov 1	Pipelining	6.4,6.5
Nov 6	Data Hazards
Nov 8	Midterm
Nov 13	Control Hazards	6.6		6.8
Nov 15	Advanced Pipelining	6.9, 6.10
Nov 20	Cache Basics	7.1-7.2
Nov 22	Thanksgiving
Nov 27
Nov 29	Better Caches	7.3, 7.5	7.6
Dec 4
Dec 6	Multiprocessing and Multithreading
Dec 13	Final, 3:00