基于超图的非规则应用局部性优化

D0L:10.13374折.issn1001-053x.2012.12.016 第34卷第12期 北京科技大学学。报 Vol.34 No.12 2012年12月 Journal of University of Science and Technology Beijing Dec.2012 基于超图的非规则应用局部性优化 曹 倩”四刘立红)颜斌》 陈洪菊) 1)北京工商大学计算机与信息工程学院，北京1000482)军械工程学院基础部，石家庄050003 3)北京科技大学计算机与通信工程学院，北京100083 ☒通信作者，E-mail:caoqian5@gmail.com 摘要针对非规则循环应用中存在的一次迭代访问多个间接数组的问题，给出了超图数组的形式化描述，提出了三种基于 超图的数据重排算法，即基于超图的非重复编码数据重排算法、基于超图的回溯搜索数据重排算法和基于超图的先划分再回 溯数据重排算法，以及两种基于超图的迭代重排算法，即基于超图的非重复编码迭代重排算法和基于超图的回溯搜索迭代重 排算法.通过对典型的非规则应用实例一流体力学问题进行实验，表明单独的重排算法提高程序执行速度约25.4%.在最 好的数据重排与迭代重排的组合算法下，一级和二级高速缓存的平均命中率分别增加到91.7%和96.5%. 关键词数据局部性；高速缓冲存储器；重排：非规则：编译 分类号TP311.1 Hypergraph-based irregular application locality optimization CAO Qian”,IULi-hong,XIE Bin》,CHEN Hong” 1)School of Computer and Information Engineering,Beijing Technology and Business University,Beijing 100048,China 2)Department of Basic Courses,Ordnance Engineering College,Shijiazhuang 050003,China 3)School of Computer and Communication Engineering,University of Science and Technology Beijing,Beijing 100083,China Corresponding author,E-mail:caoqian5@gmail.com ABSTRACT Multiple indirection arrays often exist in one iteration,which is involved in irregular loop applications.A formal description of the hypergraph arrays was presented to solve this problem.Besides,three hypergraph-based data reordering algorithms (hypergraph-based non-repetitive coding data reordering algorithm,hypergraph-based backtracking search data reordering algorithm, and hypergraph-based partition first and then backtracking data reordering algorithm)and two hypergraph-based iteration reordering algorithms (hypergraph-based non-repetitive coding iteration reordering algorithm and hypergraph-based backtracking search iteration reordering algorithm)were put forward.Experiments were performed on computational fluid dynamics,which was a representative irregular application.It is indicated that data locality is improved by the single reordering algorithm,with the execution speed increas- ing by 25.4%.The combination of the data reordering algorithm and the iteration reordering algorithm demonstrates the best perform- ance,with the average hit rates of level-1 and level-2 cache reaching 91.7%and 96.5%,respectively. KEY WORDS data locality:cache memory:reordering:irregularity:compiling 非规则应用通常在编译时无法确定内存访问情 体力学.改善程序的局部性是提高非规则问题性能 况，其循环界限和数组引用下标不再是循环控制变 的关键因素之一-习 量的线性表达式.该类问题在程序中的一个主要体 重排技术作为改善程序局部性的重要手段之 现是对间接数组的访问，如AB],其最大特点 一，逐渐成为近年来的研究热点B-.所谓重排，是 为内存访问的非连续性.非规则问题在实际应用中 指在进行真正的计算之前，改变数据在内存中的存 普遍存在，如大规模油藏数值模拟、分子动力学和流 放顺序或者改变计算顺序，以提高数据的重用 收稿日期：20120203 基金项目：国家自然科学基金资助项目(61103124)：国家重点基础研究发展规划资助项目(2012CB821200,2012CB821206):北京工商大学青 年教师科研启动基金项目(QNJJ2011-37):北京市大学生科学研究与创业行动计划建设项目(PXM2012_014213000067)

第 34 卷 第 12 期 2012 年 12 月 北京科技大学学报 Journal of University of Science and Technology Beijing Vol． 34 No． 12 Dec． 2012 基于超图的非规则应用局部性优化 曹 倩1)  刘立红2) 颉 斌3) 陈洪菊1) 1) 北京工商大学计算机与信息工程学院，北京 100048 2) 军械工程学院基础部，石家庄 050003 3) 北京科技大学计算机与通信工程学院，北京 100083  通信作者，E-mail: caoqian5@ gmail． com 摘 要 针对非规则循环应用中存在的一次迭代访问多个间接数组的问题，给出了超图数组的形式化描述，提出了三种基于 超图的数据重排算法，即基于超图的非重复编码数据重排算法、基于超图的回溯搜索数据重排算法和基于超图的先划分再回 溯数据重排算法，以及两种基于超图的迭代重排算法，即基于超图的非重复编码迭代重排算法和基于超图的回溯搜索迭代重 排算法． 通过对典型的非规则应用实例———流体力学问题进行实验，表明单独的重排算法提高程序执行速度约 25. 4% ． 在最 好的数据重排与迭代重排的组合算法下，一级和二级高速缓存的平均命中率分别增加到 91. 7% 和 96. 5% ． 关键词 数据局部性; 高速缓冲存储器; 重排; 非规则; 编译 分类号 TP311. 1 Hypergraph-based irregular application locality optimization CAO Qian1)  ，LIU Li-hong2) ，XIE Bin3) ，CHEN Hong-ju1) 1) School of Computer and Information Engineering，Beijing Technology and Business University，Beijing 100048，China 2) Department of Basic Courses，Ordnance Engineering College，Shijiazhuang 050003，China 3) School of Computer and Communication Engineering，University of Science and Technology Beijing，Beijing 100083，China  Corresponding author，E-mail: caoqian5@ gmail． com ABSTRACT Multiple indirection arrays often exist in one iteration，which is involved in irregular loop applications． A formal description of the hypergraph arrays was presented to solve this problem． Besides，three hypergraph-based data reordering algorithms ( hypergraph-based non-repetitive coding data reordering algorithm，hypergraph-based backtracking search data reordering algorithm， and hypergraph-based partition first and then backtracking data reordering algorithm) and two hypergraph-based iteration reordering algorithms ( hypergraph-based non-repetitive coding iteration reordering algorithm and hypergraph-based backtracking search iteration reordering algorithm) were put forward． Experiments were performed on computational fluid dynamics，which was a representative irregular application． It is indicated that data locality is improved by the single reordering algorithm，with the execution speed increas￾ing by 25. 4% ． The combination of the data reordering algorithm and the iteration reordering algorithm demonstrates the best perform￾ance，with the average hit rates of level-1 and level-2 cache reaching 91. 7% and 96. 5% ，respectively． KEY WORDS data locality; cache memory; reordering; irregularity; compiling 收稿日期: 2012--02--03 基金项目: 国家自然科学基金资助项目( 61103124) ; 国家重点基础研究发展规划资助项目( 2012CB821200，2012CB821206) ; 北京工商大学青 年教师科研启动基金项目( QNJJ2011--37) ; 北京市大学生科学研究与创业行动计划建设项目( PXM2012_014213_000067) 非规则应用通常在编译时无法确定内存访问情 况，其循环界限和数组引用下标不再是循环控制变 量的线性表达式． 该类问题在程序中的一个主要体 现是对间接数组的访问，如 A［B［i］］，其最大特点 为内存访问的非连续性． 非规则问题在实际应用中 普遍存在，如大规模油藏数值模拟、分子动力学和流 体力学． 改善程序的局部性是提高非规则问题性能 的关键因素之一［1--2］． 重排技术作为改善程序局部性的重要手段之 一，逐渐成为近年来的研究热点［3--4］． 所谓重排，是 指在进行真正的计算之前，改变数据在内存中的存 放顺序或者改变计算顺序，以提高数据的重用 DOI:10.13374/j.issn1001-053x.2012.12.016

·1470· 北京科技大学学 报 第34卷 性B-).重排主要包括数据重排和迭代重排（又称 超图中，每个椭圆代表一条超边，即一次迭代，每个 计算重排).数据重排指把迭代所访问的数据尽量 数据代表一个超点，即间接数组中的值：而时间局部 排列到一起，提高程序的空间局部性，以便于对数据 性超图以一个数据代表一条超边，一次迭代代表一 的连续访问：迭代重排是指把使用相同数据的迭代 个超点. 排列到一起，使得之前迭代中访问的全部或大部分 本文针对非规则循环应用中一次迭代访问多个 数据都在后面的迭代中可以重用，以提高数据的时 间接数组的问题进行研究，提出了基于超图的解决 间局部性 方案：首先对超图数组的生成过程进行形式化描述， 利用图划分技术进行重排转换通常可以改善非 在此基础上提出了三种基于超图的数据重排算 规则应用的程序效率-0.然而，在实际的应用中， 法—基于超图的非重复编码数据重排 如流体力学应用和分子动力学应用，经常出现一次 (hypergraph-based non-repetitive coding data reorde- 迭代涉及多于两个间接数组的情况.以流体力学应 ring,H_NRC_D)算法、基于超图的回溯搜索数据重 用ZEUS-2D中的一段代码为例，如图1所示，其中 (hypergraph-based backtracking search data reorde- X、Y和Z为实际要访问的数据数组，A、B、C和D为 ring,H_BS_D)算法和基于超图的先划分再回溯数 间接数组.假设其内层循环的访存情况如图2所 据重排(hypergraph-based partition first and then 示.可见，虽然循环变量i是连续的，但实际访问的 backtracking data reordering,H_PFB_D)算法，以及 数据却不连续.为了提高程序的局部性，可以使用 两种基于超图的迭代重排算法一基于超图的非重 重排技术.若采用普通图进行数据或迭代重排，由 复编码迭代重排(hypergraph_based non-repetitive 于图1所示的循环每次迭代均访问到A、B、C和D coding iteration reordering,H_NRC_I)算法、基于超 四个间接数组，则会导致图的一条边连接四个顶点， 图的回溯搜索迭代重排(hypergraph-based back- 因此采用普通图无法实现 tracking search iteration reordering,H_BS_I)算法，解 Do 50t=1,n_step 决了图1所示的非规则循环应用中涉及多个间接数 Do 50i=1,N 组的问题. S1:X(B(i))=X(A()) 本文先介绍了超图最常用的存储格式，给出了 S2:X(D(i))=X(C()) S3:Y(A())=Y(A(i))+Z(C(i))-X(A()) 超图的生成算法：然后提出了基于超图的三种数据 S4:Y(D(i)=Y(C(i))-X(C()) 重排算法及两种迭代重排算法，给出了各自的适用 5 CONTINUE 范围及算法的复杂度：最后进行了实验测试，证明了 50 CONTINUE 算法的有效性. 图1简化的流体力学代码 Fig.1 Simplified fluid dynamic code 1 超图的形式化描述 本节首先介绍了最常见的超图存储格式，然后 037 对一次迭代访问多个间接数组的问题进行抽象，分 72 D 3 836 析其迭代过程，给出了超图的形式化描述及超图数 xa be d e f名hi■ 组的生成过程，为后面利用超图进行数据重排和迭 0123456789 代重排提供了理论依据. y a h cd e f g hij 0123456789 1.1超图的存储格式 za b e d e f g h ij 压缩稀疏行(compressed sparse row,CSR)表示 0123456789 法是超图数据结构最常用的压缩存储格式.CSR方 图2非规则问题中间接引用 Fig.2 Indirection access in the irregular application 法表示超图结构的原理如下：对于一个具有n个超 点和m个超边的超图，可以用数组xadj和adjncy来 为此，本文引入超图1-的思想以解决更为普 表示.其中，数组xad用来存储结点的信息，数组 遍的问题.超图与普通图的最大区别在于一条超图 adjncy用来存储邻接结点的信息.即对于超点i,其 的边可以包含多个顶点，因此可以直观地描述非规 邻接表存储在数组adjncy的一段连续的空间中，数 则应用中一次迭代访问多个间接数组的问题.超图 组xadj用来指向其起点与终点，具体表示为adjncy 的顶点和边分别被称作超点和超边.超图可以分为 [xadj [i]],adjncy [xadj]+1],,adjncy [xadj [i+ 空间局部性超图和时间局部性超图.在空间局部性 1]-1].与邻接表、邻接矩阵表等存储格式相比，压

北 京 科 技 大 学 学 报 第 34 卷 性［5--7］． 重排主要包括数据重排和迭代重排( 又称 计算重排) ． 数据重排指把迭代所访问的数据尽量 排列到一起，提高程序的空间局部性，以便于对数据 的连续访问; 迭代重排是指把使用相同数据的迭代 排列到一起，使得之前迭代中访问的全部或大部分 数据都在后面的迭代中可以重用，以提高数据的时 间局部性． 利用图划分技术进行重排转换通常可以改善非 规则应用的程序效率［8--10］． 然而，在实际的应用中， 如流体力学应用和分子动力学应用，经常出现一次 迭代涉及多于两个间接数组的情况． 以流体力学应 用 ZEUS--2D 中的一段代码为例，如图 1 所示，其中 X、Y 和 Z 为实际要访问的数据数组，A、B、C 和 D 为 间接数组． 假设其内层循环的访存情况如图 2 所 示． 可见，虽然循环变量 i 是连续的，但实际访问的 数据却不连续． 为了提高程序的局部性，可以使用 重排技术． 若采用普通图进行数据或迭代重排，由 于图 1 所示的循环每次迭代均访问到 A、B、C 和 D 四个间接数组，则会导致图的一条边连接四个顶点， 因此采用普通图无法实现． Do 50 t = 1，n_step Do 50 i = 1，N S1: X( B( i) ) = X( A( i) ) S2: X( D( i) ) = X( C( i) ) S3: Y( A( i) ) = Y( A( i) ) + Z( C( i) ) － X( A( i) ) S4: Y( D( i) = Y( C( i) ) － X( C( i) ) 5 CONTINUE 50 CONTINUE 图 1 简化的流体力学代码 Fig． 1 Simplified fluid dynamic code 图 2 非规则问题中间接引用 Fig． 2 Indirection access in the irregular application 为此，本文引入超图［11--12］的思想以解决更为普 遍的问题． 超图与普通图的最大区别在于一条超图 的边可以包含多个顶点，因此可以直观地描述非规 则应用中一次迭代访问多个间接数组的问题． 超图 的顶点和边分别被称作超点和超边． 超图可以分为 空间局部性超图和时间局部性超图． 在空间局部性 超图中，每个椭圆代表一条超边，即一次迭代，每个 数据代表一个超点，即间接数组中的值; 而时间局部 性超图以一个数据代表一条超边，一次迭代代表一 个超点． 本文针对非规则循环应用中一次迭代访问多个 间接数组的问题进行研究，提出了基于超图的解决 方案: 首先对超图数组的生成过程进行形式化描述， 在此基础上提出了三种基于超图的数据重排算 法———基于超图的非重 复 编 码 数 据 重 排 ( hypergraph-based non-repetitive coding data reorde￾ring，H_NRC_D) 算法、基于超图的回溯搜索数据重 排( hypergraph-based backtracking search data reorde￾ring，H_BS_D) 算法和基于超图的先划分再回溯数 据 重 排 ( hypergraph-based partition first and then backtracking data reordering，H_PFB_D) 算法，以及 两种基于超图的迭代重排算法———基于超图的非重 复编 码 迭 代 重 排 ( hypergraph _ based non-repetitive coding iteration reordering，H_NRC_I) 算法、基于超 图的 回 溯 搜 索 迭 代 重 排 ( hypergraph-based back￾tracking search iteration reordering，H_BS_I) 算法，解 决了图 1 所示的非规则循环应用中涉及多个间接数 组的问题． 本文先介绍了超图最常用的存储格式，给出了 超图的生成算法; 然后提出了基于超图的三种数据 重排算法及两种迭代重排算法，给出了各自的适用 范围及算法的复杂度; 最后进行了实验测试，证明了 算法的有效性． 1 超图的形式化描述 本节首先介绍了最常见的超图存储格式，然后 对一次迭代访问多个间接数组的问题进行抽象，分 析其迭代过程，给出了超图的形式化描述及超图数 组的生成过程，为后面利用超图进行数据重排和迭 代重排提供了理论依据． 1. 1 超图的存储格式 压缩稀疏行( compressed sparse row，CSR) 表示 法是超图数据结构最常用的压缩存储格式． CSR 方 法表示超图结构的原理如下: 对于一个具有 n 个超 点和 m 个超边的超图，可以用数组 xadj 和 adjncy 来 表示． 其中，数组 xadj 用来存储结点的信息，数组 adjncy 用来存储邻接结点的信息． 即对于超点 i，其 邻接表存储在数组 adjncy 的一段连续的空间中，数 组 xadj 用来指向其起点与终点，具体表示为 adjncy ［xadj［i］］，adjncy［xadj［i］+ 1］，…，adjncy［xadj［i + 1］－ 1］． 与邻接表、邻接矩阵表等存储格式相比，压 ·1470·

第12期 曹倩等：基于超图的非规则应用局部性优化 ·1471· 缩稀疏行存储表示法的最大优点在于避免使用指针 [base (Y)dtsize*X:]U... (1) 链表，从而消除了邻接关系的检索及维护工作，同时 其中，dtsize表示访问的数据类型的大小，base(Y,) 有效地节约了存储空间. 为Y,的基地址.则对于第i次迭代，访问的地址空 1.2超图的形式化描述 间Add山r(i)为 为了便于进行超图形式化描述，对实际问题进 Addr(i)=(base (Y,)+dtsize*X [i]}U 行抽象，得到一次迭代访问多个间接数组的典型代 {base(Y)+dtsize*X2 [i])U 码，如图3所示.在for循环的每次迭代中，访问了 (base (Y)dtsize*X i])U... (2) X,]X2)和X,]等多个间接数组.下面以此为 为了便于说明问题，作如下假设： 例，逐步推导超图数组xadj和adjncy的相应值，为 (1)设cmt()表示X,],X2],X],…这 基于超图的重排算法的提出提供条件. 些元素中不相同的数据的个数，即第i次迭代访问 到的不同数据的个数； for(i=0:i<=n:i++){ y1K,],Y2],yK] (2)设val[0],val[1],val,[2],…, 2K,]],y22],y2K] val,[cnt(i)-l]分别表示第i次迭代所访问的 YK]],YK2],Y,X3],…共cmt(i) Y,DX,Gi]].Y,DX2 G]].Y.DX;]] 个数据的值，即第i次迭代中数组adincy的值. 则对于数据数组Y1,第i次迭代访问的数据空 图3抽象的一次迭代访问多个间接数组应用 间Data(i)为 Fig.3 Abstract application of multiple indirection arrays in one iteration Data (i)=val,0]Uval,[1]U 初始条件下，数组adjncy为空.由于数组xadj val,]+.+val,[ent (i)-1].(3) 的第0个元素存储的是数组adjncy的第0个元素的 则cnt(O)为第0次迭代访问到的数组adjncy 索引，所以在初始条件下，xadD]=0. 的元素个数，其具体的值分别表示为vl。(0), 首先分析数据数组Y,对于第0次迭代，访问 val(1),val(2),,val(cnt(0)-1).同理，对于 的地址空间Addr(O)为 i=l,2,…,n,得到其具体的xadj和adjncy数组元 Addr(0)={base (Y)+dtsize*X]U 素.至此，得到了关于数据数组Y的xadj和adjncy {base(Y)dtsize*X2 ]U 的数组元素值，见表1. 表1超图数组的描述 Table 1 Description of hypergraph arrays 索引，i xadj adjncy index 0 valo[] 0 0 valo[] 1 valo [ent (0)-1] cmt(0)-1 ent(0) val,] cnt(0） val,[ cnt(0)+1 val,[ent(1)-1] cnt(0)+cmt(1)-1 ; ent(n-1) val [0] ent(0)+cnt(1) val,[I] cnt(0)+cnt(1)+1 val,[ent (n)-1] cnt(o）+cnt(1)+…+cnt(n)-1 n+1 cnt(n) 同理，可以得到其他数据数组Y2,Y,…,Yn关 虑到整个程序的超图表示，给出超图生成算法，如算 于数组xadj和adjncy的相应值，在此不再累述.考 法1所示

第 12 期 曹 倩等: 基于超图的非规则应用局部性优化 缩稀疏行存储表示法的最大优点在于避免使用指针 链表，从而消除了邻接关系的检索及维护工作，同时 有效地节约了存储空间． 1. 2 超图的形式化描述 为了便于进行超图形式化描述，对实际问题进 行抽象，得到一次迭代访问多个间接数组的典型代 码，如图 3 所示． 在 for 循环的每次迭代中，访问了 X1［i］、X2［i］和 X3［i］等多个间接数组． 下面以此为 例，逐步推导超图数组 xadj 和 adjncy 的相应值，为 基于超图的重排算法的提出提供条件． for ( i = 0; i ＜ = n; i + + ) { Y1［X1［i］］，Y1［X2［i］］，Y1［X3［i］］ Y2［X1［i］］，Y2［X2［i］］，Y2［X3［i］］  Yn［X1［i］］，Yn［X2［i］］，Yn［X3［i］］ } 图 3 抽象的一次迭代访问多个间接数组应用 Fig． 3 Abstract application of multiple indirection arrays in one iteration 初始条件下，数组 adjncy 为空． 由于数组 xadj 的第 0 个元素存储的是数组 adjncy 的第 0 个元素的 索引，所以在初始条件下，xadj［0］= 0． 首先分析数据数组 Y1，对于第 0 次迭代，访问 的地址空间 Addr( 0) 为 Addr( 0) = { base( Y1 ) + dtsize* X1［0］} ∪ { base( Y1 ) + dtsize* X2［0］} ∪ { base( Y1 ) + dtsize* X3［0］} ∪… ( 1) 其中，dtsize 表示访问的数据类型的大小，base( Y1 ) 为 Y1的基地址． 则对于第 i 次迭代，访问的地址空 间 Addr( i) 为 Addr( i) = { base( Y1 ) + dtsize* X1［i］} ∪ { base( Y1 ) + dtsize* X2［i］} ∪ { base( Y1 ) + dtsize* X3［i］} ∪… ( 2) 为了便于说明问题，作如下假设: ( 1) 设 cnt( i) 表示 X1［i］，X2［i］，X3［i］，…这 些元素中不相同的数据的个数，即第 i 次迭代访问 到的不同数据的个数; ( 2 ) 设 vali ［0 ］，vali ［1 ］，vali ［2 ］，…， vali ［cnt( i) － 1］分 别 表 示 第 i 次 迭 代 所 访 问 的 Y1［X1［i］］，Y1［X2［i］］，Y1［X3［i］］，…共 cnt( i) 个数据的值，即第 i 次迭代中数组 adjncy 的值． 则对于数据数组 Y1，第 i 次迭代访问的数据空 间 Data( i) 为 Data( i) = vali ［0］∪vali ［1］∪ vali ［2］+ … + vali ［cnt( i) － 1］． ( 3) 则 cnt( 0) 为第 0 次迭代访问到的数组 adjncy 的元 素 个 数，其具体的值分别表示为 val0 ( 0 ) ， val0 ( 1) ，val0 ( 2) ，…，val0 ( cnt( 0) － 1) ． 同理，对于 i = 1，2，…，n，得到其具体的 xadj 和 adjncy 数组元 素． 至此，得到了关于数据数组 Y1的 xadj 和 adjncy 的数组元素值，见表 1． 表 1 超图数组的描述 Table 1 Description of hypergraph arrays 索引，i xadj adjncy index 0 val0［0］ 0 0 val0［1］ 1   val0［cnt( 0) － 1］ cnt( 0) － 1 cnt( 0) val1［0］ cnt( 0) 1 val1［1］ cnt( 0) + 1   val1［cnt( 1) － 1］ cnt( 0) + cnt( 1) － 1     cnt( n － 1) valn［0］ cnt( 0) + cnt( 1) n valn［1］ cnt( 0) + cnt( 1) + 1   valn［cnt( n) － 1］ cnt( 0) + cnt( 1) + … + cnt( n) － 1 n + 1 cnt( n) — — 同理，可以得到其他数据数组 Y2，Y3，…，Yn关 于数组 xadj 和 adjncy 的相应值，在此不再累述． 考 虑到整个程序的超图表示，给出超图生成算法，如算 法 1 所示． ·1471·

·1472· 北京科技大学学报 第34卷 算法1超图生成算法 便于描述算法的复杂度，在下文中，以V代表超点 输入：数组X1],X2],X3],…及数组 数，以E代表超边数 YG],Y2],Y3],: 2.1基于超图的数据重排算法 输出：超图数组xadj和adjncy; 该部分提出了三种基于超图的数据重排算法： 步骤： HNRC_D、H_BS_D和H_PFB_D.H_NRC_D算法 11第1步：初始化 基于遍历的思想，适用于对时间开销要求比较严格 给数组的0号元素赋值：xadj 0]=0: 的情况：HPB_D算法应用多级图划分的思想，原 给变量num赋初值：num=0; 理相对复杂，适用于对时间开销要求不高的场合； cnt_dataarray=数据数组的个数； HBS_D算法的时间开销介于前两者之间 11第2步：依次遍历各数据数组 2.1.1H_NRC_D算法 for(j=0;j<cnt_dataarray;j++) H_NRC_D算法来源于CPACK算法，即采用 { 遍历的思想访问空间局部性超图的各个超边，当遇 for(i=0;i<=n;i++)/对于数据数组Y 到不同的超点时依次进行编码.与CPACK算法不 同的是，对于特定的每一条超边，H_NRC_D算法按 /1第3步：统计本次迭代中X],X2], 照结点度由小到大的顺序依次编码.对于具有相同 X3],…中不同的值 度的结点，其编码顺序按照程序本身的顺序即可. cnt(i)=get_Cnt(j,i): 之所以按照度的升序对结点进行遍历，主要在于考 /将这cnt(i)个值，如dt(0),dt(1), 虑到对于度较大的结点，很有可能在后面的迭代中 …,dt(cnt(i)-l),存入数组val中 被再次访问，因此访问延后可能会提高程序的局部 for(I=0;I<ent(i);1++) 性.HNRC_D算法的大致过程如下. val(1)dt(1) 第1步按照程序本身的迭代顺序遍历间接数 xadE+1]=cmt]:/为数组xad赋值 组，对于特定迭代内访问到的数据，按照结点度的升 num+=xadj i]; 序顺序进行编号.编号从0开始，依次递增.每遇到 I/第4步：为数组adjncy赋值 一个与之前不相同的值，就对这个值进行编号. for(k =0;k<ent(i);++) 第2步遇到己经编号的值则跳过继续向下 adjncy[+num]=val(k);/为数组 遍历. adjncy赋值 第3步将原间接数组的访问顺序替换为相应 } 的编号顺序，即实现数据的重排. 经过上述三步之后，间接数组中很多不连续的 该算法大致分为以下几步 值被替换为连续的值，间接数组的空间局部性得到 第1步初始化.主要是对一些变量及数组 了改善，从而使得数据在缓存内尽量被重用. xad等的初始化. 以图4(a)所示空间局部性超图为例来直观地 第2步依次遍历数据数组Y,直到整个for循 说明该算法，其中每个闭合的曲线代表一次迭代，闭 环遍历结束 合区域内的数据代表该迭代访问到的数据. 第3步对于数据数组Y,统计其每次迭代中 H_NRC_D算法的具体执行过程为：在第1次迭代过 访问的不同数据，存入数组vl中，并记录不同数据 程中，对访问到的数据11,2,8,4按照度由小到大 的个数.依次遍历数组val,并将其赋值给数组xadj. 排列为11,2,4,8，并依次编号为0、1、2和3；然后 第4步为数组adjncy赋值，然后循环遍历下 对第2次迭代访问到的数据8,3,5,7按照度由小 一个数据数组，直到所有的数据数组遍历结束，超图 到大进行排序，结果为3,8,5,7，由于数据8己经 构建完成 在第1次迭代内编号，所以只对3,5,7进行编号， 依次为4、5和6；同理对第3次、第4次迭代访问到 2基于超图的重排算法 的数据依次进行编号.最终编号结果如图4(b)所 本节提出了三种基于超图的数据重排算法及两 示，其中圆圈内的数据代表经过H_NRC_D算法之 种基于超图的迭代重排算法，这些重排算法主要针 后的编号.至此，间接数组中的很多不连续的值被 对的是双重间接数组（即AB]])的情况.为了 替换成了连续的值

北 京 科 技 大 学 学 报 第 34 卷 算法 1 超图生成算法． 输入: 数组 X1［i］，X2［i］，X3［i］，…及数组 Y1［i］，Y2［i］，Y3［i］，…; 输出: 超图数组 xadj 和 adjncy; 步骤: / /第 1 步: 初始化 给数组的 0 号元素赋值: xadj［0］= 0; 给变量 num 赋初值: num = 0; cnt_dataarray = 数据数组的个数; / /第 2 步: 依次遍历各数据数组 for( j = 0; j ＜ cnt_dataarray; j + + ) { for( i =0; i ＜ =n; i + +) / /对于数据数组 Yj { / /第 3 步: 统计本次迭代中 X1［i］，X2［i］， X3［i］，…中不同的值 cnt( i) = get_Cnt( j，i) ; / /将这 cnt( i) 个值，如 dt( 0) ，dt( 1) ， …，dt( cnt( i) － 1) ，存入数组 val 中 for( l = 0; l ＜ cnt( i) ; l + + ) val( l) = dt( l) ; xadj［i +1］=cnt［i］; / /为数组 xadj 赋值 num + = xadj［i］; / /第 4 步: 为数组 adjncy 赋值 for( k = 0; k ＜ cnt( i) ; k + + ) adjncy［k + num］= val( k) ; / /为数组 adjncy 赋值 } } 该算法大致分为以下几步． 第 1 步 初始化． 主要是对一些变量及数组 xadj 等的初始化． 第 2 步 依次遍历数据数组 Yj ，直到整个 for 循 环遍历结束． 第 3 步 对于数据数组 Yj ，统计其每次迭代中 访问的不同数据，存入数组 val 中，并记录不同数据 的个数． 依次遍历数组 val，并将其赋值给数组 xadj． 第 4 步 为数组 adjncy 赋值，然后循环遍历下 一个数据数组，直到所有的数据数组遍历结束，超图 构建完成． 2 基于超图的重排算法 本节提出了三种基于超图的数据重排算法及两 种基于超图的迭代重排算法，这些重排算法主要针 对的是双重间接数组( 即 A［B［i］］) 的情况． 为了 便于描述算法的复杂度，在下文中，以 V 代表超点 数，以 E 代表超边数． 2. 1 基于超图的数据重排算法 该部分提出了三种基于超图的数据重排算法: H_NRC_D、H_BS_D 和 H_PFB_D． H_NRC_D 算法 基于遍历的思想，适用于对时间开销要求比较严格 的情况; H_PFB_D 算法应用多级图划分的思想，原 理相对复杂，适用于对时间开销要求不高的场合; H_BS_D算法的时间开销介于前两者之间． 2. 1. 1 H_NRC_D 算法 H_NRC_D 算法来源于 CPACK 算法［13］，即采用 遍历的思想访问空间局部性超图的各个超边，当遇 到不同的超点时依次进行编码． 与 CPACK 算法不 同的是，对于特定的每一条超边，H_NRC_D 算法按 照结点度由小到大的顺序依次编码． 对于具有相同 度的结点，其编码顺序按照程序本身的顺序即可． 之所以按照度的升序对结点进行遍历，主要在于考 虑到对于度较大的结点，很有可能在后面的迭代中 被再次访问，因此访问延后可能会提高程序的局部 性． H_NRC_D 算法的大致过程如下． 第 1 步 按照程序本身的迭代顺序遍历间接数 组，对于特定迭代内访问到的数据，按照结点度的升 序顺序进行编号． 编号从0 开始，依次递增． 每遇到 一个与之前不相同的值，就对这个值进行编号． 第 2 步 遇到已经编号的值则跳过继续向下 遍历． 第 3 步 将原间接数组的访问顺序替换为相应 的编号顺序，即实现数据的重排． 经过上述三步之后，间接数组中很多不连续的 值被替换为连续的值，间接数组的空间局部性得到 了改善，从而使得数据在缓存内尽量被重用． 以图 4( a) 所示空间局部性超图为例来直观地 说明该算法，其中每个闭合的曲线代表一次迭代，闭 合区 域 内 的 数 据 代 表 该 迭 代 访 问 到 的 数 据． H_NRC_D算法的具体执行过程为: 在第 1 次迭代过 程中，对访问到的数据 11，2，8，4 按照度由小到大 排列为 11，2，4，8，并依次编号为 0、1、2 和 3; 然后 对第 2 次迭代访问到的数据 8，3，5，7 按照度由小 到大进行排序，结果为 3，8，5，7，由于数据 8 已经 在第 1 次迭代内编号，所以只对 3，5，7 进行编号， 依次为 4、5 和 6; 同理对第 3 次、第 4 次迭代访问到 的数据依次进行编号． 最终编号结果如图 4( b) 所 示，其中圆圈内的数据代表经过 H_NRC_D 算法之 后的编号． 至此，间接数组中的很多不连续的值被 替换成了连续的值． ·1472·

第12期 曹倩等：基于超图的非规则应用局部性优化 ·1473· (a) 11 11(0) 3 42) 第1条超边 第2条超边 第1条超边 第2条超边 9 9 7)13(8 5 9 第3条超边 第4条超边 第3条超边 第4条超边 12(10 (1 10(12) 图4HNRC_D算法实例.(a)原始的空间局部性超图：(b)应用H_NRC_D算法后 Fig.4 An example of H_NRC_D algorithm:(a)original spatial locality hypergraph:(b)situation of H_NRC_D algorithm HNRC_D算法原理非常简单，仅需要移动超 Move to child;I/移动到子结点 图中的超点即可.在最坏的情况下，需要将所有超 点均进行一次移动，因此H_NRC_D算法的复杂度 else if(stack is empty)I/若栈为空 为0()，相对来说比较低，特别是当迭代次数较少 return 0; 时，其优势更为明显. backtrack to the stack top;/I回溯到栈顶 2.1.2HBS_D算法 } HBS_D算法基于图论中比较常用的回溯搜索 算法.其特点是：每次搜索指定点，并将其所有未访 问过的子结点依次加入到搜索队列，循环搜索直到 首先，任取一个未被编号的超点，对该超点按顺 队列为空.然后通过回潮法由深层到浅层依次对间 序编号. 接数组的值进行编号.对空间局部性超图进行分 其次，对该超点的子结点依次按顺序编号.由 析，得到HBS_D算法如算法2所示. 于一条超边中有多个超点，其中可能存在不与其他 算法2基于超图的回溯搜索数据重排算法. 超边相连的超点，而普通图则不存在这种问题.本 输入：空间局部性超图G: 文在编号时，对一条超边中的所有超点采用全部按 输出：经过H_BS_D重排算法后的数据访问 顺序编号的原则，即遍历到一条超边，就把该超边中 顺序； 的所有超点都进行编号，以确保不会漏掉任何一个 步骤： 超点. HBS_D(G){/基于超图的回溯搜索数据重排 再次，通过回溯法对还未编号的超点进行下一 算法 轮的编号. current=begin_node in graph G;I/开始结点作 最后，若仍有未编号的超点，则返回第1步 为当前结点 执行. while(current not the last){/若当前结点不是 H_BS_D算法的原理比较简单，该算法的时间 最后结点 复杂度表示为O(E+) visit current;/访问当前结点 2.1.3H_PFB_D算法 visited[current]=true;I/标志当前结点己 该算法将超图划分技术与回溯搜索算法相结 被访问 合，先借助现有的超图划分方法对空间局部性超 for child current-next;child!=-1; 图进行划分，再针对划分的每一个图利用回溯搜索 child=child→next) 算法对其进行数据重排，具体过程如算法3所示. 算法3基于超图的先划分再回溯数据重排 if(visited[child]==false)I/若子结点还 算法. 未被访问 输入：空间局部性超图G: 输出：经过HP℉BD算法重排算法后的数据 push current;I/将当前结点入栈 访问顺序：

第 12 期 曹 倩等: 基于超图的非规则应用局部性优化 图 4 H_NRC_D 算法实例． ( a) 原始的空间局部性超图; ( b) 应用 H_NRC_D 算法后 Fig． 4 An example of H_NRC_D algorithm: ( a) original spatial locality hypergraph; ( b) situation of H_NRC_D algorithm H_NRC_D 算法原理非常简单，仅需要移动超 图中的超点即可． 在最坏的情况下，需要将所有超 点均进行一次移动，因此 H_NRC_D 算法的复杂度 为 O( V) ，相对来说比较低，特别是当迭代次数较少 时，其优势更为明显． 2. 1. 2 H_BS_D 算法 H_BS_D 算法基于图论中比较常用的回溯搜索 算法． 其特点是: 每次搜索指定点，并将其所有未访 问过的子结点依次加入到搜索队列，循环搜索直到 队列为空． 然后通过回溯法由深层到浅层依次对间 接数组的值进行编号． 对空间局部性超图进行分 析，得到 H_BS_D 算法如算法 2 所示． 算法 2 基于超图的回溯搜索数据重排算法． 输入: 空间局部性超图 G; 输出: 经过 H_BS _D 重排算法后的数据访问 顺序; 步骤: H_BS_D( G) { / /基于超图的回溯搜索数据重排 算法 current = begin_node in graph G; / /开始结点作 为当前结点 while( current not the last) { / /若当前结点不是 最后结点 visit current; / /访问当前结点 visited［current］= true; / /标志当前结点已 被访问 for ( child = current → next; child! = － 1; child = child→next) { if( visited［child］= = false) / /若子结点还 未被访问 { push current; / /将当前结点入栈 Move to child; / /移动到子结点 } else if ( stack is empty) / /若栈为空 return 0; backtrack to the stack top; / /回溯到栈顶 } } } 首先，任取一个未被编号的超点，对该超点按顺 序编号． 其次，对该超点的子结点依次按顺序编号． 由 于一条超边中有多个超点，其中可能存在不与其他 超边相连的超点，而普通图则不存在这种问题． 本 文在编号时，对一条超边中的所有超点采用全部按 顺序编号的原则，即遍历到一条超边，就把该超边中 的所有超点都进行编号，以确保不会漏掉任何一个 超点． 再次，通过回溯法对还未编号的超点进行下一 轮的编号． 最后，若 仍 有 未 编 号 的 超 点，则 返 回 第 1 步 执行． H_BS_D 算法的原理比较简单，该算法的时间 复杂度表示为 O( E + V) ． 2. 1. 3 H_PFB_D 算法 该算法将超图划分技术与回溯搜索算法相结 合，先借助现有的超图划分方法［14］对空间局部性超 图进行划分，再针对划分的每一个图利用回溯搜索 算法对其进行数据重排，具体过程如算法 3 所示． 算法 3 基于超图的先划分再回溯数据重排 算法． 输入: 空间局部性超图 G; 输出: 经过 H_PFB_D 算法重排算法后的数据 访问顺序; ·1473·

·1474· 北京科技大学学报 第34卷 步骤： HP℉B_D算法将超边中的第1个点作为降维 HPFB_D(G){//基于超图的先划分再回溯数 点，而实际上超边中的超点无所谓顺序，任何一个超 据重排算法 点都可作为降维点，这个顺序是为了算法的方便而 order nodes according to degree;/结点按度 假定的.本文选用超边中的第1个点作为降维点的 排序： 原因是：预排序过程是全部按照每条超边的第1 while(Size_cacheLinenext) H_NRCI算法与H_NRC_D算法相似，其基本 思想为依次遍历时间局部性超图的超边，并将其包 if(visited[child]==false)I/若子结点还 含的超点进行排序，按照该顺序对迭代进行重排以 未被访问 提高程序的局部性.对于一个非规则应用，在不确 定其访存情况时，可以假设数据的访问是随机的 push current;I/将当前结点入栈 所以，一般来讲，对于一个访问多个数据的迭代，其 Move to child;II移动到子结点 数据重用性要高于一个仅访问很少个数据的迭代. } 因此，对于一个特定的超边，H_NRC_I算法按照超 else if(stack is empty)II若栈为空 点度由小到大进行排序，即将访问数据个数比较多 return 0; 的迭代延后，以提高数据重用性及cache性能. backtrack to the stack top;//回溯到栈顶 下面以图5所示的具体实例来说明该算法的执 行过程，假设初始的时间局部性超图如图5(a)所 } 示，其中圆圈内的数据代表迭代，闭合曲线代表迭代 访问到的数据，具体的数值由方框内的数据表示 该算法首先按照结点度进行排序，使得关联度 H_NRCI算法的具体执行过程如下. 高的点排在一起，以提高数据局部性，排序时通常按 第1步依次遍历时间局部性超图中的超边， 照每条超边中第1个超点的度进行.对于超边所连 统计每条超边包含的超点.具体到非规则应用，则 接的点的问题，需降维成普通图来处理，即把一条超 指依次统计非规则应用访问到的数据在哪些迭代 边中的N个超点看成第1个超点连接N-1个超 中被访问.例如，第1条超边包含了超点1和2，即 点.之后算法按照划分的结果采用回溯搜索算法对 数据1在第1、2次迭代中被访问：第2条超边包含 超点进行编号，根据编号重排数据 了超点2、4和5，即数据2在第2、4和5次迭代中

北 京 科 技 大 学 学 报 第 34 卷 步骤: H_PFB_D( G) { / /基于超图的先划分再回溯数 据重排算法 order nodes according to degree; / /结 点 按 度 排序; while( Size _ cacheLine ＜ = maxLimit) { / /规模 小于预定上限时 for( each node) { / /对于每个结点 Adjust the Size _ par by comparing Size_ current with maxLimit; / /通过对比当前规模与预定上限来调整划 分规模 } Size_par = Size_par * factor; / /乘以增量因 子，确定新的划分大小; } current = begin_node in graph par_G; / /开始结 点作为当前结点 while( current not the last) { / /若当前结点不是 最后结点 visit current; / /访问当前结点 visited［current］= true; / /标志当前结点已被 访问 for ( child = current → next; child! = － 1; child = child→next) { if( visited［child］= = false) / /若子结点还 未被访问 { push current; / /将当前结点入栈 Move to child; / /移动到子结点 } else if ( stack is empty) / /若栈为空 return 0; backtrack to the stack top; / /回溯到栈顶 } } } 该算法首先按照结点度进行排序，使得关联度 高的点排在一起，以提高数据局部性，排序时通常按 照每条超边中第 1 个超点的度进行． 对于超边所连 接的点的问题，需降维成普通图来处理，即把一条超 边中的 N 个超点看成第 1 个超点连接 N － 1 个超 点． 之后算法按照划分的结果采用回溯搜索算法对 超点进行编号，根据编号重排数据． H_PFB_D 算法将超边中的第 1 个点作为降维 点，而实际上超边中的超点无所谓顺序，任何一个超 点都可作为降维点，这个顺序是为了算法的方便而 假定的． 本文选用超边中的第 1 个点作为降维点的 原因是: 预排序过程是全部按照每条超边的第 1 个点的度来排的． 但是，在实际的超图中，全部按 每条超边 的 第 1 个点的度排序不一定是最佳方 案． 当然，如果想要更为准确地确定以哪个超点作 为降序点能够使得程序执行最优，可以对各种组 合方式逐一进行测试，但是该方案势必引入额外 的开销，特别是当超边数与超点数增加时，该开销 会急剧增加． 因此，综合考虑算法开销与程序执行 效率，同时考虑到预排序是按照每条超边的第 1 个点的度进行的，本文选用超边中的第 1 个点作 为降维点． 如果采用 k 路划分技术，H_PFB_D 算法的复杂 度为 O( ( V + E)·log2 k) ． 算法的优点在于具有较高 的划分质量，但由于采用了图划分的方案，导致时间 开销比较大． 2. 2 基于超图的迭代重排算法 与数据重排可以任意改变数据的位置不同，迭 代重排必须对一个迭代所涉及的全部数据整体 移动． 2. 2. 1 H_NRC_I 算法 H_NRC_I 算法与 H_NRC_D 算法相似，其基本 思想为依次遍历时间局部性超图的超边，并将其包 含的超点进行排序，按照该顺序对迭代进行重排以 提高程序的局部性． 对于一个非规则应用，在不确 定其访存情况时，可以假设数据的访问是随机的． 所以，一般来讲，对于一个访问多个数据的迭代，其 数据重用性要高于一个仅访问很少个数据的迭代． 因此，对于一个特定的超边，H_NRC_I 算法按照超 点度由小到大进行排序，即将访问数据个数比较多 的迭代延后，以提高数据重用性及 cache 性能． 下面以图 5 所示的具体实例来说明该算法的执 行过程，假设初始的时间局部性超图如图 5 ( a) 所 示，其中圆圈内的数据代表迭代，闭合曲线代表迭代 访问到的数据，具体的数值由方框内的数据表示． H_NRC_I 算法的具体执行过程如下． 第 1 步 依次遍历时间局部性超图中的超边， 统计每条超边包含的超点． 具体到非规则应用，则 指依次统计非规则应用访问到的数据在哪些迭代 中被访问． 例如，第 1 条超边包含了超点 1 和 2，即 数据 1 在第 1、2 次迭代中被访问; 第 2 条超边包含 了超点 2、4 和 5，即数据 2 在第 2、4 和 5 次迭代中 ·1474·

第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·

·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·

第12期 曹倩等：基于超图的非规则应用局部性优化 ·1477· 图9所示为各个重排算法的时间开销图.可以 Proceedings of the 16th Principles and Practices of Parallel Pro- 看出：原理简单的算法，如基于遍历思想的H_NRC_ gramming (PPoPP).San Antonio,2011:13 B]Zhou M,Sahni O,Shephard M S,et al.Adjacencyased data re- D算法，时间开销很小：而原理相对复杂的算法，如 ordering algorithm for acceleration of finite element computations 使用了多级图划分思想的H_P℉B_D算法，时间开 Sci Program,2010,18(2):107 销比较大，HPFB_D算法的时间开销约为H_NRC_ 4]Wang M.Parallel Compilation and Optimization for Multi-core Pro- D算法的3倍.对于开销较大的H_PFB_D算法，在 cessors [Dissertation].Changsha:National University of Defense 一定范围内，当迭代次数增加时，可以有效地分摊算 Technology,2010 法本身的开销，因此程序性能也会相应地提高 (王淼.面向多核处理器的并行编译及优化关键技术研究[学 位论文].长沙：国防科学技术大学，2010) 2.50 5] Camata JJ,Rossa A L,Valli A M P,et al.Reordering and in- 200 complete preconditioning in serial and parallel adaptive mesh re- finement and coarsening flow solutions.Int J Numer Methods Flu- ids,2012,69(4):802 盘100 [6]Liu X H,Yang Y,Zhang J Y,et al.Basic-block reordering algo- 50 ◆一 rithm based on structural analysis.J Softcare,2008,19(7): 1603 H_NRC_D H_BS_D H_PFB_D H NRC_I H_BS_I 重排算法 (刘先华，杨阳，张吉豫，等.一种基于子结构分析的基本块 重排算法.软件学报.2008,19(7)：1603) 图9各种算法的时间开销 ] Hsu C H,Chen S C.Efficient selection strategies towards proces- Fig.9 Cost of each algorithm sorreordering techniques for improving data locality in heterogene ous clusters.J Supercomput,2012,60(3):284 4结论 [8]Rjeili AA,Karypis G.Multilevel algorithms for partitioning pow- er-aw graphs /Proceedings of the 20th International Parallel and (1)采用超图的思想实现数据重排和迭代重 Distributed Processing Symposium (IPDPS).Rhodes Island, 排，可以改善非规则应用中cache的局部性，提高非 2006:566 规则应用的执行速度. ]Lu H,Tan Y P,Xue X Y,et al.Real-ime,adaptive,and locali- (2)最优的基于超图的数据重排算法与最优的 ty-based graph partitioning method for video scene clustering. IEEE Trans Circuits Syst Video Technol,2011,21(11)1747 基于超图的迭代重排算法相结合，其效果不一定是 [10]Fan N,Pardalos P M.Linear and quadratic programming approa- 最优的，即数据重排算法与迭代重排算法不能简单 ches for the general graph partitioning problem.J Global Optim, 地叠加 2010,48(1):57 (3)对于开销较大的重排算法，在一定范围内， [11]Huang R J.Counting series of undirected hypergraphs.J Unin 增加迭代次数，可以有效地分摊算法本身的开销，因 Sci Technol Beijing,1999,21(5):507 (黄汝激.无向超图的计数级数.北京科技大学学报，1999， 此程序性能也会相应地提高. 21(5):507) (4)本文提出的基于超图的重排算法仍具有一 [12]Han H,Tseng C W.Exploiting locality for irregular scientific 定的局限性，如这些算法并不适用于循环迭代间存 codes.IEEE Trans Parallel Distrib Syst,2006,17(7):606 在数据依赖的情况，这也将是我们下一步研究的 [13]Strout MM,Osheim N,Rostron D,et al.Evaluation of hierar- 重点 chical mesh reorderings/Proceedings of the 9th International Conference on Computational Science (ICCS).Baton Rouge, 2009:540 参考文献 [14]Ucara B.Catalyurekb 0 V,Aykanat C.A matrix partitioning in- [1]Kim S,Han H,Choe K M.Region-based parallelization of irregu- terface to PaToH in MATLAB.J Parallel Comput,2010,36 lar reductions on explicitly managed memory hierarchies.Super- (5):254 comput,2011,56(1):25 [15]Norman M,Padoan P,Bordner J,et al.ZEUS2D Codes Online Bauer M,Clark J,Schkufza E,et al.Programming the memory [EB/0L](2007-0807)[2011-12-01].htp:/lca.ucsd. hierarchy revisited:Supporting irregular parallelism in sequoia// edu/portal/codes/zeus2d

第 12 期 曹 倩等: 基于超图的非规则应用局部性优化 图 9 所示为各个重排算法的时间开销图． 可以 看出: 原理简单的算法，如基于遍历思想的 H_NRC_ D 算法，时间开销很小; 而原理相对复杂的算法，如 使用了多级图划分思想的 H_PFB_D 算法，时间开 销比较大，H_PFB_D 算法的时间开销约为 H_NRC_ D 算法的 3 倍． 对于开销较大的 H_PFB_D 算法，在 一定范围内，当迭代次数增加时，可以有效地分摊算 法本身的开销，因此程序性能也会相应地提高． 图 9 各种算法的时间开销 Fig． 9 Cost of each algorithm 4 结论 ( 1) 采用超图的思想实现数据重排和迭代重 排，可以改善非规则应用中 cache 的局部性，提高非 规则应用的执行速度． ( 2) 最优的基于超图的数据重排算法与最优的 基于超图的迭代重排算法相结合，其效果不一定是 最优的，即数据重排算法与迭代重排算法不能简单 地叠加． ( 3) 对于开销较大的重排算法，在一定范围内， 增加迭代次数，可以有效地分摊算法本身的开销，因 此程序性能也会相应地提高． ( 4) 本文提出的基于超图的重排算法仍具有一 定的局限性，如这些算法并不适用于循环迭代间存 在数据依赖的情况，这也将是我们下一步研究的 重点． 参 考 文 献 ［1］ Kim S，Han H，Choe K M． Region-based parallelization of irregu￾lar reductions on explicitly managed memory hierarchies． J Super￾comput，2011，56( 1) : 25 ［2］ Bauer M，Clark J，Schkufza E，et al． Programming the memory hierarchy revisited: Supporting irregular parallelism in sequoia / / Proceedings of the 16th Principles and Practices of Parallel Pro￾gramming ( PPoPP) ． San Antonio，2011: 13 ［3］ Zhou M，Sahni O，Shephard M S，et al． Adjacency-based data re￾ordering algorithm for acceleration of finite element computations． Sci Program，2010，18( 2) : 107 ［4］ Wang M． Parallel Compilation and Optimization for Multi-core Pro￾cessors ［Dissertation］． Changsha: National University of Defense Technology，2010 ( 王淼． 面向多核处理器的并行编译及优化关键技术研究［学 位论文］． 长沙: 国防科学技术大学，2010) ［5］ Camata J J，Rossa A L，Valli A M P，et al． Reordering and in￾complete preconditioning in serial and parallel adaptive mesh re￾finement and coarsening flow solutions． Int J Numer Methods Flu￾ids，2012，69( 4) : 802 ［6］ Liu X H，Yang Y，Zhang J Y，et al． Basic-block reordering algo￾rithm based on structural analysis． J Software，2008，19 ( 7 ) : 1603 ( 刘先华，杨阳，张吉豫，等． 一种基于子结构分析的基本块 重排算法． 软件学报． 2008，19( 7) : 1603) ［7］ Hsu C H，Chen S C． Efficient selection strategies towards proces￾sor reordering techniques for improving data locality in heterogene￾ous clusters． J Supercomput，2012，60( 3) : 284 ［8］ Rjeili A A，Karypis G． Multilevel algorithms for partitioning pow￾er-law graphs / / Proceedings of the 20th International Parallel and Distributed Processing Symposium ( IPDPS ) ． Rhodes Island， 2006: 566 ［9］ Lu H，Tan Y P，Xue X Y，et al． Real-time，adaptive，and locali￾ty-based graph partitioning method for video scene clustering． IEEE Trans Circuits Syst Video Technol，2011，21( 11) : 1747 ［10］ Fan N，Pardalos P M． Linear and quadratic programming approa￾ches for the general graph partitioning problem． J Global Optim， 2010，48( 1) : 57 ［11］ Huang R J． Counting series of undirected hypergraphs． J Univ Sci Technol Beijing，1999，21( 5) : 507 ( 黄汝激． 无向超图的计数级数． 北京科技大学学报，1999， 21( 5) : 507) ［12］ Han H，Tseng C W． Exploiting locality for irregular scientific codes． IEEE Trans Parallel Distrib Syst，2006，17( 7) : 606 ［13］ Strout M M，Osheim N，Rostron D，et al． Evaluation of hierar￾chical mesh reorderings / / Proceedings of the 9th International Conference on Computational Science ( ICCS ) ． Baton Rouge， 2009: 540 ［14］ Uara B，atalyürekb  V，Aykanat C． A matrix partitioning in￾terface to PaToH in MATLAB． J Parallel Comput，2010，36 ( 5) : 254 ［15］ Norman M，Padoan P，Bordner J，et al． ZEUS-2D Codes Online ［EB /OL］( 2007--08--07) ［2011--12--01］． http: / /lca． ucsd． edu /portal /codes/zeus2d ·1477·