最小生成树的多核并行算法【范本模板】.pdf
最小生成树的多核并行算法 马成刚（09008230）摘要：最小生成树是图论中的经典问题,在现实生活中也有很多应用。本文讨论一种最小生成树的多核并行算法.关键字：最小生成树;索林算法;并行 一、介绍 最小生成树问题是图论中的一个经典问题，也是众多广泛应用的问题之一.关于最小生成树问题已有一些经典的算法，如：Prim 算法、Kruskal 算法，都具有近线性的算法复杂度。对于稀疏图来说，使用 Kruskal 算法更好，否则两种算法复杂性没有什么区别【1】。Prim 算法每次选择一个顶点,Kruskal 算法每次选择一条边，下一个顶点或边是否选择与以前选的顶点或边有关，这样都不适合于并行计算，即当今的多核计算机不能太大提高计算效率。本文介绍一种基于 Sollin 算法的求解最小生成树的多核并行算法,能够提高求最小生成树的并行效率。二、算法 先给出 Sollin 算法 从连通带权简单图G=（V,E）这样产生最小生成树：相继地添加成组的边。假定对V里的顶点进行了排序，这样就产生了一个顺序，其中若u0先于u1，或者若u0=u1并且v0先于v1，则u0，v0 先于 u1，v1。这个算法首先同时选择每个顶点关联的权最小的边。在平局的情形下选择在上述顺序里的第一条边.这样就产生了一个没有简单回路的图,即一些树组成的森林.其次,对森林里的每棵树，同时选择在该树里的一个顶点与在不同的一棵树里顶点之间最短的边.同样在平局的情况下选择在上述顺序下的第一条边。（这样就产生了一个没有简单回路的图，它包含着比在这一步之前出现的更少的边树）继续进行同样的添加树的过程，指导已选择了n1条边为止.（摘自【1】第 576 页)以我对该算法的理解,该算法可以分为三个步骤：选择边、合并顶点、合并边依次循环直到结束.选择边即选择连接每个顶点的权值最小的边，在相同权值的情况下选序号小的；合并顶点将通过选择的边的连通的树中的所有顶点合并成一个新的顶点,进入下一次循环；合并边(在原算法中并没有）用新顶点之间边的权值代替原来树中所有顶点与另一棵树所有顶点之间边的权的最小值，以避免重复查看比较.我没有见过对 Sollin 算法的证明，但这是很简单的.这里给出 Sollin 算法正确性的简单证明。先证明每个顶点关联的权最小的边至少有一个（对有相同的）最终被选到最小生成树中。用反证法如果一个顶点关联的最小的边不被选到最小生成树中，则在最小生成树中添加这条边一定会出现环,这个顶点有两条边在环上。可以去掉其中一条使其成为树.除非这两条边的权值相同即都为最小的边，否则去掉另一条边（不是最小的边）得到的树比最小生成树的总权值小,违反了最小生成树的定义。在证明不会有环产生。点合并和边合并明显不会有环产生。如果产生了环,假设 v1v2,vn构成了环，则是 v1选择了边（v1，v2)，v2 选择了边（v2，v3）或反向。由于选择的边都是各个顶点关联的最小权的边,则有 w12w23w34w12（wij表示边(vi,vj)的权值）,则 w12=w23=w34=w12。同理，反向也可以得到相同的结论。又由于规定当权值相同时选择序号小的边，如果有环必不符合这条规则.因此可以证明不会出现环。最后证明算法一定会终止.表示算法终止可以用选了 n1 条边，也可以用最后剩下一棵树,易证明两个条件是等价的。在每一次循环，至少是两个顶点结合成一棵树，再把树合并成新顶点,这样顶点数目就减少了一半。循环进行，顶点一定会变为 1。（由此可见，该算法的复杂度是线性的）接下来我们分别就每个步骤讨论一下其并行实现。1.选择边 申请数组存放每一个顶点连接到的边的最小值和所对应的边，对所有边进行遍历，找到连接到各个顶点的最小权值和对应的边。我们知道,图的边的存储方式可以是多种多样的，如邻接表，邻接矩阵，再次为方便采用邻接矩阵讨论,此算法也同样适合其他表示方式，而且效率不会相差太大。对于一个邻接矩阵，可以对每一个顶点并行的求其最小值。按下标从小到大依次遍历，同时可以保证相同权值下标最小。2.合并顶点 将通过选择的边的连通的所有顶点合并成一个新的顶点，进入下一次循环。这里用数组实现的链表。对于每一个顶点分配一个 int型空间，保存与它相邻的一个顶点的索引。为了便于对联标处理,这里规定，每个顶点保存的顶点的索引必须小于该顶点的索引。接下来将原顶点与新顶点对应,即原顶点保存新顶点的索引。用 nn 表示新的顶点个数，对链表从小到大遍历,如果不是指向下一个顶点，那么它就是第一个对应新的索引为 nn 的顶点,新顶点数 nn 加一。由于已经规定链表中的相邻顶点的索引小于当前顶点的索引,可以直接把链表中相邻顶点对应的新顶点的索引给当前顶点.3.合并边 生成新的邻接表权值设为无穷大，遍历当前图的每一条边，如果这条边的两个顶点对应同一个新顶点则跳过。否则判断是否比当前新的邻接表中对应的两个新顶点确定的边的权值小，如果是，则更新新的邻接表中这条边的权值。在这个算法中很多地方都用求最小值。在看多核计算与并行程序设计【2】有关 lock-free 算法的介绍，即多个线程同时访问同一块资源时（比如同时写）,能保证至少有一个线程操作的结果是正确的，其他线程判断操作是否正确，如果不正确，则重复操作。对于求数组最小值，可不可以循环判断目标值是否比要写的数值大，如果是则写入，不是就跳过？这样做很容易想到的一个问题是线程调度，如果判断过之后要写，但是写之前线程发生了切换，当其他线程将自己发现的最小值写入后,这个线程恢复执行，不加判断地将等待写入的值写入，就可能出错了（其实这样的概率是很小的,我在测试的时候没有发现过出错,前提是线程数不要太多)。可不可以控制线程在某一段内不被打断或打断之后回到段首开始执行，我以为原子操作是【2】，后来发现那是针对特定操作的。希望操作系统和 CPU 尽快提供对求数组最小值的 lockfree 算法的支持.没有 lock-free 算法，也是加锁是不可接受的.比如说对一个有10000 个点的完全图，权值是 065535 随机（测试是这样的）需要第一次合并有 nn 个顶点（测试结果接近 2500），这样需要（nn1)*nn/2 把锁,总共开合(100001）10000/2 次，这样时间和空间代价都是不可接受的.在此提出一种解决方法：将访问同一块内存的操作交给同一个线程做，这样线程既可以并行，又可以避免冲突。这样需要对第二步合并顶点进行修改，即对指向相同新的顶点的原顶点的表示做修改，使能够很快找到指向相同顶点的原顶点,一种很好的实现方式就是链表了。在上面的基础上进行以下操作：申请一个长度为 nn 的 int 型数组 head，作为新顶点指向原顶点的头指针，初始化为1.对原数组从后向前遍历，对每一个原顶点，将对应新顶点 head 里的值给原顶点的链表，将原顶点的索引赋给对应新顶点的 head,这样 head 里的值就是当前遍历到的对应于该新顶点的最前面一个原顶点，原顶点的链表指向下一个指向相同新顶点的原顶点，这其实就是建立链表的过程。在第三步合并边中,将按原邻接表遍历改为按新邻接表遍历，对于新邻接表中的每一条边的两个顶点,可以很快由链表找到对应它的所有原顶点.这样并没有增加很多工作，但测试时会发现效率明显降低,这将在下面讨论。对于一个这个算法，最耗时间的就是对二维数组的遍历，但求一个图的最小生成树最少也要将图中各边遍历一次.那可否只遍历一次呢?我没想到只遍历一次的方法，但由此我考虑到了这个算法一个可以优化的地方，将合并边的操作同下一次求每个顶点最小权的关联边,即在合并边的同时求出每个顶点最小权的关联边，由此减少了一次遍历。至此这个算法的大体框架已经完成,不过现实中用户还想要知道最小生成树的总权值，以及最小生成树里的边。在第一步已经找到了各个顶点关联的权值最小的边，同时也保存了最小的权值.在对算法介绍中已经说明这些边不构成环，而且都是最终的最小生成树中的边。但这些边中有重复的,如顶点A、B 关联的最小权值的边都是边AB，那么 A 就会保存 B，同时 B 保存 A。可以证明有且仅有这一种情况.这样遍历到 A 时只需看一下 A保存的顶点里保存的是不是 A就可以了.在这里约定如果出现上述情况，在遍历到序号较大的顶点时才将这条边加入所选边集中，同时将所选边的权值加入总权值中。这样当遍历到一个顶点时，如果它保存的那另一个顶点的序号小于它的序号，就可以直接把这条边和它的权值加入边集和权值总和中（算法已经约定相同权值的情况下取序号小的），否则才判断是否是上述情况，不是的话也加入边和权。这一步也可并行计算，还可以再开一个线程来完成。这里附带说明一下，如果不能保证图连通，在这里首先判断一下权值是否是无穷大（或顶点保存的另一个顶点是否合法）,如果是（或否)，则说明图不连通，如果图不连通，该算法也可以求得每个连通子图的最小生成树，不过终止条件需要修改。至此这个算法已经基本完成了，我们在接下来讨论其它一些优化。我们注意到图的邻接矩阵表示是对称矩阵，也就是说一半是冗余的，可不可以把这一半的冗余去掉呢?这样时间和空间复杂度都有近一半的降低。我尝试了这样一种方法：用一维数组作二维数组用，只保存下三角部分。第 i 行第 j 个元素（ij)可用一维数组的第（i1)*i/2 个元素表示。每次访问二维数组时必须保证行大于列，否则把行和列调换。在访问每一条边时同时考虑两个方向.这样做我原以为是没问题的，后来发现还是有数据冲突的可能，因为在遍历边时同时考虑了两个顶点，而不能同时保证两个顶点不发生数据竞争.这里并不需要返回到完全的二维数组，我们可以每次只考虑边的一个顶点，这样时间复杂度没有明显的增加，但空间节省了一半，同样避免了数据冲突。由于串行算法可以不考虑数据竞争，因此无需考虑将按原边遍历改为按新边遍历（在测试中会发现效率相差很大)，也无需考虑将二维数组减半的时候的数据冲突。这样程序只在第一次对所有边进行了两次遍历,以后边集的规模以至少 1/4 的速率递减（点集以至少 1/2的速率递减）,总的时间复杂度不超过三次遍历所有边。可以说这个算法在最小生成树的串行算法中是比较优秀的了。在没有其他信息引入的情况下不可能有比这个快的多的算法。在下面的测试中我们将看到这个算法优于 Kruskal 算法。并行优化暂时谈到这里。至此算法的主要部分已经进行过并行优化了，其他部分也并不是不可以并行化，但有时候会得不偿失。如前面说的计算总的权值和记录所选择的边可以分线程做，在测试中发现当 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)(f）图二运行环境：(a）,（b），（e）Intel Dual E2160 1。80GHz，DDR2 667 内存 2G；(c)Intel Core i5 M450 2。40GHz；(d），(f)Intel core2 q6600 2。4GHz DDR2 800 内存 4G；操作系统（a），（b)，(c）,(d)windows7,(e）,(f）Ubuntu10.04 需要说明的是在测试(f）时并行明显没有 34s，CPU 系统监视如下：图二(f)运行时的 CPU 监视 可以看到 4 和运行的时间明显小于总的前面一个的运行时间.计时程序段如下：start=clock（）;spanningTreeParallel（A,N）；stop=clock（）;cout”time:tt”（(double）（stop start）/CLOCKS_PER_SEC）”snn;我认为时间应该是上面显示时间除以内核数，对于图二（e)也是。对比中可以看出，在双核中并行的的算法时间可以缩小近一半,但是跟不考虑数据冲突的串行算法近似，在四核中并行算法可以缩小 2/3 左右的时间。明显比不考虑数据冲突的串行算法还要好。四、分析 我们可以看出各种算法最终得到的结果都是完全相同的,只是时间上有些差别。Kruskal 算法所用的时间都要比其它算法长很多，当 N 从 2500 到5000 再到 10000 时，Kruskal 算法时间增长都是近 10 倍的，而其它算法增长都是六倍左右。解决冲突的串型算法比不解决冲突的要慢很多（第三种和第二种算法），用两个核比一个核所用时间的一半稍多一些。我们知道 Kruskal 算法对稀疏图效果比较好，Prim 算法更适合于边稠密的图.前面我们也提到了本文中的算法复杂度与边的数目有关，接近于遍历所有边所需时间的三倍。当边数目减小时所需时间也会相应减少.我们还提到过本文的算法对很多图的输入形式是接受的，效率不会有太大的差别。前面也引用过对于边稠密的图“两种算法复杂性没有什么差别”【1】我们前面提到算法二和三都是串行的，只是将按照原边的顺序遍历改为按新边的顺序遍历（同时还有在二维数组空间缩小时没改变时间复杂度，这影响相对较小），结果就发生了很大变化，我想其原因与存储有关。计算机的存储系统是按程序局部性原理分层次构造的，由于没按照存储顺序访问内存，Cache 失效的概率会很大，程序执行效率会受到很大影响.我们可以看到 DDR2667 的内存比DDR2-800 的内存影响更为明显.五、总结 通过上面的讨论，我们实现了最小生成树的快速并行算法，测试中发现这种算法还是不错的。在这个算法中，我们看到由于进程调度不可控制（只是没提供线程控制）以及程序局部性原理对多核程序性能的发挥有一定的障碍作用。多核应该是 CPU 及其他设备、操作系统、程序共同协调以最大限度发挥计算机的性能.六、参考文献【1】离散数学及其应用(原书第 5版）(美)Kenneth H.Rosen 著 袁崇义 等译，机械工业出版社 2008 年 7 月【2】多核计算与程序设计 郑伟明著 华中科技大学出版社 20093-1【3】并发程序设计基础教程 赵煜辉 等著 北京理工大学出版社 2008年 12 月第一版
