LSI/VLSI任意元胞模式的自动布局算法

A New Algorithm for LSI/VLSI General Cell Layout

本文提出一种新的层次式结群布局算法.通过引入模糊连接图模型和巧妙构造无形式约束的目标函数,用快速算法可得连线总长最优化的单元拓扑分布;提出一种高效的可布局性预分析方法,深入剖析了五个单元以内的布局组合方式;进行单元的层次式动态结群和布局优化,实现了芯片面积和连线总长优化,且布局结构规整、布线方便.本算法时间复杂度随单元数呈权线性增长.

A new approach for hierarchical clusteringplacement for general cell layout is presented.We establish a new graph model and objectivefunction of minimizing the total wire lengthwith given electrical and physical constraints.Based on the cell global topological positionsand cell shape fitness analysis,hierarchicalclustering is formed dynamically.The place-ment in higher hierarchy take slicing struc-ture so facilitate the routing.The timecomplexity of the algorithm is J.O(n).