《最小生成树的多核并行算法》由会员分享，可在线阅读，更多相关《最小生成树的多核并行算法（6页珍藏版）》请在金锄头文库上搜索。
1、最小生成树的多核并行算法马成刚（09008230）摘要：最小生成树是图论中的经典问题，在现实生活中也有很多应用。本文讨论一种最小生成树的多核并行算法。关键字：最小生成树；索林算法；并行一、介绍最小生成树问题是图论中的一个经典问题，也是众多广泛应用的问题之一。关于最小生成树问题已有一些经典的算法，如：Prim算法、Kruskal算法，都具有近线性的算法复杂度。对于稀疏图来说，使用Kruskal算法更好，否则两种算法复杂性没有什么区别【1】。Prim算法每次选择一个顶点，Kruskal算法每次选择一条边，下一个顶点或边是否选择与以前选的顶点或边有关，这样都不适合于并行计算，即当今的多核计算机不能太
2、大提高计算效率。本文介绍一种基于Sollin算法的求解最小生成树的多核并行算法，能够提高求最小生成树的并行效率。二、算法先给出Sollin算法从连通带权简单图G=（V，E）这样产生最小生成树：相继地添加成组的边。假定对V里的顶点进行了排序，这样就产生了一个顺序，其中若u0先于u1，或者若u0=u1并且v0先于v1，则u0，v0先于u1，v1。这个算法首先同时选择每个顶点关联的权最小的边。在平局的情形下选择在上述顺序里的第一条边。这样就产生了一个没有简单回路的图，即一些树组成的森林。其次，对森林里的每棵树，同时选择在该树里的一个顶点与在不同的一棵树里顶点之间最短的边。同样在平局的情况下选择在上述
3、顺序下的第一条边。（这样就产生了一个没有简单回路的图，它包含着比在这一步之前出现的更少的边树）继续进行同样的添加树的过程，指导已选择了n-1条边为止。（摘自【1】第576页）以我对该算法的理解，该算法可以分为三个步骤：选择边、合并顶点、合并边依次循环直到结束。选择边即选择连接每个顶点的权值最小的边，在相同权值的情况下选序号小的；合并顶点将通过选择的边的连通的树中的所有顶点合并成一个新的顶点，进入下一次循环；合并边（在原算法中并没有）用新顶点之间边的权值代替原来树中所有顶点与另一棵树所有顶点之间边的权的最小值，以避免重复查看比较。我没有见过对Sollin算法的证明，但这是很简单的。这里给出Sol
4、lin算法正确性的简单证明。先证明每个顶点关联的权最小的边至少有一个（对有相同的）最终被选到最小生成树中。用反证法如果一个顶点关联的最小的边不被选到最小生成树中，则在最小生成树中添加这条边一定会出现环，这个顶点有两条边在环上。可以去掉其中一条使其成为树。除非这两条边的权值相同即都为最小的边，否则去掉另一条边（不是最小的边）得到的树比最小生成树的总权值小，违反了最小生成树的定义。在证明不会有环产生。点合并和边合并明显不会有环产生。如果产生了环，假设v1v2, vn构成了环，则是v1选择了边（v1，v2），v2选择了边（v2，v3） 或反向。由于选择的边都是各个顶点关联的最小权的边，则有w12w2
5、3w34w12（wij表示边(vi，vj)的权值），则w12=w23=w34=w12。同理，反向也可以得到相同的结论。又由于规定当权值相同时选择序号小的边，如果有环必不符合这条规则。因此可以证明不会出现环。最后证明算法一定会终止。表示算法终止可以用选了n-1条边，也可以用最后剩下一棵树，易证明两个条件是等价的。在每一次循环，至少是两个顶点结合成一棵树，再把树合并成新顶点，这样顶点数目就减少了一半。循环进行，顶点一定会变为1。（由此可见，该算法的复杂度是线性的）接下来我们分别就每个步骤讨论一下其并行实现。1. 选择边申请数组存放每一个顶点连接到的边的最小值和所对应的边，对所有边进行遍历，找到连接
6、到各个顶点的最小权值和对应的边。我们知道，图的边的存储方式可以是多种多样的，如邻接表，邻接矩阵，再次为方便采用邻接矩阵讨论，此算法也同样适合其他表示方式，而且效率不会相差太大。对于一个邻接矩阵，可以对每一个顶点并行的求其最小值。按下标从小到大依次遍历，同时可以保证相同权值下标最小。2. 合并顶点将通过选择的边的连通的所有顶点合并成一个新的顶点，进入下一次循环。这里用数组实现的链表。对于每一个顶点分配一个int型空间，保存与它相邻的一个顶点的索引。为了便于对联标处理，这里规定，每个顶点保存的顶点的索引必须小于该顶点的索引。接下来将原顶点与新顶点对应，即原顶点保存新顶点的索引。用nn表示新的顶点个
7、数，对链表从小到大遍历，如果不是指向下一个顶点，那么它就是第一个对应新的索引为nn的顶点，新顶点数nn加一。由于已经规定链表中的相邻顶点的索引小于当前顶点的索引，可以直接把链表中相邻顶点对应的新顶点的索引给当前顶点。3. 合并边生成新的邻接表权值设为无穷大，遍历当前图的每一条边，如果这条边的两个顶点对应同一个新顶点则跳过。否则判断是否比当前新的邻接表中对应的两个新顶点确定的边的权值小，如果是，则更新新的邻接表中这条边的权值。在这个算法中很多地方都用求最小值。在看多核计算与并行程序设计【2】有关lock-free算法的介绍，即多个线程同时访问同一块资源时（比如同时写），能保证至少有一个线程操作的
8、结果是正确的，其他线程判断操作是否正确，如果不正确，则重复操作。对于求数组最小值，可不可以循环判断目标值是否比要写的数值大，如果是则写入，不是就跳过？这样做很容易想到的一个问题是线程调度，如果判断过之后要写，但是写之前线程发生了切换，当其他线程将自己发现的最小值写入后，这个线程恢复执行，不加判断地将等待写入的值写入，就可能出错了（其实这样的概率是很小的，我在测试的时候没有发现过出错，前提是线程数不要太多）。可不可以控制线程在某一段内不被打断或打断之后回到段首开始执行，我以为原子操作是【2】，后来发现那是针对特定操作的。希望操作系统和CPU尽快提供对求数组最小值的lock-free算法的支持。没
9、有lock-free算法，也是加锁是不可接受的。比如说对一个有10000个点的完全图，权值是065535随机（测试是这样的）需要第一次合并有nn个顶点（测试结果接近2500），这样需要（nn-1）*nn/2把锁，总共开合（10000-1）*10000/2次，这样时间和空间代价都是不可接受的。在此提出一种解决方法：将访问同一块内存的操作交给同一个线程做，这样线程既可以并行，又可以避免冲突。这样需要对第二步合并顶点进行修改，即对指向相同新的顶点的原顶点的表示做修改，使能够很快找到指向相同顶点的原顶点，一种很好的实现方式就是链表了。在上面的基础上进行以下操作：申请一个长度为nn的int型数组head
10、，作为新顶点指向原顶点的头指针，初始化为-1。对原数组从后向前遍历，对每一个原顶点，将对应新顶点head里的值给原顶点的链表，将原顶点的索引赋给对应新顶点的head，这样head里的值就是当前遍历到的对应于该新顶点的最前面一个原顶点，原顶点的链表指向下一个指向相同新顶点的原顶点，这其实就是建立链表的过程。在第三步合并边中，将按原邻接表遍历改为按新邻接表遍历，对于新邻接表中的每一条边的两个顶点，可以很快由链表找到对应它的所有原顶点。这样并没有增加很多工作，但测试时会发现效率明显降低，这将在下面讨论。对于一个这个算法，最耗时间的就是对二维数组的遍历，但求一个图的最小生成树最少也要将图中各边遍历一次
11、。那可否只遍历一次呢？我没想到只遍历一次的方法，但由此我考虑到了这个算法一个可以优化的地方，将合并边的操作同下一次求每个顶点最小权的关联边，即在合并边的同时求出每个顶点最小权的关联边，由此减少了一次遍历。至此这个算法的大体框架已经完成，不过现实中用户还想要知道最小生成树的总权值，以及最小生成树里的边。在第一步已经找到了各个顶点关联的权值最小的边，同时也保存了最小的权值。在对算法介绍中已经说明这些边不构成环，而且都是最终的最小生成树中的边。但这些边中有重复的，如顶点A、B关联的最小权值的边都是边AB，那么A就会保存B，同时B保存A。可以证明有且仅有这一种情况。这样遍历到A时只需看一下A保存的顶点
12、里保存的是不是A就可以了。在这里约定如果出现上述情况，在遍历到序号较大的顶点时才将这条边加入所选边集中，同时将所选边的权值加入总权值中。这样当遍历到一个顶点时，如果它保存的那另一个顶点的序号小于它的序号，就可以直接把这条边和它的权值加入边集和权值总和中（算法已经约定相同权值的情况下取序号小的），否则才判断是否是上述情况，不是的话也加入边和权。这一步也可并行计算，还可以再开一个线程来完成。这里附带说明一下，如果不能保证图连通，在这里首先判断一下权值是否是无穷大（或顶点保存的另一个顶点是否合法），如果是（或否），则说明图不连通，如果图不连通，该算法也可以求得每个连通子图的最小生成树，不过终止条件需
13、要修改。至此这个算法已经基本完成了，我们在接下来讨论其它一些优化。我们注意到图的邻接矩阵表示是对称矩阵，也就是说一半是冗余的，可不可以把这一半的冗余去掉呢？这样时间和空间复杂度都有近一半的降低。我尝试了这样一种方法：用一维数组作二维数组用，只保存下三角部分。第i行第j个元素（ij）可用一维数组的第（i-1）*i/2个元素表示。每次访问二维数组时必须保证行大于列，否则把行和列调换。在访问每一条边时同时考虑两个方向。这样做我原以为是没问题的，后来发现还是有数据冲突的可能，因为在遍历边时同时考虑了两个顶点，而不能同时保证两个顶点不发生数据竞争。这里并不需要返回到完全的二维数组，我们可以每次只考虑边的
14、一个顶点，这样时间复杂度没有明显的增加，但空间节省了一半，同样避免了数据冲突。由于串行算法可以不考虑数据竞争，因此无需考虑将按原边遍历改为按新边遍历（在测试中会发现效率相差很大），也无需考虑将二维数组减半的时候的数据冲突。这样程序只在第一次对所有边进行了两次遍历，以后边集的规模以至少1/4的速率递减（点集以至少1/2的速率递减），总的时间复杂度不超过三次遍历所有边。可以说这个算法在最小生成树的串行算法中是比较优秀的了。在没有其他信息引入的情况下不可能有比这个快的多的算法。在下面的测试中我们将看到这个算法优于Kruskal算法。并行优化暂时谈到这里。至此算法的主要部分已经进行过并行优化了，其他部
15、分也并不是不可以并行化，但有时候会得不偿失。如前面说的计算总的权值和记录所选择的边可以分线程做，在测试中发现当N=5000时，用Intel Thread Profiler显示新的线程执行时间是0.00016s，但明显的开线程的时间比线程执行时间要长得太多了。用openmp并行也是可以做的，不过优化不是很明显，其它还有一些地方也是可以并行化的，有兴趣的读者可以尝试，或者是尝试加锁。三、测试为便于测试这里只需要输入顶点的个数N，程序用随机数填补所有边的权值，默认为完全图.1. 本文算法与Kruskal算法比较输出依次是Kruskal算法的输出、串行算法的输出（没考虑数据冲突解决）、并行算法单核执行（考虑了数据冲突解决）、和并行算法执行的输出。每个输出都包括总权值、所选边数和执行时间。对于后两种还要先输出使用的核数（其实是线程数，在并行算法中令线程数等于核数）。(a) (b) (c) (d)图一 (a),(b),(c),(d)分别为N=1000，N=2500，N=5000，N=10000，运行环境：Intel Dual E2160 1.80GHz，DDR2 667内存2G，windows7操作系统由于内存限制，Kruskal算法不能计算太大的数并且很耗时间，接下来的测试隐去Kruskal算法。2. 串行算法与并行算法比较(a) (b) (c) (d) (e)
