Circuit Partitioning with Logic Perturbation

1 Traditionally, the circuit partitioning problem is done by rst modeling a circuit as a graph and then partition-ing is performed on the modeling graph. Using the con-cept of alternative wires, we propose an ecient method that is able to preserve a local optimal solution in the graph domain while a dierent graph, representing the same circuit, is generated. When a conventional graph partitioning technique reaches a local optimal solution, our proposed technique generates a dierent graph that is logically equivalent to the original circuit, and that has equal or better partitioning solution. Faced with a dierent graph which is newly generated, together with a currently good partitioning solution, a conventional graph partitioning technique may then escape from the local optimum and continue searching for better solu-tions in a dierent graph domain. The proposed tech-nique can be combined with almost any graph parti-tioner. Experiments show encouraging results.