第5章指令级并行 指令集并行的基本概念及挑战 软件方法挖掘指令集并行 基本块内的指令集并行 硬件方法挖掘指令集并行 Scoreboard Tomasulo 跨越基本块的指令集并行 ·基于硬件的推测执行 ·以多发射和静态调度来挖掘指令集并行 以动态调度、多发射和推测执行来挖掘指令集 并行
2021/2/7 第5章 指令级并行 • 指令集并行的基本概念及挑战 • 软件方法挖掘指令集并行 – 基本块内的指令集并行 • 硬件方法挖掘指令集并行 – Scoreboard – Tomasulo • 跨越基本块的指令集并行 • 基于硬件的推测执行 • 以多发射和静态调度来挖掘指令集并行 • 以动态调度、多发射和推测执行来挖掘指令集 并行
◎系统结构的Fymn类(96 SISD: Single instruction stream, single data stream 单处理器模式 SIMD: Single instruction stream, multiple data streams 相同的指令作用在不同的数据 可用来挖掘数据级并行( Data level parallelism) A: Vector processors, SIMD instructions, and Graphics processing units MISD: Multiple instruction streams, single data stream No commercial implementation MIMD: Multiple instruction streams, multiple data streams 亚性款的三种结构可用米续摆子款数据级并行
系统结构的Flynn分类 (1966) • SISD: Single instruction stream, single data stream – 单处理器模式 • SIMD: Single instruction stream, multiple data streams – 相同的指令作用在不同的数据 – 可用来挖掘数据级并行(Data Level Parallelism) – 如：Vector processors, SIMD instructions, and Graphics processing units • MISD: Multiple instruction streams, single data stream – No commercial implementation • MIMD: Multiple instruction streams, multiple data streams – 通用性最强的一种结构，可用来挖掘线程级并行、数据级并行….. – 组织方式可以是松耦合方式也可以是紧耦合方式
Levels of parallelism 请求级并行 多个任务可被分配到多个计算机上并行执行 进程级并行 进程可被调度到不同的处理器上并行执行 线程级并行 任务被组织成多个线程,多个线程共享一个进程的地址空间 每个线程有自己独立的程序计数器和寄存器文件 数据级并行 单线程(逻辑上)中并行处理多个数据( SIMD/Vector execution) 个程序计数器,多个执行部件 指令级并行 针对单一指令流,多个执行部件并行执行不同的指令
Levels of Parallelism • 请求级并行 – 多个任务可被分配到多个计算机上并行执行 • 进程级并行 – 进程可被调度到不同的处理器上并行执行 • 线程级并行 – 任务被组织成多个线程，多个线程共享一个进程的地址空间 – 每个线程有自己独立的程序计数器和寄存器文件 • 数据级并行 – 单线程（逻辑上）中并行处理多个数据 (SIMD/Vector execution) – 一个程序计数器, 多个执行部件 • 指令级并行 – 针对单一指令流，多个执行部件并行执行不同的指令
Review:基本流水线 癒水线提喜的是指令带宽(吞吐率),而不是单条 相关限制了流水线性能的发挥 结构相关:需要更多的硬件资源 数据相关:需要定向,编译器调度 控制相关:尽早检测条件,计算目标地址,延迟转移, 预测 ·增加流水线的级数会增加相关产生的可能性 ·异常,浮点运算使得流水线控制更加复杂 ·编译器可降低数据相关和控制相关的开销 Load延迟槽 Branch延迟槽 Branch预测
2021/2/7 5 Review: 基本流水线 • 流水线提高的是指令带宽（吞吐率），而不是单条 指令的执行速度 • 相关限制了流水线性能的发挥 – 结构相关：需要更多的硬件资源 – 数据相关：需要定向，编译器调度 – 控制相关：尽早检测条件，计算目标地址，延迟转移， 预测 • 增加流水线的级数会增加相关产生的可能性 • 异常，浮点运算使得流水线控制更加复杂 • 编译器可降低数据相关和控制相关的开销 – Load 延迟槽 – Branch 延迟槽 – Branch预测
51指令级并行的基本概念及挑战 ILP:无关的指令重叠执行 流水线的平均cPI Pipeline CPi Ideal Pipeline CPI Struct stalls raw stalls War Stalls WAW Stalls Control Stalls Memory stalls 本章研究:减少停顿( stalls)数的方法和技术 基本途径 软件方法: ·GcC:17%控制类指令,5 instructions+1 branch 在基本块上,得到更多的并行性 挖掘循环级并行 硬件方法 动态调度方法 以MPS的浮点数操作为例
2021/2/7 6 5.1 指令级并行的基本概念及挑战 • ILP: 无关的指令重叠执行 • 流水线的平均CPI • Pipeline CPI = Ideal Pipeline CPI + Struct Stalls + RAW Stalls + WAR Stalls + WAW Stalls + Control Stalls + Memory Stalls • 本章研究：减少停顿（stalls)数的方法和技术 • 基本途径 – 软件方法： • Gcc: 17%控制类指令，5 instructions + 1 branch； • 在基本块上，得到更多的并行性 • 挖掘循环级并行 – 硬件方法 • 动态调度方法 – 以MIPS的浮点数操作为例
采用的基本技术 Technique Reduces Section Forwarding and bypassing Potential data hazard stalls A.2 Delayed branches and simple branch scheduling Control hazard stalls A.2 Basic dynamic scheduling(scoreboarding) Data hazard stalls from true dependences A.8 Dynamic scheduling with renaming Data hazard stalls and stalls from antidependences 3.2 and output dependences namic branch prediction Control stalls 3.4 Issuing multiple instructions per cycle Ideal cpi 3.6 Speculation Data hazard and control hazard stalls 3.5 Dynamic memory disambiguation Data hazard stalls with memory 3.2,3.7 Loop unrolling Control hazard stalls 4.1 Basic compiler pipeline scheduling Data hazard stalls A.2.4.1 Compiler dependence analysis Ideal CPl data hazard stalls 4.4 Software pipelining, trace scheduling Ideal CPi data hazard stalls 4.3 Compiler speculation Ideal CPI data control stalls 计算机体系结构
2021/2/7 计算机体系结构 7 采用的基本技术
本章遵循的指令延时 产生结果的指令使用结果的指令所需延时 印 ALU op Another FP ALU op FP ALU op Store double oad double FP ALU op oad double Store double 32100 Integer op nteger op (当使用结果的指令为 BRANCH指令时除外) 计算机体系结构 8
2021/2/7 计算机体系结构 8 本章遵循的指令延时 • (当使用结果的指令为BRANCH指令时除外) 产生结果的指令 使用结果的指令 所需延时 FP ALU op Another FP ALU op 3 FP ALU op Store double 2 Load double FP ALU op 1 Load double Store double 0 Integer op Integer op 0
52基本块内的指令级并行 基本块的定义: 直线型代码,无分支;单入口;程序由分支语句连接 基本块构成 循环级并行 for(i=1;i<=1000;i++)X()=X()+s; 计算x)时没有数据相关;可以并行产生1000个数据 问题:在生成代码时会有 Branch指令-控制相关 预测比较容易,但我们必须有预测方案 向量处理机模型 load vectors x and y (up to some machine dependent max then do result-vec= Xvec t yec in a single instruction
2021/2/7 9 5.2 基本块内的指令级并行 • 基本块的定义： – 直线型代码，无分支；单入口；程序由分支语句连接 基本块构成 • 循环级并行 – for (i = 1; i <= 1000; i++) x(i) = x(i) + s; – 计算x(i)时没有数据相关；可以并行产生1000个数据； – 问题：在生成代码时会有Branch指令－控制相关 – 预测比较容易，但我们必须有预测方案 – 向量处理机模型 • load vectors x and y (up to some machine dependent max) • then do result-vec = xvec + yvec in a single instruction
◎简单循环及其对应的汇编程序 for(i=1;<=1000;++) X()=Ⅺ()+S; oop: LD FO, O(R1) F0=vector element ADDd F4,F0, F2 : add scalar from f2 SD O(R1), F4 store result SUBI R1R18 decrement pointer 8B (DW) BNEZ R1, Loop branch R1=zero NOP delayed branch slot 计算机体系结构
2021/2/7 计算机体系结构 10 简单循环及其对应的汇编程序 for (i=1; i<=1000; i++) x(i) = x(i) + s; Loop: LD F0,0(R1) ;F0=vector element ADDD F4,F0,F2 ;add scalar from F2 SD 0(R1),F4 ;store result SUBI R1,R1,8 ;decrement pointer 8B (DW) BNEZ R1,Loop ;branch R1!=zero NOP ;delayed branch slot
FP循环中的相关 Loop D F0,O(R1) Fo=vector element ADDD F4 F0 F2 add scalar from f2 SD 0(R1,F4 store result SUB R1,R1,8 ,decrement pointer &B (DW) BAEZ R1, Loop branch R1l=zero NOP delayed branch slot 产生结果的指令 使用结果的指令 所需延时 FP ALU op Another FP ALU op FP ALU op Store double oad double FP ALU op Load double Store double 32100 Integer op Integer op 计算机体系结构
Loop: LD F0,0(R1) ;F0=vector element ADDD F4,F0,F2 ;add scalar from F2 SD 0(R1),F4 ;store result SUBI R1,R1,8 ;decrement pointer 8B (DW) BNEZ R1,Loop ;branch R1!=zero NOP ;delayed branch slot 2021/2/7 计算机体系结构 11 FP 循环中的相关 产生结果的指令 使用结果的指令 所需延时 FP ALU op Another FP ALU op 3 FP ALU op Store double 2 Load double FP ALU op 1 Load double Store double 0 Integer op Integer op 0