1CS232 Midterm Exam 2April 8, 2002Name:• This exam has 7 pages, including this cover.• There are three questions worth a total of 100 points.• You have 50 minutes. Budget your time!• No written references or calculators are allowed.• To make sure you receive full credit, write clearly and show your work.• We will not answer questions regarding course material.Question Maximum Your Score130235335Total 1002Question 1: Single-cycle datapath (30 points)Let’s simplify the MIPS instruction set architecture a little by removing the original lw and sw instructionsand replacing them with ones that do not contain a constant offset. Our new loads and stores will have thefollowing general forms.lw rt, rs # rt = Mem[rs]sw rt, rs # Mem[rs] = rtThese are I-type instructions, but you maynot make any assumptions about the instructions’ constant fields.Part (a)Show what changes must be made to the single-cycle datapath below so the new lw and sw instructions canavoid going through the ALU. Please try to keep your modifications as neat as possible! (10 points)RegistersReadaddrInstructionmemoryInstr[31-0]ReadaddrWriteaddrWritedataDatamemoryReaddataMemWriteMemRead1Mux0MemToReg4Shiftleft 2PCAddAdd0Mux1PCSrcSignextend0Mux1ALUSrcResultALUALUOp[15-0]rsrtrd0Mux1RegDstReadreg 1Readreg 2WriteregisterWritedataReaddata 2Readdata 1RegWrite3Question 1 continuedPart (b)Fill in the table below to show the correct control signals for the new lw and sw instructions. You must write‘X’ to indicate any don’t-care conditions. (5 points)Part (d)What general conclusions can you draw, if any, about the performance of the original processor as comparedto your modified one? (10 points)Part (c)Assume that memories and the ALU have 2ns delays, and the registers have a 1ns delay. Find the minimumclock cycle times forboth the original single-cycle datapath and your modified one. (5 points)RegDst RegWrite ALUSrc ALUOp MemWrite MemRead MemToReg PCSrclwsw4Question 2: Multicycle CPU implementation (35 points)MIPS is a register-register architecture, where arithmetic source and destinations must both be registers. Butlet’s think about including a register-memory addition instruction.addm rd, rs, rt # rd = rs + Mem[rt]In other words, register rt contains a memory address which is read to produce the ALU’s operand. Theinstruction format is given here for your reference (shamt and func are not used).It is possible to includeaddm in a multicycle processor by modifying the datapath and control unit presentedin class. Your implementation ofaddm should not need more than five stages for execution, and you shouldbe careful not to modify any registers other than rd.Part (a)The multicycle datapath from lecture appears below. Show the changes needed to support addm. Try to keepyour diagram neat! (10 points)Field op rs rt rd shamt funcBits 31-26 25-21 20-16 15-11 10-6 5-0ResultZeroALUALUOp0Mux1ALUSrcA0123ALUSrcBReadreg 1Readreg 2WriteregisterWritedataReaddata 2Readdata 1RegistersRegWriteAddressMemoryMemDataWritedataSignextendShiftleft 20Mux1PCSrcPCABALUOut4[31-26][25-21][20-16][15-11][15-0]InstrregisterMemorydataregisterIRWrite0Mux1RegDst0Mux1MemToReg0Mux1IorDMemReadMemWritePCWrite5Question 2 continuedPart (b)Complete this finite state machine diagram for the addm instruction. Control values not shown in each stageare assumed to be 0. Remember to account for any control signals that you added or modified in the previouspart of the question. (25 points)IorD = 0MemRead = 1IRWrite = 1ALUSrcA = 0ALUSrcB = 01ALUOp = 010PCSource = 0PCWrite = 1ALUSrcA = 0ALUSrcB = 11ALUOp = 010Instruction fetchand PC incrementRegister fetch andbranch computationBranchcompletionR-typeexecutionEffective addresscomputationMemoryreadlw registerwriteOp = BEQOp = R-typeOp =LW/SW Op = SWOp = LWALUSrcA = 1ALUSrcB = 00ALUOp = 110PCSource = 1PCWrite = ZeroALUSrcA = 1ALUSrcB = 00ALUOp = funcWrite-backMemorywriteRegDst = 1MemToReg = 0RegWrite = 1IorD = 1MemWrite = 1ALUSrcA = 1ALUSrcB = 10ALUOp = 010IorD = 1MemRead = 1RegDst = 0MemToReg = 1RegWrite = 1Op = ADDM6Question 3: Forwarding and stalling (35 points)Part (a)Show or list all of the dependencies in the following code fragment. Make sure that you clearly indicatewhich instructionsand registers are involved in each dependency. (5 points)add $8, $5, $5sub $8, $8, $10lw $6, 4($8)add $4, $6, $8Part (b)The pipelined datapath on the next page shows the fifth cycle of executing this program. Fill in the correctdatapath values for thefifteen question mark symbols ? in the diagram. There is one ? in the IF stage, threein the ID stage, eight in EX, two in MEM, and one in WB. (30 points; 2 points each)• Assume that registers initially contain their number plus 100: $6 contains 106, $8 contains 108, etc.• Write your values directly on the diagram, but please write clearly.• Use decimal notation. You may write ‘X’ for any values that cannot be determined.7Question 3 continuedInstructionmemoryAddressWritedataDatamemoryReaddata10PCALURead 1Read 2WriteregisterWrite dataData 2Data 1RegistersRdRt01IF/IDID/EXEX/MEMMEM/WBControlRs012012ForwardingUnitHazardUnit010ID/EX.MemReadPC Write??8?????????????ID: add $4, $6, $8(three values)EX: lw $6, 4($8)(eight values)MEM: sub $8, $8, $10(two values)WB: add$8, $5, $5(one value)IF: ???(one
View Full Document
Unlocking...