论文部分内容阅读
图论是离散数学的一个分支，凡有二元关系的系统，图论均可提供一种数学模型，因而它在许多科学领域中具有越来越重要的地位。图论的很多问题在实现上都异常复杂，大多图问题都是指数级时间复杂度甚至是NP完全问题，并且随着问题的规模急剧增大，传统的串行算法往往不能满足实际问题的需要。传统的分布式计算(如集群)虽然能够在一定程度上的提高性能，但是这种模型组织较为松散，对算法自身的提高有限，并且会增加功耗及通信开销。图形处理器(GPU)具有很强的并行处理能力以及低廉的成本，并且能够处理的问题规模越来越大，因此利用GPU解决图问题已经成为当前的研究热点。本文选择了两个具有代表性的图问题进行研究：图同构、最小steiner树。对于图同构问题，目前最有效的一类算法—标准标签法要么适合处理随机性或对称性强的图，要么适合处理两者均不强的图，并且其最核心的操作独立-精炼及证书比较通常占据总时间的70%以上，如何削弱对图的结构的局限性并提高这些操作的效率是具有挑战性的。本文提出了一种高效的图同构算法：PEACE，能够有效地削弱结构对算法的影响，尤其适合处理对称度很高的图。本文同时第一次提出了图同构算法在GPU下的并行实现方法。本文将核心的操作并行化，设计了一些新的方法并利用了一些现有的技术实现CUDA下的加速计算，这些技术能够适用于所有基于独立-精炼的图同构算法。本文对多种结构的图进行了实验，将目前最有效的标准标签法与PEACE进行了综合的比较。实验表明，在处理对称性强或自同构很多的图时，PEACE算法效率明显优于其他算法，最好情况下能有50%的性能提升。本文还将提出的并行技术应用在这些算法上，并在CPU和多种GPU设备下的性能进行了比较，结果表明我们的并行技术在所有算法下均能获得15-55的加速比。对于最小steiner树问题，本文对目前最为有效的一类近似算法—GRASP算法在GPU下进行了并行化，在CUDA下实现加速计算。在基于生成树的构建阶段，本文提出一种计算最短路径矩阵的并行策略从而得到辅助图的边集，提出一种并行桶排序策略以得到辅助图的权值集合，利用并行Kruskal算法计算辅助图的最小生成树。在基于顶点的本地搜索阶段，本文采用并行的随机Kruskal算法更新局部解。本文还提出了利用多GPU求解此问题的计算模型，实现GPU间的粗粒度并行，GPU内部的细粒度并行。