For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
A Fast Graph-Based Alternative Wiring Scheme for Boolean Networks
Yu-Liang WU Wangning LONG Hongbing FAN
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2000/06/25
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))
rewiring, logic synthesis, circuit minimization, redundancy,
Full Text: PDF>>
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.