Variable Ordering in Binary Decision Diagram using Spider Monkey Optimization for node and path length optimization

摘要

Binary Decision Diagrams (BDDs) are an important datastructure for the design of digital circuits using VLSI CAD tools. Theordering of variables affects the total number of nodes and path length inthe BDDs. Finding a good variable ordering is an optimization problem andpreviously many optimization approaches have been implemented for BDDsin a number of research works. In this paper, an optimization approachbased on Spider Monkey Optimization (SMO) algorithm is proposed forthe BDD variable ordering problem targeting number of nodes and longestpath length. SMO is a well-known swarm intelligence-based optimizationapproach based on spider monkeys foraging behavior. The proposed workhas been compared with other latest BDD reordering approaches usingParticle Swarm Optimization (PSO) algorithm. The results obtained showsignificant improvement over the Particle Swarm Optimization method.The proposed SMO-based method is applied to different benchmark digitalcircuits having different levels of complexities. The node count and longestpath length for the maximum number of tested circuits are found to be betterin SMO than PSO.