Computer Architecture and Engineering CS152 Quiz 1 February 12th 2009 Professor Krste Asanovic Name ANSWER KEY This is a closed book closed notes exam 80 Minutes 10 Pages Notes Not all questions are of equal difficulty so look over the entire exam and budget your time carefully Please carefully state any assumptions you make Please write your name on every page in the quiz You must not discuss a quiz s contents with students who have not yet taken the quiz If you have inadvertently been exposed to the quiz prior to taking it you must tell the instructor or TA You will get no credit for selecting multiple choice answers without giving explanations if the instructions ask you to explain your choice Writing name on each sheet 1 Point Question 1 26 Points Question 2 31 Points Question 3 10 Points Question 4 12 Points TOTAL 80 Points NAME Problem Q 1 Microprogramming Bus Based Architectures 26 points In this problem we explore microprogramming by writing microcode for the bus based implementation of the MIPS machine described in Handout 1 Bus Based MIPS Implementation which we have included at the end of this quiz for your reference You are going to implement a fetch and add instruction in microcode Fetch and add reads a memory location adds to it the contents of a source register stores the sum back to the same memory location and returns what was originally in memory in the destination register This instruction is commonly used to provide synchronization in multiprocessor systems The instruction has the following format XAdd rd rs XAdd performs the following operation temp M rd rs rs M rd M rd temp Fill in Worksheet Q1 1 with the microcode for XAdd Use don t cares for fields where it is safe to use don t cares Study the hardware description well and make sure all your microinstructions are legal To further simplify this problem ignore the busy signal and assume that the memory is as fast as the register file Please comment your code clearly If the pseudo code for a line does not fit in the space provided or if you have additional comments you may write in the margins as long as you do it neatly Your code should exhibit clean behavior and not modify any registers except rs in the course of executing the instruction You will receive credit for elegance and efficiency Finally make sure that the instruction fetches the next instruction i e by doing a microbranch to FETCH0 as discussed in the Handout NAME State PseudoCode ld IR Reg Sel Reg Wr en Reg ld A ld B ALUOp en ALU ld MA Mem Wr en Mem Ex Sel en Imm B r Next State FETCH0 MA PC A PC IR Mem 0 PC 0 1 1 0 1 0 0 N 1 0 0 0 0 0 1 0 N PC A 4 0 PC 1 1 0 INC A 4 1 0 0 D 0 0 0 0 0 J FETCH0 0 rd 0 1 0 1 0 0 N B R rs 0 rs 0 1 1 0 0 0 0 N A Mem A R rs Mem A B rs 1 1 1 0 0 0 0 1 0 N 0 ADD 1 1 1 0 J FETCH0 NOP0 microbranch back to FETCH0 XADD0 MA R rd There are many valid ways to solve this problem The problem description both said to use don t cares and to use elegance and efficiency so some but not too many points were deducted for extra cycles or not using don t cares everywhere possible With these tables you can think of the signals taking effect at the next rising edge which is the next row in the table except with jumps For example in the last row when writing to memory the contents of MA don t matter afterwards The last row sets ldMA to because the next rising edge memory will grab the old address from MA and at that same rising edge the don t care will take affect and MA may or may not load a value for the next cycle Another important detail is that the IR is important because it contains things like rs rd and immediates Without it the register file wouldn t know where things like R rs are It needs to be kept around at least until it is no longer needed In the example above it is the last row where rs is used Actual wrong values in the table like s where it should be 0 or 1 had larger deductions because they result in incorrect rather than just less efficient operation NAME Problem Q2 Mem ALU Pipeline 31 points In this problem we consider further modifications to the fully bypassed 5 stage MIPS processor pipeline presented in Lecture 3 and Problem Set 1 We will re order the stages so the Execute ALU stage comes after the Memory stage After this change we will only support register indirect addressing This change will let us use the contents of memory as one of the operands for arithmetic operations For example something like the CAdd instruction could be implemented CAdd rd rs0 rs1 CAdd performs the following operation rd M rs0 rs1 In this problem assume that the control logic is optimized to stall only when necessary and that the pipeline is fully bypassed You may ignore branch and jump instructions in this problem Figure 2 A Mem ALU Pipeline NAME Hazards Problem Q 2 A B 16 points Besides enabling the CAdd instruction this pipeline modification will change which hazards exist in the pipeline We want to compare the pipeline from lecture and the problem set old to this modified pipeline with the ALU after memory new Assume both the old and new pipelines are fully bypassed with correct control logic For each problem below give a sample instruction sequence to clarify your explanation Q 2 A Hazards Removed 8 points Give an example where the old pipeline will stall but the new pipeline will not A load followed by an arithmetic instruction in the next two cycles would have had to stall but not anymore LW r2 0 r3 ADD r4 r2 r5 or even LW r2 0 r3 ADD r4 r5 r6 ADD r4 r4 r2 Q 2 B Hazards Added 8 points Give an example where the new pipeline will stall but the old pipeline will not An arithmetic instruction followed by a dependent memory access ADD r2 r3 r4 LW r5 0 r2 NOTE Branches were not a valid solution to this problem On a branch mis predict the instructions following the branch are flushed not stalled The problem description also said to not consider branches and jumps NAME Problem Q 2 C D Memory Addressing 15 points Q 2 C Hardware Changes 7 points As an architect you want to maintain full compatibility for the old ISA including support for register immediate indirect addressing e g LW r2 8 r3 How would you modify the new pipeline and associated control logic to support this efficiently Option A …
View Full Document
Unlocking...