标准单元布局中的高效结群算法

High Efficiency Clustering Algorithm for Standard Cell Placement

本文提出了一个高效的结群算法 ,用以解决在超大规模条件下标准单元模式集成电路的布局问题 .与传统结群算法相比 ,本算法的特色在于在结群之前 ,建立和组织了表示所有单元之间连接关系的信息库 ,使得结群算法具有全局优化性和无冗余计算的特点 .本结群算法已应用于二次规划布局过程中 .实验结果表明 ,本算法无论在结群质量和结群速度方面都非常理想 ,从而成功地解决了超大规模电路的布局问题 .

A high-efficiency clustering algorithm is presented for solving standard-cell style placement problem with very large number of cells. Compared to traditional clustering algorithms, the main feature of the presented algorithm is that an information library including all interconnect relationships between cells is built and well organized before placement, thereby endowing the clustering algorithms, with characteristics of global optimality and non-redundancy computation. The clustering algorithm is applied to a quadratic placement procedure. Experimental results show that our clustering algorithm is very perfect in both clustering quality and clustering speed, thus solves the placement problem with very large number of cells successfully.