On improved graph-based alternative wiring scheme for multi-level logic optimization

A much extended Graph-Based Alternative Wiring (GBAW) scheme to identify alternative wires in multilevel logic with promising results is presented. By modeling subsets of circuits as minimal graphs and applying purely graph-based local pattern search technique, we have found more than 40 graph patterns which contain alternative wires within 2-edge distance from the target wire. Applying proper grouping technique for the similar patterns, the complexity of our rewiring technique can be reduced. Experimental results on MCNC benchmarks show that our technique is much faster than the ATPG-based technique RAMBO with competitive number of alternative wires found. With this augmented pattern family of alternative wires, we are able to find 30% more alternative wires compared to RAMBO with 75 times speedup on average. We applied GBAW in logic minimization as a perturbation engine and simplify the target circuit by SIS algebraic operations. Results show a further reduction of 11.1 % in literal count compared to applying algebraic operations alone. © 2000 IEEE.