A Fast Graph-Based Alternative Wiring Scheme for Boolean Networks

Yu-Liang WU  Wangning LONG  Hongbing FAN  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E83-A   No.6   pp.1131-1137
Publication Date: 2000/06/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section of Papers Selected from 1999 International Technical Conference on Circuits/Systems, Computers and Communications (ITC-CSCC'99))
Category: 
Keyword: 
rewiring,  logic synthesis,  circuit minimization,  redundancy,  

Full Text: PDF>>
Buy this Article




Summary: 
Alternative wiring techniques have been shown to be very useful for many EDA problems. The currently used rewiring techniques are mainly ATPG based. In this paper, we study the approach of applying purely graph-based local pattern search methods in locating alternative wires. The method searches minimal graph patterns containing alternative wires that limited to 2 edges distant from the target wire. The experimental result shows that this scheme is very fast and has the advantage of searching both the nearby forward and backward alternative wires easily. The overall number of alternative wires searched is quite comparable (104%), compared to the forward search only RAMBO version, and the CPU time is 200 times faster. We also illustrate its usage, among many others, by a simple coupling with the SIS algebraic operations and let this rewiring tool serve as a netlist-perturbing engine for logic minimization. The coupling scheme shows a further reduction of 8.5% in area compared to applying algebraic script alone, with a nearly negligible CPU overhead spent in rewiring.