集成电路自二十世纪五十年代出现以来得到了广泛的应用。随着半导体技术的不断发展,电子设计自动化工具在解决超大规模集成电路的布线问题中遇到了更大的挑战。为了提高布线算法的效率,学术界对各种图论算法和元启发式算法进行了大量的研究。A*算法作为被广泛使用的工业级布线算法,虽然有绕障能力强和灵活性高的优点,但是在超大规模集成电路布线中的效率不高。为了提高A*算法布线的效率,本文以GPU作为计算平台将算法并行化并进行了算法性能的测试。本文基于超大规模集成电路布线的基本原理和设计模式,总结了布线问题两种具体的数学模型,两端线网布线和多端线网布线分别对应了图论中的最短路径问题和最小斯坦纳树问题。对于最短路径问题,本文针对A*算法中的迷宫扩展步骤,分析了迷宫扩展的时间复杂度,并指出迷宫扩展机制是算法在大规模图中低效的原因。为了提高迷宫扩展的效率,本文采用了基于多队列并行的迷宫扩展方法,在此基础上利用GPU实现了并行A*算法,算法实现过程中利用到了多种GPU的内存和特性,通过冗余去除步骤避免了并行程序中原子锁的使用,极大提高了算法的效率。在最短路径问题的实验中,并行A*算法相对于串行版本可以获得2-48倍的加速。对于最小斯坦纳树问题,本文介绍了TM算法的基本原理并分析了TM算法中求取最短路径步骤的缺陷和改进方法。本文结合并行A*算法和TM算法完成了斯坦纳树近似算法的GPU实现,实现过程中对GPU的线程同步机制进行了深入的研究,提出了同步函数加速线程的同步。算法在布线质量的测试中求得的布线线长与最优解的平均误差为4.2%;在布线效率测试中相对于改进迷宫算法取得了4-51倍的加速。实验证明并行A*算法及其派生斯坦纳树近似算法可以较为有效的解决大规模线网的布线问题,GPU作为新的计算平台在超大规模集成电路布线设计中有很大的潜力。