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
Diagramas de decisão binária (BDDs) são uma estrutura de dados importante para o projeto de circuitos digitais usando ferramentas CAD VLSI. A ordenação das variáveis afeta o número total de nós e o comprimento do caminho nos BDDs. Encontrar uma boa ordenação de variáveis é um problema de otimização e anteriormente muitas abordagens de otimização foram implementadas para BDDs em vários trabalhos de pesquisa. Neste artigo, uma abordagem de otimização baseada no algoritmo Spider Monkey Optimization (SMO) é proposta para o problema de ordenação de variáveis BDD visando o número de nós e o maior comprimento do caminho. SMO é uma abordagem de otimização baseada em inteligência de enxame bem conhecida, baseada no comportamento de forrageamento de macacos-aranha. O trabalho proposto foi comparado com outras abordagens mais recentes de reordenação de BDD usando o algoritmo Particle Swarm Optimization (PSO). Os resultados obtidos mostram uma melhoria significativa em relação ao método Particle Swarm Optimization. O método proposto baseado em SMO é aplicado a diferentes circuitos digitais de benchmark com diferentes níveis de complexidade. A contagem de nós e o comprimento do caminho mais longo para o número máximo de circuitos testados são melhores no SMO do que no 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.
Copiar
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
Copiar
@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},}
Copiar
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 -