基于群法的BBL布局算法研究

BBL Placement Algorithm Based on Cluster Method

本文对BBL结群及其在布局中的应用进行了研究。提出了表示群内单元位置关系的点结构模型、扩展的点结构模型、图模型及方位树模型;导出了计算单元数为n的群的全部点结构(或方位树)数及布局方式数的公式;证明了(扩展的)点结构模型与(扩展的)方位树模型的一一对应关系;提出了适用于Floor Plan及自顶向下布局法的限定高度的结群算法及适用于自底向上等布局法的最小冗余比结群法,并提出了递归结群法。本布局法可产生Slicing及Nonslicing二种布局结构。以上算法均已在UNIVAC 1100/10机上用Fortran 77实现,结果是令人满意的。

In this paper, the clustering of BBL is researched. A (extended) vertex structure model, a graph model and an (extended) oriented tree model are proposed. A formula calculating the number of vertex structures (or oriented trees) is obtained. A conclusion that the (extended) vertex structure and the (extended) oriented tree is one to one correspondence is proven. Clustering algorithms used in top-down placement and floor plan and bottom-up placement are presented. A placement algorithm adopting recurrent clustering which can form slicing and nonslicing placement is proposed. These algorithms have been implemented on UNIVAC 1100/10 computer in Fortran 77. The experimental results are satisfactory.