The search functionality is under construction.
The search functionality is under construction.

Accelerating Logic Rewiring Using Implication Analysis Tree

Chin-Ngai SZE, Wangning LONG, Yu-Liang WU, Jinian BIAN

  • Full Text Views

    0

  • Cite this

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