The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Les diagrammes de décision binaire (BDD) constituent une structure de données importante pour la conception de circuits numériques à l'aide des outils de CAO VLSI. L'ordre des variables affecte le nombre total de nœuds et la longueur du chemin dans les BDD. Trouver un bon ordre des variables est un problème d'optimisation et de nombreuses approches d'optimisation ont déjà été mises en œuvre pour les BDD dans un certain nombre de travaux de recherche. Dans cet article, une approche d'optimisation basée sur l'algorithme Spider Monkey Optimization (SMO) est proposée pour le problème d'ordre des variables BDD ciblant le nombre de nœuds et la longueur de chemin la plus longue. SMO est une approche d’optimisation bien connue basée sur l’intelligence en essaim et basée sur le comportement de recherche de nourriture des singes-araignées. Le travail proposé a été comparé à d’autres approches de réorganisation BDD récentes utilisant l’algorithme Particle Swarm Optimization (PSO). Les résultats obtenus montrent une amélioration significative par rapport à la méthode d’optimisation par essaim de particules. La méthode proposée basée sur SMO est appliquée à différents circuits numériques de référence présentant différents niveaux de complexité. Le nombre de nœuds et la longueur de chemin la plus longue pour le nombre maximum de circuits testés se révèlent meilleurs en SMO qu'en PSO.
Mohammed BALAL SIDDIQUI
Jamia Millia Islamia
Mirza TARIQ BEG
Jamia Millia Islamia
Syed NASEEM AHMAD
Jamia Millia Islamia
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copier
Mohammed BALAL SIDDIQUI, Mirza TARIQ BEG, Syed NASEEM AHMAD, "Variable Ordering in Binary Decision Diagram Using Spider Monkey Optimization for Node and Path Length Optimization" in IEICE TRANSACTIONS on Fundamentals,
vol. E106-A, no. 7, pp. 976-989, July 2023, doi: 10.1587/transfun.2021EAP1108.
Abstract: Binary Decision Diagrams (BDDs) are an important data structure for the design of digital circuits using VLSI CAD tools. The ordering of variables affects the total number of nodes and path length in the BDDs. Finding a good variable ordering is an optimization problem and previously many optimization approaches have been implemented for BDDs in a number of research works. In this paper, an optimization approach based on Spider Monkey Optimization (SMO) algorithm is proposed for the BDD variable ordering problem targeting number of nodes and longest path length. SMO is a well-known swarm intelligence-based optimization approach based on spider monkeys foraging behavior. The proposed work has been compared with other latest BDD reordering approaches using Particle Swarm Optimization (PSO) algorithm. The results obtained show significant improvement over the Particle Swarm Optimization method. The proposed SMO-based method is applied to different benchmark digital circuits having different levels of complexities. The node count and longest path length for the maximum number of tested circuits are found to be better in SMO than PSO.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2021EAP1108/_p
Copier
@ARTICLE{e106-a_7_976,
author={Mohammed BALAL SIDDIQUI, Mirza TARIQ BEG, Syed NASEEM AHMAD, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Variable Ordering in Binary Decision Diagram Using Spider Monkey Optimization for Node and Path Length Optimization},
year={2023},
volume={E106-A},
number={7},
pages={976-989},
abstract={Binary Decision Diagrams (BDDs) are an important data structure for the design of digital circuits using VLSI CAD tools. The ordering of variables affects the total number of nodes and path length in the BDDs. Finding a good variable ordering is an optimization problem and previously many optimization approaches have been implemented for BDDs in a number of research works. In this paper, an optimization approach based on Spider Monkey Optimization (SMO) algorithm is proposed for the BDD variable ordering problem targeting number of nodes and longest path length. SMO is a well-known swarm intelligence-based optimization approach based on spider monkeys foraging behavior. The proposed work has been compared with other latest BDD reordering approaches using Particle Swarm Optimization (PSO) algorithm. The results obtained show significant improvement over the Particle Swarm Optimization method. The proposed SMO-based method is applied to different benchmark digital circuits having different levels of complexities. The node count and longest path length for the maximum number of tested circuits are found to be better in SMO than PSO.},
keywords={},
doi={10.1587/transfun.2021EAP1108},
ISSN={1745-1337},
month={July},}
Copier
TY - JOUR
TI - Variable Ordering in Binary Decision Diagram Using Spider Monkey Optimization for Node and Path Length Optimization
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 976
EP - 989
AU - Mohammed BALAL SIDDIQUI
AU - Mirza TARIQ BEG
AU - Syed NASEEM AHMAD
PY - 2023
DO - 10.1587/transfun.2021EAP1108
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E106-A
IS - 7
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - July 2023
AB - Binary Decision Diagrams (BDDs) are an important data structure for the design of digital circuits using VLSI CAD tools. The ordering of variables affects the total number of nodes and path length in the BDDs. Finding a good variable ordering is an optimization problem and previously many optimization approaches have been implemented for BDDs in a number of research works. In this paper, an optimization approach based on Spider Monkey Optimization (SMO) algorithm is proposed for the BDD variable ordering problem targeting number of nodes and longest path length. SMO is a well-known swarm intelligence-based optimization approach based on spider monkeys foraging behavior. The proposed work has been compared with other latest BDD reordering approaches using Particle Swarm Optimization (PSO) algorithm. The results obtained show significant improvement over the Particle Swarm Optimization method. The proposed SMO-based method is applied to different benchmark digital circuits having different levels of complexities. The node count and longest path length for the maximum number of tested circuits are found to be better in SMO than PSO.
ER -