• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Canadian journal of electrical and computer engineering >A new approach for minimization of binary decision diagrams
【24h】

A new approach for minimization of binary decision diagrams

机译：最小化二进制决策图的新方法

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Cet article propose une nouvelle approche qui trouve avec succès l'ordre optimal des variables pour presque tous les diagrammes d'ordre réduit de décision binaire (DDB) dans les circuits de tests de performance LGSynth91 avec jusqu'à 500 variables. Toutes les approches connues à ce jour peuvent résoudre uniquement des fonctions avec moins de 64 variables. Le progrès de la nouvelle approche est attribué au concept d'algorithmes aléatoires qui réduisent significativement l'influence de l'ordre initial des variables sur la performance de la minimisation. De plus, les propriétés des différents algorithmes de minimisation de DDB peuvent aussi être mesurées. Les résultats sont raffinés graduellement durant le progrès de la minimisation afin que des résultats valides approximés puissent être dérivés avant que le long processus ne se termine. La performance de l'approche proposée est illustrée à l'aide de son application sur les circuits de tests de performance LGSynth91. Des résultats expérimentaux démontrent que l'algorithme aléatoire est incorporé de façon appropriée. Ainsi, la performance demeure constante pour un large ensemble des circuits de tests. En plus de fournir un algorithme réalisable de minimisation de DDB, cet article présente des résultats statistiques et des analyses qui pourraient être utiles à des recherches connexes.%This paper proposes a new approach that successfully finds the optimal variable orderings for almost all reduced ordered binary decision diagrams (BDDs) in the LGSynth91 benchmark circuits with up to 500 variables. All previously known approaches can solve only functions with less than 64 variables. The progress of the new approach is attributable to the concept of randomized algorithms, which significantly reduce the influence of the initial variable ordering on the minimization performance. Furthermore, the features of different BDD minimization algorithms can also be measured as a result. The results are gradually refined during the minimization progress, such that valid approximate results can be derived before a time-consuming process terminates. The performance of the proposed approach is illustrated through its application on LGSynth91 benchmark circuits. Experimental results demonstrate that the randomized algorithm is properly incorporated; thus the performance remains consistent for a large set of benchmark circuits. In addition to providing a feasible BDD minimization algorithm, this paper presents statistical results and analyses that could be helpful for related research.
机译：本文提出了一种新方法，该方法可以为多达500个变量的LGSynth91性能测试电路中的几乎所有简化的二进制决策顺序（DDB）图成功找到变量的最佳顺序。迄今为止，所有已知方法只能求解少于64个变量的函数。新方法的进展归因于随机算法的概念，该算法显着减少了变量初始顺序对最小化性能的影响。此外，还可以测量各种DDB最小化算法的属性。在最小化过程中逐步完善结果，以便可以在漫长的过程结束之前获得近似有效的结果。通过在LGSynth91性能测试电路上的应用说明了该方法的性能。实验结果表明，随机算法已被适当地合并。因此，对于大量测试电路，性能保持恒定。除了提供可行的DDB最小化算法外，本文还提供了可用于相关研究的统计结果和分析。％本文提出了一种新方法，该方法可以成功地找到几乎所有降阶二阶二进制数的最优变量有序LGSynth91基准电路中的决策图（BDD），最多包含500个变量。所有以前已知的方法只能求解少于64个变量的函数。新方法的进展归因于随机算法的概念，该算法极大地减少了初始变量排序对最小化性能的影响。此外，还可以测量不同的BDD最小化算法的功能。在最小化过程中逐步完善结果，以便可以在耗时的过程终止之前得出有效的近似结果。通过在LGSynth91基准电路上的应用说明了该方法的性能。实验结果表明，该随机算法得到了正确的融合。因此，对于大量基准电路而言，性能保持一致。除了提供可行的BDD最小化算法外，本文还提供了统计结果和分析，可能对相关研究有所帮助。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号