基于多引脚同时扩散搜索的超大规模集成电路布线方法

摘要

本发明公开了一种基于多引脚同时扩散搜索的超大规模集成电路布线方法，包括以下步骤：(1)根据给定的带权图，以每个引脚所在节点为源点，同时进行广度优先搜索；(2)搜索相邻节点，将该相邻节点及其累计的cost加入优先队列，路径与所属引脚存储于该相邻节点；(3)当搜索到的节点属于多个引脚时，连接对应路径，以路径上所有节点为源点加入搜索；(4)重复执行(2)(3)直至所有引脚相连。该方法有利于提高布线效率，特别是对于线网中的引脚数量较大时，该方法能够快速连接距离较近的引脚，避免大量冗余搜索，同时易于使用多线程加速，显著提高布线效率。