当前集成电路设计领域,不断发展的工艺技术将电路原理图的结构、规模提高到更加复杂、多样的状态,这就要求研究人员根据复杂的需求不断改进甚至开发出新的布局布线、逻辑综合及验证工具,开发出更加适合业务定制的物理设计算法及可靠的集成电路设计软件产品。本文主要研究了集成电路物理设计中的电路划分问题和逻辑图布局问题,并将电路划分应用到逻辑图布局系统中,探讨了在小规模电路逻辑图布局中结合应用电路划分的可行性。 本文首先简要介绍了集成电路物理设计的主要内容,并对物理设计中的电路划分、电路布局问题做了详细阐述。其次,在电路划分问题的研究中,根据电路原理图图论模型化这一思想,将电路划分问题转化为数学中图的划分问题,利用成熟的图论划分算法,解决了划分问题。先后介绍了基于顶点移动的FM优化算法、基于贪婪策略的初始划分算法(如 Greedy Growing Partitioning和Min-Max Greedy Partitioning算法)。本文重点研究了FM算法。在满足固定比例因子这一约束下,综合考虑划分集合各自的顶点数和形成的割边数这两个因素,对FM算法中标杆点的选择和算法结束条件进行了改动,提高了划分的稳定性,实验结果表明无论是平均时间耗费还是平均割边数,都要优于原FM算法。最后,本文详细介绍了应用于逻辑图布局系统的串布局算法,并将改动的划分算法与串布局算法相结合,用于对电路逻辑图进行布局,考察了对小规模电路逻辑图应用划分的可行性。