基于连通分量生成优化的超级计算机基准测试加速方法

1.一种基于连通分量生成优化的超级计算机基准测试加速方法，其特征在于包括以下步骤：第一步、图生成，通过Kronecker图生成器生成随机图结构G＝(V,E)，V为顶点集合，E为边集合，图的规模由用户输入的参数scale、edgefactor确定，其中，scale指示图的顶点规模，edgefactor指示每个顶点连接边的平均数量，N＝2 scale 表示G的顶点数目，即V的元素中的顶点个数，M＝edgefactor×N表示G的边数目即E的元素数量；使用v i 表示G中编号为i的顶点，使用顶点对(v i ,v j )表示顶点v i 到顶点v j 的边；(v i ,v j )∈E，i和j均为正整数且0≤i≤N-1，0≤j≤N-1；第二步、构建存储图G的邻接矩阵A，A ij ＝0表示顶点v i 与顶点v j 之间没有边，A ij ＝1表示顶点v i 与顶点v j 之间有边；第三步、数据结构初始化，把V中所有顶点的根顶点和子顶点设置成相应的值，遍历边集合E，去除边集合E中的自环边即顶点与自身连接的边，并根据边的两个顶点的不同情况来分类，方法是：3.1.根据图G的数据规模scale，初始化V中所有顶点的根顶点向量root和二维子顶点向量son，root中包含N个元素，root[v i ]表示顶点v i 的根顶点，将root[v i ]初始化为-1，son是二维向量，包含N个元素，每个元素都是一个向量，将son中的每个元素初始化为空向量；son[v i ]表示顶点v i 的子顶点向量，用来存储以顶点v i 为根顶点的顶点集合，即以顶点v i 为根顶点的连通分量的顶点信息，连通分量是root值为自身的顶点在son向量中所存储的内容；初始化变量e＝1；3.2.创建与Graph500源代码中边数据存储格式相一致的结构体packed_edge，packed_edge包含三个int类型的整型变量，第一个变量v0_low是构成边的第一个顶点的ID，第二个变量v1_low是构成与v0_low第一个变量相连边的第二个顶点的ID，第三个变量high留作功能扩展所用；用e_b.v0_low表示ID为v0_low的边e_b的第一个顶点，用e_b.v1_low表示ID为v1_low的边e_b的第二个顶点；3.3.用结构体packed_edge创建一条边e_b，用于存贮从E中读取的边信息；3.4.若e>M，表示边集合E已处理完毕，转第六步，否则，从边集合E中按顺序读取第e条边，令e_b＝第e条边，其中e_b.v0_low和e_b.v1_low就是构成e_b的两个顶点，令e＝e+1，转3.5；3.5.如果e_b.v0_low≠e_b.v1_low，说明e_b.v0_low和e_b.v1_low连成的边不是自环边，转3.6，否则，说明e_b.v0_low和e_b.v1_low连成的边是自环边，直接转3.4；3.6.判定e_b.v0_low和e_b.v1_low的根顶点是否相同，如果root[e_b.v0_low]＝root[e_b.v1_low]，转第四步，如果不相等，转第五步；第四步、处理根顶点相同的情况，如果e_b.v0_low和e_b.v1_low均未被访问过，则将e_b.v0_low和e_b.v1_low合并到以e_b.v0_low为根顶点的连通分量son[e_b.v0_low]中，如果e_b.v0_low和e_b.v1_low均被访问过，说明e_b.v0_low和e_b.v1_low已经在同一个连通分量里了，则跳过e_b，访问E中下一条边，方法是：4.1.如果root[e_b.v0_low]＝-1，说明e_b.v0_low和e_b.v1_low均未被访问过，e_b.v0_low和e_b.v1_low所构成的边是第一次访问，转4.2；否则，说明e_b.v0_low和e_b.v1_low均被访问过且已经处于同一个连通分量son[root[e_b.v0_low]]中，不需要进行合并操作，转3.4；4.2.将e_b.v1_low合并到以e_b.v0_low为根顶点的连通分量中，把e_b.v0_low设置成e_b.v0_low和e_b.v1_low两个顶点的根顶点，e_b.v0_low和e_b.v1_low的root向量对应的元素均设置为e_b.v0_low，即令root[e_b.v0_low]＝e_b.v0_low,root[e_b.v1_low]＝e_b.v0_low；4.3.在e_b.v0_low对应的son向量中插入e_b.v0_low和e_b.v1_low的ID号，即在连通分量son[e_b.v0_low]中添加新的顶点信息，即将e_b.v0_low插入到son[e_b.v0_low],将e_b.v1_low也插入到son[e_b.v0_low])，转3.4；第五步、根据根顶点不同的情况对顶点的父子关系进行路径压缩，并对根顶点不同的两个连通分量进行合并，方法是：5.1.如果root[e_b.v0_low]＝-1，转5.2，否则，转5.3；5.2.此时顶点e_b.v1_low已被访问过，顶点e_b.v0_low未被访问过，把e_b.v0_low插入到以e_b.v1_low的根顶点所对应的连通分量son[root[e_b.v1_low]])中，即把e_b.v0_low合并到以顶点root[e_b.v1_low]为根顶点的连通分量中，并改换e_b.v0_low的根顶点为e_b.v1_low的根顶点，即令root[e_b.v1_low]＝root[e_b.v0_low]，插入和改换根顶点共同完成了对两个连通分量的合并操作，以root[e_b.v1_low]为根顶点的连通分量增加了新的顶点信息，转3.4；5.3.如果root[e_b.v1_low]＝-1，转5.4，否则，转5.5；5.4.此时顶点e_b.v0_low已被访问过，顶点e_b.v1_low未被访问过，把e_b.v1_low插入到以e_b.v0_low的根顶点所对应的连通分量son[root[e_b.v0_low])中，即把e_b.v1_low合并到以顶点root[e_b.v0_low]为根顶点的连通分量中，并改换e_b.v1_low的根顶点为e_b.v0_low的根顶点，即令root[e_b.v0_low]＝root[e_b.v1_low]，插入和改换根顶点共同完成了对两个连通分量的合并操作，以root[e_b.v0_low]为根顶点的连通分量增加了新的顶点信息，转3.4；5.5.此时root[e_b.v0_low]≠-1且root[e_b.v1_low]≠-1，比较e_b.v0_low和e_b.v1_low对应的连通分量的顶点个数，即比较son[root[e_b.v0_low]]和son[root[e_b.v1_low]]的元素数量，如果son[root[e_b.v0_low]].size<son[root[e_b.v1_low]].size，size表示向量的元素个数，son[root[e_b.v0_low]].size表示e_b.v0_low的根顶点的子节点的个数，son[root[e_b.v1_low]].size表示e_b.v1_low的根顶点的子节点的个数，把两个顶点的ID对调，使得son[root[e_b.v0_low]]的元素数量大于son[root[e_b.v1_low]]的元素数量；转5.6；5.6.将e_b.v1_low的根顶点记为root_v2，即令root_v2＝root[e_b.v1_low]，设置循环变量i，初始化i＝1；5.7.若i＝son[root_v2].size，转3.4，否则，转5.8；5.8.对以root[e_b.v0_low]为根顶点的连通分量son[root[e_b.v0_low]]中顶点的父子关系进行路径压缩，把son[root_v2]中的每个元素均调整为root[e_b.v0_low]的直接子顶点，使得son[root_v2]中的每个元素与e_b.v0_low的根顶点之间不出现中间层级的顶点；路径压缩方法是：把son[root_v2]中的第i个元素即顶点son[root_v2][i]的根顶点设置为root[e_b.v0_low]，即令root[son[root_v2][i]]＝root[e_b.v0_low],并把顶点som[root_v2][i]插入连通分量son[root[e_b.v0_low]]；5.9.令i＝i+1，转5.7；第六步、找出图G中所有连通分量的信息，采用连通分量对图G进行划分，采用scatter发散操作将采用连通分量进行划分后的图G分布至超级计算机各处理节点；第七步、BFS搜索与验证：随机生成一个根顶点v，结合邻接矩阵A中所存储的边信息，以v为源点对采用连通分量进行划分过的图G进行BFS搜索，输出生成树作为搜索结果，记录Graph500有效计时时间t，并验证搜索得到的BFS生成树是否与原图信息匹配；该过程循环64次，且分别对每次BFS搜索部分计时；第八步、计算图测试性能的评价值，即64棵生成树的BFS遍历测试性能值平均值，获得测试结果并输出；第九步、结束。 2.如权利要求1所述的一种基于连通分量生成优化的超级计算机基准测试加速方法，其特征在于， 第六步找出图G中所有连通分量的信息，采用连通分量对图G进行划分，采用scatter发散操作将采用连通分量进行划分后的图G分布至超级计算机各处理节点的方法是：6.1.设置顶点序号j、连通分量序数k，初始化j＝0,k＝1；6.2.若j＝N-1，说明所有顶点均已遍历完，此时k就是图G中连通分量的个数，转第七步，否则，转6.3；6.3.判断序号为j的顶点v j 的根顶点是否是自身，即如果root[v j ]≠v j ，说明顶点v j 不是所在连通分量的根顶点，转6.5；否则，说明顶点v j 是第k个连通分量的根顶点，son[v j ]存储了第k个连通分量的所有顶点，获取了第k个连通分量的所有顶点；令k＝k+1；转6.4；6.4.把son[v j ]中的顶点采用scatter发散操作分布至超级计算机相同或相近的物理节点；6.5.令j＝j+1，转6.2。