论文研究-基于GPU的并行最小生成树算法的设计与实现.pdf

所需积分/C币:5 2019-07-22 18:56:47 815KB .PDF

针对目前并行Prim最小生成树算法效率不高的问题,在分析现有并行Prim算法的基础上,提出了适于GPU架构的压缩邻接表图表示形式,开发了基于GPU的min-reduction数据并行原语,在NVIDIA GPU上设计并实现了基于Prim算法思想的并行最小生成树算法。该算法通过使用原语缩短关键步骤的查找时间,从而获得较高效率。实验表明,相对于传统CPU实现算法和不使用原语的算法,该算法具有较明显的性能优势。
1684 计算机应用研究 表分拆为三个数组(R1,R2,R3),便于充分利用 min-reduction用前都进行grid和 block的重新划分。在min- reduction步骤相 原语的效率。三个数组长度都为V-1,相同索引位置分别存关 kernel,中,为充分展开循环,使用C++模板技术,在可操作 放MsT中一条边的三个属性:输出顶点、输入顶点、权值。初元素数小于最大线程数时,视具体情况将hk内线程数划分 始化时存放顶点0至其他各顶点的边,若无相连边,用ma为以下各数之一:256、128、64、32、1684、2、1 weight填充。 算法完整描述 b)寻找最小权值边。使用 GPU min-reduction数据并行原 算法1 CUDA PRIM MST 语在R3中寻找最小值及其索引号,如图4所示。定义两个临 a)从输入文件中读取图数据,初始化数组E、V、W 时数组T1、T2,分别存放临时结果的最小权值与其索引号。具 b)在CPU内存中构建MST边表数组R1、R2、R3,并进行初始化,构 体过程分为 kernel1和 kernel2两步。其中, kernel1的结果存放建临时变量C,初始化为顶点0 于临时数组T、T2; kernel2为可选项,只有R3|> max block x c)将E、V、W、R1、R2、R3、C传输至GPU显存,构建临时数组T1、 max_threadsper__ block时才进行调用,调用时,与 kernel,不同 1)根据走行min- eduction操作的元素个数,配置 CUDA grid尺寸; 其操作对象为临时数组T、2,最终结果存放于T1[0]与T2 e)调用 kernel,结果写人T1、T2,若|R3'|≤max_ block x max [0]。在具体实现中,出于bok个数有最大限制,使用了静态共 reads_ per-block,则至步骤g); f)如果未得出min- -reduction最终结果,则调用 kernel2,结果放入T1 享内存,每个k分配空间大小为 i Imax_threads_per block I×2。 [0]、T2[0]; 长度:|-1 g)读取T1[0],T2[0],并将其代表的边和顶点加入MST边表,同 R引出顶点) 将新加人边另一顶点写入临时变量 h)根据行比较的元素个数,重新置 CUDA grid及 block尺寸; R2(引入顶点) 下MST边表 i)读取全局变量C,得到当前顶点号,通过查询E、V、W,计算C与 Rf(权重 各顶点的边权值; j)对每个顶点,若新权值<旧权值,则调整R1、R3对应值 c当前顶点 当前MST k)循环调用步骤d)~j),固定-2次,直至得出最终结果 1)将CPL显存内R1、R2、R3传输回CPU内存,作为MST边表结果 写入输出文件。 最小权值边 3实验测试 图4寻找最小权值边 加入新MST边。寻找到最小权值边后,个步骤读取T 3.1对比算法 [0]及T2[0],将最小权值边及其连接的顶点一起加人MsT。 选取两个对比算法:a) boost graph library(BGL)中的CPU 方法为将其交换到候选MT边表最前端,同样涉及到T、T2、 串行版本Pm算法实现;b)笔者开发的非原语的普通CUDA T3的同时调整。这一操作可能发生在两处:如果 kernel2执行 版本的Prim算法实现,与原语版本算法的区别是在寻找最小 值时采用普通GPU并行化。 则在 kernel2之后,若 kenrel2不执行则在 kernel之后。之后需 要保存当前顶点号,即R2[T2[0]],为此,需要定义全局变量C 3.2实验平台 进行保存。 Intel Pentium4 3 GHz CPU. 2 GB H/. NVIDIA GeForce GX260GU,8%6MB显存,Os为 Linux redhat5 本步骤的特殊之处在于前两步都可以多线稈并行执行,这 步由某一线程执行,防止访存冲突。 3.3来源数据 2.3.2降距操作( decrease- distance) 选取 GTgraph图数据生成套件中的 random生成工具,它 本步骤读取全局变量C,得到当前顶点号,通过查询图数生成的数据特点为:顶点的度数在一个小范围之间,很多顶点 貝有相似的度数。选取顶点数目为128~16384范围內的数据 据结构中的三个数组E、V、W计算其与每个顶点的边权值。假 作为算法输入数据,每项效据的边数一般为顶点数的10倍,边 设当前比较顶点索引号为n,计算结果用W.表示。若W<权值范围限定为1-lk。 R3[n,则调整边表:R1[n]=Wn,R1[n]=C。由于边表各组数 3.4实验结果 据元素独立不相关,调整边表可由GPU各线程并行执行。需 实验结果数据如图5和6所示。分析可知,非原语版本的 要指出的是,在查询图数据结构计算顶点C与顶点n之间的 CUDA程序在整体上性能低于 CPL BGL串行版本程序;在顶 边权值时,为避免wap内的线程产生分支,最好让所有线程都点数量大于40%6时,原语版本的CUDA程序性能高于其他两 查询C→n的边权值而不是n→C,这样可以在各线程加载数组个对比程序,并展现出稳定的优势。加速比如图5所示。分析 E和W中的C连接的边相关值至共享内存和查询共享内存时可知,在实验数据范围内,非原语版本的CUDA程序加速比低 获得尽可能多的一致性,这对于CUDA架构下的运行效率至关于1;原语版本的CUDA程序加速比在数据量大时大于1,最高 重要。 加速比约2倍,实际应用中可以考虑采用。实验结果展现了采 2.3.3外层循环调用 用数据并行原语方法在提升GPU程序性能方面的有效性。 外层循环调用即将上面两个步骤进行循环操作,直至算法 4结束语 结東。循环次数为固定值|V-2。为避免固定划分grid和 block带来的负载不均衡问题,采取动态分配的方法,即每次调 本文在GPU上设计和实现了基于Prim算(下转第1702页) 1702 计算机应用研究 第28卷 0.98 能力。此外,对于本文算法( ABC-CA)中适应度函数是最重要 的一环,将有待于进一步研究适应度函数(指标函数)的合理 0.92 性,从而设计更好的适应度两数,以提高算法性能。 0.84 参考文献: 0.82 0.8 12345678910 [1] HAN Jia-wei, KAMBER M. Data mining concepts and techniques 算法运行第n次 I M.2nd ed. [S1.1: Morgan Kaufmann Publishers, 2006 图3聚类准确率统计 1 2 DING C, LI Tao. Adaptive dimension reduction using discriminate 冋时,为表现 ABC-Cluster算法的聚类效果,本文选取IRS analysis and K-means clustering[ C]//Proc of the 24th International 数据中的两维特征和三维特征来进行描述,如图4和5所示 Conference on Machine Learning. New York: ACM Press, 2007: 5 其中点∨表示算法迭代获取的聚类中心,K1、2、K3表示该数 528 据集的特征值。 [ 3] SONG Le, SMOLA A, BORGWARDT K M. A dependence maximi zation view of clustering[ C//Proc of the 24th International Confe rence on Machine Learning. New york. A CM Press 2007 815-822 二5 [4]谢娟英,张,谢维信,等.一种新的密度加权粗袺K-均值聚类算 法[冂].山东大学学报:自然科学版,2010,45(7):1-6 L5」淦文燕,李德毅,王建民.一种基于数据场的层次聚类方法[J.电 1 子学报,2006,34(2):258-262 044.555566577.5 [6]张丽,刘希玉,李章全.基于蚁群算法的聚类优化[J].计算机工 x1特征值1 x特征值222特征值1 程,2010,36(9):190-194 图4二维特征聚类效果图5三维特征聚类效果图 [7]刘靖明,韩丽川,侯立文.一种新的聚类算法——裢子群聚类算法 从图4和5可以看出,本文算法能获取较好的聚类中心 [J].计算机工程与应用,2005,20(5):183-185 从而获得较为准确的分类。 [8 BASTURK B, KARABOCA D. An artificial bee colony (ABC)algo 仿真实验表明,本文算法充分发挥了蜂群算法良好的自组 rithm for nu function optimization[ C]// Proc of IEEE Swarm In 织性和收敛性,对聚类问题的聚类屮心进行搜索,在搜索过程 telligence Sy um Indian-apolis. 2006: 651-656 中引入紧密度指标和分离度指标来评价聚类有效性,可以获取 19 KARABOCA D, AKAY BB. Artificial bee colony algorithm on trai ning artificial neural networks C]//Proc of the 15th IEEE Signal 最佳聚类数K值,解决了K- means算法等划分聚类算法受聚类 Processing and CoinlmlunicaLiunIs Applicalions Conference. 2007: 1-4 数K影响的缺点,通过聚类准确率检验,虽然算法表现出不太10 I KARABOCA D, BASTURK B. Artificial bec colon(ABC)oimi 稳定的缺点,但是在实验过程中算法的最差解仍然表现出算法 zation algo for solving constrained optimization problems[C// 的高有效性,这就从整体上验证了算法的可行性。 Proe of the Internalional Fuzzy Systens A gress on Foundations of Fuzzy Logic and Soft Camputing. Berlin 4结束语 pringer-Verlag, 2007: 789-798 [11 KARABOGA D, BASTURK B. On the perfurlllance of artificial bee 本文基于蜂群原理提出了一种新型的划分聚类算法,可以 colony( ABC) algorithm[ J]. Applied Soft Computing, 2008, 8 在不用给定聚类数K值的前提下,自动搜索最佳聚类数,实现 自适应聚类过程。实验表明,算法不仅对最佳聚类数有良好的[12]暴励,曾建潮,自适应搜索空间的混沌蝼群算法[J,计算机应用 确定能力,而且与其他经典聚类算法比较也表现出良好的分类 研究,2010,27(4):1330-1334 (上接第1684页)法思想的MST算法,并使用了自己开发的GPL rence on High Perform ance Computing. 2009: 1-5 min- reduction数据并行原语对算法的关键步骤进行了表示。[2] EKATERINA G, AXMIKANT V K. Parallel Prim s algorithm on 与CPU串行程序和非原语GPU程序的对比表明,使用原语的 dense graphs with a novel extension[ R]. Urbana: University of Illinois GPU程序明显提高∫算法性能。笔者认为,在使用GPU设备 at Urbana Champaign, 2007 解决图论计算几何等非规则间题时,数据并行原语的使用对31 BADER D A, CONG Guo-jing. Fast shared-me mory algorithms for 于提高性能可以起到关键的帮助作用。在下一步工作中,将研 com puting the minimum spanning forest of sparse grap of Parallel and Distributed Computing, 2006, 66(11): 1366-1378 究GPU上数据并行原语在其他图论算法中的应用 [4 VUDUCY R, CHANDRAMO WLISHWARANY A, CHOI J, et aL.On 时间m 0 时间(r 1200 thelimitsofGplacceleration[eb/ol].(2010).http://Www.Use 1000+cUDA_Nn_R-durtinn 1.81-+CUDA N Reduetion 一CUDA_ Reduction 一 CUDA Reduction nlx. ors/ eve nt/hotpar10/tech/ full_papers/Vuduc pdlf 800 [5 HARRIS M. Optimizing parallel reduction in CUDA LEB/OL 顶点数 顶点数 2007).http://developer.download.nvidiacom/compite/cuda/i 0 51220488192 12851220488192 1/Website/Data-Parallel Algorithms. html 图5算法运行时间对比 图6两种 CUDA Prim算法 L 6 VINEET V, HARISH P, PATIDAR S, ct al. Fast minimum sp 加速比对比 tree for large graphs on the GPU C]//Proc of Conference on High 参考文献: Performance Graphics. New York: ACM Press, 2009: 167-171 [1] ROHIT S, ARUN N, SHANKAR B. A new parallel algorithm for [7 BULLUC A Linear algebraic primitives for parallel computing on large minimum spanning tree problem[ C]//Proc of International Confe graphs[ D]. Santa Barbara: L niversity of California, 2010

...展开详情
试读 4P 论文研究-基于GPU的并行最小生成树算法的设计与实现.pdf
img

关注 私信 TA的资源

上传资源赚积分,得勋章
    最新推荐
    论文研究-基于GPU的并行最小生成树算法的设计与实现.pdf 5积分/C币 立即下载
    1/4
    论文研究-基于GPU的并行最小生成树算法的设计与实现.pdf第1页
    论文研究-基于GPU的并行最小生成树算法的设计与实现.pdf第2页

    试读已结束,剩余2页未读...

    5积分/C币 立即下载 >