TY - GEN
T1 - Ant colony optimization and its application to Boolean satisfiability for digital VLSI circuits
AU - Sethuram, Rajamani
AU - Parashar, Manish
PY - 2006
Y1 - 2006
N2 - Ant Colony Optimization (ACO) [8] is a non-deterministic algorithm framework that mimics the foraging behavior of ants to solve difficult optimization problems. Several researchers have successfully applied ACO framework in different fields of engineering, but never in VLSI testing. In this paper, we (Est describe the basics of the ACO framework and ways to formulate different optimization problems within an ACO framework. We then present our own ACO algorithm to simultaneously solve multiple Boolean SAT instances for digital VLSI circuits. Experiments conducted on scanned versions of ISCAS'89 benchmark circuits produced astonishing results. ACO framework for Boolean SatisiŒbility was found 200 times faster than spectral meta-heuristics [36] run in combinational mode. ACO framework has proven to be a promising optimization technique in large number of other fields. Since ACO can be used to solve different types of optimization and search problems, we believe that the concepts presented in this paper can open the gates for researchers solving different optimization problems that exist in VLSI testing more efficiently.
AB - Ant Colony Optimization (ACO) [8] is a non-deterministic algorithm framework that mimics the foraging behavior of ants to solve difficult optimization problems. Several researchers have successfully applied ACO framework in different fields of engineering, but never in VLSI testing. In this paper, we (Est describe the basics of the ACO framework and ways to formulate different optimization problems within an ACO framework. We then present our own ACO algorithm to simultaneously solve multiple Boolean SAT instances for digital VLSI circuits. Experiments conducted on scanned versions of ISCAS'89 benchmark circuits produced astonishing results. ACO framework for Boolean SatisiŒbility was found 200 times faster than spectral meta-heuristics [36] run in combinational mode. ACO framework has proven to be a promising optimization technique in large number of other fields. Since ACO can be used to solve different types of optimization and search problems, we believe that the concepts presented in this paper can open the gates for researchers solving different optimization problems that exist in VLSI testing more efficiently.
UR - http://www.scopus.com/inward/record.url?scp=47649093367&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=47649093367&partnerID=8YFLogxK
U2 - 10.1109/ADCOM.2006.4289945
DO - 10.1109/ADCOM.2006.4289945
M3 - Conference contribution
AN - SCOPUS:47649093367
SN - 142440715X
SN - 9781424407156
T3 - Proceedings - 2006 14th International Conference on Advanced Computing and Communications, ADCOM 2006
SP - 507
EP - 512
BT - Proceedings - 2006 14th International Conference on Advanced Computing and Communications, ADCOM 2006
T2 - 14th International Conference on Advanced Computing and Communications, ADCOM 2006
Y2 - 20 December 2006 through 23 December 2006
ER -