Scholarlink

The external memory BDD package Adiar can manipulate Binary Decision Diagrams (BDDs) larger than the RAM of the machine. To do so, it uses one or more priority queues to defer processing each recursion until the relevant nodes are encountered in a sequential scan. We outline how to improve the performance of Adiar’s algorithms if the BDD width of one of its inputs is small enough to fit into main memory. In this case, one of the algorithms’ priority queues can entirely be replaced with (levelised) random access to the nodes of the narrow BDD. This preserves the I/O efficiency of the original algorithm, is applicable to other types of decision diagrams, and significantly improves performance for many larger BDD computations.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Random Access on Narrow Decision Diagrams in External Memory

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Steffan Christ Sølvsten,
  • Casper Moldrup Rysgaard,
  • Jaco Van de Pol

摘要

The external memory BDD package Adiar can manipulate Binary Decision Diagrams (BDDs) larger than the RAM of the machine. To do so, it uses one or more priority queues to defer processing each recursion until the relevant nodes are encountered in a sequential scan. We outline how to improve the performance of Adiar’s algorithms if the BDD width of one of its inputs is small enough to fit into main memory. In this case, one of the algorithms’ priority queues can entirely be replaced with (levelised) random access to the nodes of the narrow BDD. This preserves the I/O efficiency of the original algorithm, is applicable to other types of decision diagrams, and significantly improves performance for many larger BDD computations.