第三次作业 : 第四章前半部习题 4. 考虑下列指令 : 指令 :AND Rd,Rs,Rt 说明 :Reg[Rd] = Reg[Rs] AND Reg[Rt] 4..(5%) 图 4.2 中的控制器为了上述指令所产生的控制讯号其值为何? 4..2(5%) 哪些资源 ( 区块 ) 会为该指令做出有用的功能? 4..3(5%) 哪些资源 ( 区块 ) 会产生并不被该指令用到的输出? 哪些资源 ( 区块 ) 并不会对该指令产生输出?
R-type Instruction Data/Control Flow 4 Add opcode ALUOp Instr[3-26] Control Unit Branch ALUSrc Shift left 2 Add PCSrc MemRead MemtoReg MemWrite PC Instruction Memory Read Address Instr[3-] p.254 ( 页 264) fig. 4.9 and $t, $t2, $t3 RegWrite RegDst Register File Instr[25-2] Read Addr $t2 Read Instr[2-6] Read Addr 2 Data $t3 Instr[ 5-] $t Instr[5-] funct. code Write Addr Write Data Read Data 2 Sign 6 Extend 32 $t3 $t2 Instr[5-] ovf zero ALU ALU control Data Memory Address Read Data Write Data 2
指令 :AND Rd,Rs,Rt 4..(5%) 图 4.2 中的控制器为了上述指令所产生的控制讯号其值为何? 4..2(5%) 哪些资源 ( 区块 ) 会为该指令做出有用的功能? 4..3(5%) 哪些资源 ( 区块 ) 会产生并不被该指令用到的输出? 哪些资源 ( 区块 ) 并不会对该指令产生输出? RegDst MemMux AND AND Rd,Rs,Rt Branch Add, Data memory, Sign extend, Shift left 2 bits Branch Add, Data memory, Sign extend, Shift left 2 bits 5
4.4 本习题的问题假设所需用以制作处理器数据信道的逻辑区块具有以下延迟 : I-Mem Add Mux ALU Regs D-Mem Sign- Shift-Left-2 Extend 2ps 7ps 2ps 9ps 9ps 25ps 5ps ps 4.4.(%) 设若我们在处理器中唯一需要做的事是撷取连续的指令 ( 图 4.6), 则时脉周期时间可以为若干? I-Mem takes longer than the Add unit, so the clock cycle time is equal to the latency of the I-Mem: 2 ps Clock D C 2 ps Q 7 Add 4 Instruction Memory 图 4.6 PC Read Address Instruction 2 6
I-Mem Add Mux ALU Regs D-Mem Sign- Shift-Left-2 Extend 2ps 7ps 2ps 9ps 9ps 25ps 5ps ps 4.4.2(%) 考虑一个类似图 4. 中所示的数据信道, 然其处理器只有一种类型的指令 : 无条件 PC- 相对地址的分支 对于这个数据信道的周期时间为若干? 7
图 4. I-Mem Add Mux ALU Regs D-Mem Sign- Shift-Left-2 Extend 2ps 7ps 2ps 9ps 9ps 25ps 5ps ps 7 7 7 PCSrc 2 the latency 35ps 2 6ps ALUSrc ALU operation MemWrite MemtoReg 2 RegWrite MemRead 5 8
I-Mem Add Mux ALU Regs D-Mem Sign- Shift-Left-2 Extend 2ps 7ps 2ps 9ps 9ps 25ps 5ps ps 4.4.3(%) 当我们仅需支持有条件 PC- 相对地址的分支时, 重复 4.4.2 题 9
图 4. I-Mem Add Mux ALU Regs D-Mem Sign- Shift-Left-2 Extend 2ps 7ps 2ps 9ps 9ps 25ps 5ps ps PCSrc 2 35ps 6ps 7 2 The longest latency: 42ps ALUSrc ALU operation MemWrite MemtoReg 9 2 2 RegWrite 9 2 MemRead 5
I-Mem Add Mux ALU Regs D-Mem Sign- Shift-Left-2 Extend 2ps 7ps 2ps 9ps 9ps 25ps 5ps ps 本习题中剩下的三题与数据信道中的 Shift-left-2 有关 : 4.4.4(5%) 哪些指令需要用到这项资源? 4.4.5(5%) 这项资源对哪些种指令 ( 如果有的话 ) 会位于关键路径上? 4.4.4 PC-relative branches. 4.4.5 None. PC-relative unconditional branch instructions.
I-Mem Add Mux ALU Regs D-Mem Sign- Shift-Left-2 Extend 2ps 7ps 2ps 9ps 9ps 25ps 5ps ps 本习题中剩下的三题与数据信道中的 Shift-left-2 有关 : 4.4.6(5%) 假设我们仅支持 beq 及 add 指令, 讨论这项资源在延迟上的变化会如何影响处理器的周期时间 假设其他资源的延迟不变 BEQ has a longer critical path >= ADD BEQ determines the clock cycle time so the latency of Shift -left -2 must be increased by 5 ps or more for it to affect cloc cycle time. Shift -left -2 >= 5ps D? ps Clock C Q 2
图 4. I-Mem Add Mux ALU Regs D-Mem Sign- Shift-Left-2 Extend 2ps 7ps 2ps 9ps 9ps 25ps 5ps ps PCSrc 35ps 2 The longest latency: BEQ 42ps ALUSrc ALU operation MemWrite ADD 42ps MemtoReg 9 2 RegWrite 9 2 2 MemRead 3
4.7 本习题中我们仔细检视一道指令是如何在单周期的数据信道中执行的 习题中的各问题请参考撷取下列指令字当时的频率周期 : 假设数据存储器中的数据全为 且处理器的缓存器在撷取上述指令的周期开 始时含有下列值 : r r r2 r3 r4 r5 r6 r8 r2 r3-2 -3-4 6 8 2-6 4.7.(%) 符号延伸及跳跃的 左移 2 单元 ( 位于图 4.24 中的上方 ) 对该指令字所产出的输出各为何? Sign-extend Jump s shift-left-2 4
图 4.24 5
4.7 本习题中我们仔细检视一道指令是如何在单周期的数据信道中执行的 习题中的各问题请参考撷取下列指令字当时的频率周期 : 假设数据存储器中的数据全为 且处理器的缓存器在撷取上述指令的周期开始时含有下列值 : r r r2 r3 r4 r5 r6 r8 r2 r3-2 -3-4 6 8 2-6? 4.7.2(5%) 对该指令而言 ALU 控制单元的输入值应为何 ALUOp[-] = 4.7.3(5%) 该指令执行后 PC 的新地址应为何? 标示出决定这个 PC 新位置所需用到的路径 ( 按 : 这里应是指在图 4.24 中标示计算 PC 新位置所需用到的路径 ) a) New PC = PC+4 b) Path: PC to Add (PC+4) to branch Mux to jump Mux to PC 6
MIPS instruction encoding p.4( 页 4)Fig.2.7 28-26 3-29 op (3:26) () () 2() 3() 4() 5() 6() 7() () R-format Bltz/gez jump jump & link branch eq branch ne blez bgtz () add immediate 2() TLB FlPt addiu set less than imm. sltiu andi ori xori load upper imm 3() 4() load byte lh lwl load word lbu lhu lwr 5() store byte sh swl store word 6() lwc lwc swr 7() swc swc 7
ALU Control Must describe hardware to compute 4-bit ALU control input given instruction type = lw, sw ALUOp = = beq, = arithmetic function code for arithmetic 6 function field ALUOp ALU control p.248 ( 页 257) fig. 4.2 2 ALU operation 4 ALU 8
PC to Add (PC+4) to branch Mux to jump Mux to PC 图 4.24 9
4.7 本习题中我们仔细检视一道指令是如何在单周期的数据信道中执行的 习题中的各问题请参考撷取下列指令字当时的频率周期 : 假设数据存储器中的数据全为 且处理器的缓存器在撷取上述指令的周期开 始时含有下列值 : r r r2 r3 r4 r5 r6 r8 r2 r3-2 -3-4 6 8 2-6 4.7.4(5%) 在该指令执行期间以及上述缓存器内容值的情形下, 则每一个 Mux 的输出值各为何? 4.7.5(5%)ALU 及两个加法单元的输入值各为何?? 或 7 2
图 4.24 sw rs rt rd (offset) PC 4 PC+4 PC+4 PC+4 2*4-3 2 或 2? 7? 或 7 X = 2 2
第四次作业 : 第四章后半部习题 4.9 在本习题中, 我们检视数据相依性会如何影响 4.5 节所述的基本 5- 阶管道的执行 习题中的各问题请参考下列指令序 : or $s,$s2,$s3 or $s2,$s,$s4 or $s,$s,$s2 另外, 假设每一种前馈方法的相关周期时间如下 : 无前馈 有充分前馈 仅有 ALU-ALU 前馈 25ps 3ps 29ps 4.9. (%) 指出所有的相依关系以及其类别 Instruction sequence Dependences I: or $s,$s2,$s3 RAW on $s from I to I2 and I3 I2: or $s2,$s,$s4 RAW on $s2 from I2 to I3 I3: or $s,$s,$s2 WAR on $s2 from I to I2 WAR on $s from I2 to I3 WAW on $s from I to I3 RAR on $s2 from I to I3 RAR on $s from I2 to I3 22
4.9 在本习题中, 我们检视数据相依性会如何影响 4.5 节所述的基本 5- 阶管道的执行 习题中的各问题请参考下列指令序 : or $s,$s2,$s3 or $s2,$s,$s4 or $s,$s,$s2 另外, 假设每一种前馈方法的相关周期时间如下 : 无前馈 有充分前馈 仅有 ALU-ALU 前馈 25ps 3ps 29ps 4.9.2 (%) 假设在此管道化的处理器中无前馈能力 指出所有的危障, 并加入 nop 指令以消除之 Instruction sequence or $s,$s2,$s3 nop Delay I2 to avoid RAW hazard on $s from I nop or $s2,$s,$s4 nop Delay I3 to avoid RAW hazard on $s2 from I2 nop or $s,$s,$s2 24
One Way to Fix a Data Hazard I n s t r. add $, nop ALU W IM Reg DM Reg Can fix data hazard by waiting stall but impacts CPI O r d e r nop sub $4,$,$5 and $6,$,$7 ALU IM Reg DM Reg R ALU IM Reg DM Reg R (Bubbles) 25
4.9 在本习题中, 我们检视数据相依性会如何影响 4.5 节所述的基本 5- 阶管道的执行 习题中的各问题请参考下列指令序 : or $s,$s2,$s3 or $s2,$s,$s4 or $s,$s,$s2 另外, 假设每一种前馈方法的相关周期时间如下 : 无前馈 有充分前馈 仅有 ALU-ALU 前馈 25ps 3ps 29ps 4.9.3 (%) 假设有充分的前馈能力 指出所有的危障, 并加入 nop 指令以消除之 Instruction sequence or $s,$s2,$s3 or $s2,$s,$s4 No RAW hazard on $s from I(forwarded) or $s,$s,$s2 No RAW hazard on $s2 from I2(forwarded) 26
Another Way to Fix a Data Hazard I n s t r. O r d e r add $, sub $4,$,$5 and $6,$,$7 or $8,$,$9 ALU IM Reg DM Reg ALU IM Reg DM Reg ALU IM Reg DM Reg ALU Fix data hazards by forwarding (bypassing) results as soon as they are available to where they are needed IM Reg DM Reg xor $4,$,$5 ALU IM Reg DM Reg 27
4.9 在本习题中, 我们检视数据相依性会如何影响 4.5 节所述的基本 5- 阶管道的执行 习题中的各问题请参考下列指令序 : or $s,$s2,$s3 or $s2,$s,$s4 or $s,$s,$s2 另外, 假设每一种前馈方法的相关周期时间如下 : 无前馈 有充分前馈 仅有 ALU-ALU 前馈 25ps 3ps 29ps 4.9.5 (%) 假设仅有 ALU-ALU 的前馈 ( 但是没有自 MEM 至 EX 阶的前馈 ), 在该码中加入 nop 指令以消除危障 Instruction sequence or $s,$s2,$s3 or $s2,$s,$s4 No RAW hazard on $s from I(forwarded) nop nop or $s,$s,$s2 No RAW hazard on $s2 from I2(forwarded) 28
4. 在本习题中, 我们检视资料危障 控制危障, 以及指令集架构 (ISA) 的设计如何能影响管道的执行 习题中的各问题请参考下列的 MIPS 代码段 : sw $s2,2($s6) lw $s2,8($s6) beq $s5,$s4,label add $s5,$s,$s4 slt $s5,$s3,$s4 假设个别的管道阶级中有如下的延迟 : # 假设 $s5!=$s4 IF ID EX MEM WB 2ps 2ps 5ps 9ps ps Cycle time 4.. (%) 在本问题中, 假设所有分支均可被准确预测 ( 因而消除了所有的控制危障 ) 且未使用任何延迟槽 设若我们仅有一个内存 ( 其中存放指令以及资料 ), 则每当我们需要在某一指令存取资料的同一周期中撷取指令时便会引发结构危障 为了确保程序的推进, 该危障必须给予存取资料的指令较高的优先度 在仅有一个内存的五阶管道中, 该指令串的总运行时间为何? 我们已知资料危障可经由在程序中加入 nops 来消除 你可以对结构危障使用相同的方法吗? 为何如此? 29
x 2ps =22ps No! We can not add NOPs to the code to eliminate this hazard NOPs need to be fetched just like any other instructions, so this hazard must be addressed with a hardware hazard detection unit in the processor. 3
4.3 本习题旨在帮助你了解前馈 危障侦测以及 ISA 设计间的关系 习题中的各问题请参考下列指令串, 并假设其执行于五阶的管道式数据信道中 : add $s5,$s2,$s lw $s3,4($s5) lw $s2,($s2) or $s3,$s5,$s3 sw $s3,($s5) 4.3. (%) 若无前馈或是危障侦测, 试插入 nops 以确保正确的执行 add $s5,$s2,$s nop nop lw $s3,4($s5) lw $s2,($s2) nop or $s3,$s5,$s3 nop nop sw $s3,($s5) 3
4.3.2 (%) 重复 4.3., 但是只有在无法改变或重新安排这些指令来避免危障时才使用 nops 你可以假设程序代码中可以使用缓存器 $s7 来存放暂时值 add $s5,$s2,$s nop nop lw $s3,4($s5) lw $s2,($s2) nop or $s3,$s5,$s3 nop nop sw $s3,($s5) add $s5,$s2,$s lw $s2,($s2) nop lw $s3,4($s5) nop nop or $s3,$s5,$s3 nop nop sw $s3,($s5) 32
4.3.3 (%) 若处理器可做前馈但是我们忘记置入危障侦测单元, 则执行该指令串将会有何结果? Code executes correctly! add $s5,$s2,$s lw lw $s3,4($s5) $s2,($s2) or $s3,$s5,$s3 sw $s3,($s5) 33
Another Way to Fix a Data Hazard I n s t r. O r d e r add $, sub $4,$,$5 and $6,$,$7 or $8,$,$9 ALU IM Reg DM Reg ALU IM Reg DM Reg ALU IM Reg DM Reg ALU Fix data hazards by forwarding (bypassing) results as soon as they are available to where they are needed IM Reg DM Reg xor $4,$,$5 ALU IM Reg DM Reg 34
4.3 本习题旨在帮助你了解前馈 危障侦测以及 ISA 设计间的关系 习题中的各问题请参考下列指令串, 并假设其执行于五阶的管道式数据信道中 : add $s5,$s2,$s lw $s3,4($s5) lw $s2,($s2) or $s3,$s5,$s3 sw $s3,($s5) 4.3.4 (%) 若有前馈功能, 则在执行该码的前五个周期中, 指出每一周期中图 4.6( 如次页 ) 所示的危障侦测 (3 条 ) 及前馈单元 (4 条 ) 将会设定的讯号 Note that IF/IDWrite is always equal to PCWrite, and ID/ExZero is always the opposite of PCWrite. 35
With forwarding datapath R5 Instruction Formats: all 32 bits wide OP rs rt rd sa funct OP rs rt immediate p. 297( 页 37) Fig. 4.54 R format I format 36
PC.Write IF/ID.Write Datapath with Hazard Detection p.34( 页 35) Fig. 4.6 Stall by letting an instruction that won t write anything go forward stall rs rt ID/EX.MemRead (load instruction) Insert NOP LOAD continues to next stage ID/EX.RegisterRt 37
4.6 本习题检视不同的分支预测器对以下重复出现的分支结果样式 ( 例如循环分支 ) 可以得到的准确度 : T,NT,T,T,NT (T: Taken, NT: Not Taken) 4.6. (5%) 对于该分支结果样式, 总是会发生 (Taken) 与总是不会发生 (Not taken) 的预测器其准确度各为何? Always Taken Always not-taken 3/5 = 6% 2/5 = 4% 38
4.6 本习题检视不同的分支预测器对以下重复出现的分支结果样式 ( 例如循环分支 ) 可以得到的准确度 : T,NT,T,T,NT 4.6.2 (5%) 对于该样式的前四个分支, 假设 2 位分支预测器的开始状态位于图 4.63 的左下方 ( 即预测不发生 ), 则其准确度为何? Outcomes Correct or Incorrect Accuracy T, NT, T, T I, I, C, C 5% 图 4.63 39
4.6 本习题检视不同的分支预测器对以下重复出现的分支结果样式 ( 例如循环分支 ) 可以得到的准确度 : T,NT,T,T,NT (T: Taken, NT: Not Taken) 4.6.3 (%) 假设该样式不断重复, 则 2 位分支预测器的准确度为何? T, NT, T, T, NT, T, NT, T, T, NT, I/C, I, C,C, I, C, I, C, C, I, C, I, C, C, I Accuracy = 3/5 = 6% 图 4.63 4
Chapter 5 Exercises ( 不用交作业, 纯练习 ) 5.2 快取在提供高效能内存阶层予处理器这方面具有重要性 下列为一序列的 32 位的内存字组存取地址 : 3,8,43,2,9,88,9,4,8,44,86,253 5.2. 对上述的每一次存取, 指出其二进制地址 以及在包含 6 个大小为一个字组的区块直接映对快取中的标签与索引值 并且假设快取原为空的话, 指出每一次存取会是命中或错失 43
Direct Mapped Cache p. 374( 页 388) 范例图 5.9 说明了一个 8 字组大小 采用直接对映的高速缓存如何响应处理器一连串的需求 Tag 2 Index 2 44 4
Index Valid Tag 2 3 4 5 6 7 22Miss p. 389 ( 页 375) Fig. 5.9 26 Miss 26 Hit 6 Miss 22 Hit 45
p. 389( 页 375) Fig. 5.9 6 Hit 3 Miss 8 () Miss 46
5.3 对于使用 32 位地址的直接映对快取, 地址中用存取快取的位如下 : 標籤 索引 位移值 3-9-5 4-5.3. 快取的区块大小 ( 以字组作单位 ) 为若干? 每个区块有 8 个字组 ( ~ )(Bit 4-2) 5.3.2 快取中的区块数为若干? 32 个区块数 ( 看索引位数 Bit 9-5) 3 3... 9... 5 4 3 2 Byte Tag Index Block address offset 48
A Typical Memory Hierarchy By taking advantage of the principle of locality Can present the user with as much memory as is available in the cheapest technology at the speed offered by the fastest technology On-Chip Components Control DRAM Datapath RegFile ITLB DTLB Instr Data Cache Cache Second Level Cache (SRAM) Main Memory (DRAM) Page table Secondary Memory (Disk) Speed (%cycles): ½ s s s s, s Size (bytes): s K s K s M s G s to T s Cost($/bit): highest lowest 5
Making Address Translation Fast A cache for address translations: translation lookaside buffer TLB (TLB) Virtual page number Valid Dirty Ref Valid Dirty Ref Page table Tag Physical page or disk address Physical page address p. 526( 页 444) Fig. 5.29 Physical memory TLB Typical values: 6-52 entries, miss-rate:.% - % miss-penalty: cycles Disk storage 52
A TLB in the Memory Hierarchy CPU VA ¼ t hit PA ¾ t miss TLB Lookup Cache Main Memory miss hit Translation Page table data A TLB miss is it a page fault or merely a TLB miss? If the page is loaded into main memory, then the TLB miss can be handled (in hardware or software) by loading the translation information from the page table into the TLB - Takes s of cycles to find and load the translation info into the TLB If the page is not in main memory, then it s a true page fault - Takes,, s of cycles to service a page fault TLB misses are much more frequent than true page faults 53
感谢同学本学期的辛苦学习与合作, 敬祝大家新年快乐心想事成! 54