Accelerating Logic Rewiring Using Implication Analysis Tree

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

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E85-A   No.12   pp.2725-2736
Publication Date: 2002/12/01
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)
Category: Logic Synthesis
alternative wire,  logic transformation,  logic synthesis,  

Full Text: PDF>>
Buy this Article

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.