An Improvement of Network-Flow Based Multi-Way Circuit Partitioning Algorithm

Kengo R. AZEGAMI  Masato INAGI  Atsushi TAKAHASHI  Yoji KAJITANI  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E85-A   No.3   pp.655-663
Publication Date: 2002/03/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: VLSI Design Technology and CAD
Keyword: 
circuit partition,  hyper-graph partition,  network flow,  min-cut,  integrated circuit design,  

Full Text: PDF(614.2KB)>>
Buy this Article




Summary: 
In this paper, we propose an improved network-flow based multi-way circuit partitioning algorithm whose objective is to minimize the number of sub-circuits. It iteratively extracts a size-maximal feasible sub-circuit one at a time. In our approach, two devices are applied. One is in the use of an exact min-cut graph, and the other is in the idea of keeping the number of I/O pins of the residual circuit as small as possible after one-time extraction. We implemented our algorithm in C for experiments, and tested it with several industrial cases and MCNC benchmarks. Compared to the known approach, we observed more than 10% reduction in average of the sub-circuit number.