An optimal algorithm for area minimization of slicing floorplans
作者： Weiping Shi
关键词: Average-case complexity 、 Computational complexity theory 、 Worst-case complexity 、 Upper and lower bounds 、 Minification 、 Time complexity 、 Slicing 、 Algorithm 、 Combinatorics 、 Floorplan 、 Mathematics
摘要: The traditional algorithm of L. Stockmeyer (1983) for area minimization slicing floorplans has time (and space) complexity O(n/sup 2/) in the worst case, or O(n log n) balanced slicing. For more than a decade, it is considered best possible. In this paper, we present new worst-case n), where n total number realizations basic blocks, regardless whether not. We also prove /spl Omega/(n lower bound and any algorithm. Therefore, not only finds optimal realization, but an running time.
acm.org
ieeecomputersociety.org参考文章(16)
Robert Endre Tarjan, Data Structures and Network Algorithms ,(1983)
Weiping Shi, C.L. Liu, Peichen Pan, Area minimization for hierarchical floorplans international conference on computer aided design. pp. 436- 440 ,(1994) , 10.5555/191326.191509
Wei-Ming Dai, E.S. Kuh, Simultaneous Floor Planning and Global Routing for Hierarchical Building-Block Layout IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. ,vol. 6, pp. 828- 837 ,(1987) , 10.1109/TCAD.1987.1270326
Majid Sarrafzadeh, Transforming an arbitrary floorplan into a sliceable one international conference on computer aided design. pp. 386- 389 ,(1993) , 10.5555/259794.259857
Michael Ben-Or, Lower bounds for algebraic computation trees symposium on the theory of computing. pp. 80- 86 ,(1983) , 10.1145/800061.808735
Larry Stockmeyer, Optimal orientations of cells in slicing floorplan designs Information & Computation. ,vol. 57, pp. 91- 101 ,(1984) , 10.1016/S0019-9958(83)80038-2
Athanasios K. Tsakalidis, AVL-trees for localized search Information and Control. ,vol. 67, pp. 173- 194 ,(1985) , 10.1016/S0019-9958(85)80034-6
CHENG-HSI CHEN, IOANNIS G. TOLLIS, AREA OPTIMIZATION OF SPIRAL FLOORPLANS Journal of Circuits, Systems, and Computers. ,vol. 03, pp. 833- 857 ,(1993) , 10.1142/S0218126693000484
K. Chong, S. Sahni, Optimal realizations of floorplans (VLSI layout) IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. ,vol. 12, pp. 793- 801 ,(1993) , 10.1109/43.229753
Ralph H.J.M. Otten, Automatic Floorplan Design design automation conference. pp. 261- 267 ,(1982) , 10.5555/800263.809216