基于二进制多因素优化的集成电路布线方法

布线是集成电路版图设计的核心环节,主要内容是根据电路单元的位置、引脚位置以及线网连接信息等因素,确定布线方案,使其总体长度最短,并符合网络辐射的约束。现有研究已证明,集成电路的布线是NP-完全问题,无法使用数学方法在线性时间内求解。现有算法一般使用启发式方法逐步优化和收敛布线结果,如粒子群优化、蚁群算法等。在纳米级工艺下,现有算法难以有效优化如此大规模的集成电路布线问题。首先,由于传统启发式优化算法在搜索能力方面的缺陷,其有效的搜索空间一般不超过千维。而基于网格的集成电路布线问题规模可达数万维。造成优化算法收敛困难,布线时间过长。