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

摘要

In this paper, we propose an improved network- flow based multi-way circuit partitioning algorithm whose objec- tive is to minimize the number of sub-circuits. It iteratively ex- tracts 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 num- ber of I/O pins of the residual circuit as small as possible after one-time extraction. We implemented our algorithm in C for ex- periments, and tested it with several industrial cases and MCNC benchmarks. Compared to the known approach, we observed more than 10/100 reduction in average of the sub-circuit number.