IEICE TRANSACTIONS on Fundamentals
Accelerating Logic Rewiring Using Implication Analysis Tree
Summary :
In this paper, we present a novel algorithm to the alternative wiring problem by analyzing the implication relationship between nodes of alternative wires. Alternative wiring, or rewiring, refers to the process of adding a redundant connection to a circuit so as to make a target connection redundant and removable from the circuit without altering the functionality of the circuit. The well-known ATPG-based alternative wiring scheme, Redundancy Addition and Removal for Multi-level Boolean Optimization (RAMBO), has shown its effectiveness in solving the problem in the last decade. But, the deficiency of RAMBO lies in its long execution time for redundancy identification among a large set of candidate alternative wires. Our approaches of redundancy identification by source node and destination node implication relationship indicate that a large subset of unnecessary redundancy check processes can be further avoided to improve the efficiency significantly. We propose an algorithm, the Implication Based Alternative Wiring Logic Transformation (IBAW), to integrate the two adroit techniques. IBAW provides a competent solution to the alternative wiring problem and shows an outstanding efficiency in our experiments. Experiments were performed on MCNC benchmark circuits. Results show that IBAW runs 6.8 times faster than the original RAMBO in locating alternative wires and solution quality is maintained.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E85-A No.12 pp.2725-2736
- Publication Date
- 2002/12/01
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)
- Category
- Logic Synthesis
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
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.
Cite this
Copy
Chin-Ngai SZE, Wangning LONG, Yu-Liang WU, Jinian BIAN, "Accelerating Logic Rewiring Using Implication Analysis Tree" in IEICE TRANSACTIONS on Fundamentals,
vol. E85-A, no. 12, pp. 2725-2736, December 2002, doi: .
Abstract: In this paper, we present a novel algorithm to the alternative wiring problem by analyzing the implication relationship between nodes of alternative wires. Alternative wiring, or rewiring, refers to the process of adding a redundant connection to a circuit so as to make a target connection redundant and removable from the circuit without altering the functionality of the circuit. The well-known ATPG-based alternative wiring scheme, Redundancy Addition and Removal for Multi-level Boolean Optimization (RAMBO), has shown its effectiveness in solving the problem in the last decade. But, the deficiency of RAMBO lies in its long execution time for redundancy identification among a large set of candidate alternative wires. Our approaches of redundancy identification by source node and destination node implication relationship indicate that a large subset of unnecessary redundancy check processes can be further avoided to improve the efficiency significantly. We propose an algorithm, the Implication Based Alternative Wiring Logic Transformation (IBAW), to integrate the two adroit techniques. IBAW provides a competent solution to the alternative wiring problem and shows an outstanding efficiency in our experiments. Experiments were performed on MCNC benchmark circuits. Results show that IBAW runs 6.8 times faster than the original RAMBO in locating alternative wires and solution quality is maintained.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e85-a_12_2725/_p
Copy
@ARTICLE{e85-a_12_2725,
author={Chin-Ngai SZE, Wangning LONG, Yu-Liang WU, Jinian BIAN, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Accelerating Logic Rewiring Using Implication Analysis Tree},
year={2002},
volume={E85-A},
number={12},
pages={2725-2736},
abstract={In this paper, we present a novel algorithm to the alternative wiring problem by analyzing the implication relationship between nodes of alternative wires. Alternative wiring, or rewiring, refers to the process of adding a redundant connection to a circuit so as to make a target connection redundant and removable from the circuit without altering the functionality of the circuit. The well-known ATPG-based alternative wiring scheme, Redundancy Addition and Removal for Multi-level Boolean Optimization (RAMBO), has shown its effectiveness in solving the problem in the last decade. But, the deficiency of RAMBO lies in its long execution time for redundancy identification among a large set of candidate alternative wires. Our approaches of redundancy identification by source node and destination node implication relationship indicate that a large subset of unnecessary redundancy check processes can be further avoided to improve the efficiency significantly. We propose an algorithm, the Implication Based Alternative Wiring Logic Transformation (IBAW), to integrate the two adroit techniques. IBAW provides a competent solution to the alternative wiring problem and shows an outstanding efficiency in our experiments. Experiments were performed on MCNC benchmark circuits. Results show that IBAW runs 6.8 times faster than the original RAMBO in locating alternative wires and solution quality is maintained.},
keywords={},
doi={},
ISSN={},
month={December},}
Copy
TY - JOUR
TI - Accelerating Logic Rewiring Using Implication Analysis Tree
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2725
EP - 2736
AU - Chin-Ngai SZE
AU - Wangning LONG
AU - Yu-Liang WU
AU - Jinian BIAN
PY - 2002
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E85-A
IS - 12
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - December 2002
AB - In this paper, we present a novel algorithm to the alternative wiring problem by analyzing the implication relationship between nodes of alternative wires. Alternative wiring, or rewiring, refers to the process of adding a redundant connection to a circuit so as to make a target connection redundant and removable from the circuit without altering the functionality of the circuit. The well-known ATPG-based alternative wiring scheme, Redundancy Addition and Removal for Multi-level Boolean Optimization (RAMBO), has shown its effectiveness in solving the problem in the last decade. But, the deficiency of RAMBO lies in its long execution time for redundancy identification among a large set of candidate alternative wires. Our approaches of redundancy identification by source node and destination node implication relationship indicate that a large subset of unnecessary redundancy check processes can be further avoided to improve the efficiency significantly. We propose an algorithm, the Implication Based Alternative Wiring Logic Transformation (IBAW), to integrate the two adroit techniques. IBAW provides a competent solution to the alternative wiring problem and shows an outstanding efficiency in our experiments. Experiments were performed on MCNC benchmark circuits. Results show that IBAW runs 6.8 times faster than the original RAMBO in locating alternative wires and solution quality is maintained.
ER -
English
