A fast graph-based alternative wiring scheme for Boolean networks

Abstract

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 are 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.