1.1 课题研究背景及意义

超大规模集成电路的平面布局规划作为物理设计过程中的重要构成部分，近 年来受到了极为广泛关注，之后的布线工作能否的顺利完成很大程度的取决于它 的质量，甚至最终的电路性能也受其的影响。随着布图设计过程中各类新型问题 的不断提出，其面临多样化的挑战，因此，能否成功破解布图设计中的一系列问 题对今后布局设计的发展意义重大。如今，关于超大规模集成电路平面布图算法 的研究，主要体现在以下两个大的方面：

（1）传统超大规模集成电路的平面布图问题 芯片所占面积较大且内部元器件互连线长繁琐一直是困扰传统超大规模集

成电路平面布图的首要问题，为此，我们通常采用以下几类方法来解决这个问题： 寻找平面布图表示法、软模块调整法、带位置约束的平面布图规划法等。

对于可二分平面布图来说，使用 NPE 表示法[1]；对于一般情况的平面布图， 使用序列对表示法；之后产生了 TCG（Transitive Closure Graph）表示法，一年 后，[Lin，02]基于序列对表示法和 TCG 表示法提出了一种新的表示法 TCG-S， 该方法大幅度降低了解码时间和复杂度[1]。对于 LB-Compact 平面布图，Chang 和 Lee 基于 O-Tree 提出了更为优化的 B*-tree 表示法[2]；在马赛克平面布图的概 念的基础上改进出了角模块序列的表示方法，使用 Twin Binary Tree 表示法解决 马赛克平面布图中软模块的调整问题；之后又分别提出了构造法，凸规划法，基

于线性规划法，带对齐约束的平面布图规划法， Hong 研究了带边界约束的平面 布图规划的计算方法[3]。虽然我们研究了众多传统平面布图规划中出现的问题， 但是因为平面布图规划问题本就是一个多解问题，在给定邻域中寻求最优解的过 程中，我们需要考虑许多其他问题。在解决传统的平面布图规划问题的道路上仍 有许多阻力，我们能做就是坚持自己的信念，让研究一直进行下去。

(2)平面布图规划的各种新问题的探究 随着超大规模集成电路技术的日益发展，芯片功耗、多时钟域、关键路径延、

缓冲器插入、多总线等诸多原本在布图设计时无需考虑的问题也开始为芯片设计 者关注。布图设计中所遭遇的新问题伴随着日新月异的超大规模集成电路技术接 踵而来，为了解决这些问题，Koide 提出了基于时延驱动的平面布图规划的计算 方法[4]；Xiang 提出总线平面布图规划的计算方法[5]；Ma 提出基于缓冲器插入的 平面布图的计方算法[6]；Chen 提出电源网络供电的平面布图规划的计算方法[7]。

1.2 国内外研究现状

1.3 本论文的主要工作

在超大规模集成电路固定边界问题的研究中，本文将完成以下工作：

（1）介绍了超大规模集成电路研究背景及意义和国内外研究现状。

（2）介绍了超大规模集成电路的布图设计：VLSI 的设计流程，物理设计。

（3）在布图规划中着重讲解两类算法：模拟退火算法（SA）和 B*tree。

（4）介绍了改进的模拟退火算法和满足约束条件的成本函数。

（5）进行实验数据仿真，得出结论。

2 布图规划

随着电子晶体管的出现，集成电路应运而生，因其展现出的极大实用性而迅 速发展，其先后历经五个阶段：小规模集成电路（SSI）、中规模集成电路（MSI）、 大规模集成电路（LSI）、超大规模集成电路（VLSI）和特大规模集成电路（ULSI）。

如今，随着芯片制造技术已达到深亚微米阶段，电子设备已步入了片上系统 时代。顾名思义，片上系统（SOC）是指在单个硅片上是集成一个完整的系统。 集成电路的制作一般需要考虑四个方面：减小芯片尺寸、增大模块集成度、