CS/COE0447 Computer Organization & Assembly LanguageFor ReferenceMulti-Cycle Execution: R-typeMulti-cycle Execution: lwMulti-cycle Execution: swMulti-cycle execution: beqMulti-cycle execution: jFig 5.28 Our final multicycle datapathA Finite State Machine to generate the control signalsQuestionAnswerSlide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Remember this from the single-cycle datapath?And this (from single-cycle datapath)?from the single-cycle datapathSlide 30Slide 31Slide 32Slide 33Slide 34Slide 351CS/COE0447Computer Organization & Assembly LanguageChapter 5 Part 3In-Class Exercises2For Reference•The following slides contain a subset of Chapter 5 Part 3 – the essentials, without the animations, discussion, and so on.•You will get a copy of Figure 5.28 on Exam3 and the Final•Rather than trying to memorize the other slides, try to reconstruct them while looking at Figure 5.28 and thinking about how the instructions are executed3Multi-Cycle Execution: R-type•Instruction fetch–IR <= Memory[PC]; sub $t0,$t1,$t2–PC <= PC + 4;•Decode instruction/register read–A <= Reg[IR[25:21]]; rs–B <= Reg[IR[20:16]]; rt–ALUOut <= PC + (sign-extend(IR[15:0])<<2);•Execution–ALUOut <= A op B; op = add, sub, and, or,…•Completion–Reg[IR[15:11]] <= ALUOut; $t0 <= ALU result4Multi-cycle Execution: lw•Instruction fetch–IR <= Memory[PC]; lw $t0,-12($t1)–PC <= PC + 4;•Instruction Decode/register read–A <= Reg[IR[25:21]]; rs–B <= Reg[IR[20:16]];–ALUOut <= PC + (sign-extend(IR[15:0])<<2);•Execution–ALUOut <= A + sign-extend(IR[15:0]); $t1 + -12 (sign extended) •Memory Access–MDR <= Memory[ALUOut]; M[$t1 + -12]•Write-back–Load: Reg[IR[20:16]] <= MDR; $t0 <= M[$t1 + -12]5Multi-cycle Execution: sw•Instruction fetch–IR <= Memory[PC]; sw $t0,-12($t1)–PC <= PC + 4;•Decode/register read–A <= Reg[IR[25:21]]; rs–B <= Reg[IR[20:16]]; rt–ALUOut <= PC + (sign-extend(IR[15:0])<<2);•Execution–ALUOut <= A + sign-extend(IR[15:0]); $t1 + -12 (sign extended) •Memory Access–Memory[ALUOut] <= B; M[$t1 + -12] <= $t06Multi-cycle execution: beq•Instruction fetch–IR <= Memory[PC]; beq $t0,$t1,label–PC <= PC + 4;•Decode/register read–A <= Reg[IR[25:21]]; rs–B <= Reg[IR[20:16]]; rt –ALUOut <= PC + (sign-extend(IR[15:0])<<2);•Execution–if (A == B) then PC <= ALUOut; •if $t0 == $t1 perform branch7Multi-cycle execution: j•Instruction fetch–IR <= Memory[PC]; j label–PC <= PC + 4;•Decode/register read–A <= Reg[IR[25:21]];–B <= Reg[IR[20:16]];–ALUOut <= PC + (sign-extend(IR[15:0])<<2);•Execution–PC <= {PC[31:28],IR[25:0],”00”};8Fig 5.28 Our final multicycle datapath9A Finite State Machine to generate the control signals wrong; RegDst = 0; MemtoReg = 110Question•In terms of the datapath in Figure 5.28, how is the branch target address calculated, and where is it stored?•In other words, fill in the following:______ <= ______ + ______________11Answer•In terms of the datapath in Figure 5.28, how is the branch target address calculated, and where is it stored?ALUOut <= PC + (sign-extend(IR[15:0])<<2)Recall: beq is I-format:Opcode[31:26] rs[25:21] rt[20:16] imm[15:0]Quiz yourself until it’s easy: what is imm[15:0] for a beq instruction? Why is the above the branch target address?12Question•For which instruction(s) is the branch target address calculated? During which cycle(s)?•Ans: It is calculated during cycle 2 for all instructions. If the current instruction turns out to not be a branch, then the value was calculated for nothing. But, doing this means that branch instructions take 3 rather than 4 cycles. •Go back and look at the instruction execution steps for beq (slide 6). The ALU is not being used for anything else that cycle, so we can use it for this. The things added are the PC and information from the IR, both of which are available during this cycle.•Note: the hardware is decoding the instruction during this cycle, but the various fields ARE available, in the IR. The hardware HAS the current instruction; it just doesn’t “understand” it yet.13Question•What happens during the 3rd cycle for a memory access instruction?•Well, which are the memory access instructions? lw, sw in the subset covered in this chapter. [Others are lbu, lhu, lui]•_____ <= _______ + _______________14Answer•What happens during the 3rd cycle for a memory access instruction?•ALUOut <= A + sign-extend(IR[15:0])•What does A contain?•rs, which was read into A 2nd cycle•What does ALUOut now contain?•The effective address for the memory access: the memory location we are reading from or writing to15Question•What happens during the first cycle for all instructions?•Ans: –IR <= Memory[PC] •The next instruction is read from memory, and stored in the Instruction Register (IR)–PC = PC + 4•The PC is incremented to point to the next instruction16Question•Is the ALU needed to execute a j instruction?•No: its execution is –PC <= {PC[31:28],IR[25:0],”00”}17Question•Why does the j instruction require 3 cycles, since it doesn’t require rs, rt, or rd and does not require the ALU?•Cycle 1: instruction fetch•Cycle 2: decode instruction•Cycle 3: It is only by here that the instruction has been decoded, and the hardware “knows” it is a j (see slide 7)18Question•For a LW, what is ALUSrcB on each cycle? (Figure 5.28 is on slide 8)•Cycle 1: PC = PC+4, so ans = 01•Cycle 2: Compute branch target address, so ans = 3 0b11•Cycle 3: Compute effective address, so ans = 2 0b10•Cycle 4: No use of ALU, so X•Cycle 5: No use of ALU, so X19Question•For a BEQ, what is ALUSrcB on each cycle? (Figure 5.28 is on slide 8)•Cycle 1: PC = PC+4, so ans = 01•Cycle 2: Compute branch target address, so ans = 3 0b11•Cycle 3: Perform A – B, so ans = 0020Question•For which instructions, during which cycles, is ALUSrcA = 0?•Well, it is 0 whenever something is added to the PC•All instructions, Cycle 1 PC = PC + 4•All instructions, Cycle 2–ALUOut <= PC + (sign-extend(IR[15:0])<<2)•That’s it!21Question•For which instructions, during which cycles, is ALUSrcA = 01? (not X)•Whenever the ALU is used to compute something and the top input is A (rs)•R-type, cycle 3 –ALUOut <= A op B •Memory access (lw, sw), cycle 3–ALUOut <= A +