论文部分内容阅读
斯坦纳树问题是图论的一个经典的问题,在工业生产中具有广泛和重要的应用。传统的串行算法在速度上无法适应图规模日益增大的斯坦纳树问题。为了加速求解大规模的斯坦纳树问题,学术界开始尝试利用GPU来加速求解斯坦纳树问题。然而,目前对于GPU加速斯坦纳树问题的研究仍然较少,仍需进一步寻找适合于在GPU平台上并行求解图近似斯坦纳树问题的算法,以充分挖掘GPU的计算能力。VLSI布线设计是斯坦纳树问题的一个重要的应用方向。VLSI多端线网布线问题从数学上可抽象为斯坦纳树问题。随着集成电路规模的日渐增大,VLSI多端线网布线的图规模也在扩张。以往串行的VLSI布线算法在求解速度上逐渐跟不上工业界的需求。利用并行的平台和算法来进行VLSI多端线网布线具有很大的加速潜力。本文研究了GPU图加速框架Gunrock的基本原理,挖掘了串行求解斯坦纳树问题的Shrubbery算法中可并行加速的部分,并借助Gunrock,提出了并行度较高的Shrubbery-GPU算法。其中,并行求解向外的Voronoi diagram为Shrubbery-GPU算法的快速求解提供了重要的基础。对VLSI布线问题进行研究,抽象出VLSI多端线网布线问题的数学模型。将Shrubbery-GPU算法应用到求解VLSI多端线网布线问题。Shrubbery-GPU算法经实验证明对终端节点、顶点和边均为较大规模的斯坦纳树问题在保持与原Shrubbery相似的求解质量下取得了1至3个数量级的加速效果,并能很好地应用于VLSI多端线网布线上。更重要的是,Shrubbery-GPU算法对斯坦纳树问题的终端节点的数目不敏感,大部分测试数据在终端节点数目增大时求解时间反而呈现轻微的下降趋势。这使得Shrubbery-GPU算法的应用场景更加广泛。Shrubbery-GPU算法求得的斯坦纳树的解为近似最优,因此斯坦纳树的解仍然存在改进的空间。本文利用快速局部搜索来进一步提高Shrubbery-GPU算法的求解质量。快速局部搜索在Shrubbery-GPU算法的初始解基础上均改善了解的质量,在大规模的测试集上改善效果最为明显,代价改善了8%至12%。