软件流水中的循环展开优化.pdf

收稿日期 2004 06 25 基金项目 国家自然科学基金资助项目 60173010 作者简介 李文龙 1977 男 辽宁鞍山人 博士生 IiwenIong 软件流水中的循环展开优化 李文龙刘利汤志忠 清华大学 计算机科学与技术系 北京 100084 摘要 在软件流水中应用循环展开可以实现分数值的启动间距 提高资 源的利用率 同时基于展开的优化技术可以降低程序的资源需求和关键路径的长度 提出了基于程序特性的展开因子算法 UTBPC UnroIIing Times Based Program Character istics 解决了循环展开的核心问题 展开因子的确定 同时提出了基于展开的软 件数据预取优化技术 提高了软件数据预取的效率 所有这些都在 ORC Open Re search CompiIer 中实现 并对 SPEC 2000 中的程序进行了测试 平均性能提高了 2 6 实验结果表明新提出的算法和基于展开的数据预取优化技术提高了编译器的整 体性能 关键词 计算机软件 软件流水 循环展开 展开因子 数据预取 中图分类号 TP 311 文献标识码 A文 章 编 号 1001 5965 2004 11 1111 05 Loop unrolling optimization for software pipelining Li WenIongLiu LiTang Zhizhong Dept of Computer Science and TechnoIogy Tsinghua University Beijing 100084 China Abstract Loop unroIIing can make software pipeIining achieve fractionaI initiation intervaI and improve re source utiIization Optimizations based on unroIIing can reduce resource reguirements and the heights of criticaI paths An aIgorithm named UTBPC unroIIing times based program characteristics for determining unroIIing factors and unroIIing based optimization for software data prefetching were proposed These optimizations were impIemented in ORC open research compiIer and SPEC CPU2000 benchmarks were tested in Itanium processor The average performance was improved by 2 6 The resuIts show that UTBPC aIgorithm and unroIIing based optimization for software data prefetching can improve the overaII performance of compiIers Key words software software pipeIining Ioop unroIIing unroIIing times data prefetching 软件流水 1 是一种重要的指令调度技术 它 通过并行执行来自不同循环体的指令来加快循环 程序的执行速度 在前一个循环体未结束前启动 下一个新的循环体 在软件流水中 相邻循环体的 启动时间间隔称为启动间距 II Initiation IntervaI 循环展开 2 是一种简单的循环变换技术 它 将循环体中的指令复制多份 增加循环体的代码 量 减少了循环的重复次数 降低了循环转移的开 销 展开后的循环体包含更多的指令 使后面的调 度器能够更加自由地挑选不相关的指令进行调 度 从而产生更好的调度结果 在软件流水中应用循环展开可以使软件流水 实现分数值的启动间距 同时基于展开的优化技 术可以降低程序的资源需求和关键路径的长度 但是循环展开会引起代码量增长和寄存器需求增 大 代码量的增长会导致缓存的性能变差 寄存器 需求的增大则有可能使软件流水失败 本文提出了基于程序特性的展开因子算法 UTBPC UnroIIing Times Based Program Characteris tics 解决了软件流水的核心问题 展开因子 2004 年11 月 第30卷 第11期 北 京 航 空 航 天 大 学 学 报 JournaI of Beijing University of Aeronautics and Astronautics November2004 VoI 30No 11 的确定 另外提出了基于展开的软件数据预取优 化技术 提高了数据预取的效率 降低了预取的开 销 1软件流水和循环展开 1 1软件流水 软件流水通过重叠不同循环体的执行来获得 加速 在软件流水中 最重要的启发式之一就是模 调度 3 所有循环体按照一个固定的启动间距依 次启动 每个循环体的调度都相同 调度结果由装 入 核心和排空 3 部分组成 对于图 la 中的循环 经过软件流水后 所得 调度如图 lb 所示 其中 每个循环体有 3 个阶段 Al A 2 A 3 循环体长度为 3 II 虚框内是核心 a一个单重循环b软件流水 图 l 经典的单重循环模调度软件流水 1 2循环展开 循环展开是一种简单而有效的开发指令级并 行性的方法 它通过复制循环体代码多次 同时调 整循环出口代码而得到一个新的循环体 这样相 对于分支转移和循环开销指令而言 有更多的指 令在一个循环体中执行 1 3软件流水中应用循环展开的动机 在软件流水中 启动间距 II 是衡量软件流水 效率的重要指标 II 的下限 MII 由两个因素决定 资源限制 RGSMII 和数据相关 RGOMII 其中 RGSMII 和 RGOMII 的计算公式分别如下 RGSMII max 资源r 使用 r 类资源的操作个数总和 目标处理机中资源 r 的总数 RGOMII max 资源c 回路 c 上的所有相关延迟之和 回路 c 上所有相关体差之和 因为启动间距必须是整数值 对于 RGSMII 或 者 RGOMII 为分数的循环而言 通过展开可以避免 分数值的向上取整导致的性能降低 同时也可以 提高资源的利用率 1 4基于展开的循环优化技术 对于展开后的循环 因为包含指令的多个拷 贝 所以可以应用一些基于展开的优化技术 比如 规约变量的优化 这些基于展开的优化技术不仅 可以降低程序的资源需求 同时可以降低关键路 径的长度 2基于程序特性的展开因子算法 2 1限制循环展开的因素 在软件流水中应用循环展开 最终目标就是 为了降低 II 的值 提高资源的利用率 软件流水 所能实现的 II 受以下几个因素的限制 限制 1 体系结构限制 例如功能部件的个 数 指令延迟的长短 寄存器的个数以及体系结构 对软件流水的硬件支持 如条件执行 旋转寄存 器 特殊的循环分支指令等 限制 2 编译技术限制 例如采用何种调度 和寄存器分配算法 以及该算法的性能等 限制 3 程序特性限制 例如循环的结构 DO LOOP WHILE LOOP 操作的类型 相关性约 束 寄存器需求等 定义 基于程序特性的展开因子算法 在给 定上述限制 l 和限制 2 的条件下 即对于特定的 体系结构和编译技术 对不同程序特性的循环在 展开时所选择的展开因子是不同的 这种展开因 子的算法称之为基于程序特性的展开因子算法 根据前面的分析 提出限制展开因子的因素 如下 因素 1 RGSMII 和 RGOMII 的关系 RGSMII 和 RGOMII 哪个起主导作用 起主导作用的是否为整 数值 因素 2 循环本身是否包含分支 如果包含 分支指令 可以适当减少展开的次数 避免循环对 拷贝操作的依赖 因素 3 循环自身的寄存器需求 如果寄存 器压力很大 需要减少展开次数 因素 4 循环体中的操作个数 如果操作个 数很少 并且相关限制很轻 则可以适当增大展开 次数 因素 5 循环展开引入的开销 循环展开引 入的开销会减轻软件流水和循环展开的性能贡 献 wirrGr 0 for i 0 i a wirrGr wirrGr i 2lll 北 京 航 空 航 天 大 学 学 报2004 年 对于因素 2 以上面的循环为例进行解释 这 是一个包含一路分支的计数循环 因为软件流水 中旋转寄存器的特点 需要对分支上的定值操作 添加一条额外的拷贝操作 如果不展开这个循环 添加的拷贝操作会使得软件流水所能实现的 II 为 16 展开 2 次后 则不必添加拷贝操作 软件流 水所能实现的平均 II 可以达到 15 如果再增大展 开次数 平均 II 始终为 15 对于这样的带分支循 环 展开 2 次后就可以实现较好的效果 对于因素 4 在软件流水中 每个时钟周期最 多只能执行一个循环体 而对于操作很少 相关限 制很轻的循环而言 展开后就可以实现每个时钟 周期执行多个循环体 计算展开因子的算法 UTBPC 算法的流程如下 int Determine SWPUnroII Factor 1 根据编译选项确定展开因子下限 min unr 2 根据编译选项和操作个数确定展开因子 上限 max unr 3 FOR 每个展开因子 min unr max unr 根据资源利用率计算每个展开因子所对 应的循环体执行周期数 Swp cycIe ENDFOR 4 IF 存在预取指令 THEN FOR 每个展开因子 min unr max unr 计算最小相关自环长度 min recur rence Swp cycIe max Swp cycIe min recurrence ENDFOR ENDIF 5 FOR 每个展开因子 min unr max unr 计算循环体所需的最小周期数 min cycIe min Swp cycIe ENDFOR 6 FOR每个展开因子 minunr maxunr AND Swp cycIe min cycIe 计算最小的展开 因 子 unroII factor min ENDFOR 7 调整 unroII factor 的值为 2 的整数次幂 8 IF 循环中操作很少 THEN RETURN unroII factor ENDIF 9 IF ReSMII RecMII THEN unroII factor 1 ENDIF 10 IF 循环中含有分支指令 THEN unroII factor max unroII factor 2 ENDIF 11 IF T1 ReSMII 时 将展开后对应原来一个 Pre fetch 操作的多个预取实例合并成 N 个预取操作 其中 N Unr 通过对展开后的数据预取合并 减少了冗余 预取的个数 提高了数据预取的效率 4实验结果 本节将以 SPEC 2000 benchmarks 中的部分程 序为例 对软件流水中的循环展开优化进行了测 试 其它程序测试的结果是性能没有变化 故不列 出 全部的程序采用 ORC 5 进行编译 编译选项 采用 O3 编译结果在 Itanium 处理器 6 上执行 Itanium 是第一代 IA 64 EPIC 7 体系结构的处理 器 为软件流水 数据预取等提供硬件支持 表 1 给出了实验结果 第 1 列和第 3 列是测 试用例 分别来自 SPEC INT 和 SPEC FP 第 2 列和 第 4 列表示应用展开优化前后的性能加速比 即 T TUTBPC 1X 100 表中的数据表明 UTBPC 算法的效果是相当 明显的 所有测试程序性能都得到了提高 其中 mesa性能提高了 4 测试程序平均性能提高了 2 6 这对仅优化软件流水中的循环展开而言 这样的性能贡献是非常大的 这说明优化软件流 水和循环展开对于提升编译器的性能潜力还是很 大的 表 1 UTBPC 算法的性能 benchmarksspeedup benchmarksspeedup Vpr1wupwise3 Crafty2 6mesa4 Vortex1gaIgeI2 TwoIf3art2 7 Sixtract1 6平均2 6 表 2 统计了应用 UTBPC 算法前后展开次数 的变化情况 从表 2 中可以看出 应用 UTBPC 后 展开因 子在较小值占据了很大的比例 这表明对于大部 分循环而言减小软件流水中的循环展开因子有利 于加快程序的执行速度 但 wupwise 程序是个特 例 实验发现如果增大 wupwise 中的循环展开因 子 性能会进一步提高 这说明 UTBPC 算法还有 进一步完善的潜力 关于如何确定循环展开因子 的算法还需要进一步的研究 表 2 应用算法前后循环展开次数变化的统计 展开 次数 INT benchmarksFP benchmarks 算法前 比例 算法后 比例 算法前 比例 算法后 比例 00 5740 7450 3790 507 20 0930 1020 1870 182 40 1540 0620 1930 131 80 1450 0690 2220 166 5相关工作 通常 循环展开是在软件流水调度之前进行 的 即根据最优的启动间距 II 来确定展开因子 如果在软件流水时无法得到启动间距为 II 的调 度 则增加 II 继续调度 这样 原来计算的展开因 子 可能就不是最优的了 Sanchez 等提出了一种在二维空间 II 搜 索展开因子的方法 8 其中 II 表示循环展开 次 时的启动间距 它首先将二元组 II 按照吞吐 率的降序排列 然后依次进行调度 实验表明 他 们的方法可以比传统方法提高 5 12 5 但 该方法需要重复进行循环展开和模调度 计算复 杂度较高 Vivek 在文献 9 中提出了针对完美多重循环 展开因子的选择算法 此算法并没有考虑循环展 开对软件流水的影响 只是单纯地从循环展开的 角度来计算展开因子 6结 束 语 在软件流水中应用循环展开可以有效地提高 编译器的性能 展开因子是影响循环展开性能贡 献的关键因素 本文提出的基于程序特性的展开 因子算法 UTBPC 和基于展开的数据预取优化 为 软件流水中循环展开优化的应用提供了有效的支 持 参考文献 References 1 AIIen V H Jones R B Lee R M et al Software pipeIining J ACM Computing Surveys 1995 27 3 367 432 2 Weiss S Smith J E A study of scaIar compiIation technigues for 4111 北 京 航 空 航 天 大 学 学 报2004 年 pipeIined supercomputers J ACM Transactions on MathematicaI Software 1990 16 3 223 245 3 Rau B R Iterative moduIo scheduIing R HPL 94 115 1994 4 Mowry T C Lam M S Gupta A Design and evaIuation of a compiI er aIgorithm for prefetching A In Proceeding of the Fifth Interna tionaI Conference on ArchitecturaI Support for Programming Languag es and Operating Systems C Massachusetts ACM Press 1992 62 73 5 Roy J Sun C Wu C Y Open research compiIer for itanium proces sor famiIy IPF A In MICRO 34 TutoriaI C Texas ACM Press 2001 6 InteI Corporation InteI IA 64 architecture software deveIoper s man uaI VoIume 3 Instruction set reference M InteI Corp 2000 7 InteI Corporation InteI IA 64 architecture software deveIoper s man uaI VoIume 1 IA 64 appIication architecture M InteI Corp 2000 8 Sanchez F CortadeIIa J Badia R M OptimaI expIoration of the un roIIing degree for software pipeIining R UPC DAC 1996 41 1996 9 Vivek Sarkar Optimized unroIIing of nested Ioops A In Pro ceedings of the 14th InternationaI Conference on Supercomputing C New Mexico ACM Press 2000 153 166 我校组团参加第六届重庆高交会 第六届中国重庆高新技术交易会暨第二届国际军转民科技博览会于 11 月 13 日 至 17 日在重庆召开 本次高交会上 我校与建设工业集团就 两轮摩托车道路模拟 试验台 项目签署了合作协议 今年我校与重庆市政府签订了 共建重庆 北航制造 业工程研究院 的协议 目前与重庆市企业有 3 个项目 基于虚拟样机技术的 ATV 全地形车研发 UGP 游戏开发通用平台 PROFIBUS PA 总线关键技术及产品研究 获 得重庆市科委立项支持 另有 3 个项目 无人飞行平台 自主移动行走机构 民用产品 可靠性工程 正在进一步洽谈 一个项目 车载智能管理仪 与深圳企业共同申请信息 产业部电子基金立项 今后北航根据重庆市的发展规划和企业结构 初步确定以兵 器工业和两车行业为重点发展与重庆地区的科技合作 摘自 北航 报第 期 5111 第 11 期李文龙等 软件流水中的循环展开优化 软件流水中的循环展开优化软件流水中的循环展开优化 作者 李文龙 刘利 汤志忠 作者单位 清华大学 计算机科学与技术系 北京 100084 刊名 北京航空航天大学学报 英文刊名 JOURNAL OF BEIJING UNIVERSITY OF AERONAUTICS AND ASTRONAUTICS 年 卷 期 2004 30 11 被引用次数 8次 参考文献 9条 参考文献 9条 1 Sanchez F Cortadella J Badia R M Optimal exploration of the unrolling degree for software pipelining 1996 2 Intel Corporation Intel IA 64 architecture software developer s manual Volume 1 IA 64 application architecture 2000 3 Vivek Sarkar Optimized unrolling of nested loops 外