十章依赖于机器的优化.ppt
《十章依赖于机器的优化.ppt》由会员分享,可在线阅读,更多相关《十章依赖于机器的优化.ppt(77页珍藏版)》请在三一文库上搜索。
1、第十章 依赖于机器的优化,在指令级并行的机器上,程序的运行速度依赖于下面几个因素 程序中潜在的并行 处理器上可用的并行 从串行程序提取并行的能力 在给定的调度约束下发现最佳并行调度的能力 并行的提取和并行执行的调度都可以静态地在软件中或动态地在硬件中完成,第十章 依赖于机器的优化,本章内容 使用指令级并行的基础问题 提取并行的数据相关性分析 代码调度的基本概念 基本块调度的技术、发现通用程序中的高度数据相关控制流的方法、调度数值程序的软件流水线技术 在多处理器系统上,使用数组的计算密集型程序的并行化和数据局部性优化的概念和方法,10.1 处理器体系结构,在考虑指令级并行时,通常想象成一个处理器
2、在单个时钟周期内发射几个操作 事实上,在每周期内发射一个操作是可能的, 而指令级并行的获得是通过使用流水线技术 本节先解释流水线,然后讨论多指令发射,10.1 处理器体系结构,10.1.1 指令流水线和分支延迟 i i + 1 i + 2 i + 3 i + 4 1. IF 2. ID IF 3. EX ID IF 4. MEM EX ID IF 5. WB MEM EX ID IF 6. WB MEM EX ID 7. WB MEM EX 8. WB MEM 9. WB,取指令IF, 译码ID, 执行操作EX, 访问内存MEM, 回写结果WB,5级指令流水线中 的5条连续指令,10.1 处理
3、器体系结构,10.1.1 指令流水线和分支延迟 分支延迟 发现应该执行一个分支而不是直接后继 转向一个分支时会引起取分支目的地址指令的延迟并引起指令流水线“打嗝” 可以通过使用硬件,根据分支的执行历史来预测分支结果并从预测的目的地址预取指令 分支延迟不可避免,因为分支预测会发生偏差,10.1 处理器体系结构,10.1.2 流水化的执行 如果不依赖一条指令结果的随后指令在该结 果产生前就被允许执行 有些指令的执行需要几个周期,几个操作同时出现在它们的执行级上可能的 如果最长的执行流水线是n级,n个操作同时进行的可能性是存在的 并非所有的指令都能被完全流水化,例如浮点除 通用处理器大都动态察觉相继
4、指令之间的依赖性 嵌入式系统把数据相关性的检查交给软件,10.1 处理器体系结构,10.1.3 多指令发射 每周期发射几个操作,让更多操作同时进行 超长指令字机器 将若干个操作编码在单周期中发射 编译器需要确定哪些操作可以并行发射 超标量机器 超标量机器有按普通顺序执行语义的正规指令集 硬件自动察觉指令之间的相关性,并且在它们的操作数可用时就发射它们 更复杂的调度器能够“乱序”执行指令,10.2 代码调度的约束,代码调度 用在代码生成器产生的机器代码上的优化技术 本节讨论代码调度的约束 控制相关约束 在原程序中执行的所有操作都必须在优化代码中执行 数据相关约束 优化程序中的操作产生的结果必须同
5、原程序对应操作的结果一样 资源约束 调度不能过分占用机器的资源 优化程序很难调试 内存状态可能和顺序执行的任何内存状态不匹配,10.2 代码调度的约束,10.2.1 数据相关 真相关 如果对同一个单元先写后读,那么读依赖于所写的值 反相关 如果对同一个单元先读后写。可以通过把值存在不同的单元来删除反相关 输出相关 如果对同一个单元先后写两次。也可删除 数据相关概念可同时用于内存访问和寄存器访问,10.2 代码调度的约束,10.2.2 发现内存访问中的相关性 例 (1) a = 1 (2) p = 2 (3) x = a 语句(1)和(2)可能构成输出相关 语句(1)和(3)可能构成真相关 语句
6、(2)和(3)可能构成真相关 除非编译器知道p不可能指向a,否则3个操作必须串行执行,10.2 代码调度的约束,10.2.2 发现内存访问中的相关性 发现数据相关需要不同形式的分析 数组元素间的别名分析 Ai和Aj是否互为别名 指针别名分析 若p和q相等,则p和q、p-next和q-next、 p-data和q-data等都分别互为别名 过程间分析 引用调用场合:形参和形参之间、形参和全局变量之间因实参而引起互为别名,10.2 代码调度的约束,10.2.3 寄存器使用和并行执行之间的折衷 例:(a + b) + c + (d + e) LD R1, a LD R2, b ADD R1, R1,
7、 R2 LD R2, c ADD R1, R1, R2 LD R2, d LD R3, e ADD R2, R2, R3 ADD R1, R1, R2,若瞄准极小化寄存器的使用个数,则只需使用3个寄存器,10.2 代码调度的约束,10.2.3 寄存器使用和并行执行之间的折衷 例:(a + b) + c + (d + e) LD R1, a LD R2, b ADD R1, R1, R2 LD R2, c ADD R1, R1, R2 LD R2, d LD R3, e ADD R2, R2, R3 ADD R1, R1, R2,完成整个计算需要7步,10.2 代码调度的约束,10.2.3 寄存
8、器使用和并行执行之间的折衷 例:(a + b) + c + (d + e),如果对每个中间结果使用不同寄存器,则完成计算只需要4步,10.2 代码调度的约束,10.2.4 寄存器分配和代码调度的次序安排 先寄存器分配 结果代码中会有很多存储相关 非数值应用本质上没有多少并行,采用这种方式 先代码调度 导致寄存器溢出,抵消指令级并行的优点 适用于有许多大表达式的数值应用 在假定伪寄存器就是物理寄存器情况下,先调度指令,然后寄存器分配,把处理寄存器溢出的代码附加在必要的地方,并再次进行代码调度,10.2 代码调度的约束,10.2.5 控制相关 在非数值计算中,基本块非常小,其中的操作通常高度相关,
9、几乎不能并行 调查跨基本块的并行是至关重要的 若一条指令很可能被执行且有空闲的资源可“免费”用于完成该指令的操作,则可以投机地执行该指令;若投机成功,则程序运行得快一些 例 if (a t) b = a a依赖于比较a t的结果 b = a a; 若a a不会产生副作用,则 d = a + c; a a可以投机地执行,10.2 代码调度的约束,10.2.6 投机执行的支持 内存读取是一类使用频繁,且能从投机执行大大获益的指令 但在 if (p != null) q = p 中,投机地对p脱引用将引起该程序因p等于null而错误地停止 许多高性能处理器提供专门的特性来支持投机地内存访问,10.2
10、 代码调度的约束,10.2.6 投机执行的支持 预取指令 在数据使用前将其从内存取到缓存,若该单元无效或访问它会引起缺页,则忽略 抑制位 允许投机地从内存将数据读取到寄存器堆,若出现非法内存访问或缺页,则设置目标寄存器的抑制位 判定指令 在判定条件为真时才执行的指令 例 if (a = 0) 翻译成 ADD R3, R4, R5 b = c + d; CMOVZ R2, R3, R1 假定a、b、c和d分别被分配了R1、R2、R4和R5 可用来将相邻基本块组合成一个更大基本块,10.2 代码调度的约束,10.2.7 一个基本的机器模型 机器模型M = (R, T) T:操作类型集,如读取、存储
11、和算术运算等 R = r1, r2, :硬件资源向量集,如内存访问部件、算术运算部件和浮点功能部件 ri代表第i类资源中可用的部件数 每个操作有一组输入操作数、一组输出操作数和一个资源需求 和每个输入操作数相关的是一个输入延迟 和每个输出操作数相关的是一个输出延迟,10.2 代码调度的约束,10.2.7 一个基本的机器模型 机器模型M = (R, T) 对每种操作类型t,资源使用由一张二维资源预留表RTt来建模 条目RTti, j是t类型的一个操作在它被发射i时钟周期后,使用第j种资源的部件数 对任何t、i和j,RTti, j必须小于或等于Rj,10.3 基 本 块 调 度,10.3.1 数据
12、依赖图 基本块由数据依赖图G = (N, E)来表示 结点集合N表示该块的机器指令中的操作集合 有向边集合E表示这些操作之间的数据相关约束 G的结点集N和边集E按如下两步构造 N中的每个操作n有一张资源预留表RTn,其值直接就是n的操作类型的资源预留表 每条边e都标示有延迟de,表示e的目的结点必须在它源结点发射de个时钟周期之后才可以发射,10.3 基 本 块 调 度,灰色表 示1 白色表 示0,操作是全流水 的,只需显示 在第1行使用 的资源,10.3 基 本 块 调 度,10.3.2 基本块的表调度 关键路径包括最后5个结点,故第3条指令先调度 再调度第1条指令,因为第4条指令还需等1周
13、期 第4周期调度2条,10.3 基 本 块 调 度,10.3.2 基本块的表调度 根据每个结点同先前已经被调度的各结点之间的数据相关约束,来计算一个结点可以执行的最早时间槽 这个结点所需资源根据一张资源预留表来进行检查,该资源预留表收集了所有到目前为止被占用资源。这个结点的调度按有足够资源的最早时间槽来安排,10.4 全局代码调度,对于有适度指令级并行的机器,仅对每个基本块进行紧凑调度会引起许多资源空闲 全局调度:为了更好地利用机器资源,需要考虑把指令从一个基本块移到另一个基本块的代码生成策略 必须保证 原来程序中所有指令在优化程序中都被执行 当优化程序可以投机地执行额外指令时,这些指令肯定不
14、能有任何多余的副作用,10.4 全局代码调度,10.4.1 简单的代码移动 先用例子展示操作在基本块之间移动涉及的问题,10.4 全局代码调度,假定a, b, c, d和e的地址不同,分别保存在R1到R5 由于数据相关,块内的指令必须串行执行,且插入 NOP,10.4 全局代码调度,假定机器在一个时钟周期执行任意的两个操作 读取操作有2周期的延迟,其他指令1周期的延迟,10.4 全局代码调度,B3肯定要执行,因而可以和B1并行执行 B2的读取操作在执行B1时投机地完成 B2的存储操作放到B3的 一份拷贝中,10.4 全局代码调度,10.4 全局代码调度,基本块之间的支配关系 指令在基本块之间的
15、移动因支配关系不同而不同 B1和B3控制等价:B1支配B3, B3后支配B1 B1支配B2, 但是B2并非后支配B1 B2不支配B3, 但是B3后支配B2,10.4 全局代码调度,10.4.2 向上的代码移动 从块src向上移动到块dst,假定移动未违反数据相 关,并使得通过dst到src的路径运行得较快 若dst和src等价,则被移动操作应该被执行时,它正好仅被执行一次,10.4 全局代码调度,10.4.2 向上的代码移动 从块src向上移动到块dst,假定移动未违反数据相 关,并使得通过dst到src的路径运行得较快 若dst和src等价,则被移动操作应该被执行时,它正好仅被执行一次 若s
16、rc未后支配dst,被移动操作可利用空闲资源免费执行,在控制流到达src时获益,10.4 全局代码调度,10.4.2 向上的代码移动 从块src向上移动到块dst,假定移动未违反数据相 关,并使得通过dst到src的路径运行得较快 若dst和src等价,则被移动操作应该被执行时,它正好仅被执行一次 若src未后支配dst,被移动操作可利用空闲资源免费执行,在控制流到达src时获益 若dst不支配src, 需要插入被移动操作的拷贝,10.4 全局代码调度,10.4.3 向下的代码移动 从块src向下移动到块dst,假定移动未违反数据相 关,并使得通过dst到src的路径运行得较快 若dst和sr
17、c等价,则被移动操作应该被执行时,它正好仅被执行一次,10.4 全局代码调度,10.4.3 向下的代码移动 从块src向下移动到块dst,假定移动未违反数据相 关,并使得通过dst到src的路径运行得较快 若dst和src等价,则被移动操作应该被执行时,它正好仅被执行一次 src未后支配dst, 向下移动的代码经常是存储操作, 复制从src到dst路径上的各块,并把 被移动操作仅放置在dst的新拷贝中,10.4 全局代码调度,9.5节的例子可作为参考,10.4 全局代码调度,10.4.3 向下的代码移动 从块src向下移动到块dst,假定移动未违反数据相 关,并使得通过dst到src的路径运行
18、得较快 若dst和src等价,则被移动操作应该被执行时,它正好仅被执行一次 src未后支配dst, 向下移动的代码经常是存储操作, 复制从src到dst路径上的各块,并把 被移动操作仅放置在dst的新拷贝中 dst没有后支配src,插入补偿代码以 保证被移动操作在不经dst路径上也执行,10.4 全局代码调度,10.4.4 更新数据相关 代码移动会改变操作之间的数据相关关系 两个对x的赋值之一可以移动到最上面的基本块,该变换能维持原来程序中的所有相关性 一旦一个对x的赋值被上移,另一个就不能移动了 移动使得x在最上面块的出口 由不活跃变成活跃 一个变量在某个程序点 活跃,则就不能把对它的投机
19、定值移到该点的上面,10.4 全局代码调度,10.4.5 全局调度的其他问题 程序调度应该使经常执行的路径运行得快一些, 不经常执行的路径可能会因调度变得慢一些 编译器可用来估计执行频率的技术有若干种 (1) 内循环比外循环执行得更频繁 (2) 分支指令往回跳转比不跳转要更经常 (3)看守程序出口或异常处理例程的分支语句很少被执行 最好的频率估计来自动态剖析,程序被静态插桩以用来运行时记录条件分支每次的走向,10.4 全局代码调度,10.4.5 全局调度的其他问题 最简单的全局调度算法也相当复杂,不介绍 在一些全局调度算法中,循环迭代的边界是代码移动的一种屏障,需循环展开 for(i = 0;
20、 i N; i +) for ( i = 0; i + 4 N; i += 4) S(i); S(i); S(i +1); S(i +2); S(i +3); for ( ; i N; i +) S(i); ,10.4 全局代码调度,10.4.6 静态调度器和动态调度器的相互影响 动态调度器的优点是可以根据运行时的情况建立新 的调度表,无需事先编码所有可能的调度表,10.4 全局代码调度,10.4.6 静态调度器和动态调度器的相互影响 存在动态调度情况下,静态调度器的作用 保证尽早地取高延迟的指令,使得动态调度器能够尽早发射它们 尽早安排预取指令,使数据到要用时已经在缓存, 或尽早安排可能不命
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 依赖于 机器 优化
链接地址:https://www.31doc.com/p-2641016.html