1CS232 Midterm Exam 2March 30, 2005100Total203402401Your ScoreMaximumQuestionName:Section: This exam has 6 pages (including a cheat sheet at the end). Read instructions carefully! You have 50 minutes, so budget your time ! 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: Single-cycle CPU implementation (40 points)On the last page of the exam is a single-cycle datapath for a machine very different than the one we saw inlecture. It supports the following (complex) instructions:lw_add rd, (rs), rt # rd = Memory[R[rs]] + R[rt];addi_st (rs), rt, imm # Memory[R[rs]] = R[rt] + imm;sll_add rd, rs, rt, imm # rd = (R[rs] << imm) + R[rt];All instructions use the same format (shown below), but not all instructions use all of the fields.Part (a)For each of the above instructions, specify how the control signals should be set for correct operation. Use Xfor don’t care. ALUOp can be ADD, SUB, SLL, PASS_A, or PASS_B (e.g., PASS_A means pass through thetop operand without change). Full points will only be awarded for the fastest implementation. (20 points)Part (b)Given the functional unit latencies as shown to the right, compute the minimumtime to perform each type of instruction. Explain. (15 points)Part (c)What is the CPI and cycle time for this processor? (5 points)10-0imm15-1120-1625-2131-26BitsrdrtrsopFieldsll_addaddi_stlw_addRegWriteMemWriteMemReadALUop2ALUop1ALUsrc3ALUsrc2ALUsrc1instExplainsll_addaddi_stlw_addMinimum timeinst2 nsRegister File4 nsALU3 nsMemoryLatencyFunc. Unit3Question 2, Multi-cycle implementation (40 points)The (imaginary) jump memory (jmem) instruction is like a jump-and-link (jal) instruction, except both the targetis loaded from memory and the return address is saved to memory. The i-type format is used, as shown below.You can assume that R[rt] and (R[rs] + offset) are distinct (non-overlapping) addresses.jmem (rt), offset(rs) # Memory[R[rs]+offset] = PC+4; # PC = Memory[R[rt]]Part (a)The multicycle datapath from lecture appears below. Show what changes are needed to support jmem. Youshould only add wires and muxes to the datapath; do not modify the main functional units themselves (thememory, register file, and ALU). Try to keep your diagram neat! (15 points)Note: While we’re primarily concerned about correctness, five (5) of the points will only be rewarded tosolutions that use a minimal number of cycles and do not lengthen the clock cycle. Assume that everythingbesides the ALU, Memory and Register File is instantaneous. MemToRegResultZeroALUALUOp 0 M u x 1ALUSrcA0123ALUSrcBReadreg 1Readreg 2WriteregisterWritedataReaddata 2Readdata 1RegisterfileRegWriteAddressMemoryMemDataWritedataSignextendShiftleft 20Mux1PCSrcPC A BALUOut4[31-26][25-21][20-16][15-11][15-0]InstrregisterMemorydataregister IRWrite 0 M u x 1 RegDst 0 M u x 1 0 M u x 1IorDMemReadMemWritePCWrite15-020-1625-2131-26BitsimmrtrsopField4Question 2, continuedPart (b)Complete this finite state machine diagram for the jmem 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 = ADDPCSource = 0PCWrite = 1 ALUSrcA = 0 ALUSrcB = 11 ALUOp = ADDInstruction fetchand PC incrementRegister fetch andbranch computationBranch completionR-type executionEffective addresscomputationMemoryreadlw registerwriteOp = BEQOp = R-typeOp =LW/SW Op = SWOp = LWALUSrcA = 1ALUSrcB = 00ALUOp = SUBPCSource = 1PCWrite = ZeroALUSrcA = 1ALUSrcB = 00ALUOp = funcWrite- backMemorywriteRegDst = 1MemToReg = 0RegWrite = 1ALUSrcA = 1ALUSrcB = 10ALUOp = ADDIorD = 1MemRead = 1RegDst = 0MemToReg = 1RegWrite = 1Op = JMEM IorD = 1MemWrite = 15Question 3: Conceptual Questions (20 points)Write a short answer to the following questions. For full credit, answers should not be longer than twosentences.Part (a)Can the following factors of performance be affected by the implementation (e.g., single-cycle, multi-cycle,etc.)? Explain. (10 points)Number of Instructions:Cycles per Instruction (CPI):Clock Period:Part (b)What is optimistic (or eager) execution? How does it relate to the machine implementations we’ve seen? (5points)Part (c)What differentiates one computer from another? List 5 distinct, important ways (other than ISA) . Single wordanswers are fine, if they are clear. (5 points)1.2.3.4.5.Do not write in shaded region6Performance1. Formula for computing the CPU time of a program P running on a machine X:CPU timeX,P = Number of instructions executedP x CPIX,P x Clock cycle timeX2. CPI is the average number of clock cycles per instruction:CPI = Number of cycles needed ⁄ Number of instructions executed3. Speedup is a metric for relative performance of 2 executions:Speedup = Performance after improvement ⁄ Performance before improvement = Execution time before improvement / Execution time after improvement4PCAddReadaddressWriteaddressWritedataDatamemoryReaddataMemWriteMemReadReadaddressInstructionmemory Instru-ction[31-0]I [10 - 0]I [25 - 21]I [20 - 16]I [15 - 11]0Mux1ALUSrc2Readregister 1Readregister 2WriteregisterWritedataReaddata 2Readdata 1RegistersRegWriteSignextend0Mux1ALUSrc1ResultALUALUOp1Single Cycle
View Full Document
Unlocking...