1CS232 Midterm Exam 2April 9, 2001Name:• This exam has 8 pages, including this cover.• There are four questions, each worth 25 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 Score125225325425Total 10021996RegistersQuestion 1: Single-cycle datapathLet’s say we want to execute the following immediate addition instruction in the single-cycle datapath:addi $29, $29, 16The single-cycle datapath diagram below shows the execution of this instruction. Several of the datapathvalues are filled in already. You are to provide values for the twelve remaining signals in the diagram, whichare marked with a ? symbol. (2 points each)You should:• Write your answers directly on the diagram, but write clearly.• Show decimal values.• Assume register $29 initially contains the number 129.• If a value cannot be determined, mark it as ‘X.’ReadaddrInstructionmemoryInstr[31-0]ReadaddrWriteaddrWritedataDatamemoryReaddataMemWriteMemRead1Mux0MemToReg4Shiftleft 2PCAddAdd0Mux1PCSrcSignextend0Mux1ALUSrcResultALUALUOp(add)16292900Mux1RegDstReadreg 1Readreg 2WriteregisterWritedataReaddata 2Readdata 1RegWrite????????????3Question 2: Multicycle CPU implementationWe would like to add a “scaled” addressing mode to the MIPS multicycle architecture:lws rd, rs, rt # rd = Mem[rt + (4 × rs)]For example, if $a0 contains 1000 and $a1 contains 10, then “lws $t0, $a1, $a0” loads $t0 with the value ataddress 1040 (1000 + 4×10).You need to show the correct control signals necessary to implement the lws instruction, by either:• completing the finite state machine diagram on page 4, or• filling in the microprogramming table on page 5.You only need to do one or the other, not both.The multicycle datapath from lecture is shown below, with one important change: the ALUOut register isconnected to the ALUSrcA mux (shown with a dotted line), which now has three inputs instead of two. Noother changes to the datapath are needed.You may assume that ALUOp = 100 performs an integer multiplication, and 010 performs an addition.Finally, here is the instruction format, for your reference (shamt and func are not used):ResultZeroALUALUOp012ALUSrcA0123ALUSrcBReadreg 1Readreg 2WriteregisterWritedataReaddata 2Readdata 1RegistersRegWriteAddressMemoryMemDataWritedataSignextendShiftleft 20Mux1PCSrcPCABALUOut4[31-26][25-21][20-16][15-11][15-0]InstrregisterMemorydataregisterIRWrite0Mux1RegDst0Mux1MemToReg0Mux1IorDMemReadMemWritePCWriteField op rs rt rd shamt funcBits 31-26 25-21 20-16 15-11 10-6 5-04Question 2 continuedComplete this finite state machine diagram for the lws instruction, or fill in the microprogramming table onthe next page,but not both!You can show the control values in either binary or decimal, whichever is more convenient for you.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 = 15Question 2 continuedFill in this microprogramming table for the lws instruction, or complete the finite state machine diagram onthe previous page,but not both!You may need to make up new values for some of these fields, but just make sure your intentions are clear.LabelALUControl Src1 Src2Registercontrol MemoryPCWritecontrol NextFetch Add PC 4 Read PC ALU SeqAdd PC Extshift Read Dispatch 1BEQ1 Sub A B ALU-Zero FetchRtype1 Func A B SeqWrite ALU FetchMem1 Add A Extend Dispatch 2SW2 Write ALU FetchLW2 Read ALU SeqWrite MDR Fetch6Question 3: Pipelining and forwardingPart (a)Show or list all of the dependencies in this program. For each dependency, indicate which instructionsandregister are involved. (5 points)add $8, $5, $5add $2, $5, $8sub $3, $8, $4add $2, $2, $3Part (b)The pipelined datapath on the next page shows the fifth cycle of executing this program, including values forseveral of the stages. Fill in the ten remaining values, marked with a ? symbol, in the EX and MEM stages.(20 points; 2 points each)Again, please:• Write your answers directly on the diagram, but write clearly.• Show decimal values.• Assume that registers initially contain their number plus 100: $2 contains 102, $8 contains 108, etc.• Write ‘X’ for any numbers that cannot be determined.7Question 3 continuedInstructionmemoryDatamemory10PCALURegisters2(Rd)3(Rt)01IF/IDID/EXEX/MEMMEM/WB2(Rs)012012ForwardingUnitEX: sub $3, $8, $4ID: add $2, $2, $3IF: ???MEM: add $2, $5, $8WB: add$8, $5, $5Read 1Read 2WriteregWrite dataData 1Data 2AddrWritedataReaddata23102103X21021082108??????????3388Question 4: Pipelining performanceOne CPU manufacturer has proposed the 10-stage pipeline above for a 500MHz (2ns clock cycle) machine.Here are the correspondences between this and the MIPS pipeline:• Instructions are fetched in the FET stage.• Register reading is performed in the REG stage.• ALU operationsand memory accesses are both done in the EXE stage.• Branches are resolved in the DET stage.• WRB is the writeback stage.Part (a)How much time is required to execute one million instructions on this processor, assuming there are nodependencies or branches in the code? (5 points)Part (b)Without forwarding, how many stall cycles are needed for the following code fragment? (5 points)lw $t0, 0($a0)add $v1, $t0, $t0Part (c)If a branch is mispredicted, how many instructions would have to be flushed from the pipeline? (5 points)Part (d)Assume that a program executes one million instructions. Of these, 15% are load instructions which stall,and 10% of the instructions are branches. The CPU predicts branches correctly 75% of the time. How muchtime will it take to execute this program? (10 points)IPG FET ROT EXP REN WLD REG EXE DET WRB12 3 4 5 6 7 8
View Full Document
Unlocking...