1CS232 Midterm Exam 3April 27, 2005100Total+63502501Your ScoreMaximumQuestionName:Section: This exam has 6 pages (nothing to tear off this time). You have 50 minutes, so budget your time carefully! No written references or calculators are allowed. To make sure you receive credit, please write clearly and show your work. We will not answer questions regarding course material.2Question 1: Pipelined Datapath (50 points)Here is the final datapath that we discussed in class, much like the one we built in Verilog. Branches areresolved in the decode stage.Part (a)If branches are not predicted, how many stall/flush cycles would be required for each branch? Assume no datahazards. (5 points)As drawn, there is an unsupported data hazard when branches use register values computed by earlierinstructions, e.g.,add $3, $1, $2bne $3, $0, branch targetPart (b)Add forwarding data paths to correctly support all data hazards for the bne instruction to the data path below.Hint: by forwarding from the ALU output (marked with a dot), you can avoid adding new stalls. (15 points) Zero Result 0 1 0 1 0 1 0 1 2 0 1 0 1 2 0 1 40 Adrs Data RAM DataForward Control Hazard + + P CAdrs Instr. RAM R1 R2 Wr Data 1 2 Regs= ID/EX.RegisterRt ID/EX.MemRead Rt Rs PC Write IF/ID.Write× 4Ext IF.Flush Rt Rd RsIF/IDID/EXEX/MEMMEM/WB EX/Mem.RegRdMEM/WB.RegisterRdMEM/WB.RegWriteEX/Mem.RegWriteControlMux3Question 1, continuedHere is the control logic for the multiplexor that handles the rs input of the ALU:Part (c)Write the control logic for one of the forwarding muxes you implemented in part (a). (15 points)Part (d)Identify the (true) data dependences in the following piece of code: (10 points)addi $7, $7, 1sll $8, $7, 2add $8, $8, $14lw $8, 0($8)lw $8, 0($8)bne $7, $22, targetPart (e)For the pipeline on the previous page, do any of these data dependences cause stalls? If so, which ones and forhow many cycles. (5 points)if ((EX/MEM.RegWrite == 1) and(EX/MEM.RegisterRd == ID/EX.RegisterRs))ForwardA = 1else if ((MEM/WB.RegWrite == 1) and (MEM/WB.RegisterRd == ID/EX.RegisterRs))ForwardA = 2elseForwardA = 04Question 2: Cache Organization and Performance (50 points)Part (a)Consider the cache drawn above in a processor that uses 32-bit addresses for a byte-addressable memory. Ifthe cache uses 10-bit indices, how big (in bits) are the cache tags? (5 points)Part (b)How much data can the cache hold? (10 points)Part (c)How many bits of storage are required to implement the cache (include all data, tag, and control state)? (5points)Part (d)Explain how dirty bits get used (i.e., when are they set, and when are they read). (5 points)AddressTag IndexBlockoffset0……?=Hit 2-to-1 muxData8B 8B8B=Tag DataValidTagValid DataDirtyDirty5Question 2, continuedPart (e)Given a direct-mapped cache with 4 blocks of 8 bytes, which of the following byte accesses hit? For thoseaccesses that hit indicate whether the hit is because of spatial locality, temporal locality, or neither in thereason column. (20 points)Part (f)If you were given a processor’s base CPI (i.e., the CPI that a processor would have if it never missed in thedata cache), what information would you need in order to compute its CPI with a real cache? (5 points)011100 ---Reason111111000111110111111111000100011111010000111111010101Miss000000Hit/MissAddress (binary)AddressTag IndexBlockoffset6Problem 3, More Pipelined Datapath (+6 extra credit points)Below is a MIPS pipelined datapath, annotated with some signal values. Select the instructions in each pipestage that are consistent with the annotated signal values. Be careful, these are tricky because we’ve includedsome values that are correct, but will be ignored (e.g., the memory address is ignored by the instruction in theMEM stage). A good approach to this problem is to eliminate the answers that are inconsistent with the datapath. (+2 points each) Zero Result 0 1 0 1 0 1 0 1 2 0 1 0 1 2 0 1 40 Adrs Data RAM DataForward Control Hazard + + P CAdrs Instr. RAM R1 R2 Wr Data 1 2 Registers= ID/EX.RegisterRt ID/EX.MemRead Rt Rs PC Write IF/ID.Write× 4Ext IF.Flush Rt Rd RsIF/IDID/EXEX/MEMMEM/WB $s1MEM/WB.RegisterRdMEM/WB.RegWriteEX/Mem.RegWriteControlMuxID stagea) add $t0, $s0, $v0b) bne $t0, $s0, labelc) bne $s0, $v0, labeld) add $s0, $v0, $t0e) bne $v0, $t0, label $t0 $s0 $v0 0regwrite 0 1 $ramemwrite 0EX stagea) sub $t0, $s8, $t0b) addi $t0, $s0, 100c) subi $s1, $t0, 100d) addi $a2, $s1, 100e) sub $t0, $t0, $s1WB stagea) sw $t0, -4($v0)b) addi, $ra, $v0, 100c) lw $a1, 16($s1)d) sll $ra, $s1, $t0e) sub $s1, $ra, $a3 $t0 10xF020 100IF stage MEM stageR-type: op rd, rs, rtI-type: op rs, rt, immop rt,
View Full Document
Unlocking...