A replication cut for two-way partitioning

Author

Liu, Lung-Tien ; Kuo, Ming-Ter ; Cheng, Chung-Kuan ; Hu, T.C.

Author_Institution

AT&T Bell Labs., Murray Hill, NJ, USA

Volume

14

Issue

5

fYear

1995

fDate

5/1/1995 12:00:00 AM

Firstpage

623

Lastpage

630

Abstract

Graph partitioning is crucial in multiple-chip design, floorplanning and mapping large logic networks into multiple FPGA´s. Replication logic can be used to improve the partitioning. Given a network G with only two-pin nets and a pair of nodes s and t to be separated, we introduce a replication graph and an O(mn log(n²/m)) algorithm for optimum partitioning with replication and without size constraints, where m and n denote the number of nets and the number of nodes in G, respectively. In VLSI designs, each partition has size constraints and the given network contains multiple-pin nets. A heuristic extension is adopted to construct replication graphs with multiple-pin nets. Then we use a directed Fiduccia-Mattheyses algorithm in the constructed replication graph to solve the replication cut problem with size constraints

Keywords

VLSI; circuit layout CAD; field programmable gate arrays; graph theory; logic CAD; logic partitioning; network topology; VLSI design; circuit layout; directed Fiduccia-Mattheyses algorithm; floorplanning; graph partitioning; heuristic extension; logic networks; multiple FPGAs; multiple-chip design; optimum partitioning; replication cut; replication logic; size constraints; two-pin nets; two-way partitioning; Circuits; Computer science; Costs; Logic design; Partitioning algorithms; Very large scale integration;

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.384426

Filename

384426