一个有效的圆片规模布局算法

AN EFFICIENT ALGORITHM FOR WAFER SCALE PLACEMENT

本文提出了一个圆片规模布局算法,它是国外一个相应算法的改进形式,区别在于利用力定向布局法的方式不同。在相对位置阶段,该算法利用布局的层次特性将需确定所有电路元件相对位置的问题缩减至仅需确定宏电路元件相对位置的问题;在实际位置阶段,采用分治策略和取消前阶段层次划分的方式回避了需确定任意元实际位置的问题。其时间复杂度远低于国外相应算法。

An improved wafer scale placement algorithm is proposed in this paper,which employes force-directed placement algorithm in a different manner.In relative location phase,it only needs to determine the relative location of macro circuit component,instead of all circuit components,by using the hierarchical property of placement.In real location phase,it avoids the problem of determining the real location of arbitrary component by employing divide-and-conquer strategy and removing the hierarchical division.Its computational complexity is much lower.