随着科技的快速发展,超大规模集成电路的规模变得越来越大,其设计工作也愈加复杂。人们广泛地使用分级设计和知识产权核复用技术来处理复杂的设计工作。作为物理设计的核心,布图规划需要确定模块在芯片上的位置,并达到芯片面积最小和线网连接线长度最短等优化目标。布图规划问题已被证明是NP难题。在深入研究了当前主流的布图算法之后,本论文基于传导闭包图结构,在芯片面积最小和连接线长度最优等布图规划的关键问题上展开了进一步的研究,并取得如下成果:1.大部分现有的布图规划算法基于模拟退火框架实现,在放置完所有模块后才得到目标面积,判断是否接受此次扰动。本文提出了一种不可二划分且可预判面积的传导闭包图算法(AP-TCG)。该算法在循环框架下实现,能估计目标面积而无需放置所有的模块,具有速度快,效果好,易于得到高品质次优解的特点。2.在实际的物理设计中,有时需要将一些模块放置在芯片边界,以便更好地连接输入/输出接口。为了解决带边界约束条件的布图规划问题,本文提出了一种将边界约束的可行条件引入扰动操作的改进型AP-TCG算法。该算法能保证每次扰动后的中间结果均是可行解,而不像当前的其它算法需把非可行解转换成可行解而付出大量额外的计算开销。3.大部分现有的布图规划算法得到左下压缩的版图结果。对结果中的空白区域重分配,且不改变原版图的拓扑结构和面积,能得到连接线总长度不同的版图。本文提出一种基于模块移动的贪婪算法。它首先计算出各模块唯一的移动范围。然后,创建移动代价树来表示移动和连接线长度之间的关系。最终可以得到不改变拓扑结构和面积、具有更短连接线的版图。4.通过研究,我们提出一种新的模型化方法,可以将空白区域重分配优化连接线总长度问题公式化成为一个混合型整数线性规划问题,利用线性规划问题解决器,得到每个模块的最佳位置,且使连接线总长度最短。5.通过反装一些模块,也可以在不改变原版图的拓扑结构和面积的约束下优化连接线长度。本文提出一种混合型的算法,同时考虑空白区域分配和模块反装来综合优化连接线长度。该方法对现有的布图规划算法做了进一步的补充和完善。