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