Circuit partitioning with coupled logic restructuring techniques

Traditionally, the circuit partitioning is done by modeling the circuit as a graph and the partitioning is carried out without altering the circuit itself. Applying the technique of circuit rewiring, the partitioning can be further improved by doing some local logic perturbation along the cut-line to drag the solution out of some local minimal. In this paper, we propose an effective coupling scheme of two powerful rewiring techniques to further improve upon those already selected best partition results produced by other conventional partition tools. The improvement is attributed to the additional capability of exercising a guided circuit perturbation, which was not available in the conventional schemes, The known ATPG-based and the recently proposed graph-based rewiring techniques compose our coupling scheme. The ATPG-based rewiring technique is very flexible; however the graph-based rewiring technique is faster and can couple quite well with the ATPG-based scheme to exploit a much larger room for logic perturbations. Our encouraging experimental results show that these two techniques couple each other quite well for this application without costing much CPU overhead. This scheme is also quite efficient thus should be very useful for large circuits.