最小生成树的多核并行算法

《最小生成树的多核并行算法》由会员分享，可在线阅读，更多相关《最小生成树的多核并行算法（6页珍藏版）》请在金锄头文库上搜索。

1、最小生成树的多核并行算法马成刚（09008230）摘要：最小生成树是图论中的经典问题，在现实生活中也有很多应用本文讨论一种最小生成树的多核并行算法。关键字：最小生成树；索林算法；一、介绍最小生成树问题是图论中的一个 经典问题，也是众多广泛应用的问题 之一。关于最小生成树问题已有一些 经典的算法，如：Prim算法、Kruskal 算法，都具有近线性的算法复杂度。 对于稀疏图来说，使用 Kruskal 算法更 好，否则两种算法复杂性没有什么区 别【1】。Prim算法每次选择一个顶点， Kruskal 算法每次选择一条边，下一个 顶点或边是否选择与以前选的顶点或 边有关，这样都不适合于并行计算， 即

2、当今的多核计算机不能太大提高计 算效率。本文介绍一种基于Sollin算法 的求解最小生成树的多核并行算法， 能够提高求最小生成树的并行效率。二、算法先给出 Sollin 算法 从连通带权简单图（V, E）这样 产生最小生成树：相继地添加成组的边。 假定对V里的顶点进行了排序，这样就产 生了一个顺序，其中若u先于u，或者若01uo=ui并且町先于贝巧先于他， v 。这个算法首先同时选择每个顶点关联 1 的权最小的边。在平局的情形下选择在上 述顺序里的第一条边。这样就产生了一个 没有简单回路的图，即一些树组成的森 林。其次，对森林里的每棵树，同时选择 在该树里的一个顶点与在不同的一棵树 里顶点之间

3、最短的边。同样在平局的情况 下选择在上述顺序下的第一条边（。这样 就产生了一个没有简单回路的图，它包含并行着比在这一步之前出现的更少的边树）继 续进行同样的添加树的过程，指导已选择 了 n1 条边为止。（摘自【1】第576 页）以我对该算法的理解，该算法可 以分为三个步骤：选择边、合并顶点、 合并边依次循环直到结束。选择边即 选择连接每个顶点的权值最小的边， 在相同权值的情况下选序号小的；合 并顶点将通过选择的边的连通的树中 的所有顶点合并成一个新的顶点，进 入下一次循环；合并边（在原算法中 并没有）用新顶点之间边的权值代替 原来树中所有顶点与另一棵树所有顶 点之间边的权的最小值，以避免重复

4、查看比较。我没有见过对 Sollin 算法的证明， 但这是很简单的。这里给出 Sollin 算法 正确性的简单证明。先证明每个顶点关联的权最小的 边至少有一个（对有相同的）最终被 选到最小生成树中。用反证法如果一 个顶点关联的最小的边不被选到最小 生成树中，则在最小生成树中添加这 条边一定会出现环，这个顶点有两条 边在环上。可以去掉其中一条使其成 为树。除非这两条边的权值相同即都 为最小的边，否则去掉另一条边（不 是最小的边）得到的树比最小生成树 的总权值小，违反了最小生成树的定 义。在证明不会有环产生。点合并和边合并明显不会有环产生。如果产生了环，假设vy,., v构成了环，则是1 2 n

5、v1选择了边（vl, v2）, v2选择了边（v2, v3） . 或反向。由于选择的边都是各 个顶点关联的最小权的边，则有 w12 沁23沁34八沁12（%表示边M，叩 的权值），则 w12=w23=w34=.=w12。同 理，反向也可以得到相同的结论。又 由于规定当权值相同时选择序号小的 边，如果有环必不符合这条规则。因 此可以证明不会出现环。最后证明算法一定会终止。表示 算法终止可以用选了 n-1 条边，也可以 用最后剩下一棵树，易证明两个条件 是等价的。在每一次循环，至少是两 个顶点结合成一棵树，再把树合并成 新顶点，这样顶点数目就减少了一半。 循环进行，顶点一定会变为1。 （由此 可见

6、，该算法的复杂度是线性的） 接下来我们分别就每个步骤讨论 一下其并行实现。1. 选择边申请数组存放每一个顶点连 接到的边的最小值和所对应的边， 对所有边进行遍历，找到连接到各 个顶点的最小权值和对应的边。我 们知道，图的边的存储方式可以是 多种多样的，如邻接表，邻接矩阵， 再次为方便采用邻接矩阵讨论，此 算法也同样适合其他表示方式，而 且效率不会相差太大。对于一个邻接矩阵，可以对每 一个顶点并行的求其最小值。按下 标从小到大依次遍历，同时可以保 证相同权值下标最小。2. 合并顶点将通过选择的边的连通的所 有顶点合并成一个新的顶点，进入 下一次循环。这里用数组实现的链 表。对于每一个顶点分配一个

7、 int 型空间，保存与它相邻的一个顶点 的索引。为了便于对联标处理，这 里规定，每个顶点保存的顶点的索 引必须小于该顶点的索引。接下来 将原顶点与新顶点对应，即原顶点 保存新顶点的索引。用nn表示新 的顶点个数，对链表从小到大遍 历，如果不是指向下一个顶点，那 么它就是第一个对应新的索引为 nn 的顶点，新顶点数 nn 加一。由 于已经规定链表中的相邻顶点的 索引小于当前顶点的索引，可以直 接把链表中相邻顶点对应的新顶 点的索引给当前顶点。3. 合并边生成新的邻接表权值设为无 穷大，遍历当前图的每一条边，如 果这条边的两个顶点对应同一个 新顶点则跳过。否则判断是否比当 前新的邻接表中对应的两

8、个新顶 点确定的边的权值小，如果是，则 更新新的邻接表中这条边的权值。在这个算法中很多地方都用 求最小值。在看多核计算与并行 程序设计【2】有关lock-free算法 的介绍，即多个线程同时访问同一 块资源时（比如同时写），能保证 至少有一个线程操作的结果是正 确的，其他线程判断操作是否正 确，如果不正确，则重复操作。对 于求数组最小值，可不可以循环判 断目标值是否比要写的数值大，如 果是则写入，不是就跳过？这样做 很容易想到的一个问题是线程调 度，如果判断过之后要写，但是写 之前线程发生了切换，当其他线程 将自己发现的最小值写入后，这个 线程恢复执行，不加判断地将等待 写入的值写入，就可能出

9、错了（其 实这样的概率是很小的，我在测试 的时候没有发现过出错，前提是线 程数不要太多）。可不可以控制线 程在某一段内不被打断或打断之 后回到段首开始执行，我以为原子 操作是【2】，后来发现那是针对特 定操作的。希望操作系统和 CPU 尽 快提供对求数组最小值的 lock-free 算法的支持。没有 lock-free 算法，也是加锁 是不可接受的。比如说对一个有 10000 个点的完全图，权值是 065535 随机（测试是这样的）需 要第一次合并有 nn 个顶点（测试 结果接近2500）,这样需要（nn-1） *nn/2把锁，总共开合（10000-1） *10000/2 次，这样时间和空间代

10、价 都是不可接受的。在此提出一种解决方法：将访 问同一块内存的操作交给同一个 线程做，这样线程既可以并行，又 可以避免冲突。这样需要对第二步 合并顶点进行修改，即对指向相同 新的顶点的原顶点的表示做修改， 使能够很快找到指向相同顶点的 原顶点，一种很好的实现方式就是 链表了。在上面的基础上进行以下 操作：申请一个长度为 nn 的 int 型 数组head,作为新顶点指向原顶点 的头指针，初始化为-1。对原数组 从后向前遍历，对每一个原顶点， 将对应新顶点 head 里的值给原顶 点的链表，将原顶点的索引赋给对 应新顶点的head，这样head里的 值就是当前遍历到的对应于该新 顶点的最前面一个

11、原顶点，原顶点 的链表指向下一个指向相同新顶 点的原顶点，这其实就是建立链表 的过程。在第三步合并边中，将按 原邻接表遍历改为按新邻接表遍 历，对于新邻接表中的每一条边的 两个顶点，可以很快由链表找到对 应它的所有原顶点。这样并没有增 加很多工作，但测试时会发现效率 明显降低，这将在下面讨论。对于一个这个算法，最耗时间 的就是对二维数组的遍历，但求一 个图的最小生成树最少也要将图 中各边遍历一次。那可否只遍历一 次呢？我没想到只遍历一次的方 法，但由此我考虑到了这个算法一 个可以优化的地方，将合并边的操 作同下一次求每个顶点最小权的 关联边，即在合并边的同时求出每 个顶点最小权的关联边，由此减

12、少 了一次遍历。至此这个算法的大体框架已 经完成，不过现实中用户还想要知 道最小生成树的总权值，以及最小 生成树里的边。在第一步已经找到 了各个顶点关联的权值最小的边， 同时也保存了最小的权值。在对算 法介绍中已经说明这些边不构成 环，而且都是最终的最小生成树中 的边。但这些边中有重复的，如顶 点 A、B 关联的最小权值的边都是 边AB，那么A就会保存B,同时B 保存A。可以证明有且仅有这一种 情况。这样遍历到 A 时只需看一下 A 保存的顶点里保存的是不是 A 就 可以了。在这里约定如果出现上述 情况，在遍历到序号较大的顶点时 才将这条边加入所选边集中，同时 将所选边的权值加入总权值中。这

13、样当遍历到一个顶点时，如果它保 存的那另一个顶点的序号小于它 的序号，就可以直接把这条边和它 的权值加入边集和权值总和中（算 法已经约定相同权值的情况下取 序号小的），否则才判断是否是上 述情况，不是的话也加入边和权。 这一步也可并行计算，还可以再开 一个线程来完成。这里附带说明一下，如果不能保 证图连通，在这里首先判断一下权值 是否是无穷大（或顶点保存的另一个 顶点是否合法），如果是（或否），则 说明图不连通，如果图不连通，该算 法也可以求得每个连通子图的最小生 成树，不过终止条件需要修改。至此这个算法已经基本完成 了，我们在接下来讨论其它一些优 化。我们注意到图的邻接矩阵表 示是对称矩阵，

14、也就是说一半是冗 余的，可不可以把这一半的冗余去掉呢？这样时间和空间复杂度都 有近一半的降低。我尝试了这样一 种方法：用一维数组作二维数组 用，只保存下三角部分。第 i 行第 j个元素（ij）可用一维数组的第 （i-1） *i/2个元素表示。每次访问 二维数组时必须保证行大于列，否 则把行和列调换。在访问每一条边 时同时考虑两个方向。这样做我原 以为是没问题的，后来发现还是有 数据冲突的可能，因为在遍历边时 同时考虑了两个顶点，而不能同时 保证两个顶点不发生数据竞争。这 里并不需要返回到完全的二维数 组，我们可以每次只考虑边的一个 顶点，这样时间复杂度没有明显的 增加，但空间节省了一半，同样避

15、 免了数据冲突。由于串行算法可以不考虑数 据竞争，因此无需考虑将按原边遍 历改为按新边遍历（在测试中会发 现效率相差很大），也无需考虑将 二维数组减半的时候的数据冲突。 这样程序只在第一次对所有边进 行了两次遍历，以后边集的规模以 至少 1/4 的速率递减（点集以至少 1/2 的速率递减），总的时间复杂度 不超过三次遍历所有边。可以说这 个算法在最小生成树的串行算法 中是比较优秀的了。在没有其他信 息引入的情况下不可能有比这个 快的多的算法。在下面的测试中我 们将看到这个算法优于 Kruskal 算 法。并行优化暂时谈到这里。至此 算法的主要部分已经进行过并行 优化了，其他部分也并不是不可以

16、并行化，但有时候会得不偿失。如 前面说的计算总的权值和记录所 选择的边可以分线程做，在测试中 发现当 N=5000 时，用 Intel Thread Profiler 显示新的线程执行时间是 0.00016s，但明显的开线程的时间 比线程执行时间要长得太多了。用 openmp 并行也是可以做的，不过 优化不是很明显，其它还有一些地 方也是可以并行化的，有兴趣的读 者可以尝试，或者是尝试加锁。三、测试为便于测试这里只需要输入顶点 的个数N,程序用随机数填补所有边的 权值，默认为完全图.1. 本文算法与 Kruskal 算法比较 输出依次是Kruskal算法的输 出、串行算法的输出（没考虑数据 冲突解决）、并行算法单核执行（考 虑了数据冲突解决）、和并行算法 执行的输出。每个输出都包括总权 值、所选边数和执行时间。对于后 两种还要先输出使用的核数（其实 是线程数，在并行算法中令线程数 等于核数）。N=1000