Title :
Almost linear time optimization for single-row floorplanning
Author :
Teng-Sheng Moh ; Hakimi, S. Louis ; Moh, Teng-Sheng
Author_Institution :
silicon Valley Res.Inc., Mountain View, CA, USA
Abstract :
Given n cells with their areas and aspect ratio constraints, we present an O(n+d log d) time algorithm to obtain the optimal floorplan of placing these n cells into a single-row, where d is related to the total number of distinct cell classes. Since d is much smaller than n in practical design, our algorithm runs in almost linear time for practical problems
Keywords :
VLSI; cellular arrays; circuit layout CAD; circuit optimisation; integrated circuit layout; logic CAD; VLSI; aspect ratio constraints; distinct cell classes; linear time optimization; optimal floorplan; physical layout; single-row floorplanning; Polynomials; Shape;
Conference_Titel :
Circuits and Systems, 1994., Proceedings of the 37th Midwest Symposium on
Conference_Location :
Lafayette, LA
Print_ISBN :
0-7803-2428-5
DOI :
10.1109/MWSCAS.1994.519256
