Title | Circuit partitioning with logic perturbation |

Publication Type | Conference Paper |

Year of Publication | 1995 |

Authors | Cheng, DI, Lin, C-C, Marek-Sadowska, M |

Conference Name | Computer-Aided Design, 1995. ICCAD-95. Digest of Technical Papers., 1995 IEEE/ACM International Conference on |

Date Published | nov |

Keywords | alternative wires, circuit partitioning, graph domain, graph partitioning, graph theory, logic CAD, logic circuits, logic partitioning, logic perturbation, modeling graph |

Abstract | Traditionally, 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 |

DOI | 10.1109/ICCAD.1995.480198 |