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

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·