A clustering algorithm for circuit partitioning

Author

Allam, M.W. ; Vannelli, A. ; Elmasry, M.I.

Author_Institution

Dept. of Electr. & Comput. Eng., Waterloo Univ., Ont., Canada

Volume

1

fYear

1997

fDate

25-28 May 1997

Firstpage

12

Abstract

This paper describes a fast greedy clustering algorithm for circuit partitioning. The algorithm is used to generate a good initial partitioning, then a module interchange approach is used to improve the initial partitioning. The proposed algorithm is tested against three well known algorithms namely, simulated annealing, Tabu search approach, and module interchange algorithm alone using some benchmark netlist partitioning problems (between 300 to 3000 nets and modules each). Test results show that the proposed algorithm yields results comparable to that of the other approaches with a faster execution time

Keywords

circuit layout CAD; computational complexity; heuristic programming; logic CAD; logic partitioning; Tabu search; benchmark netlist partitioning problems; circuit partitioning; clustering algorithm; greedy clustering algorithm; module interchange; simulated annealing; Benchmark testing; Circuit simulation; Circuit testing; Clustering algorithms; Image processing; Joining processes; Partitioning algorithms; Pattern recognition; Simulated annealing; Very large scale integration;

fLanguage

English

Publisher

ieee

Conference_Titel

Electrical and Computer Engineering, 1997. Engineering Innovation: Voyage of Discovery. IEEE 1997 Canadian Conference on

Conference_Location

St. Johns, Nfld.

ISSN

0840-7789

Print_ISBN

0-7803-3716-6

Type

conf

DOI

10.1109/CCECE.1997.614777

Filename

614777