Title :
Circuit optimization by rewiring
Author :
Shih-Chieh Chang ; Van Ginneken, L.P.P.P. ; Marek-Sadowska, M.
Author_Institution :
Dept. of Comput. Sci. & Inf., Nat. Chung Cheng Univ., Chiyai, Taiwan
Abstract :
Presents 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.
Keywords :
automatic test pattern generation; circuit optimisation; combinational circuits; logic CAD; redundancy; wiring; Boolean optimization method; automatic test pattern generation; circuit optimization; circuit rewiring; incremental circuit restructuring; industrial applications; logic assignments; logic optimization; logic synthesis; multi-level combinational circuits; performance improvement; redundancy detection algorithm; redundant wires; run time; scalability; wire redundancy checking; Automatic test pattern generation; Circuit optimization; Circuit synthesis; Circuit testing; Combinational circuits; Logic testing; Network synthesis; Observability; Optimization methods; Wire;
Journal_Title :
Computers, IEEE Transactions on
