Circuit optimization by rewiring

TitleCircuit optimization by rewiring
Publication TypeJournal Article
Year of Publication1999
AuthorsChang, S-C, Van Ginneken, LPPP, Marek-Sadowska, M
JournalComputers, IEEE Transactions on
Pagination962 -970
Date Publishedsep
Keywordsautomatic test pattern generation, Boolean optimization method, circuit optimisation, circuit optimization, circuit rewiring, combinational circuits, incremental circuit restructuring, industrial applications, logic assignments, logic CAD, logic optimization, logic synthesis, multi-level combinational circuits, performance improvement, redundancy, redundancy detection algorithm, redundant wires, run time, scalability, wire redundancy checking, wiring
AbstractPresents a very efficient optimization method suitable for multi-level combinational circuits. The optimization is based on incremental restructuring of a circuit through a sequence of additions and removals of redundant wires. Our algorithm applies the techniques of automatic test pattern generation (ATPG), which can efficiently detect redundancies. During the ATPG process, certain nodes in the circuit must have particular logic assignments for a test to exist. Based on the properties of these mandatory assignments, we have developed theorems to eliminate unnecessary wire redundancy checking. This results in a significant performance improvement. The fast run time and the excellent scaling to large circuits make our Boolean optimization method practical for industrial applications