LSI多元胞版图设计的一种布局方法

本文提出LSI版图自动布局的一个实用程序.该程序适用于多元胞布局模式,由块的划分和块内布局两个步骤完成.求解的算法主要有:分配问题的近似算法、Ketnighan-Lin算法和分枝界限法.文中着重介绍对上述算法的改进.主要的改进为:1,在采用分配问题求解时,定义了三个选择函数以适应不同的要求,其中 F_2带有一定预见性; 2,对 Kernighan-Lin算法的目标函数及交换方式作了改进,以满足布局问题划分中特有的几何参数的要求.此外在迭代过程中使用了分枝界限法,通常可显著减少迭代时间.该程序使用Fortran-IV语言编写,已在PDP-11/34计算机上调试通过,并运行了若干实例.