动态调度(Cont),推断执行和ILP
- 格式：ppt
- 大小：1.06 MB
- 文档页数：62
下载文档原格式
合集下载
cpu的ipc机制
CPU的IPC机制什么是IPCIPC（Inter-Process Communication）即进程间通信，是指不同进程之间进行数据交换和共享的机制。
在计算机系统中，多个进程可能需要相互协作完成任务，而IPC机制提供了一种有效的方式来实现进程间的通信。
CPU的IPC在计算机体系结构中，指令级并行（Instruction-Level Parallelism，简称ILP）是指在一个程序中的不同指令之间存在的并行性。
而CPU的IPC（Instructions Per Cycle）机制就是一种用于提高指令级并行性的技术。
IPC是衡量CPU性能的一个重要指标，它表示在一个时钟周期内可以执行的指令数量。
IPC的值越高，表示CPU在同一时间周期内可以执行更多的指令，从而提高了CPU的效率。
提高IPC的技术1. 流水线流水线是一种将指令执行过程划分为多个阶段的技术。
在流水线中，每个阶段都可以同时处理不同的指令，从而实现指令级并行。
流水线可以将指令的执行时间缩短，提高CPU的吞吐量。
流水线的基本原理是将指令的执行过程划分为取指、译码、执行、访存和写回等多个阶段，并将这些阶段连接起来，使得每个阶段都可以同时处理不同的指令。
通过这种方式，CPU可以在同一时钟周期内同时执行多条指令，提高IPC的值。
2. 超标量超标量是指在一个时钟周期内可以同时发射多条指令的技术。
传统的CPU一次只能发射一条指令，而超标量技术可以同时发射多条指令到不同的执行单元，从而提高了IPC的值。
超标量技术需要具备多个执行单元和指令调度器。
指令调度器负责将多条指令按照其依赖关系进行调度，并将其发送到不同的执行单元执行。
通过这种方式，CPU可以在同一时钟周期内同时执行多条指令，提高了CPU的效率。
3. 动态调度动态调度是指在运行时根据指令的依赖关系动态地调度指令的执行顺序。
传统的静态调度是在编译时根据指令的依赖关系确定指令的执行顺序，而动态调度可以在运行时根据实际情况进行调度。
系统结构名词解释（3）
系统结构名词解释（3）系统结构名词解释结构冲突：因硬件资源满足不了指令重叠执行的要求而发生的冲突。
数据冲突：当指令在流水线中重叠执行时，因需要用到前面指令的执行结果而发生的冲突。
控制冲突：流水线遇到分支指令或其它会改变PC值的指令所引起的冲突。
定向：用来解决写后读冲突的。
在发生写后读相关的情况下，在计算结果尚未出来之前，后面等待使用该结果的指令并不见得是马上就要用该结果。
如果能够将该计算结果从其产生的地方直接送到其它指令需要它的地方，那么就可以避免停顿。
写后读冲突：考虑两条指令i和j，且i在j之前进入流水线，指令j用到指令i的计算结果，而且在i将结果写入寄存器之前就去读该寄存器，因而得到的是旧值。
读后写冲突：考虑两条指令i和j，且i在j之前进入流水线，指令j的目的寄存器和指令i的源操作数寄存器相同，而且j在i读取该寄存器之前就先对它进行了写操作，导致i读到的值是错误的。
写后写冲突：考虑两条指令i和j，且i在j之前进入流水线，，指令j和指令i的结果单元（寄存器或存储器单元）相同，而且j在i写入之前就先对该单元进行了写入操作，从而导致写入顺序错误。
这时在结果单元中留下的是i写入的值，而不是j写入的。
链接技术：具有先写后读相关的两条指令，在不出现功能部件冲突和Vi冲突的情况下，可以把功能部件链接起来进行流水处理，以达到加快执行的目的。
分段开采：当向量的长度大于向量寄存器的长度时，必须把长向量分成长度固定的段，然后循环分段处理，每一次循环只处理一个向量段。
半性能向量长度：向量处理机的性能为其最大性能的一半时所需的向量长度。
向量长度临界值：向量流水方式的处理速度优于标量串行方式的处理速度时所需的向量长度的最小值。
4.1解释下列术语指令级并行：简称ILP。
是指指令之间存在的一种并行性，利用它，计算机可以并行执行两条或两条以上的指令。
指令调度：通过在编译时让编译器重新组织指令顺序或通过硬件在执行时调整指令顺序来消除冲突。
实时系统中的实时任务调度与实时资源管理技术评估研究(一)
实时系统中的实时任务调度与实时资源管理技术评估研究概要本文将重点探讨实时系统中的实时任务调度与实时资源管理技术，并对各种技术进行评估研究。
实时系统是指对任务响应时间要求非常高的系统，能够在预定时间内完成任务。
实时任务调度与实时资源管理是实时系统中的关键问题，对于实现系统的高效运行具有重要意义。
一、实时任务调度技术1.静态调度算法静态调度算法适用于任务响应时间要求严格且不会发生变化的实时系统。
常用的静态调度算法有最早截止时间优先（EDF）调度算法和最小松弛度（LLF）调度算法。
EDF调度算法根据任务的截止时间来调度任务，保证截止时间最早的任务最先执行；LLF调度算法根据任务的松弛度来调度任务，保证松弛度最小的任务最先执行。
2.动态调度算法动态调度算法适用于任务的响应时间要求会动态变化的实时系统。
常用的动态调度算法有最早截止时间优先（EDF）调度算法、最小松弛度（LLF）调度算法和最小松弛度交换（LAX）调度算法。
这些算法根据任务的特性和运行时的变化来动态地调整任务的调度顺序，以满足实时系统的需求。
二、实时资源管理技术1.固定优先级分配（Fixed-priority assignment）固定优先级分配是一种常用的资源管理技术，根据任务的优先级来分配资源。
任务的优先级一旦确定，就不会随着运行时的变化而改变。
这种技术简单有效，但可能面临资源饥饿的问题。
2.基于服务器的资源管理技术（Server-based resource management）基于服务器的资源管理技术将系统中的资源划分为若干个服务器，任务通过请求服务器来获取资源。
这种技术可以根据任务的需求动态地分配资源，并保证任务的响应时间。
但是，服务器的数量和位置的选择会影响系统的性能。
三、实时任务调度与实时资源管理技术评估1.性能评估指标性能评估指标是评估实时任务调度与实时资源管理技术是否符合系统需求的重要标准。
常用的性能评估指标包括任务响应时间、任务延迟、资源利用率等。
全局指令调度名词解释系统结构
全局指令调度名词解释系统结构第一章名称解析：程序的局部性原理：程序执行时所访问的存储器地址不是随机分布的，而是相对地簇聚。
包括时间局部性和空间局部性。
软件兼容：一个软件可以不经修改或者只需少量修改就可以由一台计算机移植到另一台计算机上运行。
差别只是执行时间的不同。
时间重叠：在并行性概念中引入时间因素，让多个处理过程在时间上相互错开，轮流重叠地使用同一套硬件设备的各个部分，以加快硬件周转而赢得速度。
资源重复：在并行性概念中引入空间因素，以数量取胜。
通过重复设置硬件资源，大幅度地提高计算机系统的性能。
实现软件可移植的方法：采用系列机方法，只能在具有相同系统结构的各种机器之间实现软件移植，般是一个厂家生产的机器。
采用模拟与仿真的方法，可在不同系统结构的机器之间相互移植软件，对于使用频率较高的指令，尽可能用仿真方法以提高运算速度，而对于使用频率低且难于用仿真实现的指令则用模拟方法来实现。
采用统一的高级语言方法，可以解决结构相同或完全不同的各种机器上的软件移植，但是，要统一高级语言，语言的标准化很重要，但难以在短期内解决。
第二章2.1解释下列术语堆栈型机器：CPU中存储操作数的单元是堆栈的机器。
累加器型机器：CPU中存储操作数的单元是累加器的机器通用寄存器型机器：CPU中存储操作数的单元是通用寄存器的机器。
CISC：复杂指令集计算机RISC：精简指令集计算机寻址方式：指令系统中如何形成所要访问的数据的地址。
一般来说，寻址方式可以指明指令中的操作数是一个常数丶一个寄存器操作数或者是一个存储器操作数数据表示：硬件结构能够识别、指令系统可以直接调用的那些数据结构。
2.2区别不同指令集结构的主要因素是什么？根据这个主要因素可将指令集结构分为哪3类？答：区别不同指令集结构的主要因素是CPU中用来存储操作数的存储单元。
据此可将指令系统结构分为堆栈结构、累加器结构和通用寄存器结构。
2.3指令集结构设计所涉及的内容有哪些？指令集功能设计：主要有RISC和CISC两种技术发展方向；寻址方式的设计：设置寻址方式可以通过对基准程序进行测试统计，察看各种寻址方式的使用频率，根据适用频率设置必要的寻址方式。
7.ILP-动态调度(2)
反相关：后面指令要写的操作数是前面指令要读的操作数 所造成流水线停顿称为WAR冒险(Write After Read)， 传统顺序流水线不存在该问题 其根源在于对十分有限的寄存器资源的重复使用
− 所有在中断产生指令之前的指令都执行完毕 − 所有中断指令之后的指令都停止，且不能修改处理器状态 − 保存中断产生指令的PC，然后跳转到处理中断的例程入口指令处 − 当中断处理结束后，通过保存的PC返回到中断处恢复正常执行
而对于乱序执行处理器来说，即便是在发生中断时，“及 时”暂停流水线，也不能保证精确中断
WB WB
理想化加速比（speed-up）
− pipe_stages * issue_width (e.g. 5 * 2 = 10x)
（发射宽度）
但若干因素使得很难达到这种理想的加速比
− 程序因素：各种相关和冒险的存在，限制了理论可并发执行度 − 硬件因素：发掘并发指令的能力受限于硬件复杂度和时钟周期
−理想化CPI: 流水线实现方式所能达到的最高性能 −结构冒险: 由于硬件资源冲突而导致的两条指令组合的 执行限制 −数据冒险: 一条指令的源数据与流水线中某一条较早指 令的结果相关 −控制冒险: 由于分支跳转指令关于控制流改变的决策要 晚于后续指令的取指时间，影响后续取指及执行
15
相关的分类
（Data dependence）
IF ID IF EX MEM WB ID EX MEM WB IF ID EX MEM WB IF ID EX MEM WB
for (i = N; i >= 0; i--) sum += a[i--]; loop： ld r2, 10(r1) add r3, r3, r2 sub r1, r1, 1 bne r1, r0
llvm 指令调度算法
5.资源约束调度（Resource-Constrained Scheduling）：
-考虑目标体系结构的硬件资源限制，以确保生成的代码能够在实际硬件上运行而不引起资源竞争。
总体而言，LLVM的指令调度算法是一个复杂的系统，涉及到对程序依赖关系的建模、硬件资ห้องสมุดไป่ตู้的考虑以及对目标体系结构的了解。这些算法的目标是生成高效且充分利用硬件资源的机器代码。
1.超标量调度器（Out-of-Order Scheduler）：
- LLVM的超标量调度器负责在超标量或超流水线体系结构上调度指令。
-它会考虑指令之间的依赖关系，并将能够并行执行的指令安排在适当的位置。
2.限制宽度调度（Limited Width Scheduling）：
-在某些情况下，硬件可能有限制，不能同时调度太多指令。因此，LLVM的调度器会考虑目标硬件的特性，以确保生成的代码在实际执行时能够充分利用硬件资源。
3.动态调度（Dynamic Scheduling）：
- LLVM采用动态调度的方式，以充分利用运行时的信息，例如指令的实际执行时间和硬件状态。
-动态调度允许在程序运行时对指令进行重新排序，以最大程度地减小执行时间。
4.贪心调度（Greedy Scheduling）：
- LLVM的调度器通常采用贪心策略，优先选择能够立即执行的指令，以最大程度地提高并行度。
llvm
LLVM（Low Level Virtual Machine）是一个开源的编译器基础设施项目，提供了一套通用的、模块化的编译器和工具链。在LLVM中，指令调度是指优化编译生成的汇编代码的过程，以改进程序在目标体系结构上的执行性能。
LLVM使用了基于依赖关系的调度算法，以最大程度地提高指令的并行度和减小指令的等待时间。下面是LLVM中一些常见的指令调度算法：
-考虑目标体系结构的硬件资源限制，以确保生成的代码能够在实际硬件上运行而不引起资源竞争。
总体而言，LLVM的指令调度算法是一个复杂的系统，涉及到对程序依赖关系的建模、硬件资ห้องสมุดไป่ตู้的考虑以及对目标体系结构的了解。这些算法的目标是生成高效且充分利用硬件资源的机器代码。
1.超标量调度器（Out-of-Order Scheduler）：
- LLVM的超标量调度器负责在超标量或超流水线体系结构上调度指令。
-它会考虑指令之间的依赖关系，并将能够并行执行的指令安排在适当的位置。
2.限制宽度调度（Limited Width Scheduling）：
-在某些情况下，硬件可能有限制，不能同时调度太多指令。因此，LLVM的调度器会考虑目标硬件的特性，以确保生成的代码在实际执行时能够充分利用硬件资源。
3.动态调度（Dynamic Scheduling）：
- LLVM采用动态调度的方式，以充分利用运行时的信息，例如指令的实际执行时间和硬件状态。
-动态调度允许在程序运行时对指令进行重新排序，以最大程度地减小执行时间。
4.贪心调度（Greedy Scheduling）：
- LLVM的调度器通常采用贪心策略，优先选择能够立即执行的指令，以最大程度地提高并行度。
llvm
LLVM（Low Level Virtual Machine）是一个开源的编译器基础设施项目，提供了一套通用的、模块化的编译器和工具链。在LLVM中，指令调度是指优化编译生成的汇编代码的过程，以改进程序在目标体系结构上的执行性能。
LLVM使用了基于依赖关系的调度算法，以最大程度地提高指令的并行度和减小指令的等待时间。下面是LLVM中一些常见的指令调度算法：
流水线原理——ILP
– 编译器，指令调度。乱序执行，动态调度
llxx@ 18
直到C6，数据才可用
指令调度
• 指令调度，是RISC微处理器编译技术之一。 • 指令调度是解决数据相关的最经济的方法，它可以解决RAW、WAR 和WAW数据相关。 • 假设有这样一个指令序列： I0: R1+R2R3 I1: R3+R4R5 I2: R7 OR R8R9 • 假定我们按下列方法重新安排指令次序： R1+R2 R3 R7 OR R8 R9 R3+R4 R5
从此开始，每个 周期流出一条指 令，IPC≈1
Execute Store res.
pipelined instruction execution
Time
llxx@
9
流水线分类
• 单功能流水线：只能完成一种功能的流水线，如浮点加法 流水线。 • 多功能流水线：流水线的各段可以进行不同的连接，从而 使流水线在不同的时间完成不同的功能。 • 静态流水线：在某一时间段内，流水线的各段只能按同一 种功能的连接方式工作，即只有当输入是一串相同性质的 操作时其性能才能得到发挥。 • 动态流水线：在某一段时间内，某些段正在实现某类操作 （定点乘），其他段却在实现另一类操作（浮点加）。 • 线性流水线：流水线的各段串行连接，没有反馈回路。 • 非线性流水线：流水线中除了串行的通路，还有反馈回来。 • 顺序流水线：流水线的流出顺序与其流入顺序相同。 • 乱序流水线：流水线的流出顺序与其流入顺序不同。
Pipelined
non-pipelined dish cleaning
Time
pipelined dish cleaning
Time
• 流水过程由多个相互联系的子过程组成，每个子过程称为 流水线的“级”或“段”。
llxx@ 18
直到C6，数据才可用
指令调度
• 指令调度，是RISC微处理器编译技术之一。 • 指令调度是解决数据相关的最经济的方法，它可以解决RAW、WAR 和WAW数据相关。 • 假设有这样一个指令序列： I0: R1+R2R3 I1: R3+R4R5 I2: R7 OR R8R9 • 假定我们按下列方法重新安排指令次序： R1+R2 R3 R7 OR R8 R9 R3+R4 R5
从此开始，每个 周期流出一条指 令，IPC≈1
Execute Store res.
pipelined instruction execution
Time
llxx@
9
流水线分类
• 单功能流水线：只能完成一种功能的流水线，如浮点加法 流水线。 • 多功能流水线：流水线的各段可以进行不同的连接，从而 使流水线在不同的时间完成不同的功能。 • 静态流水线：在某一时间段内，流水线的各段只能按同一 种功能的连接方式工作，即只有当输入是一串相同性质的 操作时其性能才能得到发挥。 • 动态流水线：在某一段时间内，某些段正在实现某类操作 （定点乘），其他段却在实现另一类操作（浮点加）。 • 线性流水线：流水线的各段串行连接，没有反馈回路。 • 非线性流水线：流水线中除了串行的通路，还有反馈回来。 • 顺序流水线：流水线的流出顺序与其流入顺序相同。 • 乱序流水线：流水线的流出顺序与其流入顺序不同。
Pipelined
non-pipelined dish cleaning
Time
pipelined dish cleaning
Time
• 流水过程由多个相互联系的子过程组成，每个子过程称为 流水线的“级”或“段”。
精简指令集计算(RISC)实战演练试卷
精简指令集计算（RISC）实战演练试卷（答案见尾页）一、选择题1. RISC架构的主要特点是什么？A. 指令长度固定且种类繁多B. 指令长度不固定且种类较少C. 指令长度固定且种类较少D. 指令长度不固定且种类繁多2. 在RISC处理器中，哪种类型的指令通常用于执行复杂的控制流操作？A. 短指令B. 长指令C. 控制指令D. 数据处理指令3. RISC处理器相比传统CISC处理器的优势是什么？A. 更高的指令执行速度B. 更高的内存访问效率C. 更高的功耗D. 更高的成本4. 下列哪个选项不是RISC处理器的典型应用场景？A. 移动设备B. 服务器C. 超级计算机D. 微型计算机5. 在RISC设计中，为了提高指令流水线的效率，通常会采用哪种技术？A. 指令乱序执行B. 指令并行执行C. 指令分支预测D. 指令静态调度6. RISC处理器中的寄存器数量通常与下列哪项因素相关？A. 处理器时钟频率B. 指令集大小C. 内存访问速度D. 哈佛结构7. 在RISC架构中，为了减少访问内存的次数，通常会使用哪种数据存储方式？A. 短期存储B. 长期存储C. 闪存D. 硬盘8. RISC处理器中的指令通常具有以下哪种特性？A. 长指令字（VLIW）B. 短指令字（SISD）C. 单指令单数据（SISD）D. 单指令多数据（SIMD）9. 下列哪种优化技术不是RISC处理器中常用的以提高性能的手段？A. 指令重排B. 循环展开C. 动态调度D. 指令合并10. 在设计RISC处理器时，为了提高指令的吞吐量，通常会考虑哪种硬件设计特征？A. 多核处理器B. 高速缓存一致性C. 并行处理单元D. 中断控制器11. 在RISC架构中，通常采用哪种方式组织指令？A. 短指令集（VLIW）B. 长指令字（VLIW）C. 指令流水线D. 指令乱序执行12. RISC处理器的典型应用场景是哪种？A. 大型科学计算B. 互联网服务C. 工业自动化控制D. 数字信号处理13. 在RISC设计中，为了提高指令流水线的效率，通常会采用哪项技术？A. 指令预取B. 动态调度C. 指令重排D. 增加寄存器数量14. RISC架构与传统架构相比，最显著的优点是什么？A. 更高的指令执行速度B. 更高的内存访问速度C. 更高的处理器频率D. 更强的并行处理能力15. 在RISC设计中，如何降低指令的执行时间？A. 增加指令流水线的级数B. 减少指令的复杂性C. 提高指令的并行度D. 增加指令的缓存容量16. 下列哪种方法不是RISC处理器设计中的优化策略？A. 指令压缩B. 单周期指令C. 指令乱序执行D. 多指令发出17. RISC处理器通常需要哪种类型的存储器来存储代码和数据？A. 高速缓存存储器（如SRAM）B. 动态随机存取存储器（DRAM）C. 只读存储器（ROM）D. 闪存18. 在RISC系统中，为了提高指令吞吐量，通常会采用哪种技术？A. 指令预取B. 动态调度C. 指令乱序执行D. 增加处理器核心数量19. RISC架构的设计原则之一是“简单至上”，这意味着在设计过程中应遵循哪些原则？A. 指令集简化和统一B. 指令级并行（ILP）最大化C. 处理器频率提升D. 内存访问速度优化20. 在RISC架构中，哪种类型的指令通常被设计为访问内存中的特定地址？A. 数据操作指令B. 算术逻辑指令C. 控制指令D. 内存访问指令21. RISC处理器通常采用哪种内存访问模式？A. 顺序访问B. 分支预测C. 哈希访问D. 乱序访问22. 在RISC设计中，为了提高指令执行效率，通常会采取哪些措施？A. 复杂化指令集B. 减少指令数量C. 增加指令流水线D. 使用分支预测器23. RISC处理器与传统CISC处理器的最大区别是什么？A. 指令执行速度B. 指令集大小C. 处理器功耗D. 编程复杂性24. 在RISC架构中，编译器需要如何优化代码以适应不同的处理器实现？A. 生成大量不同的汇编代码B. 生成大量相似的汇编代码C. 生成少量不同的汇编代码D. 生成少量相似的汇编代码25. RISC处理器通常具有较高的每条指令执行速度，这是由于其采用了哪种设计策略？A. 简化指令集B. 增加指令数量C. 强化控制单元D. 扩大寄存器文件26. 在RISC系统中，为了提高指令吞吐量，处理器通常会采用哪种技术？A. 多线程技术B. 流水线技术C. 异步处理技术D. 超线程技术27. RISC处理器的设计原则之一是尽量减少指令的执行时间，这主要是通过什么来实现？A. 采用更多的寄存器B. 优化指令流水线C. 增加指令预取机制D. 改进数据总线带宽28. RISC处理器通常比CISC处理器的哪个方面表现得更好？A. 代码执行速度B. 存储器访问速度C. 并行处理能力D. 调试和调试的难易程度29. 在RISC设计中，为什么通常选择较少的寄存器数量？A. 提高指令集的复杂性B. 减少内存访问开销C. 增加指令的灵活性D. 降低硬件成本30. 下列哪个不是RISC处理器的典型应用场景？A. 移动设备B. 服务器端C. 消费电子产品D. 工业控制系统31. RISC编译器的主要目标是什么？A. 最大化程序的运行速度B. 最小化程序的体积C. 实现高级语言的直接翻译D. 生成尽可能多的汇编代码32. 在RISC架构中，哪种类型的指令通常用于实现数据传输？A. 控制指令B. 数据传输指令C. 逻辑运算指令D. 状态寄存器操作指令33. RISC处理器中的流水线技术是如何提高处理器性能的？A. 通过增加处理器的数量B. 通过同时执行多个指令C. 通过减少指令的执行时间D. 通过优化指令的依赖关系34. 在RISC系统中，为了提高指令的并行度，通常会采用哪种结构？A. 管道结构B. 流水线结构C. 计数器结构D. 循环结构35. RISC处理器中的缓存机制主要用于解决什么问题？A. 提高数据传输速度B. 减少内存访问延迟C. 增加处理器的功率消耗D. 减少指令的位数36. 在设计RISC处理器时，为什么需要考虑指令的功耗？A. 功耗是影响处理器性能的唯一因素B. 功耗与处理器的性能和稳定性密切相关C. 功耗不会影响处理器的功能D. 功耗总是导致处理器的性能下降37. 在RISC系统中，为了减少访问内存的次数，通常会使用哪种数据存储类型？A. 硬件缓存B. 寄存器C. 内存D. 以上都不是38. RISC处理器的指令集设计原则是什么？A. 指令越多越好B. 指令越少越好C. 指令大小不固定D. 指令执行时间不一致39. 下列哪个选项是RISC处理器相比CISC处理器的一个优势？A. 更高的指令执行速度B. 更高的程序可读性C. 更高的功耗D. 更多的寄存器40. 在RISC处理器的设计中，为了提高指令集的兼容性，通常会采用哪种技术？A. 指令集扩展B. 指令集压缩C. 指令集仿真D. 指令集重排41. RISC处理器的优点包括哪些？A. 更高的性能B. 更低的功耗C. 更简单的编程模型D. 更容易的设计二、问答题1. 什么是RISC？请简要介绍其特点。
并行算法的设计与分析(19)
任务调度的概念
并行计算中任务调度的模型 目标机器（Target Machine）假定有m个处理器组成，该m个处理器 可以是同构的，也可以是异构的，它们通过任意的互连网络进行连 接。每个处理器某一时刻只能处理一个任务，每个任务可在任何一 个处理器上运行。 可用六元组TM=（P, [Pij], [Si], [Ii], [Bi], [Rij]）来刻画目标机器的 特性： ① P=｛P1,P2,…,Pm｝为构成并行分布系统的一组处理器； ② [Pij]为m×m的互连网络拓扑矩阵； ③ Si(1≤i≤m)为处理器Pi的执行速度；
静态任务调度的最优算法
在忽略通信延迟的情况下，对任务图再加以一些限制 条件可以得到最优调度算法。 限制一：任务图是树结构。代表算法：T.C.Hu线性的 最优调度算法、M.Kaufman最优调度算法。
限制二：区间有序条件。代表算法：C.Papadimitriou算 法。 限制三：对目标机器加以限制 。代表算法： E.G.Coffman调度算法，时间复杂度为O(n2)。
任务调度的概念
并行计算中任务调度的分类 抢占式调度和非抢占式调度 抢占式调度：动态地将优先权更高的任务调度分配给处理器。 自适应调度和非自适应调度 自适应调度（Adaptive Scheduling）：根据调度程序在 以前一段时间内的执行效果，以及当前系统状态信息（系统 资源和任务负载情况）自动修正调度程序的执行机制，它们 通过收集当前系统状态信息来动态修正调度策略。 非自适应调度（Non-adaptive Scheduling）：一旦确定 任务调度算法的调度策略，那么在并行程序执行过程中就固 定地按照这些调度策略来进行任务调度，即使某些不确定因 素（如动态产生的任务）使得调度效率比较低，那么也必须 等到非执行状态时，再修正调度策略。
ILP开发的技术
综述：ILP开发的技术前言：自1985年以来，所有的处理器都采用流水线方式使指令的执行可以重叠进行以提高性能。
由于可以将指令间的关系看做是并行的，因此将指令间的这种潜在重叠称为指令级并行。
于是可以提高对并行的开发能力的相关技术越来越受到人们的关注。
开发指令级并行的方法大致可以分为两类，一种方法是依赖硬件，动态地发现和开发指令级并行；另一种方法是依赖与软件技术，在编译阶段静态地发现。
本文中将着重讨论一系列技术，这些技术都是用来提高指令序列的并行度和扩展流水线的。
1.静态编译技术基本流水线调度：要保持一条流水线不停顿，就要去发现可以流水重叠的不想关的指令序列，并加以充分利用，为避免流水线的停顿，就要事先找出指令代码中的相关指令并将它们分离，使其相隔的时钟周期能正好等于原来指令在流水执行时的时延，编译器进行这类调度的能力既依赖与程序的指令级并行度，也依赖与流水线中功能单元的时延循环展开：为了增加有效操作对转移和开销指令的比重，循环展开可以通过多次复制循环体和调整循环中止码来实现。
循环展开因为它可以消除转移，所以它也可以用来改进调度。
并且循环展开这种转换方法对于各种处理器，从简单流水线到超标量多发射结构等等都适用。
但是这种转换也确实增加了现代编译器的复杂度。
预测技术：由于需要通过转移冒险和停顿来保持控制相关，因此转移会降低流水线的性能，上文提到的循环展开是减小转移冒险的方法之一，另外还可以通过转移预测技术来减小转移引起的性能损耗。
而且想要开发指令级并行，转移预测的准确率是个关键问题。
可以通过缓存的容量，增加每次预测所使用的预测方案的准确率。
2.动态调度机制一个简单的静态调度流水线负责取指令并将它发射出去，除非流水线中的指令与取到的指令之间存在数据相关，而且无法通过旁路技术和直接通路技术避免数据相关，如果有无法避免的数据相关，那么检测冒险的硬件将从使用相关结果的指令开始暂停流水线，停止取指令和发射指令的工作，直到相关被清除，而动态调度技术就是通过硬件对指令执行顺序进行重组，在保持数据流和异常行为的同时减少停顿，它可以处理一些在编译阶段无法预见的相关情况，同时它简化了编译器的设计，但是动态调度的这些优势是以硬件复杂度的显著增加为代价的。
体系结构试题及答案
一．名词解释2:1Cache经验规则：大小为N的直接印象Cache的失效率约等于大小为N/2的两路组相联Cache的失效率。
通道处理机：通道的专用处理机，来专门负责整个计算机体系的输入/输出工作。
通道处理机只能执行有限的一组输入/输出指令。
透明性：在计算机技术中，把这种本来存在的事物或属性，但从某种角度看又好像不存在的概念称为透明性。
向量处理机：设置了向量数据表示和相应的向量指令的流水线处理机称为向量处理机。
虚拟Cache：直接用虚拟地址进行访问的Cache计算机系统结构：传统机器程序员所看到的计算机属性，即概念性结构与功能特性。
系列机：由同一厂家生产的具有相同系统结构、但具有不同组成和实现的一系列不同型号的计算机。
同构型多处理机系统：由多个同类型或至少担负同等功能的处理机组成，它们同时处理同一作业中能并行执行的多个任务。
堆栈型机器：CPU 中存储操作数的单元是堆栈的机器。
累加器型机器：CPU 中存储操作数的单元是累加器的机器。
通用寄存器型机器：CPU 中存储操作数的单元是通用寄存器的机器。
数据相关：考虑两条指令i和j，i在j的前面，如果下述条件之一成立，则称指令j与指令i数据相关：（1）指令j使用指令i产生的结果；（2）指令j与指令k数据相关，而指令k又与指令i数据相关。
定向：用来解决写后读冲突的。
在发生写后读相关的情况下，在计算结果尚未出来之前，后面等待使用该结果的指令并不见得是马上就要用该结果。
如果能够将该计算结果从其产生的地方直接送到其它指令需要它的地方，那么就可以避免停顿。
指令级并行：简称ILP。
是指指令之间存在的一种并行性，利用它，计算机可以并行执行两条或两条以上的指令。
指令的动态调度：是指在保持数据流和异常行为的情况下，通过硬件对指令执行顺序进行重新安排，以提高流水线的利用率且减少停顿现象。
是由硬件在程序实际运行时实施的。
指令的静态调度：是指依靠编译器对代码进行静态调度，以减少相关和冲突。
系统结构 名词解释
系统结构の名词解释第一章1.虚拟机：由软件实现的机器。
虚拟机中有些操作可以由硬件或固件实现。
（固件：具有软件功能的硬件。
）2.计算机系统结构：计算机系统的软、硬件的界面，即机器语言程序员所看到的传统机器级所具有的属性。
3.Amdahl定律：加快某部件执行速度所能获得的系统性能加速比，受限于该部件的执行时间占系统中总执行时间的百分比。
4.CISC：复杂指令集计算机。
RISC：精减指令集计算机。
第二章5.数据表示：计算机硬件能够直接识别、指令系统可以直接调用的数据类型。
第三章6.流水线需要有通过时间和排空时间。
通过时间：第一个任务从进入流水线到流出结果所需的时间。
排空时间：最后一个任务从进入流水线到流出结果所需的时间。
7.系统级流水线（宏流水线）：把多台处理机串行连接起来，对同一数据流进行处理，每个处理机完成整个任务中的一部分。
8.静态流水线：在同一时间内，多功能流水线中的各段只能按同一种功能的连接方式工作。
对于静态流水线来说，只有当输入的是一串相同的运算任务时，流水的效率才能得到充分的发挥。
9.动态流水线：在同一时间内，多功能流水线中的各段可以按照不同的方式连接，同时执行多种功能。
优点是灵活，能够提高流水线各段的使用率，从而提高处理速度。
缺点是控制复杂。
10.线性流水线：流水线的各段串行连接，没有反馈回路。
数据通过流水线中的各段时，每一个段最多只流过一次。
11.非线性流水线：流水线中除了有串行的连接外，还有反馈回路。
第四章12.横向(水平)处理方式：向量计算是按行的方式从左到右横向地进行。
纵向处理方式：向量计算是按列的方式从上到下纵向地进行。
纵横处理方式：又称为分组处理方式。
把向量分成若干组，组内按纵向方式处理，依次处理各组。
第五章13.指令并行级：指指令之间存在的一种并行性，利用它，计算机可以并行执行两条或两条以上的指令。
（ILP：Instruction-Level Parallelism）14.IPC：（Instructions Per Cycle）每个时钟周期完成的指令条数。
《指令动态调度》课件
IA-64架构的指令动态调度实现
1 IA-64架构
2 指令动态调度
由In te l和HP合作开发的处理器架构，广泛 应用于服务器和高性能计算领域。
IA-64架构提供了丰富的指令集和硬件支持， 实现了高效的指令动态调度。
根据指令之间的相关性和依 赖关系，灵活地调整指令的 执行顺序。
超标量执行
同时执行多条指令，充分利 用处理器的多个功能单元。
指令调度的优化技术
1 重排指令
通过调整指令的执行顺序，减少数据相关性和控制相关性，提高指令级并行度。
2 动态调度
根据当前的系统状态和资源利用情况，动态地调整指令的执行顺序，提高程序执行效率。
优点
简单、可控、资源消耗较少，适用于大部分处理器和指令集架构。
缺点
对分支指令和数据相关性处理不够灵活，可能会导致性能下降。
VLIW处理器的介绍
1 概念
Very Lo ng Instructio n W o rd （超长指 令字）处理器，一条指令包含多个操作 。
2 特点
通过静态调度和指令级并行，同时执行多 条操作，提高处理器性能。
Tomasulo算法的介绍
原理
通过将指令的执行和操作数的准备解耦，实现指令级并行执行。
优点
有效利用处理器资源，提高并行度和程序执行效率。
缺点
实现复杂，对硬件要求较高，需要较多的硬件资源。
Scoreboarding算法的介绍
原理
通过建立和管理保留站，并进行指令发射、执行和完成的控制，实现动态调度和执行。
动态调度和静态调度的区别
1 动态调度
实时地对指令进行调度和重排序，根据当前的系统状态进行优化，灵活适应不同的程序 和环境。
多核处理器体系结构设计考试
多核处理器体系结构设计考试（答案见尾页）一、选择题1. 多核处理器的基本工作原理是什么？A. 它们通过将多个CPU核心集成到一个芯片上来实现高性能计算。
B. 它们通过将多个任务分配给不同的核心来提高系统响应速度。
C. 它们通过增加缓存容量来提高数据处理速度。
D. 它们通过使用专用硬件来加速特定类型的计算任务。
2. 在多核处理器中，核间通信的主要方式有哪些？A. 管道通信B. 共享内存通信C. 消息传递通信D. 事件驱动通信3. 多核处理器的性能主要受哪些因素影响？A. 核心数量B. 链路带宽C. 缓存大小D. 电源管理效率4. 在多核处理器的设计中，如何平衡性能和功耗？A. 通过降低每个核心的功耗来实现节能。
B. 通过优化任务调度来减少空闲核心的功耗。
C. 通过增加核心数量来提高并行处理能力。
D. 通过使用更先进的制程技术来减小芯片面积和功耗。
5. 多核处理器中的任务分配通常是如何进行的？A. 由操作系统根据系统负载动态分配。
B. 由用户直接指定每个任务在哪个核心上运行。
C. 由编译器在编译时预先分配。
D. 由硬件自动分配，无需人工干预。
6. 在多核处理器的调试过程中，常用的工具和技术有哪些？A. 性能分析工具B. 调试器C. 监控工具D. 仿真器7. 多核处理器在哪些应用场景下表现最为出色？A. 计算密集型任务B. 内存密集型任务C. 多媒体处理D. 网络安全8. 在多核处理器的设计中，如何防止一个核过载而影响系统性能？A. 使用负载均衡技术B. 对于关键任务进行优先级调度C. 增加更多的核心数量D. 使用专用硬件加速器9. 多核处理器的发展趋势是什么？A. 更高的核数B. 更低的功耗C. 更强的并行处理能力D. 更高的单核性能10. 在多核处理器的应用中，如何确保数据的一致性和线程安全？A. 使用锁机制B. 使用原子操作C. 使用无锁数据结构D. 使用操作系统提供的同步原语11. 在多核处理器体系结构设计中，哪种类型的缓存通常被用来提高数据访问速度？A. 一级缓存（L1）B. 二级缓存（L2）C. 三级缓存（L3）D. 四级缓存（L4）12. 在多核处理器的设计中，为了实现高效的并行处理，以下哪个因素不是关键考虑点？A. 指令级并行（ILP）B. 核心间通信带宽C. 能耗D. 缓存一致性协议13. 在多核处理器的性能优化中，哪种技术通常用于减少缓存未命中率？A. 预取算法B. 乱序执行C. 动态调度D. 多线程技术14. 在多核处理器的资源管理中，哪种机制用于确保每个核都能公平地访问其分配的资源？A. 资源预留B. 资源分配算法C. 负载均衡D. 优先级调度15. 在多核处理器的设计中，为了提高能源效率，哪种技术被广泛采用？A. 超线程技术（Hyper-Threading）B. 硬件加速C. 微架构优化D. 低功耗工艺16. 在多核处理器的体系结构中，哪种类型的指令集被设计来支持复杂的数据处理任务？A. 简单指令集计算（SISD）B. 复杂指令集计算（CISC）C. 精简指令集计算（RISC）D. 并行指令集计算（IPC）17. 在多核处理器的设计中，为了提高系统的可靠性和稳定性，通常会采用哪种技术？A. 冗余设计B. 故障检测与纠正（FEC）C. 电源管理D. 热插拔技术18. 在多核处理器的性能测试中，哪种基准测试最能反映处理器在真实世界应用中的表现？A. 基准测试软件（如SPEC）B. 游戏测试C. 3D渲染测试D. 网络传输测试19. 在多核处理器的调试过程中，哪种工具用于监控和分析处理器在运行时的行为？A. 性能分析器（Profiler）B. 调试器（Debugger）C. 仿真器（Emulator）D. 逻辑分析仪（Logic Analyzer）20. 在多核处理器的安全设计中，哪种加密技术用于保护多核处理器免受侧信道攻击？A. 对称密钥加密B. 非对称密钥加密C. 密码分组链接（GCM）D. 访问控制列表（ACL）21. 在多核处理器中，以下哪个不是常见的核间通信方式？A. 管道通信B. 共享内存通信C. 消息队列通信D. 电路交换通信22. 在多核处理器的设计中，为了平衡负载和提高性能，通常会采取哪种策略？A. 随机分配任务B. 根据核心性能分配任务C. 固定分配任务D. 动态任务调度23. 多核处理器中的缓存一致性协议主要用于解决什么问题？A. 提高缓存的访问速度B. 防止数据竞争和一致性问题C. 增加处理器的计算能力D. 降低功耗24. 在多核处理器的设计中，为了提高系统的可扩展性，通常会选择哪种类型的核间通信机制？A. 管道通信B. 共享内存通信C. 消息队列通信D. 无锁机制25. 多核处理器在面对单核处理器无法处理的复杂任务时，表现如何？A. 性能显著提升B. 性能下降C. 性能无变化D. 可能会降低性能26. 在多核处理器的设计中，为了避免某个核心过载而其他核心闲置，通常会采用哪种技术？A. 负载均衡B. 缓存一致性C. 任务调度D. 中断处理27. 在多核处理器的应用场景中，以下哪个不是其主要的应用领域？A. 高性能计算B. 数据库处理C. 智能手机D. 家庭自动化28. 在多核处理器的设计中，为了提高处理器的能效比，通常会考虑哪些因素？A. 核心数量B. 缓存大小C. 电源管理D. 以上都是29. 在多核处理器的设计中，为了实现更高的吞吐量，通常会采用哪种优化技术？A. 多线程技术B. 数据压缩技术C. 并行计算技术D. 以上都是30. 在多核处理器中，核间通信通常使用什么方式？A. 系统总线B. 内存总线C. 专用指令集D. 中断驱动31. 多核处理器的性能主要取决于哪些因素？A. CPU核心数量B. 缓存大小C. 主频D. 内存容量32. 在多核处理器的设计中，如何平衡各个核的性能和功耗？A. 通过调整CPU频率B. 通过增加缓存容量C. 通过引入任务调度算法D. 通过优化内存访问策略33. 下列哪种多核处理器的架构不是对称多核架构？A. 超线程技术（Hyper-Threading）B. 图形多处理器（GPGPU）C. 对称多核处理器（SMP）D. 异构多核处理器（HMP）34. 在多核处理器的性能测试中，常用的基准测试程序包括哪些？A. LINPACKB. Prime95C. FIOD. DBench35. 在多核处理器的安全设计中，常见的安全漏洞有哪些？A. 数据竞争（Data Race）B. 死锁（Deadlock）C. 缓冲区溢出（Buffer Overflow）D. 侧信道攻击（Side-Channel Attack）36. 在多核处理器的编程模型中，有哪些常用的编程范式？A. 异步编程B. 并发编程C. 多线程编程D. 事件驱动编程37. 在未来多核处理器的发展趋势中，可能会出现哪些新技术？A. 多核与GPU的融合B. 量子计算与多核处理器的结合C. 机器学习加速与多核处理器的集成D. 基于光子的多核处理器38. 在多核处理器体系中，什么是Cache？A. 一种快速存储器，用于存储CPU频繁访问的数据和指令。
动态调度(Cont),推断执行和ILP
Predictor B
Tournament Predictor in Alpha 21264
Selector：4K 2-bit 计数器用来选择全局预测器依然局部预测器
Global predictor： 使用4K项，依照最近的12个分支的执行情况来 索引，每项为标准的2-bit预测器
• 12-bit pattern: ith bit 0 => ith prior branch not taken; ith bit 1 => ith prior branch taken;
Correlating 预测器的预测和执行情况， 显然只有在第一次d=2时，预测错误，其他都预测正确 记为（1，1）预测器，即依照最近一次分支的行为来选择一对1-bit预测器中的一个。
更一般的表示为（m, n)，即根据最近的m个分支，从2m个分支预测器中选择预测器，每个预测器的位 数为n
实现精确中断的技术：顺序完成（或提交） • 即提交指令完成的顺序必须与指令发射的顺序相同
进行循环重叠执行需要尽快解决分支问题!
在循环展开的例子中，我们假设整数部件能够快速解决分支问题，以便进行循环重叠执行!
Loop: LD
F0
0
R1
MULTD
F4
F0
F2
SD
F4
0
R1
SUBI
R1
R1
#8
BNEZ
Total size: 4K*2 + 4K*2 + 1K*10 + 1K*3 = 29K bits! (~180,000 transistors)
% of predictions from local predictor in Tournament Scheme
数字系统的优化方案
数字系统的优化方案1. 引言在现代科技发展日新月异的时代，数字系统已经成为我们生活中不可或缺的一部分。
数字系统涵盖了从计算机到智能手机，从电子商务到物联网的各个领域。
为了满足不断增长的需求和提高性能，数字系统的优化变得尤为重要。
本文将介绍数字系统的优化方案，包括硬件和软件两方面。
首先，我们将讨论硬件优化，包括处理器架构、存储器层次结构和并行计算。
然后，我们将转向软件优化，涵盖编译器优化、算法优化和并发编程。
最后，我们将总结数字系统优化的未来发展方向。
2. 硬件优化2.1 处理器架构优化处理器架构优化是提高数字系统性能的核心。
现代处理器采用了多核心和超线程等技术来增加并行性。
为了充分利用处理器的并行性，我们需要进行线程调度、指令级并行和数据级并行的优化。
•线程调度：合理的线程调度可以最大程度地利用处理器核心，避免资源竞争和负载不均衡。
优化方法包括静态调度和动态调度等。
•指令级并行：通过提高指令级并行度（ILP），可以并行执行多条指令。
优化方法包括超标量、超长指令字和乱序执行等。
•数据级并行：通过利用SIMD（单指令多数据）和向量化指令等技术，可以实现数据级并行。
优化方法包括数据对齐、循环展开和软件预取等。
2.2 存储器层次结构优化存储器层次结构是数字系统中存储数据的关键组成部分。
优化存储器层次结构可以减少访问延迟和提高带宽，从而提高系统性能。
•缓存优化：通过合理地利用缓存层次结构，可以减少内存访问的延迟。
优化方法包括局部性原理、空间局部性和时间局部性等。
•存储器对齐：将数据对齐到存储器的边界可以提高数据访问的效率。
•数据压缩：采用数据压缩算法可以降低存储器带宽需求，提高存储器效率。
2.3 并行计算优化并行计算是数字系统中提高性能的重要手段。
通过将计算任务划分为多个并行的子任务，可以充分利用多核处理器的并行能力。
•并行算法设计：设计合适的并行算法可以实现任务的高效并行计算。
常用的并行算法包括分治法、并行排序和图算法等。
嵌入式系统设计中的CISC与RISC选择题
嵌入式系统设计中的CISC与RISC选择题（答案见尾页）一、选择题1. 嵌入式系统设计中，CISC和RISC的主要区别是什么？A. 执行速度B. 指令集大小C. 系统复杂性D. 可维护性2. 在CISC架构中，以下哪个不是常见的指令集类型？A. 流水线指令B. 循环指令C. 专用指令D. 内存访问指令3. RISC架构中，通常哪个不是其优势的特点？A. 高性能B. 低功耗C. 较少的指令集D. 较高的开发成本4. 在RISC架构中，为了提高指令执行效率，通常会采用哪种技术？A. 指令流水线B. 动态调度C. 指令乱序执行D. 哈希表加速5. CISC和RISC在设计嵌入式系统时各有优势，以下哪个是CISC在嵌入式系统中更常遇到的问题？A. 内存访问速度慢B. 指令集庞大C. 处理器负担重D. 代码体积大6. RISC架构的一个显著特点是其指令集的简洁性，这有助于：A. 提高处理器速度B. 减少内存访问时间C. 降低开发难度D. 增加代码体积7. 在嵌入式系统设计中，如果选择了RISC处理器，以下哪个不是其主要优势？A. 高性能B. 低功耗C. 易于编程D. 需要更多的内存8. CISC架构的处理器通常具有较宽的指令流水线，这意味着：A. 处理器可以在单个时钟周期内执行多个指令B. 处理器需要更多的内存带宽C. 编译器需要生成更多的代码D. 系统的功耗较高9. 在RISC架构中，为了减少指令执行时间，通常会采用哪种技术？A. 动态调度B. 指令乱序执行C. 分支预测D. 哈希表加速10. CISC和RISC在设计嵌入式系统时各有优劣，选择CISC架构在嵌入式系统设计中可能导致的缺点是：A. 代码体积过大B. 性能不足C. 开发成本高D. 调试困难11. 在CISC架构中，以下哪个不是常见的指令类型？A. 数据传输指令B. 算术逻辑指令C. 控制指令D. 内存访问指令12. RISC架构中，通常哪种类型的指令会被优化以减少延迟？A. 逻辑运算指令B. 算术运算指令C. 控制指令D. 内存访问指令13. CISC处理器通常需要多少个时钟周期来完成一条指令？A. 1B. 2C. 3D. 414. 在RISC处理器中，如何实现流水线技术来提高吞吐量？A. 通过增加指令流水线的数量B. 通过减少指令流水线的数量C. 通过增加指令的复杂性D. 通过减少指令的复杂性15. CISC和RISC处理器在内存访问方面的主要区别是什么？A. CISC处理器通常有更多的寄存器，因此可以更高效地访问内存。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
Correlating Branch Predicator
例如：
if (aa==2) aa=0;
if (bb==2) bb=0;
if (aa!=bb) {
翻译为DLX
SUBI R3,R1,#2
BNEZ R3,L1
; branch b1 (aa!=2)
ADDI R1,R0,R0
;aa=0
L1: SUBI R3,R2,#2
Loop:
LD MULTD SD SUBI BNEZ
F0 0 R1 F4 F0 F2
F4 0 R1 R1 R1 #8 R1 Loop
• 假如分支依赖于multd,如何办?? • 需要能预测分支方向
假如分支成功，我们就能够重叠执行循环
关于superscalar机器这一问题更加突出
控制相关的动态解决技术
• 分支预测错误的缘故: • 预测错误 • 由于使用PC的低位查找BHT表，可能得到错误的分支历史记录
BHT表的大小问题
• 4096 项的表分支预测错误的比例为1% (nasa7, tomcatv) to 18% (eqntott), spice at 9% and gcc at 12%
• 再增加项数，对提高预测准确率几乎没有效果 (in Alpha 21164)
Use the predictor that tends to guess correctly
addr history
Predictor A
Predictor B
Tournament Predictor in Alpha 21264
Selector：4K 2-bit 计数器用来选择全局预测器依然局部预测器
WAR相关
• Load/store disambiguation • 算法的要紧缺陷 • 复杂 • 要求高速CDB • 性能受限于Common Data Bus
动态硬件方案能够用硬 件进行循环展开
如何处理分支? 我们能够用硬件做循环
展开必须能够解决分支 指令问题
如何处理精确中断?
• Out-of-order execution out-of-order completion!
动态分支预测：预测分支的方向在程序运行时刻动态确定 需解决的关键问题是：
• 如何记录转移历史信息
如何依照所记录的转移历史信息，预测转移的方向
• 要紧方法 • 基于BPB(Branch Prediction Buffer)或BHT(Branch History Table)的方法
- 1-bit BHT和2-bit BHT - Correlating Branch Predictors - Tournament Predictors: Adaptively Combining Local and Global Predictors • High Performance Instruction Delivery - BTB - Integrated Instruction Fetch Units - Return Address Predictors
• 精确中断的含义是其返回地址为： - 该地址之前的所有指令都已完成 - 其后的指令还都没有完成
实现精确中断的技术：顺序完成（或提交） • 即提交指令完成的顺序必须与指令发射的顺序相同
进行循环重叠执行需要尽快解决分支问题!
在循环展开的例子中，我们假设整数部件能够快速解决分 支问题，以便进行循环重叠执行!
Total size: 4K*2 + 4K*2 + 1K*10 + 1K*3 = 29K bits!
(~180,000 transistors)
% of predictions from local predictor in Tournament Scheme
0%
na s a7 m atrix30 0
最近一次执行的分支通常与要预测的分支不是同一条指令
记为 （1，1）前一位表示最近一次分支失败时的预测位， 后一位表示最近一次分支成功时的预测位
Correlating 预测器的预测和执行情况，
显然只有在第一次d=2时，预测错误，其他都预测正确
记为（1，1）预测器，即依照最近一次分支的行为来选择 一对1-bit预测器中的一个。
Local predictor ：两级预测器
• Top level ：1024个10-bit 项构成，每个10-bit项对应最近10次分支的 转移方向
• Next level ：由Top level所选项中的10-bit索引找到1K 项中的对应项 ，每项由3-bit saturating counter 作为局部预测器
更一般的表示为（m, n)，即依照最近的m个分支，从2m个分支预测器中选择预测器，每 个预测器的位数为n
Correlating Branches
Branch address (4 bits)
2-bits per branch local predictors
Prediction
2-bit recent global branch history
结论：条件转移指令对流水线的影响很大，必须采取相关 措施来减少这种影响。
• 预测能够是静态预测“Static” (at compile time) 或动态预测 “Dynamic” (at runtime)
• 动态分支预测 vs. 静态分支预测，哪个好？
Dynamic Branch Prediction
假设d的初始值在2和0之间切换。
用1-bit预测器，初始设置为预测失败，T表示预测成功， NT表示预测失败。
结论：如此的序列每次预测都错，预测错误率100％
Correlating Branches
差不多思想：用1位作为correlation位。即每个分支都有两 个相互独立的预测位：一个预测位假设最近一次执行的分 支失败时的预测位，另一个预测位是假设最近一次执行的 分支成功时的预测位。
;d==0, so d=1
L1: ADDI R3,R1,#-1
BNEZ R3,L2
;branch b2(d!=1)
...
L2:
两级预测器差不多工作原理
假设d的初始值序列为0，1，2 b1 假如分支失败，b2一定也分支失败。 前面的两位标准的预测方案就没法利用这一点，而两级预
测方案就能够。
(01 = not taken then taken)
(2,2) predictor: 2-bit global, 2-bit local
Tournament Predictors
Tournament predictors:
• 使用两个预测器 • 一个基于全局信息 • 一个基于局部信息 • 再加一个选择器
例题：一个循环供循环10次，它将分支成功9次，1次不成 功，假设此分支的预测位始终在缓冲区中，那么分支预测 的准确性是多少？
• 静态预测 vs. 动态预测
问题: 在一个循环中, 1-bit BHT 将导致2次分支预测错误(avg is 9 iteratios before exit):
• 最后一次循环, 前面基本上预测成功，而这次需要退出循环 • 第一次循环，由于前面预测为失败，而这次实际上为成功
tom catv do duc s p ice fpppp gcc
es presso eq nto tt li
20% 40% 60% 80% 100%
98% 100% 94% 90% 55% 76% 72% 63% 37% 69%
Accuracy of Branch Prediction
tomcatv doduc fpppp li
什么原因顺序发射?
• 顺序发射使我们能够进行程序的数据流分析 • 我们能够明白某条指令的结果会流向哪些指令
假如我们乱序发射，可能会混淆RAW和WAR相关
• 每一周期发射多条指令也使用该原那么将会正确地工作: • 需要多端口的 “rename table” ,以便同时对一组指令所用的
寄存器重命名 • 需要在单周期内发射到多个RS中. • 寄存器文件需要有2x 个读端口和x个写端口.
Correlating predictors 或 两级预测器：分支预测器依照其他 分支的行为来进行预测。
工作原理：依照一个简单的例子我们来看其差不多原理
if (d==0)d=1;
if (d==1) d=0; 翻译为DLX
BNEZ R1,L1
;branch b1(d!=0)
ADDI R1,R0,#1
• Global predictor： 使用4K项，依照最近的12个分支的执行情况来索引，每项 为标准的2-bit预测器
• 12-bit pattern: ith bit 0 => ith prior branch not taken; ith bit 1 => ith prior branch taken;
espresso gcc
99% 99% 100%
95% 84%
97%
86% 82%
98% 88% 77%
98%
关于异常处理???
乱序完成加大了实现精确中断的难度
• 在前面指令还没有完成时，寄存器文件中可能会有后面指令的 运行结果.
• 假如这些前面的指令执行时有中断产生，如何办？ • 例如：
DIVD F10, F0, F2
SUBD F4, F6, F8
ADDD F12, F14, F16 需要“rollback” 寄存器文件到原来的状态:
• 控制相关：由条件转移或程序中断引起的相关，也称全局相关。控制相 关对流水线的吞吐率和效率影响相关于数据相关要大得多
• 条件指令在一般程序中所占的比例相当大