CS232 Fall 2006 Practice Midterm 2 October 25, 2006CS232 Practice Midterm 2Viraj KumarOctober 25, 2006Time: 50 minsName:Instructions:1. This exam has 7 pages, including this cover.2. This is a closed-book, closed-notes examination.3. The exam has 4 questions. Please budget your time.4. Calculators are not allowed. Answers can be left as fractions.5. Please write your answers neatly and, wherever applicable, put the final answer in a box.6. Please show all your work. Partial credit will be awarded for correct approaches.Goo d luck!Problem No. Max. Points Your Score1234Total 1001CS232 Fall 2006 Practice Midterm 2 October 25, 20061. Datapaths(a) We wish to implement a new I-type instruction sw addi on the single-cycle datap-ath shown above. The instruction sw addi $rs, $rt, immediate has the followingmeaning:sw $rt, immediate($rs)addi $rt, $rs, immediateShow that the given datapath can support this new operation simply by setting thecontrol signals appropriately. Fill in the missing values below. Use X to indicate“don’t-care” values:Control signal ValueRegDstRegWriteALUSrcALUOp addMemWriteMemReadMemToRegPCSrc2CS232 Fall 2006 Practice Midterm 2 October 25, 2006(b) The latencies of some of the components of the datapath are given below:Name Latency (ns)Memory 1.25ALU 0.1Control 0.05Note: 1 ns = 10−9seconds(Recall that the Control unit generates the control signals for the datapath based onthe opcode.)The datapath has a 250 MHz clock. Compute the maximum possible latency of theregister file, assuming that reads and writes take the same amount of time. Explainyour answer.(c) Define the imbalance of a pipelined datapath as the ratio of the time required bythe slowest stage to the time required by the fastest stage. (Thus, an ideal pipelineddatapath has imbalance = 1.) If we convert the above single-cycle datapath into a 5-stage pipelined datapath using the components given above, compute the imbalanceof the datapath. Assume that pipeline registers have zero latency, and that the stagesare IF, ID, EX, MEM, WB. How would you reduce the imbalance of the pipelineddatapath?3CS232 Fall 2006 Practice Midterm 2 October 25, 20062. More Datapaths(a) The above figure is a slightly modified version of the 5-stage pipelined datapath wesaw in class. In which stage is the branch target com puted? In which stage is thebranch decision computed? Justify your answers.(b) Explain how the control signal RegWrite propogrates through the datapath. Whereis it produced? What happens to it from the time it is produced to the time it used?(c) If the MEM stage is split into two, how many inputs would the forwarding muxes(not shown) in the EX stage have?4CS232 Fall 2006 Practice Midterm 2 October 25, 20063. Hazards(a) The following chunk of code runs on a 6-stage MIPS pipeline with stages IF, ID, E1,E2, MM, WB. The ALU output is produced at the end of E2, and ALU inputs mustbe available at the start of E1. The datapath implements full fowarding. Clearlyindicate each data hazard with an arrow:add $2, $2, $3 IF ID E1 E2 MM WBsw $2, 0($2) IF ID E1 E2 MM WBlw $1, 0($2) IF ID E1 E2 MM WBadd $2, $1, $0 IF ID E1 E2 MM WB(b) Compute the total number of cycles needed to execute the above code.(c) Re call that jr is an R-type instruction whose rs register contains the PC value of thejump target. The following questions refer to the 5-stage MIPS pipelined datapathdiscussed in class:• The jump target can be computed as early as the stage.• The datapath treats jr instructions as branches that are always predicted taken.Based on your answer above, flushes are necessary to resolve a controlhazard involving jr.(d) The following code is executed on the usual 5-stage MIPS pipeline.loop_top:beq $a0, $0, donelw $s0, 0($a0)bne $s0, $v0, skipaddi $v0, $v0, 1skip:addi $a0, $a0, -4jr $t0 # jump to loop_topdone:jr $raThe pipeline diagram on the next page shows the first iteration of the loop and apart of the second iteration as well.5CS232 Fall 2006 Practice Midterm 2 October 25, 20061 2 3 4 5 6 7 8 9 10 11 12beq IF ID EX MM WBlw IF ID EX MM WBIF IDIF IDbne IF ID EX MM WBaddi IF ID EX MM WBaddi IF ID EX MM WBjr IF ID EX MM WBIF×beq IF · · ·Justify your answer to each of the following questions base d on the diagram:i. The first beq branch is : taken not taken can’t sayii. The bne branch is predicted: taken not taken can’t sayiii. The datapath implements full forwarding: yes no c an’t sayiv. Branches are resolved in: ID stage EX stage other can’t say(e) In all subsequent iterations of the loop, the bne branch is taken. Assuming that thedatapath implements full forwarding, compute the total number of cycles needed ifthe loop body executes N times.6CS232 Fall 2006 Practice Midterm 2 October 25, 20064. Conceptual questi ons:(a) Re call that the I-type instructions lw and sw compute the sum of the rs registerand the immediate value in the EX stage of the 5-stage MIPS pipeline. Suppose wemodify the pipelined datapath as follows:• Switch the order of the EX and MEM stages (i.e. the pipeline now has stagesIF, ID, MEM, EX, WB).• Inse rt a new adder that sums the 16-bit immediate and the 32-bit rs registervalue in the ID stage and stores the result in the ID/MEM pipeline register.• Modify the MEM stage so that the Address input is the value of rs + immediatecomputed in the ID stage.Can forwarding resolve all data hazards in this datapath? If so, argue why. If not,give an example of a data hazard that remains.(b) Consider the 5-stage pipeline from part (a): IF, ID, MEM, EX, WB. Branch targetsare com puted at the end of ID stage and branch decisions are computed at the end ofthe EX stage. Explain why the following statement is true: “A predict taken strategyis easier to implement than a predict not taken strategy.”(c) A graph with n vertices can be represented as a boolean matrix of size n × n whose(i, j)thentry is true if and only if there is an edge between the ithand jthvertices.Alternatively, the graph can be represented as an array of n linked lists whose ithentry is the list of vertices that share an edge with the ithvertex.Knowing that caches exploit s patial and te mporal locality, which graph representa-tion would you choose if n is small and the entire graph is explored several times?How about if n is large and only a portion of the graph is
View Full Document
Unlocking...