计算机系统结构系统结构课程总复习-1229new

1、计算机体系结构计算机体系结构要点复习要点复习Computer Architecture u1960s, (大型机大型机)u1970s, (小型机小型机)u1980s, (桌面计算机桌面计算机)u1990s, Internet and the World Wide Web PDA（个人数字助理）（个人数字助理）(机顶盒机顶盒)u2000s, embedded computers(嵌入式计算机嵌入式计算机)Computer Architecture Desktop Computing(桌面计算机桌面计算机) 最早最大的市场最早最大的市场 性价比突出性价比突出Servers(服务器服务器) 提供更大

2、规模更可靠的文件与计算服务提供更大规模更可靠的文件与计算服务 availability(可用性）可用性） scalability(可扩充性可扩充性) throughput(吞吐量吞吐量)Embedded Computers(嵌入式计算机嵌入式计算机) 在市场中增长最快在市场中增长最快 设计原则：以最低价格满足实际的性能需求设计原则：以最低价格满足实际的性能需求 Real time(soft & hard)(实时性实时性) 最大化存储需求和最小化功耗需求最大化存储需求和最小化功耗需求 处理器核心与处理器核心与ASIC的异构的异构 DSP定量分析 可改进比例：该部件的原执行时间在原系统总执

3、行时间中所占的比例，它总是小于等于.部件加速比：部件改进前后执行时间之比，一般情况下它大于。系统加速比 = =改进前改进后系统性能系统性能改进后改进前总执行时间总执行时间CPU的性能1. 将程序执行的时间进行分解 程序执行的 CPU时间 = 总时钟周期数 / 时钟频率 CPI = 总时钟周期数 / IC CPU时间 = CPI IC / 时钟频率 IC：程序执行过程中所处理的指令数。2. 将总时钟周期数进一步分解 总时钟周期数= CPI IC 对许多CPU来说，不同的指令运行时所用的周期数是不同的，如果计算机系统有 n 种指令，其中 CPIi ： 第 i 种指令所用的时钟周期数； ICi ：在

4、程序运行过程中第 i 种指令被运行的次数；CPU时间 = (CPIi ICi) / 时钟频率CPI = (CPIi ICi) / IC = (CPIi ICi / IC)其中：(ICi / IC) 反映了第 i 种指令在程序中所占的比例。 i=1i=1nnni=1CPU时间时间(CPU执行周期数存储器停顿周期数执行周期数存储器停顿周期数) 时钟周期时间时钟周期时间存储器停顿周期数存储器停顿周期数访存次数访存次数失效率失效率失效开销失效开销于是于是 CPU时间时间ICCPI流水线流水线访存次数访存次数/指令数指令数 失效率失效率失效开销失效开销时钟周期时间时钟周期时间 CPI流水线流水线= CP

5、I理想理想+停顿停顿结构相关结构相关+停顿停顿数据相关数据相关+停顿停顿控制相关控制相关提高指令级并行的最基本方法提高指令级并行的最基本方法: (1) 指令调度指令调度 (2) 循环展开循环展开 一般由编译器来完成一般由编译器来完成。指令调度：指令调度：通过改变指令在程序中的位置，将相关指令通过改变指令在程序中的位置，将相关指令 之间的距离加大到不小于指令执行延迟的时之间的距离加大到不小于指令执行延迟的时 钟数，使相关指令成为实际上的无关指令。钟数，使相关指令成为实际上的无关指令。循环展开：循环展开：通过多次复制循环体通过多次复制循环体(并改变循环结束条件并改变循环结束条件)来减少循环控制对性

6、能的影响来减少循环控制对性能的影响(循环控制指令引起的循环控制指令引起的停顿停顿)。指令级并行指令级并行例：例： for (i=999; i=0; i=i-1) xi = xi + s;考虑对应的考虑对应的 DLX 汇编语言实现汇编语言实现.约定：约定：x0 的内存地址为的内存地址为 8(R2) （为简单起见）（为简单起见） R1的初值为的初值为x999的地址的地址 F2中存放的值为常量中存放的值为常量 s 不考虑分支转移的延迟时间不考虑分支转移的延迟时间LOOP:LD F0, 0(R1)ADDDF4, F0, F2SD F4, 0(R1)DADDUI R1, R1, #-8BNER1, R2

7、,LOOP 指令级并行指令级并行实际运行：实际运行：(1)LOOP:LD F0, 0(R1)(2)(空转空转)(3)ADDDF4, F0, F2(4)(空转空转)(5)(空转空转)(6)SDF4, 0(R1)(7)DADDUI R1, R1, #-8(8) (空转空转) (9)BNER1, R2,LOOP 一共一共 9 个时钟周期，其中有个时钟周期，其中有 4 个空转周期。个空转周期。 指令级并行指令级并行指令调度：指令调度：(1)LOOP:LDF0, 0(R1)(2)(空转空转)(3)ADDDF4, F0, F2(4) (空转空转)(5) DADDUI R1, R1, #-8(6) SDF4

8、, 8(R1)(7) BNER1, R2,LOOP 一共一共 7 个时钟周期，其中有个时钟周期，其中有 2 个空转周期。个空转周期。这种指令调度由编译器完成的，其基本思想是将指令这种指令调度由编译器完成的，其基本思想是将指令序列中的序列中的“无关无关”指令调入空转周期指令调入空转周期。 指令级并行指令级并行循环展开循环展开4次，每次迭代分配不同的寄存器：次，每次迭代分配不同的寄存器：(1)LOOP:LDF0, 0(R1)(2)(空转空转)(3)ADDD F4, F0, F2(4)(空转空转)(5)(空转空转)(6)SDF4, 0(R1)(7)LDF6, -8(R1)(8)(空转空转)(9)AD

9、DD F8, F6, F2(10)(空转空转)(11)(空转空转)(12)SDF8, -8(R1)指令级并行指令级并行(13)LDF10, -16(R1)(14)(空转空转)(15)ADDD F12, F10, F2(16)(空转空转)(17)(空转空转)(18)SDF12, -16(R1)(19)LDF14, -24(R1)(20)(空转空转)(21)ADDD F16, F14, F2(22)(空转空转)(23)(空转空转)(24)SDF16, -24(R1)(25)DADDUI R1, R1, #-32(26)(空转空转) (27)BNE R1, R2,LOOP 一共一共 27 个时钟周期

10、，平均每次循环使用个时钟周期，平均每次循环使用27 / 4 6.7个周期。个周期。 循环展开循环展开+指令调度指令调度(循环展开调度循环展开调度)：(1)LOOP:LDF0,0(R1)(2)LDF6,-8(R1)(3)LDF10,-16(R1)(4)LDF14,-24(R1)(5)ADDD F4,F0,F2(6)ADDD F8,F6,F2(7)ADDD F12,F10,F2(8)ADDD F16,F14,F2 指令级并行指令级并行(9)SDF4, 0(R1)(10)SDF8, -8(R1)(11)SDF12, -16(R1)(12)DADDUI R1, R1, #-32(13)SDF16, 8

11、(R1)(14)BNER1, R2,LOOP 一共一共 14 个时钟周期，平均每次循环使用个时钟周期，平均每次循环使用14 / 4 3.5个周期。所有个周期。所有“空转空转”消失，即数据相关被消除，消失，即数据相关被消除，达到完全指令级并行。达到完全指令级并行。 结论：结论：由编译器所完成的循环展开和指令调度由编译器所完成的循环展开和指令调度(静态静态调度调度)，能有效提高指令级并行。，能有效提高指令级并行。指令级并行指令级并行InstructionInstructionLatency producing result using result in cyclesFP ALU opAnothe

12、r FP ALU op 3FP ALU opStore double2Load double FP ALU op1Load double Store double0指令级并行指令级并行指令运行过程指令运行过程 (1)指令流出指令流出(发射发射)(IS)：如果指令如果指令所需的功能部件所需的功能部件空闲空闲，并且其他正在运行的指令与它，并且其他正在运行的指令与它不发生目的不发生目的寄存器冲突寄存器冲突，则记分牌将向该功能部件流出指令，则记分牌将向该功能部件流出指令，功能部件被置成准备运行该指令状态功能部件被置成准备运行该指令状态(记录于记分记录于记分牌牌)解决了解决了结构相关结构相关和和写后写相

13、关写后写相关。动态算法之一：记分牌动态算法之一：记分牌 (2)读操作数读操作数(RO)：如果前面已流出的正在运行的如果前面已流出的正在运行的指令指令不对本指令的源操作数寄存器进行写操作不对本指令的源操作数寄存器进行写操作，或者一个正在工作的功能部件或者一个正在工作的功能部件已完成对该寄存器已完成对该寄存器的写操作的写操作，则进行读操作数，并完成该步骤，则进行读操作数，并完成该步骤(离开离开挂起状态挂起状态)。 有可能有多个功能部件挂起在这一步。有可能有多个功能部件挂起在这一步。 解决解决写后读相关写后读相关。动态算法之一：记分牌动态算法之一：记分牌 (3)执行执行(EX)：对浮点运算来讲，这一

14、步可能要花多对浮点运算来讲，这一步可能要花多个时钟周期，由于功能部件独立，不会发生冲突。个时钟周期，由于功能部件独立，不会发生冲突。 (4)写结果写结果(WR)：记分牌知道功能部件执行完成后，记分牌知道功能部件执行完成后，检查目标寄存器，如果前面检查目标寄存器，如果前面没有指令读该寄存器没有指令读该寄存器或或已完成对该寄存器的读操作已完成对该寄存器的读操作，则完成这一步骤，则完成这一步骤，否则将该功能部件挂起在这一步。否则将该功能部件挂起在这一步。 有可能有多个功能部件挂起在这一步。有可能有多个功能部件挂起在这一步。 解决解决读后写相关读后写相关。动态算法之一：记分牌动态算法之一：记分牌MIP

15、S计分板的数据结构计分板的数据结构(1) 指令状态表：指令状态表：表示正在执行的各指令处于四步中的表示正在执行的各指令处于四步中的 哪一步。哪一步。动态算法之一：记分牌动态算法之一：记分牌(2)功能状态表：功能状态表：表示各功能部件的状态，每个功能部表示各功能部件的状态，每个功能部 件一共有九个域：件一共有九个域：Busy: 该功能部件是否在工作该功能部件是否在工作(被分配被分配)Op: 该功能部件当前操作该功能部件当前操作Fi: 目的寄存器编号目的寄存器编号Fj, Fk: 源寄存器编号源寄存器编号Qj, Qk: 向源寄存器写结果的功能部件向源寄存器写结果的功能部件 Rj, Rk:源寄存器是否

16、源寄存器是否就绪并且还未被使用就绪并且还未被使用 Yes: 就绪并且还没有被使用过就绪并且还没有被使用过 (后面指令不可改写它后面指令不可改写它) No: (1) 未就绪未就绪 (前面指令可改写它前面指令可改写它) (2)已被使用过已被使用过 (后面指令可改写它后面指令可改写它) (3)结果寄存器状态表：结果寄存器状态表：表示每个寄存器是当前哪一表示每个寄存器是当前哪一 个功能部件的目的寄存器个功能部件的目的寄存器 (不是则为空不是则为空)。动态算法之一：记分牌动态算法之一：记分牌指令运行过程指令运行过程 (1)指令流出（发射指令流出（发射/指派）指派）(IS)： 取一条浮点指令，如果有相应的

17、空闲保留站，并取一条浮点指令，如果有相应的空闲保留站，并且操作数就绪且操作数就绪(在寄存器中在寄存器中)，就将指令和操作数一，就将指令和操作数一起发射到保留站；如果没有空闲的保留站，则发生起发射到保留站；如果没有空闲的保留站，则发生结构相关，停顿指令；如果操作数不在寄存器中，结构相关，停顿指令；如果操作数不在寄存器中，则需要跟踪将要产生该操作数的功能单元，寄存器则需要跟踪将要产生该操作数的功能单元，寄存器重命名在此步进行，以消除读后写和写后写相关。重命名在此步进行，以消除读后写和写后写相关。 如果是访存指令，有空的缓冲则流出。否则等待。如果是访存指令，有空的缓冲则流出。否则等待。解决了结构相关

18、、读后写、写后写。解决了结构相关、读后写、写后写。 动态算法之二：动态算法之二：Tomasulo算法算法(2)执行执行(EX)： 如果操作数未就绪，监视公共数据总线等待如果操作数未就绪，监视公共数据总线等待结果结果(某个操作完成后会以广播方式通知所某个操作完成后会以广播方式通知所有等待该结果的保留站有等待该结果的保留站)，当两个操作数都，当两个操作数都就绪则开始运行。如果对某个功能单元而言，就绪则开始运行。如果对某个功能单元而言，有多条指令在同一个时钟周期内就绪，保留有多条指令在同一个时钟周期内就绪，保留站可以任意选择。站可以任意选择。 如果是访存指令，首先当基址寄存器可用时如果是访存指令，首

19、先当基址寄存器可用时计算有效地址，之后地址被置于访存缓存中；计算有效地址，之后地址被置于访存缓存中；其次当存储单元可用时，其次当存储单元可用时，load立即执行，而立即执行，而store则要等待被保存的值。则要等待被保存的值。解决了写后读相关。解决了写后读相关。动态算法之二：动态算法之二：Tomasulo算法算法(3)写结果写结果(WB)：结果计算完，写入公共数据总线，广播至所有等结果计算完，写入公共数据总线，广播至所有等待该结果的保留站和目的寄存器待该结果的保留站和目的寄存器(如果存在如果存在)。Store指令被缓存在指令被缓存在store缓存中，直到将要保存的缓存中，直到将要保存的值和保存

20、地址都可用时为止，当存储单元可用时，值和保存地址都可用时为止，当存储单元可用时， store立即执行。立即执行。动态算法之二：动态算法之二：Tomasulo算法算法数据结构数据结构(1)指令状态表：指令状态表： 表示正在执行的各指令处于三步表示正在执行的各指令处于三步 中的哪一步。中的哪一步。(2)寄存器状态表：寄存器状态表：表示各寄存器分别是哪一个保表示各寄存器分别是哪一个保 留站的目的寄存器。留站的目的寄存器。(3)保留站：保留站：一共有六个域一共有六个域Busy: 该保留站是否空闲该保留站是否空闲Op: 对操作数对操作数S1、S2的操作的操作Vj,Vk: 操作数值操作数值Qj,Qk: 将

21、产生操作数值的保留站号，为空表将产生操作数值的保留站号，为空表 示操作数值已在示操作数值已在Vj、Vk中或不需要。中或不需要。注：对每个操作数而言，注：对每个操作数而言，V或或Q字段只有一个有效字段只有一个有效动态算法之二：动态算法之二：Tomasulo算法算法(4)取缓冲：取缓冲：一共有两个域一共有两个域Busy: 该保留站是否空闲该保留站是否空闲Address: 存储器地址值存储器地址值(5)存缓冲：存缓冲：一共有四个域一共有四个域Busy: 该保留站是否空闲该保留站是否空闲Address: 存储器地址值存储器地址值Vj: 操作数值操作数值Qj: 将产生操作数值的保留站号，将产生操作数值的

22、保留站号，为空表示操作数值已在为空表示操作数值已在Vj中中。动态算法之二：动态算法之二：Tomasulo算法算法基本思想：基本思想：基于该分支指令的历史记录基于该分支指令的历史记录-根据该分支根据该分支指令在最近一次或几次的运行情况指令在最近一次或几次的运行情况(分支成功或失败分支成功或失败)，来预测该分支指令的本次运行情况来预测该分支指令的本次运行情况(分支成功或失败分支成功或失败)。实现方法：实现方法：建立一片缓冲区，记录各运行过的分支指建立一片缓冲区，记录各运行过的分支指令的运行情况令的运行情况(分支成功或失败分支成功或失败)。缓冲区如何寻址缓冲区如何寻址-根据分支指令根据分支指令地址的

23、低位地址的低位，究竟，究竟 多少位取决于缓冲区大小。多少位取决于缓冲区大小。缓冲区的内容缓冲区的内容 -预测位，其长度预测位，其长度(多少位多少位)决定能决定能 记录该指令前多少次运行情况。记录该指令前多少次运行情况。进一步减少分支延迟：分支预测缓冲进一步减少分支延迟：分支预测缓冲分支指令的执行过程：分支指令的执行过程：(1) 现场保留。现场保留。(2) 按预测方向取后继指令。按预测方向取后继指令。(3) 得到分支结果后得到分支结果后如果预测成功，继续运行；如果预测成功，继续运行；如果预测失败，恢复保留的现场，从分支处重新如果预测失败，恢复保留的现场，从分支处重新执行；执行；(4) 修改预测位。修改预测位。进一步减少分支延迟：分支预测缓冲进一步减少分支延迟：分支预测缓冲分支指令无延迟的前提：分支指令无延迟的前提：(1) 分支预测成功分支预测成功(2) 分支预测和目标地址计算都在分支预测和目标地址计算都在 IF 阶段就能完成。阶段就能完成。基本思想：基本思想：设立一个缓冲区设立一个缓冲区(称为分支目标缓冲区，称为分支目标缓冲区，或或BTB )，其中存放最近一次运行时分支成功的分支，其中存放最近一次运