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