数字系统设计2 习题课 2012年11月29日 TA: 沈炳锋 沈炳锋 13738073472（683472） 数字系统设计2 习题课 2012年11月29日 TA: 沈炳锋 沈炳锋 13738073472（683472） shenbingfeng@zju.edu.cn 翁波拉 18868818893（544666） wengbola@zju.edu.cn

OUTLINE 1.Pipeline Review 2.HW4 Analysis 3.HW3 Analysis 4.HW2 Analysis 6.Quiz Ι Analysis

作业未交名单 HW1:3090101331 3100101159 3100000122 3100101017 3100102813 3100103897 HW2:3090101331 3100101159 3100101622 HW3:3090101331 3100101159 3100101622 3100101640 3100102766 HW4:3090101331 3100101159 3100104815 3100100798 3100102119 3100102921

1.Pipeline Review

4.12.6 2.HW4 Analysis 未经任何优化的流水数据通路中，分支地址在MEM级写回IF级（需四拍） 多时钟周期 中，分支指令（BEQ）三拍完成。 未经任何优化的流水数据通路中，分支地址在MEM级写回IF级（需四拍）

4.13.2 4.13.5 注意：在考虑$1的数据冒险时，也需考虑$6的数据冒险 注意：a中可使用ALU-ALU转发 无转发，用nop解决冒险 lw $1,40($6) IF ID EX MEM WB add $6,$2,$2 IF ID EX MEM WB Nop N N N N N Nop N N N N N sw $6,50($1) IF ID EX MEM WB $6 注意：在考虑$1的数据冒险时，也需考虑$6的数据冒险 4.13.5 仅使用ALU-ALU转发 $1 lw $1,40($6) IF ID EX MEM WB Nop N N N N N add $6,$2,$2 IF ID EX MEM WB sw $6,50($1) IF ID EX MEM WB $6 注意：a中可使用ALU-ALU转发

4.19.3 注意：MEM to1st ，在仅从EX/MEM转发的机制中，由于结果在MEM产生，无法使用转发机制，需停顿两拍。 仅从EX/MEM或MEM/WB转发，分析两种情况下的延迟。 0 IF ID EX MEM WB 1st IF ID EX MEM WB 2nd IF ID EX MEM WB 注意：MEM to1st ，在仅从EX/MEM转发的机制中，由于结果在MEM产生，无法使用转发机制，需停顿两拍。

两个不应该犯的错误 4.20.1 b中不存在WAR ($1)I1 to I3 提醒：即使参考了答案，也希望能够对其正确性多加思考，答案中明显的或不明显的错误较多。

分支使用了延迟槽； 预测转移发生； EX级产生了分支地址 4.22.2 有转发机制，不需要阻塞 注意：红色部分需整体右移一拍。

4.22.5 全转发；predict-taken机制；分支地址在ID级产生 lw $1,40($6) IF ID EX MEM WB beq $2,$3,label2 （T） IF ID EX MEM WB beq $1,$2,label1 (NT) IF IF ID EX MEM WB sw $2,20($4) IF ID EX MEM WB and $1,$1,$4 ) IF ID EX MEM WB

4.23 Question：如果分支指令处理时使用predict-taken的方法，当预测失败时将产生几个停顿？ Answer:2 beq IF ID EX MEM WB Target inst. IF IF IF ID EX MEM WB Answer:2

4.37.3 分析各级流水线寄存器位数 4.37.4-5 WB级的执行时间由一个多路复用器延迟和寄存器写延迟组成。

附加题 控制信号详见P313 Cycle 5 lw $5, 40($2) IF ID EX MEM WB add $6, $3, $2 IF ID EX MEM WB or $7, $2, $1 IF ID EX MEM WB and $8, $4, $3 IF ID EX MEM WB sub $9, $2, $1 IF ID EX MEM WB 100ten IF/ID (and $8,$4,$3) ID/EX (or $7,$2,$1) EX/MEM (add $6,$3,$2) MEM/WB (lw $5,40($2)) pc+4 100ten control inst 0x00834024 EX RegDst:1 WB RegWrite:1 MemtoReg:0 MemtoReg:1 ALUOp:10 ALUsrc:0 MEM MemRead:0 EX_ANS 52ten MemWrite：0 25ten MEM_OUT 1052ten 96ten wdata 12ten reg_w 5 reg1 6 reg2 11ten sign_exp 0x00003825 rs 2 rt 1 rd 7 控制信号详见P313

3.HW3 Analysis 4.2.4 考察关键路径上时钟的计算。(lw指令) IF: I-MEM ID: Regs EX: 1Mux+ALU MEM: D-MEM WB: 1Mux+Regs （4.7，4.10中情况相同）

4.3.4 分析4.3.2中设计的电路的延迟 指令存储器，分析其读指令延迟，从电路中不难发现，一位数据的读出，需经过一个非门，一个与门和一个或门，因此，总延迟为20+30+30=80ps write latency: max(50,100)+100+160=360ps read latency(Reg1): 50+100+100=250ps read latency(Reg0): 100+100=200ps

4.10.1 在读I-MEM后，控制单元便可开始产生MemWrite信号，但由于memory与regs（RegWrite）均由触发器组成，其写发生在时钟边沿，其控制信号的产生在单周期实现中具有最大的余量，为关键路径时间-Imem延迟时间。关键路径需注意加上WB级中的寄存器写延迟，这里将写延迟理解为触发器的建立时间。 1ALU control 1D_mem 1Mux 1Reg ALUOp ALUSrc MemtoReg RegDst MemWrite RegWrite > MemRead > > Branch > jump > 1Mux 1D_mem 1Reg 1D_mem 1Mux 1Reg 1Mux 1Reg 2Mux 1Mux 边沿

2.将rs寄存器的值作为地址写入PC寄存器中 控制单元中除操作字段外还需输入功能字段 JALR 所执行的操作： 1.将下一条指令的PC存入31号寄存器中。 2.将rs寄存器的值作为地址写入PC寄存器中 附加题

算数逻辑(ALU)指令:addiu;addu;sll;slti 常数指令:lui;li 存储(Memory)指令:lw;sw 附加题 4.HW2 Analysis b) Please compute the number of dynamic instructions and show the instruction mix (types: ALU, Branch, Memory) for both version of the code. 指令类型分类： 算数逻辑(ALU)指令:addiu;addu;sll;slti 常数指令:lui;li 存储(Memory)指令:lw;sw 数据移动指令:move 转移(Branch)指令:bne 跳转指令:j;jr

链接程序用于处理分支指令，跳转指令和数据地址中，其基本工作方式是：找到旧的地址，代之以新的地址。 c) In the optimized code, find the code or data references that need to be resolved by the linker. 链接程序用于处理分支指令，跳转指令和数据地址中，其基本工作方式是：找到旧的地址，代之以新的地址。 0x0: lui gp, 0 0x4: addiu gp, gp, 0 0x8: addu gp, gp, t9   0xc: li a2, 10   0x10: move a1, zero 0x14: lw a0, 0(gp) 0x18: lw v1, 4(gp)   0x1c: lw v0, 0(v1) 0x20: addiu v1, v1, 4 0x24: addiu a1, a1, 1 0x28: addu v0, v0, a2 0x2c: sw v0, 0(a0) 0x30: slti v0, a1, 100 0x34: addiu a0, a0, 4 0x38: bne v0, zero, 0x1c 0x3c: jr ra 链接程序工作的三个步骤： （1）将数据和代码模块装入存储器 （2）确定数据和指令标号的地址 （3）修补所有内部和外部调用的真正地址 the linker need to resolve the following code or data references 1.0x38: bne v0, zero, 0x1c 2.ra，gp

5.HW1 Analysis ack: # prologue addiu $sp, $sp, -12 sw $ra, 0($sp) unsigned int ack(unsigned int m, unsigned int n) { unsigned int answer; if(m == 0) answer = n+1; else if(n == 0) answer = ack(m-1, 1); else answer = ack(m-1, ack(m, n-1)); return answer; } 5.HW1 Analysis ack: # prologue addiu $sp, $sp, -12 sw $ra, 0($sp) sw $a0, 4($sp) sw $a1, 8($sp) bne $a0, $0, elseif # the m == 0 case addiu $v0, $a1, 1 # answer = n + 1 j epilogue elseif: # the m != 0, n == 0 case bne $a1, $0, else addiu $a0, $a0, -1 # arg0 = m-1 li $a1, 1 # arg1 = 1 jal ack # answer = ack(m-1, 1) j epilogue else: # the final case addiu $a1, $a1, -1 # arg1 = n-1. arg0 is already m. jal ack # v0 = ack(m, n-1) addiu $a0, $a0, -1 # arg0 = m-1 move $a1, $v0 # arg1 = ack(m, n-1) jal ack # answer = ack(m-1, v0) epilogue: lw $ra, 0($sp) lw $a0, 4($sp) lw $a1, 8($sp) addiu $sp, $sp, 12 jr $ra

5.QUIZ1 Analysis 1.3 lw $1,0($6) lw $2,0($6) lw $3,0($6) lw $4,0($6) add $5, $0,$0 单纯地减少内存访问指令？ OR 减少内存访问指令后以其他指令代替？ 前一种情况 后一种情况

二 ws1的优先级高于ws2 得分点：使能信号，写入数据选择

2.分支指令具有一个延迟槽，lw指 令无延迟槽，EX级产生分支结果 三 注意：1.具有阻塞和冲刷流水线的能力 2.分支指令具有一个延迟槽，lw指 令无延迟槽，EX级产生分支结果 3.无predict-taken电路逻辑，则转 移机制是predict-untaken 4.题中没有说明寄存器写和读可在 一拍内完成，WB级写回结果后， 需在下一拍的ID中才能使用更新值 I1：OR R5,R1,R2 I2：OR R6,R1,R2 I3：BEQ R6,R5,I7 I4：LW R3,0(R5) I5：OR R7,R5,R6 I7：OR R6,R0,R3 I8：OR R5,R0,R1 I9：OR R11,R9,R9 I10：OR R12,R9,R9 I1 to I3 RAW($5) I2 to I3 RAW($6) I4 to I7 RAW($3) t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11 t12 t13 I1 IF ID EX MEM WB I2 I3 I4 I5 I7 I8 I9 $6 得到分支结果，冲刷掉I5，取指I7 $3

1.I3的ID级需在I2的WB级之后执行 2.I3的EX级后冲刷掉I5的ID级 3.I7的ID级需在I4的WB级之后执行 t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11 t12 t13 I1 IF ID EX MEM WB I2 I3 I4 I5 I7 I8 I9 $6 得到分支结果，冲刷掉I5，取指I7 $3 1.I3的ID级需在I2的WB级之后执行 2.I3的EX级后冲刷掉I5的ID级 3.I7的ID级需在I4的WB级之后执行   t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11 t12 t13 IF ID EX MEM WB I1 I2 I3 I4 I4 I4 I4 I5 I7 I8 I8 I8 I9 I1 I2 I3 I3 I3 I3 I4 N I7 I7 I7 I8 I1 I2 N N N I3 I4 N N N I7 I1 I2 N N N I3 I4 N N N I1 I2 N N N I3 I4 N N