动态调度(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.动态调度机制一个简单的静态调度流水线负责取指令并将它发射出去，除非流水线中的指令与取到的指令之间存在数据相关，而且无法通过旁路技术和直接通路技术避免数据相关，如果有无法避免的数据相关，那么检测冒险的硬件将从使用相关结果的指令开始暂停流水线，停止取指令和发射指令的工作，直到相关被清除，而动态调度技术就是通过硬件对指令执行顺序进行重组，在保持数据流和异常行为的同时减少停顿，它可以处理一些在编译阶段无法预见的相关情况，同时它简化了编译器的设计，但是动态调度的这些优势是以硬件复杂度的显著增加为代价的。
- 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” 寄存器文件到原来的状态:
• 控制相关：由条件转移或程序中断引起的相关，也称全局相关。控制相 关对流水线的吞吐率和效率影响相关于数据相关要大得多
• 条件指令在一般程序中所占的比例相当大