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 PointsNAME: ___________________________ 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 µBr Next State FETCH0: MA <- PC; A <- PC 0 PC 0 1 1 * * 0 1 * 0 * 0 N * IR <- Mem 1 * * 0 0 * * 0 0 0 1 * 0 N * PC <- A+4 0 PC 1 1 0 * INC_A_4 1 * * 0 * 0 D * . . . NOP0: microbranch back to FETCH0 0 * * 0 * * * 0 * * 0 * 0 J FETCH0 XADD0: MA <- R[rd] 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] * rs 1 1 1 0 * 0 0 0 1 * 0 N * Mem <- A+B * * * 0 * * ADD 1 * 1 1 * 0 J FETCH0 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 PipelineNAME: ___________________________ Problem Q.2.A-B Hazards [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) or even LW r2, 0(r3) ADD r4, r2, r5 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
View Full Document
Unlocking...