A fast algorithm for area minimization of slicing floorplans

Author

Shi, Weiping

Author_Institution

Dept. of Comput. Sci., North Texas Univ., Denton, TX, USA

Volume

15

Issue

12

fYear

1996

fDate

12/1/1996 12:00:00 AM

Firstpage

1525

Lastpage

1532

Abstract

The traditional algorithm for area minimization of slicing floorplans due to Stockmeyer has time and space complexity O(n²) in the worst case. For more than a decade, it has been considered the best possible. This paper presents a new algorithm of worst-case time and space complexity O(n log n), where n is the total number of realizations for the basic blocks, regardless whether the slicing is balanced or not. We also show R(n log n) is the lower bound on the time complexity of any area minimization algorithm. Therefore, the new algorithm not only finds the optimal realization, but also has the optimal running time

Keywords

VLSI; circuit analysis computing; circuit layout CAD; circuit optimisation; computational complexity; digital simulation; integrated circuit layout; IC design; VLSI; area minimization; balanced slicing; layout; minimization algorithm; optimal realization; running time; slicing floorplans; space complexity; time complexity; Binary trees; Circuits; Computer science; Design automation; Minimization methods; Notice of Violation; Very large scale integration; Wheels;

fLanguage

English

Journal_Title

Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on

Publisher

ieee

ISSN

0278-0070

Type

jour

DOI

10.1109/43.552085

Filename

552085