新型电路版图布局布线算法设计

袁 也，王 刚，刘晓光，李雨森

(1.南开大学计算机学院，天津 300350；2.天津市网络与数据安全重点实验室(南开大学)，天津 300350)

1 引言

发达国家在集成电路领域的高新技术成果方面始终对我国形成封锁。近年来，集成电路自动化设计技术高速发展，为了推动我国迈入该领域发展的快车道，越来越多的学者开始研究电路自动化设计的相关技术。

当前我国虽然在大规模电路的布局布线方面已有许多成果，但是对于中小规模电路的布局布线研究却很少，更多的是追求快速求得整体结果和解决大规模问题的卓越能力，而暂时忽略了软件商用时用户自主设计的便捷性和舒适性以及用户使用软件时一些更具体的需求。对此本文改进了划分算法，提升了划分结果质量，提出了全新的布局算法，满足对美观度的要求，提升了A*算法的布线速度，提高了布线质量，形成一套适用于中小规模模块的布局布线方案，方便用户在实际布线前检查电路各模块的逻辑错误，填补了相关研究领域的空白。

2 相关工作

目前电路布局算法主要有2类，一类是直接布局算法，另一类是面向划分的布局算法。直接布局算法大多采用传统启发式算法如模拟退火算法[3,4]、遗传算法[5,6]和粒子群优化算法[7]等，是在一个初始布局的基础上通过尝试性改变的效果决定下一步迭代改进的方向，循环往复直至结果满足一定条件为止。这类算法的特点是布局效果较好，不易陷入局部最优，但算法运行速度慢、时间长。……