Title :
An Ω(k2) lower bound for area optimization of spiral floorplans
Author :
Chen, Cheng-Hsi ; Tollis, Ioannis G.
Author_Institution :
Dept. of Comput. Sci., Texas Univ., Dallas, TX, USA
fDate :
3/1/1996 12:00:00 AM
Abstract :
Let F be a spiral floorplan where each of its five basic rectangles has k implementations. In this paper, we show that there can be as many as Ω(k2) useful implementations generated for F, in the worst case. This implies that the previously known O(k2 log k)-time algorithm is almost optimal
Keywords :
VLSI; circuit layout CAD; circuit optimisation; integrated circuit layout; VLSI layout; area optimization; lower bound; spiral floorplans; Area measurement; Circuits; Costs; Position measurement; Process design; Semiconductor device measurement; Shape; Spirals; Topology; Very large scale integration;
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
