·1474· 北京科技大学学报 第34卷 步骤： HP℉B_D算法将超边中的第1个点作为降维 HPFB_D(G){//基于超图的先划分再回溯数 点，而实际上超边中的超点无所谓顺序，任何一个超 据重排算法 点都可作为降维点，这个顺序是为了算法的方便而 order nodes according to degree;/结点按度 假定的.本文选用超边中的第1个点作为降维点的 排序： 原因是：预排序过程是全部按照每条超边的第1 while(Size_cacheLine<=maxLimit){/规模 个点的度来排的.但是，在实际的超图中，全部按 小于预定上限时 每条超边的第1个点的度排序不一定是最佳方 for(each node){I/对于每个结点 案.当然，如果想要更为准确地确定以哪个超点作 Adjust the Sizepar by comparing Size 为降序点能够使得程序执行最优，可以对各种组 current with maxLimit; 合方式逐一进行测试，但是该方案势必引入额外 /通过对比当前规模与预定上限来调整划 的开销，特别是当超边数与超点数增加时，该开销 分规模 会急剧增加.因此，综合考虑算法开销与程序执行 } 效率，同时考虑到预排序是按照每条超边的第1 Size_par=Size_par*factor;/乘以增量因 个点的度进行的，本文选用超边中的第1个点作 子，确定新的划分大小： 为降维点 如果采用k路划分技术，H_P℉B_D算法的复杂 current=begin_node in graph par_G;I/开始结 度为O((V+E)·log2k).算法的优点在于具有较高 点作为当前结点 的划分质量，但由于采用了图划分的方案，导致时间 while(current not the last),{/若当前结点不是 开销比较大. 最后结点 2.2基于超图的迭代重排算法 visit current;//访问当前结点 与数据重排可以任意改变数据的位置不同，迭 visited[current].=true;/标志当前结点己被 代重排必须对一个迭代所涉及的全部数据整体 访问 移动 for(child=-current→next;child！=-; 2.2.1H_NRC_I算法 child child->next) 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·