Page 85 - 《软件学报》2024年第6期

方燕飞 等: 申威众核处理器访存与通信融合编译优化 2661

4.3 启发式循环优化方案迭代求解框架
从 region 收益公式 (6) 和循环收益公式 (11) 可以看出, 当 TR 大于 0 时, 优化有正向的收益, 而当 TR 小于 0
时, 优化收益是负的, 即优化产生的缓冲数据传输开销超过了数据访问节省的时间. 这种情况出现的可能原因两
个, 一是用户给出的缓冲区空间过小, 还有一种可能是循环总迭代数太小, 使得最终求出的最大 block_len 过于小,
从而使得某些 region 的每次 DMA 或者 RMA 传输的数据量不足以填满带宽. 极端的如 block_len=1 时, 对于
region 的元素宽度为 4 的数组访问, 每次传输 4 字节, 由于固定的 DMA 启动开销相对较大, DMA 总开销远超过
直接主存访问的开销.
因此, 在利用第 4.2 节中介绍的二分搜索算法求得 block_len 和 region 方案后, 需要将具体优化方案下的 region
数据进一步代入第 4.1 节中的收益公式进行评估, 如果收益值不为正, 则需要舍弃一个或更多个 region 的优化, 以确
保剩下的数组 region 优化可以获得正向收益. 当发生负向收益时, 选择放弃哪个 region 的优化, 以及最终需要选择放
弃多少个 region, 是一个关键问题. 本文利用第 4.1 节构建的时间收益与空间开销比模型 P region (见公式 (7)) 衡量一
个 region 的优先级, 当发生负向收益时, 优先级最低的 region (即收益开销比值 P region 最小的 region) 首先被放弃.
本文设计了一个基于收益模型的启发式迭代求解框架. 为尽量满足编译指示意图, 框架在保证收益为正的情
否
况下尽可能多地实现对用户编译指示中所指出的数组的优化. 算法框架如图 12 所示, 主要思想是先将循环中被编
译指示的所有数组的访问信息作为启发式初值信息, 调用第 4.2 节中的搜索算法求解当前条件下的最优循环分块
方案. 然后根据优化收益函数评估求得的当前最优循环分块方案下的每个 region 的收益和总体收益, 当发生收益
为负的情况, 则舍弃最低优先级 region 的信息, 然后根据剩下的 region 信息重新输入算法 1 进行优化方案求解, 以
此迭代直至剩下的所有 region 收益为正. 从算法流程可以看出, 整个框架调用二分搜索算法的次数最差情况下是
被指示的待优化数组的访问总个数. 而二分搜索算法复杂度为 logN (N 为循环长度), 因此, 整个搜索算法的时间复
杂度是多项式时间的, 经实际测试, 编译阶段的搜索时间开销可忽略.

编译器识别编译指示
分析循环提取待
优化数组信息

二分搜索求解循环优化方案
得到 block_len、region 等信息

利用收益模型计算时间收益

判断 region 收益 是 根据优化方案
是否全为正 开展代码变换
是

输出优化
丢弃一个优先级 后的代码
最低的 region 信息

是否还有需要 否
优化的访问
结束对当前循环
的分析与优化

图 12 基于收益模型的启发式迭代求解算法框架