一种模拟“退火”的二维总体压缩算法

摘要

在集成电路版图设计中,对积木块模式布图进行总体压缩,可以改善最终布图的质量,然而,二维的总体压缩是个非常复杂与困难的问题。本文设计并实现了一个模拟退火的二维总体压缩算法,并且对它采取了一系列技术措施,使得它的算法复杂度可以接受。本文不仅提出了关于“布线区布线密度函数”的概念以准确地描述当布局移动时布线区动态的布线密度,而且通过使用密度函数保持约束图与动态布局之间的一致性。此外,还提出了将“均匀分布空闲空间”作为总体压缩的优化目标之一,以使得由于布线区布线容量不足而引起的溢出大大地减少了,并且优化过程的效率也将提高。实例表明,本算法既实用又有效。