A new placement algorithm for custom chip design

Z. M. Lin, Hung C. Lin

研究成果: Conference article同行評審


A placement algorithm which consists of three subalgorithms--an O(kn2) circle model relative placement algorithm, an O(n2 log n triangulation algorithm, and an O(n2 log n2) optimal slicing algorithm for custom chip design--is presented. This relative placement algorithm addresses size effect and net connectivity effect simultaneously, while attaining a low polynomial time complexity O(kn2) without loss of global perspective, where k is a constant and depends on the accuracy that the placement required. The triangulation algorithm has O(n2 log n) time complexity. The triangulated planar graph can be used to do the floorplan by either the nonslicing RDG (rectangular dual graph) or slicing embedding methods. The optimum slicing algorithm has O(n2 log n2) time complexity. As expected, the wire length of the placement algorithm is shorter than that of a point model. However, since the optimal values of l0 and DEF (deformation ratio) are unknown, different values for l0 and DEF should be used in different circuits to obtain better placement results.

頁(從 - 到)1672-1675
期刊Proceedings - IEEE International Symposium on Circuits and Systems
出版狀態Published - 1990
事件1990 IEEE International Symposium on Circuits and Systems Part 3 (of 4) - New Orleans, LA, USA
持續時間: 1990 五月 11990 五月 3

All Science Journal Classification (ASJC) codes

  • Electrical and Electronic Engineering

指紋 深入研究「A new placement algorithm for custom chip design」主題。共同形成了獨特的指紋。