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

【Abstract】 This paper presents a placement technique devoted to polycell layout of LSI andinvolving two steps:partitioning a circuit into blocks and placing the cells in them.Themain algorithms used are:approximation method for assignment problem,Kernighan-Lin’s method and branch-bound method.Improvements for these algorithms are propo-sed:1.For solving assignment three selective functions are defined and among whichF₂ is with prediction;2. The objective functions and the interchange form of the Ker-nighan-Lin’s method are tailored to meet the special requirements of geometric parame-ters in partitioning.In addition,the branch-bound method is used in iterative process,these making it possible to reduce the search time in many situations. The schematic diagram is given.The program is written in Fortran-4 language andhas been implemented on PDP-11/34 computer.更多还原