·1476· 北京科技大学学报 第34卷 H_NRC_I算法是最好的. 实验还测试了各种组合方法优化后的各个程序 图7所示为数据重排算法与迭代重排算法组合 (其中也包括不使用重排算法、单独的数据重排算 下程序的运行时间，组合顺序为先使用数据重排算 法以及单独的迭代重排算法)运行时一级cache命 法然后使用迭代重排算法.可见，组合算法最好的 中率、二级cache命中率和TLB命中率，结果如图8 情况是数据重排使用H_PFB_D算法、迭代重排使 所示，程序命名采用“数据重排算法+迭代重排算 用H_NRCI算法，而不是图6中最优数据重排算法 法”的方式. H_NRC_D与最优迭代重排算法H_NRC_I的组合. 从图中可以看到，使用组合算法之后，一级 这就说明，数据重排与迭代重排的效果不能简单叠 cache、二级cache及TLB的命中率均有不同程度 加.组合算法中，H_NRC_D与HNC_I组合算法 的改善.在未使用任何重排算法的情况下，一级 的执行速度略低于最优组合算法 cache和二级cache平均命中率大约为75.1%和 30 90.6%;当经过最优组合算法之后，一级cache和 25 二级cache命中率达到91.7%和96.5%.命中率 20 最高的情况为数据重排使用H_PFB_D算法以及 迭代重排使用H_NRC_I算法，与图7中最优组合 10 方案一致.可见，当cache性能较高时，程序的局 部性得以保证，非规则应用的执行效率会相应地 NONE H NRCD H_BS_D H PFB_D H_NRC_I H BS. 提高.另外，H_P℉B_D算法中按照结点度排序起 重排算法 了很重要的作用.而使用H_NRC_I算法进行的迭 图6各个重排算法的运行时间 代重排对于数据数组大小与实际运算数据量相差 Fig.6 Runtime of each reordering algorithm 不多的情况下，效果非常好 同时我们看到，某些基于超图的数据重排算 35m 法尽管单独使用时性能没有明显优势，但当与基 30 H_NRC_D回HBSD☒HPFB_D 于超图的迭代重排算法进行组合时，性能明显提 20 高.如数据重排算法H_PFB_D算法，从图6可以 15 看出，单独使用H_PFB_D算法比单独使用H_ 10 NRC_D算法的时间开销高出约1倍；而从图7和 5 图8可知，当与迭代重排算法进行组合时，数据重 H_NRC_I H_BS_I 排算法H_PFB_D比H_NRC_D在执行速度和 重排算法 cache命中率方面均具有明显优势.可见，数据重 图7各种组合算法的运行时间 排算法H_PFB_D只有与迭代重排算法相结合才 Fig.7 Runtime of each combined algorithm 能起到较好的优化效果 100 ☑一级cuche 图“级cache TLB 70 H_NRC_D+NONE H_NRC_D+H_NRC_I H_BS_D+NONE H_NRC_D+H_BS_I H_BS_D+H_NRC_I H_PFB_D+NONE H._BS_D+H_BS_l H_PFB_D+H_NRC_I H_PFB_D+H_BS_I NONE+H_NRC_I NONE+NONE NONE+H_BS_ 重排算法 图8优化后的cache性能 Fig.8 Optimized cache performance北 京 科 技 大 学 学 报 第 34 卷 H_NRC_I算法是最好的． 图 7 所示为数据重排算法与迭代重排算法组合 下程序的运行时间，组合顺序为先使用数据重排算 法然后使用迭代重排算法． 可见，组合算法最好的 情况是数据重排使用 H_PFB_D 算法、迭代重排使 用 H_NRC_I 算法，而不是图 6 中最优数据重排算法 H_NRC_D 与最优迭代重排算法 H_NRC_I 的组合． 这就说明，数据重排与迭代重排的效果不能简单叠 加． 组合算法中，H_NRC_D 与 H_NRC_I 组合算法 的执行速度略低于最优组合算法． 图 6 各个重排算法的运行时间 Fig． 6 Runtime of each reordering algorithm 图 7 各种组合算法的运行时间 Fig． 7 Runtime of each combined algorithm 实验还测试了各种组合方法优化后的各个程序 ( 其中也包括不使用重排算法、单独的数据重排算 法以及单独的迭代重排算法) 运行时一级 cache 命 中率、二级 cache 命中率和 TLB 命中率，结果如图 8 所示，程序命名采用“数据重排算法 + 迭代重排算 法”的方式． 从图中 可 以 看 到，使用组合算法之后，一 级 cache、二级 cache 及 TLB 的命中率均有不同程度 的改善． 在未使用任何重排算法的情况下，一级 cache 和二级 cache 平均命中率 大 约 为 75. 1% 和 90. 6% ; 当经过最优组合算法之后，一级 cache 和 二级 cache 命中率达到 91. 7% 和 96. 5% ． 命中率 最高的情况为数据重排使用 H_PFB_D 算法以及 迭代重排使用 H_NRC_I 算法，与图 7 中最优组合 方案一致． 可见，当 cache 性能较高时，程序的局 部性得以保证，非规则应用的执行效率会相应地 提高． 另外，H_PFB_D 算法中按照结点度排序起 了很重要的作用． 而使用 H_NRC_I 算法进行的迭 代重排对于数据数组大小与实际运算数据量相差 不多的情况下，效果非常好． 同时我们看到，某些基于超图的数据重排算 法尽管单独使用时性能没有明显优势，但当与基 于超图的迭代重排算法进行组合时，性能明显提 高． 如数据重排算法 H_PFB_D 算法，从图 6 可以 看出，单 独 使 用 H _ PFB _D 算法比单独使用 H _ NRC_D 算法的时间开销高出约 1 倍; 而从图 7 和 图 8 可知，当与迭代重排算法进行组合时，数据重 排算法 H _ PFB _D 比 H _NRC _D 在 执 行 速 度 和 cache 命中率方面均具有明显优势． 可见，数据重 排算法 H_PFB_D 只有与迭代重排算法相结合才 能起到较好的优化效果． 图 8 优化后的 cache 性能 Fig． 8 Optimized cache performance ·1476·