第12期 曹倩等：基于超图的非规则应用局部性优化 ·1475· 被访问；….因此得到各个数据被访问的情况. 据，分别为1、3和4；第2次迭代访问三个数据，分 第2步按第1步记录的信息统计每次迭代访 别为1、2和3：….因此得到各个迭代访问到的数 问的数据个数及数据值.如第1次迭代访问三个数 据情况，如图5(b)所示： 数据 选代 迭代 访问数据 个数 数据 迭代 迭代顺序 1 1,3,4 1,2 1,2 1.2 第一步 2 1,2.3 3 第二步 2,4,5 2,4,5 1,2,5,4 1 3 3,4 2 1.2,3,4 2,3 1,2,3,4 1,2,5,4,3 4 1,3 2 1,3 ,2,5,4,3 (b) 图5HNRC_I算法实例.(a)初始的时间局部性超图：()统计每次迭代访问的数据：()最终的选代顺序 Fig.5 An example of H_NRC_I algorithm:(a)original temporal locality hypergraph:(b)data accessed in each iteration:(c)final iteration order 第3步根据第1步得到的各个数据被访问的 杂度为O(E+V) 情况，依次遍历各个超边.例如，对于第1条超边所 3 实验方案及其结果 对应的数据1，访问它的迭代为1,2，查看第2步得 到的每次迭代访问的数据情况可知，迭代1和2的 3.1实验方案 访问的数据个数是一样的，所以按照现有的顺序直 实验使用的计算机配置如下：CPU为Xeon 接排列迭代，即迭代顺序为1,2；对于第2条超边所 2.8GHz,一级cache的容量为64kB,二级cache的 对应的数据2，访问它的迭代为2,4,5.由于迭代2 容量为1MB,cache行为64B,内存为2GB.Linux版 己经被排序，则仅考虑迭代4,5.迭代4,5访问的 本为Fedora3,编译器版本为GCC3.2.2.使用Intel 数据个数分别为2和1，按照访问的数据个数由少 VTune Performance Analyzer8.0测试cache及快表 到多排序，则迭代顺序为5,4.因此，分析完前两条 (translation lookaside buffer,TLB)的性能 超边后，迭代顺序为1,2,5,4.同理分析第3、4条 该文针对非规则循环中一次迭代访问多个间接 超边的情况.最终得到迭代顺序为1,2,5,4,3， 数组的典型应用一流体力学ZEUS-2D进行实 如图5(c)所示. 验，其核心子程序X2 INTZC包含了类似于图1的循 H NRC I算法思路简单，实现起来比较容易， 环.实验中的迭代次数为3万次，每个数据为8bit 其时间复杂度比较低，对时间开销要求较低的情况 的双精度浮点型.间接数组的值由循环变量的一个 表现较好. 线性函数获得，即每个间接数组的元素值与索引变 2.2.2HBSI算法 量值为一对一的映射关系 HBS_I算法的思想与H_BS_D相同，H_BS_I 3.2各个算法的效果比较 在时间局部性超图上通过回溯法由深层到浅层依次 实验过程：首先测试不使用任何重排算法以及 对间接数组的值进行编号，从而实现迭代重排 使用单个重排算法的运行时间：然后给出数据重排 第1步遍历间接数组，统计每个值对应的使 与迭代重排各种组合算法下程序的运行时间（这两 用该值的迭代次数及迭代序号，根据所得信息构建 种运行时间均不包括重排算法本身的时间开销)以 时间局部性超图. 及一级cache、二级cache和TLB的命中率；最后测 第2步在第1步构建的超图上，任取一个未 试各种重排算法本身的时间开销.实验中所得数据 被编号的超点，对该超点按顺序编号.这里仍旧使 均为5次运行下的平均值. 用数据重排算法H_BS_D中处理超点的方法. 图6给出使用单个重排算法时程序的运行时 第3步按编号顺序对已编号的超点的子结点 间，其中包括不使用任何重排算法的情况，用 进行下一轮的编号. “NONE”表示.由图可见，使用任何一种重排算法 第4步若仍有未编号的超点，则返回第2步. 程序的执行速度均有所改善，平均执行速度提高约 HBSI算法跟HBSD算法相似，因此不再给 25.4%.单独对数据重排来说，HNRC_D算法是最 出伪码.该算法的原理比较简单，其算法的时间复 好的，H_P℉B_D算法次之；单独对迭代重排来说，第 12 期 曹 倩等: 基于超图的非规则应用局部性优化 被访问; ……． 因此得到各个数据被访问的情况． 第 2 步 按第 1 步记录的信息统计每次迭代访 问的数据个数及数据值． 如第 1 次迭代访问三个数 据，分别为 1、3 和 4; 第 2 次迭代访问三个数据，分 别为 1、2 和 3; ……． 因此得到各个迭代访问到的数 据情况，如图 5( b) 所示; 图 5 H_NRC_I 算法实例． ( a) 初始的时间局部性超图; ( b) 统计每次迭代访问的数据; ( c) 最终的迭代顺序 Fig． 5 An example of H_NRC_I algorithm: ( a) original temporal locality hypergraph; ( b) data accessed in each iteration; ( c) final iteration order 第 3 步 根据第 1 步得到的各个数据被访问的 情况，依次遍历各个超边． 例如，对于第 1 条超边所 对应的数据 1，访问它的迭代为 1，2，查看第 2 步得 到的每次迭代访问的数据情况可知，迭代 1 和 2 的 访问的数据个数是一样的，所以按照现有的顺序直 接排列迭代，即迭代顺序为 1，2; 对于第 2 条超边所 对应的数据 2，访问它的迭代为 2，4，5． 由于迭代 2 已经被排序，则仅考虑迭代 4，5． 迭代 4，5 访问的 数据个数分别为 2 和 1，按照访问的数据个数由少 到多排序，则迭代顺序为 5，4． 因此，分析完前两条 超边后，迭代顺序为 1，2，5，4． 同理分析第 3、4 条 超边的情况． 最终得到迭代顺序为 1，2，5，4，3， 如图 5( c) 所示． H_NRC_I 算法思路简单，实现起来比较容易， 其时间复杂度比较低，对时间开销要求较低的情况 表现较好． 2. 2. 2 H_BS_I 算法 H_BS_I 算法的思想与 H_BS_D 相同，H_BS_I 在时间局部性超图上通过回溯法由深层到浅层依次 对间接数组的值进行编号，从而实现迭代重排． 第 1 步 遍历间接数组，统计每个值对应的使 用该值的迭代次数及迭代序号，根据所得信息构建 时间局部性超图． 第 2 步 在第 1 步构建的超图上，任取一个未 被编号的超点，对该超点按顺序编号． 这里仍旧使 用数据重排算法 H_BS_D 中处理超点的方法． 第 3 步 按编号顺序对已编号的超点的子结点 进行下一轮的编号． 第 4 步 若仍有未编号的超点，则返回第 2 步． H_BS_I 算法跟 H_BS_D 算法相似，因此不再给 出伪码． 该算法的原理比较简单，其算法的时间复 杂度为 O( E + V) ． 3 实验方案及其结果 3. 1 实验方案 实验 使 用 的 计 算 机 配 置 如 下: CPU 为 Xeon 2. 8 GHz，一级 cache 的容量为 64 kB，二级 cache 的 容量为1 MB，cache 行为64 B，内存为2 GB． Linux 版 本为 Fedora 3，编译器版本为 GCC 3. 2. 2． 使用 Intel VTune Performance Analyzer 8. 0 测试 cache 及快表 ( translation lookaside buffer，TLB) 的性能． 该文针对非规则循环中一次迭代访问多个间接 数组的典型应用———流体力学 ZEUS--2D［15］进行实 验，其核心子程序 X2INTZC 包含了类似于图 1 的循 环． 实验中的迭代次数为 3 万次，每个数据为 8 bit 的双精度浮点型． 间接数组的值由循环变量的一个 线性函数获得，即每个间接数组的元素值与索引变 量值为一对一的映射关系． 3. 2 各个算法的效果比较 实验过程: 首先测试不使用任何重排算法以及 使用单个重排算法的运行时间; 然后给出数据重排 与迭代重排各种组合算法下程序的运行时间( 这两 种运行时间均不包括重排算法本身的时间开销) 以 及一级 cache、二级 cache 和 TLB 的命中率; 最后测 试各种重排算法本身的时间开销． 实验中所得数据 均为 5 次运行下的平均值． 图 6 给出使用单个重排算法时程序的运行时 间，其中包括不使用任何重排算法的情况，用 “NONE”表示． 由图可见，使用任何一种重排算法 程序的执行速度均有所改善，平均执行速度提高约 25. 4% ． 单独对数据重排来说，H_NRC_D 算法是最 好的，H_PFB_D 算法次之; 单独对迭代重排来说， ·1475·