基于gpu若干图问题加速算法的研究

《基于gpu若干图问题加速算法的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号⋯⋯⋯⋯⋯⋯⋯UDC密级．⋯公⋯无⋯⋯舅毋声夕擎硕士研究生学位论文基于6PU的若干图问题加速算法的研究申请人：学号：培养单位：学科专业：研究方向：指导教师：完成日期：王仁达2100787计算机科学技术学院计算机应用技术并行计算郭龙江教授2013年4月10日中文摘要图论是离散数学的一个分支，凡有二元关系的系统，图论均可提供一种数学模型，因而它在许多科学领域中具有越来越重要的地位。图论的很多问题在实现上都异常复杂，大多图问题都是指数级时间复杂度甚至是NP完全问题，并且随着问题的规模急剧增大，传统的串行算法往往不能满足实际问题的需要。传统

2、的分布式计算(如集群)虽然能够在一定程度上的提高性能，但是这种模型组织较为松散，对算法自身的提高有限，并且会增加功耗及通信开销。图形处理器(GPU)具有很强的并行处理能力以及低廉的成本，并且能够处理的问题规模越来越大，因此利用GPU解决图问题已经成为当前的研究热点。本文选择了两个具有代表性的图问题进行研究：图同构、最dxsteiner树。对于图同构问题，目前最有效的一类算法一标准标签法要么适合处理随机性或对称性强的图，要么适合处理两者均不强的图，并且其最核心的操作独立．精炼及证书比较通常占据总时间的70％以上，如何削弱对图的结构的局限性并

3、提高这些操作的效率是具有挑战性的。本文提出了一种高效的图同构算法：PEACE，能够有效地削弱结构对算法的影响，尤其适合处理对称度很高的图。本文同时第一次提出了图同构算法在GPU下的并行实现方法。本文将核心的操作并行化，设计了一些新的方法并利用了一些现有的技术实现CUDA下的加速计算，这些技术能够适用于所有基于独立．精炼的图同构算法。本文对多种结构的图进行了实验，将目前最有效的标准标签法与PEACE进行了综合的比较。实验表明，在处理对称性强或自同构很多的图时，PEACE算法效率明显优于其他算法，最好情况下能有50％的性能提升。本文还将提出的

4、并行技术应用在这些算法上，并在CPU和多种GPU设备下的性能进行了比较，结果表明我们的并行技术在所有算法下均能获得15．55的加速比。对于最小steiner树问题，本文对目前最为有效的一类近似算法一GRASP算法在GPU下进行了并行化，在CUDA下实现加速计算。在基于生成树的构建阶段，本文中文摘甍提出一种计算最短路径矩阵的并行策略从而得到辅助图的边集，提出一种并行桶排序策略以得到辅助图的权值集合，利用并行Kruskal算法计算辅助图的最小生成树。在基于顶点的本地搜索阶段，本文采用并行的随机Kruskal算法更新局部解。本文还提出了利用多G

5、PU求解此问题的计算模型，实现GPU间的粗粒度并行，GPU内部的细粒度并行。关键字：图问题，GPU，图同构，最小steiner树，CUDAIIAbstractAbstractGraphtheoryisabranchofdiscretemathematics，andforallbinaryrelationsystems，graphtheorycanprovidesamathematicalmodel，thusithasanincreasinglyimportantroleinmanyfieldsofscience．Lotsofgraphpr

6、oblemsareextraordinarilycomplexinachieving，formostlygraphproblemsareexponentialtimecomplexityevenNP-completeproblem，andwiththescaleoftheproblemareincreasingrapidly，thetraditionalserialalgorithmsoftencannotmeettheneedsofpracticalproblems．Traditionaldistributedcomputing(suc

7、hasclusters)althoughcanimprovetheperformancetosomeextent，butthismodelorganizationrelativelyloosethattheimprovementofthealgorithmitselfislimited，anditwillalsoincreasethepowerconsumptionandcommunicationoverhead．Thegraphicsprocessor(GPU)hasastrongparallelprocessingcapabiliti

8、esandlowcost，andcandealwithincreasingscaleoftheproblem，SOuseGPUtosolvethegraphproblemshasbecomet