Circuit partitioning with logic perturbation

TitleCircuit partitioning with logic perturbation
Publication TypeConference Paper
Year of Publication1995
AuthorsCheng, DI, Lin, C-C, Marek-Sadowska, M
Conference NameComputer-Aided Design, 1995. ICCAD-95. Digest of Technical Papers., 1995 IEEE/ACM International Conference on
Date Publishednov
Keywordsalternative wires, circuit partitioning, graph domain, graph partitioning, graph theory, logic CAD, logic circuits, logic partitioning, logic perturbation, modeling graph
AbstractTraditionally, the circuit partitioning problem is done by first modeling a circuit as a graph and then partitioning is performed on the modeling graph. Using the concept of alternative wires, we propose an efficient method that is able to preserve a local optimal solution in the graph domain while a different graph, representing the same circuit, is generated. When a conventional graph partitioning technique reaches a local optimal solution, our proposed technique generates a different graph that is logically equivalent to the original circuit, and that has equal or better partitioning solution. Faced with a different graph which is newly generated together with a currently good partitioning solution, a conventional graph partitioning technique may then escape from the optimum and continue searching for better solutions in a different graph domain. The proposed technique can be combined with almost any graph partitioner. Experiments show encouraging results