首页 基于GPU的并行最小生成树算法的设计与实现.pdf

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

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

上传者: 士大夫上 2011-12-19 评分1 评论0 下载29 收藏0 阅读量958 暂无简介 简介 举报

简介:本文档为《基于GPU的并行最小生成树算法的设计与实现pdf》,可适用于专题技术领域,主题内容包含收稿日期:修回日期:基金项目:国家“”计划重点资助项目(AA)上海市科委重大科技攻关资助项目(dz)作者简介:郭绍忠()女安徽合肥人副教授硕导主要研符等。

收稿日期:修回日期:基金项目:国家“”计划重点资助项目(AA)上海市科委重大科技攻关资助项目(dz)作者简介:郭绍忠()女安徽合肥人副教授硕导主要研究方向为分布式计算(xygsz.com)王伟()男山东泰安人硕士研究生主要研究方向为分布式计算、GPU通用计算王磊()男陕西临潼人讲师硕士主要研究方向为分布式计算、GPU通用计算.基于GPU的并行最小生成树算法的设计与实现*郭绍忠王伟王磊(解放军信息工程大学信息工程学院郑州)摘要:针对目前并行Prim最小生成树算法效率不高的问题在分析现有并行Prim算法的基础上提出了适于GPU架构的压缩邻接表图表示形式开发了基于GPU的minreduction数据并行原语在NVIDIAGPU上设计并实现了基于Prim算法思想的并行最小生成树算法。该算法通过使用原语缩短关键步骤的查找时间从而获得较高效率。实验表明相对于传统CPU实现算法和不使用原语的算法该算法具有较明显的性能优势。关键词:图形处理器图论最小生成树Prim算法数据并行原语中图分类号:TP.文献标志码:A文章编号:()doi:.j.issn....DesignandimplementationofGPUbasedparallelminimumspanningtreealgorithmGUOShaozhongWANGWeiWANGLei(InstituteofInformationEngineeringPLAInformationEngineeringUniversityZhengzhouChina)Abstract:ConsideringcurrentparallelPrim’sMSTalgorithms’limitedspeedupbasedonanalyzingexistingparallelMSTalgorithmsthispaperusedcompressadjacencylistgraphrepresentationsuitedtoGPUarchitecturedevelopedGPUbasedminreductiondataparallelprimitiveanddesignedparallelPrim’sMSTalgorithmonNVIDIAGPU.Thealgorithmshortenedthefindingtimeviausingprimitivesinthekeystepsoachievedhigherefficiency.ExperimentalresultsshowthatitobtainsevidentperformanceimprovementoverthetraditionalCPUimplementationandnonprimitivesGPUimplementation.Keywords:GPUgraphictheoryminimumspanningtree(MST)Prim’salgorithmdataparallelprimitive最小生成树(MST)是图论中的一个基本概念定义为:给定一个具有权值映射关系w:ER的无向图G=(VE)求一个具有|E'|=|V|-关系的连通子图T=(VE'E)使得eE'w(e)最小化。MST问题在网络规划、旅程问题及VLSI布局等许多领域发挥重要作用。Prim算法是最常用的MST算法之一目前对Prim算法的研究和使用以串行为主并行Prim算法相关研究较少且加速效果不理想[~]在图规模较大时问题尤其突出。利用GPU进行应用程序加速是近年来的一个重要趋势。GPU具有计算能力强、价格低廉等优点CUDA、OpenCL等新型开发环境的出现大大降低了GPU编程的难度大量利用GPU进行应用程序加速的例子纷纷出现。由于自身架构的特殊性GPU加速效果良好的程序大多为规则问题诸如图论、计算几何等非规则问题在GPU上的加速效果并不令人满意[]。MST属于非规则问题据笔者所知利用GPU进行Prim算法并行化的研究较为少见。使用数据并行原语将不规则问题映射到GPU是解决此类问题的一个有效解决方案。本文在CUDA环境下使用新开发的数据并行原语对Prim算法进行GPU并行化设计与实现取得了较好的加速效果。相关工作并行Prim算法由于具有内在的顺序性Prim算法的外层while循环难以并行化但是其内层的两个循环步骤可以进行并行求解。两个内层循环为:求当前候选边集中的最小权值边以及加入新点后比较并更新候选边集。到目前为止对Prim算法进行并行化的研究并不多见。文献[]针对具有共享内存的SMP结构提出了一种并行Prim算法取得了至多.倍的加速效果文献[]在MPI环境下提出了一种一次迭代增加多个顶点的并行Prim算法取得了较好的加速效果文献[]提出了一种借鉴Prim算法思想的并行MST算法也取得了一定的加速比。相对于另一种MST算法Boru。vka算法的并行版本这些算法的共同问题是加速比不高在图规模较大时尤其突出。基于GPU的数据并行原语数据并行原语是指在开发并行程序时常用的基本并行操作如scan、sort、reduction等。在不规则问题的GPU并行化过程中数据并行原语的使用可以提高运行效率。文献[]提出第卷第期年月计算机应用研究ApplicationResearchofComputersVol.No.May了GPU上的基于CUDA的reduction原语实现方法文献[]指出在GPU程序中运用sort、reduction等数据并行原语并且将问题的不规则步骤映射到这些原语或其组合之上可以提高程序的运行效率。文献[]将原语应用于求解诸如图聚类、子图提取等图论问题获得了一定的加速比。设计与实现压缩邻接表的设计传统的图数据结构包括邻接矩阵与邻接表两种。邻接矩阵适用于稠密图表示但存储空间O(|V|)要求太高而GPU设备端的显存空间相对有限所以不适用于本文的设计邻接表适用于稀疏图表示存储空间要求仅为O(|V||E|)。在CUDA架构中设备端内存空间都被视为数组对数组可以进行高效的读写操作。基于以上分析本文对传统邻接表进行改进提出一种适用于GPU的纯数组形式的压缩邻接表。如图所示压缩邻接表包含三个数组:顶点数组V、边数组E、权值数组W。V长度为|V|每一个元素指向其连接顶点在E和W中的开始位置V和E保存相关联的顶点号及相应边的权值由于MST处理的是无向图E与W长度都为|E|。GPUminreduction原语的设计Reduction数据并行原语是指对一组数据元素进行某种特定操作(如求和、乘积、最小值等)最终得出一个元素的并行处理过程。本文对文献[]提出的GPUsumreduction原语进行了扩展得出改进的GPUminreduction。改进与扩展改进主要体现在三方面:a)待比较数组的元素个数不限于的乘方可为任意数b)只需要至多两步kernel调用即可得出最终比较结果c)在比较过程中添加了index数组结果包括最小权值和对应index。改进的GPUminreduction原语包含全局内存和共享内存比较两种。重要变量及数组的名称及作用如表所示。全局内存比较图所示为GPUminreduction的全局内存比较用于kernel。由于线程对全局内存的存取改为以数组长度为边界从而不限制其长度为的乘方。以少量性能损失换取更高的灵活性从而能够更好地适用于Prim算法等比较元素长度不固定的特点由于规定了maxblocks可以预估调用kernel后的临时结果个数从而使得至多在调用kernel后即可完成最终比较便于主机端调用。表重要变量及数组名称作用V、E、W存放顶点集、边集、权值集R、R、R共同表示MST边表集分别为引出点、引入点、权值T、T临时数组存放minreduction结果最小权值与索引号R'R中当前用于比较的权值集部分C全局变量存放最近加入MST的边的R顶点kernel、kernelminreduction的两个CUDAkernel调用共享内存比较图所示为GPUminreduction的共享内存比较用于kernel的后半部分和kernel。由于在进行候选边集调整时需要用到最小权值边索引号在比较全过程中添加了index数组。在这里用到了两个技巧:a)相邻thread操作相邻元素避免了共享内存的bankconflictb)由于一个warp内的运算总是能满足顺序一致性在最后个线程比较时取消syncthreads()减少同步操作性能损耗。算法的设计与实现Prim算法是一种贪心算法。它开始选取图中任一顶点作为MST根节点然后通过增加距离当前树最近(即最小权值边)的顶点来逐渐增长树并将其连接的最小权值边也增加到树中。当所有顶点都增加到MST中时算法结束。本文实现基于CUDA.架构算法输出为MST边表。增长MSTa)初始化MST边表。将传统Prim算法中的结果MST边第期郭绍忠等:基于GPU的并行最小生成树算法的设计与实现表分拆为三个数组(RRR)便于充分利用minreduction原语的效率。三个数组长度都为|V|-相同索引位置分别存放MST中一条边的三个属性:输出顶点、输入顶点、权值。初始化时存放顶点至其他各顶点的边若无相连边用maxweight填充。b)寻找最小权值边。使用GPUminreduction数据并行原语在R'中寻找最小值及其索引号如图所示。定义两个临时数组T、T分别存放临时结果的最小权值与其索引号。具体过程分为kernel和kernel两步。其中kernel的结果存放于临时数组T、Tkernel为可选项只有|R'|>maxblockmaxthreadsperblock时才进行调用调用时与kernel不同其操作对象为临时数组T、T最终结果存放于T[]与T[]。在具体实现中由于block个数有最大限制使用了静态共享内存每个block分配空间大小为|maxthreadsperblock|。c)加入新MST边。寻找到最小权值边后本步骤读取T[]及T[]将最小权值边及其连接的顶点一起加入MST。方法为将其交换到候选MST边表最前端同样涉及到T、T、T的同时调整。这一操作可能发生在两处:如果kernel执行则在kernel之后若kenrel不执行则在kernel之后。之后需要保存当前顶点号即R[T[]]为此需要定义全局变量C进行保存。本步骤的特殊之处在于前两步都可以多线程并行执行这一步由某一线程执行防止访存冲突。降距操作(decreasedistance)本步骤读取全局变量C得到当前顶点号通过查询图数据结构中的三个数组E、V、W计算其与每个顶点的边权值。假设当前比较顶点索引号为n计算结果用Wn表示。若Wn<R[n]则调整边表:R[n]=WnR[n]=C。由于边表各组数据元素独立不相关调整边表可由GPU各线程并行执行。需要指出的是在查询图数据结构计算顶点C与顶点n之间的边权值时为避免warp内的线程产生分支最好让所有线程都查询Cn的边权值而不是nC这样可以在各线程加载数组E和W中的C连接的边相关值至共享内存和查询共享内存时获得尽可能多的一致性这对于CUDA架构下的运行效率至关重要。外层循环调用外层循环调用即将上面两个步骤进行循环操作直至算法结束。循环次数为固定值|V|-。为避免固定划分grid和block带来的负载不均衡问题采取动态分配的方法即每次调用前都进行grid和block的重新划分。在minreduction步骤相关kernell中为充分展开循环使用C模板技术在可操作元素数小于最大线程数时视具体情况将block内线程数划分为以下各数之一:、、、、、、、、。算法完整描述算法CUDAPRIMMSTa)从输入文件中读取图数据初始化数组E、V、Wb)在CPU内存中构建MST边表数组R、R、R并进行初始化构建临时变量C初始化为顶点c)将E、V、W、R、R、R、C传输至GPU显存构建临时数组T、Td)根据进行minreduction操作的元素个数配置CUDAgrid尺寸e)调用kernel结果写入T、T若|R'|maxblockmaxthreadsperblock则至步骤g)f)如果未得出minreduction最终结果则调用kernel结果放入T[]、T[]g)读取T[]T[]并将其代表的边和顶点加入MST边表同时将新加入边另一顶点写入临时变量Ch)根据进行比较的元素个数重新配置CUDAgrid及block尺寸i)读取全局变量C得到当前顶点号通过查询E、V、W计算C与各顶点的边权值j)对每个顶点若新权值<旧权值则调整R、R对应值k)循环调用步骤d)~j)固定|V|-次直至得出最终结果l)将GPU显存内R、R、R传输回CPU内存作为MST边表结果写入输出文件。实验测试对比算法选取两个对比算法:a)boostgraphlibrary(BGL)中的CPU串行版本Prim算法实现b)笔者开发的非原语的普通CUDA版本的Prim算法实现与原语版本算法的区别是在寻找最小值时采用普通GPU并行化。实验平台IntelPentiumGHzCPUGB内存NVIDIAGeForceGTXGPUMB显存OS为LinuxRedHat。来源数据选取GTgraph图数据生成套件中的random生成工具它生成的数据特点为:顶点的度数在一个小范围之间很多顶点具有相似的度数。选取顶点数目为~范围内的数据作为算法输入数据每项数据的边数一般为顶点数的倍边权值范围限定为~k。实验结果实验结果数据如图和所示。分析可知非原语版本的CUDA程序在整体上性能低于CPUBGL串行版本程序在顶点数量大于时原语版本的CUDA程序性能高于其他两个对比程序并展现出稳定的优势。加速比如图所示。分析可知在实验数据范围内非原语版本的CUDA程序加速比低于原语版本的CUDA程序加速比在数据量大时大于最高加速比约倍实际应用中可以考虑采用。实验结果展现了采用数据并行原语方法在提升GPU程序性能方面的有效性。结束语本文在GPU上设计和实现了基于Prim算(下转第页)计算机应用研究第卷同时为表现ABCCluster算法的聚类效果本文选取IRIS数据中的两维特征和三维特征来进行描述如图和所示其中点表示算法迭代获取的聚类中心X、X、X表示该数据集的特征值。从图和可以看出本文算法能获取较好的聚类中心从而获得较为准确的分类。仿真实验表明本文算法充分发挥了蜂群算法良好的自组织性和收敛性对聚类问题的聚类中心进行搜索在搜索过程中引入紧密度指标和分离度指标来评价聚类有效性可以获取最佳聚类数K值解决了Kmeans算法等划分聚类算法受聚类数K影响的缺点通过聚类准确率检验虽然算法表现出不太稳定的缺点但是在实验过程中算法的最差解仍然表现出算法的高有效性这就从整体上验证了算法的可行性。结束语本文基于蜂群原理提出了一种新型的划分聚类算法可以在不用给定聚类数K值的前提下自动搜索最佳聚类数实现自适应聚类过程。实验表明算法不仅对最佳聚类数有良好的确定能力而且与其他经典聚类算法比较也表现出良好的分类能力。此外对于本文算法(ABCCA)中适应度函数是最重要的一环将有待于进一步研究适应度函数(指标函数)的合理性从而设计更好的适应度函数以提高算法性能。参考文献:[]HANJiaweiKAMBERM.Dataminingconceptsandtechniques[M].nded.[S.l.]:MorganKaufmannPublishers.[]DINGCLITao.AdaptivedimensionreductionusingdiscriminateanalysisandKmeansclustering[C]ProcofthethInternationalConferenceonMachineLearning.NewYork:ACMPress:.[]SONGLeSMOLAABORGWARDTKM.Adependencemaximizationviewofclustering[C]ProcofthethInternationalConferenceonMachineLearning.NewYork:ACMPress:.[]谢娟英张琰谢维信等.一种新的密度加权粗糙K均值聚类算法[J].山东大学学报:自然科学版():.[]淦文燕李德毅王建民.一种基于数据场的层次聚类方法[J].电子学报():.[]张丽刘希玉李章全.基于蚁群算法的聚类优化[J].计算机工程():.[]刘靖明韩丽川侯立文.一种新的聚类算法粒子群聚类算法[J].计算机工程与应用():.[]BASTURKBKARABOGAD.Anartificialbeecolony(ABC)algorithmfornumericfunctionoptimization[C]ProcofIEEESwarmIntelligenceSymposiumIndianapolis.:.[]KARABOGADAKAYBB.Artificialbeecolonyalgorithmontrainingartificialneuralnetworks[C]ProcofthethIEEESignalProcessingandCommunicationsApplicationsConference.:.[]KARABOGADBASTURKB.Artificialbeecolony(ABC)optimizationalgorithmforsolvingconstrainedoptimizationproblems[C]ProcofthendInternationalFuzzySystemsAssociationWorldCongressonFoundationsofFuzzyLogicandSoftComputing.Berlin:SpringerVerlag:.[]KARABOGADBASTURKB.Ontheperformanceofartificialbeecolony(ABC)algorithm[J].AppliedSoftComputing():.[]暴励曾建潮.自适应搜索空间的混沌蜂群算法[J].计算机应用研究():.(上接第页)法思想的MST算法并使用了自己开发的GPUminreduction数据并行原语对算法的关键步骤进行了表示。与CPU串行程序和非原语GPU程序的对比表明使用原语的GPU程序明显提高了算法性能。笔者认为在使用GPU设备解决图论、计算几何等非规则问题时数据并行原语的使用对于提高性能可以起到关键的帮助作用。在下一步工作中将研究GPU上数据并行原语在其他图论算法中的应用。参考文献:[]ROHITSARUNNSHANKARB.Anewparallelalgorithmforminimumspanningtreeproblem[C]ProcofInternationalConferenceonHighPerformanceComputing.:.[]EKATERINAGLAXMIKANTVK.ParallelPrim’salgorithmondensegraphswithanovelextension[R].Urbana:UniversityofIllinoisatUrbanaChampaign.[]BADERDACONGGuojing.Fastsharedmemoryalgorithmsforcomputingtheminimumspanningforestofsparsegraphs[J].JournalofParallelandDistributedComputing():.[]VUDUCYRCHANDRAMOWLISHWARANYACHOIJetal.OnthelimitsofGPUacceleration[EBOL].().http:www.usenix.orgeventhotpartechfullpapersVuduc.pdf.[]HARRISM.OptimizingparallelreductioninCUDA[EBOL].().http:developer.download.nvidia.comcomputecudaWebsiteDataParallelAlgorithms.html.[]VINEETVHARISHPPATIDARSetal.FastminimumspanningtreeforlargegraphsontheGPU[C]ProcofConferenceonHighPerformanceGraphics.NewYork:ACMPress:.[]BULLUCA.Linearalgebraicprimitivesforparallelcomputingonlargegraphs[D].SantaBarbara:UniversityofCalifornia.计算机应用研究第卷

职业精品

(汽车)产品营销策划书范文.doc

HH牙膏营销方案策划书.doc

加班管理人力资源考勤管理系统方案.doc

物品采购管理制度-正式.doc

用户评论

0/200
    暂无评论
上传我的资料

精彩专题

相关资料换一换

资料评价:

/ 4
所需积分:5 立即下载

意见
反馈

返回
顶部