随着超大规模集成电路(VeryLargeScaleIntegratedcircuit，VLSI)工艺的发展，对VLSI设计工具提出了更高的要求。布局是VLSI物理设计的一个重要步骤。在当前的工艺环境下，布局工具面临着新的挑战。 当今，芯片的规模日益增大。到2004年，芯片上的晶体管数目将达到1G。布局算法需要考虑如何处理如此大规模的电路。随着特征尺寸的减小，连线上的延迟大大超过了门延迟。在布局过程中控制连线上的时延成为布局算法的一个重要目标。随着布线层数的增多，布线资源更加丰富。但是，更复杂的电路设计和更高的性能要求使得走线的局部拥挤现象仍不能避免。可布性布局算法需要关注的另一个重要问题。现在，随着系统芯片(SOC)的出现，大模块和小单元混合模式的布局是布局工具面临的一个新问题。 针对以上工艺发展的要求，本文在调研了现有布局算法，并深入分析了二次规划布局算法理论的基础上提出了如下算法： ●快速稳定的布局算法FaSa。算法采用了拉格朗日乘子法求解二次规划问题，提出适合二次规划布局解方程的增量式LU分解法，从而提高了算法的速度和稳定性。实验结果表明，FaSa比国际知名的布局算法Dragon2000快5倍。 ●时延驱动的布局算法TimFaSa。TimFaSa对电路的布局问题加入了基于路径的时延约束，并在二次规划布局算法的划分阶段采用时延驱动的划分算法以减少关键路径同划分线的切割数。实验结果表明，算法可以使芯片的最大时延减少20％。 ●可布性驱动的布局算法IMP。IMP引入包含走线拥挤程度的单元虚拟面积概念，并用它代替实际单元进行布局，以减少芯片的平均拥挤度；采用单元的定向移动的策略来减少芯片的最大拥挤度。实验结果表明，芯片在水平和垂直方向上的拥挤度都得到了有效减小。 ●同时优化电路的时延特性和可布性特性的布局算法TimIMP。算法采用多步优化策略，首先优化电路的时延特性，然后在保障时延特性不被破坏的情况下，优化拥挤度特性。目前还未见到有同时优化时延和可布性的布局算法发表。实验结果表明，TimIMP有效地优化了电路的时延和可布性这两个在局部上相互矛盾的目标。 ●实现了一个可以处理混合模式电路的布局算法EMMP。本文提出的算法优化了电路的性能，提高了布局的速度和稳定性，以适应当今VLSI工艺发展的需要。同时，它也为布局算法进一步的改进提供了一个稳定坚实的基础。