Fast Boolean optimization by rewiring

TitleFast Boolean optimization by rewiring
Publication TypeConference Paper
Year of Publication1996
AuthorsChang, S-C, Van Ginneken, LPPP, Marek-Sadowska, M
Conference NameComputer-Aided Design, 1996. ICCAD-96. Digest of Technical Papers., 1996 IEEE/ACM International Conference on
Date Publishednov
Keywordsautomatic test pattern generation, automatic testing, Boolean logic optimization, boolean optimization, logic CAD, logic testing, mandatory assignments, minimisation of switching nets, rewiring
AbstractThis paper presents a very efficient Boolean logic optimization method. The boolean optimization is achieved by adding and removing redundant wires in a circuit. Our algorithm applies the reasoning of Automatic Test Pattern Generation (ATPG) which can detect redundancy efficiently. During the ATPG process, mandatory assignments are assignments which must be satisfied. Our algorithm analyzes different characteristics of mandatory assignments during the ATPG process. New theoretical results based on the analysis are presented which lead to significant performance improvements. The fast run time and the excellent scaling to large problems make our Boolean optimization method practical for industrial applications. Experiments show that the optimization results are comparable to those of Kunz and Pradhan (1994) while the run time is two orders of magnitude faster (average 126 times; speed up). Furthermore, we report optimization results for several large examples, which were previously thought to be too large to be handled by Boolean optimization methods