论文部分内容阅读
本文提出LSI版图自动布局的一个实用程序.该程序适用于多元胞布局模式,由块的划分和块内布局两个步骤完成.求解的算法主要有:分配问题的近似算法、Ketnighan-Lin算法和分枝界限法.文中着重介绍对上述算法的改进.主要的改进为:1,在采用分配问题求解时,定义了三个选择函数以适应不同的要求,其中 F_2带有一定预见性; 2,对 Kernighan-Lin算法的目标函数及交换方式作了改进,以满足布局问题划分中特有的几何参数的要求.此外在迭代过程中使用了分枝界限法,通常可显著减少迭代时间.该程序使用Fortran-IV语言编写,已在PDP-11/34计算机上调试通过,并运行了若干实例.
In this paper, a utility program of automatic layout of LSI layout is proposed, which is suitable for mulitibond layout pattern, which consists of block partitioning and intra-block layout. The main algorithms are: approximate algorithm of distribution problem, Ketnighan-Lin algorithm and The main improvement is as follows: 1, When using the assignment problem, three selection functions are defined to meet different requirements, among which F_2 has a certain foreseeability; 2, The objective function and exchange mode of Kernighan-Lin algorithm are improved to meet the requirements of geometric parameters unique to layout problem. In addition, the branch-and-bound method is used in the iterative process, which can usually reduce the iterative time greatly. Fortran-IV language has been debugged on a PDP-11/34 computer and has run through several instances.