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.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copy
Kengo R. AZEGAMI, Masato INAGI, Atsushi TAKAHASHI, Yoji KAJITANI, "An Improvement of Network-Flow Based Multi-Way Circuit Partitioning Algorithm" in IEICE TRANSACTIONS on Fundamentals,
vol. E85-A, no. 3, pp. 655-663, March 2002, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e85-a_3_655/_p
Copy
@ARTICLE{e85-a_3_655,
author={Kengo R. AZEGAMI, Masato INAGI, Atsushi TAKAHASHI, Yoji KAJITANI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={An Improvement of Network-Flow Based Multi-Way Circuit Partitioning Algorithm},
year={2002},
volume={E85-A},
number={3},
pages={655-663},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={March},}
Copy
TY - JOUR
TI - An Improvement of Network-Flow Based Multi-Way Circuit Partitioning Algorithm
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 655
EP - 663
AU - Kengo R. AZEGAMI
AU - Masato INAGI
AU - Atsushi TAKAHASHI
AU - Yoji KAJITANI
PY - 2002
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E85-A
IS - 3
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - March 2002
AB - 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.
ER -