Design and Implementation of OBDD Variable Ordering/ Reordering Methods

OBDD变量排序/重排序方法的设计与实现

• 批准号: 9633085
• 负责人: Mitchell Thornton
• 金额: $ 10.55万
• 依托单位: University of Arkansas
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1996
• 资助国家: 美国
• 起止时间: 1996-10-01 至 1999-11-05
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9633085&HistoricalAwards=false
• 关键词: Design; Implementation; OBDD; Variable; Ordering

This research is on the design and implementation of ordered binary decision diagram (OBDD) variable ordering and reordering methods. The work explores the use of memory-efficient data structures, called Decision Diagrams (DD), to describe the behavior of Boolean functions. Being developed is a methodology for finding an ordering of the Boolean function variables so that the DD has minimal size. This research exploits the use of conditional probabilities for the purposes of variable ordering and dynamic reordering. Efficient techniques for computation of the spectrum of a Boolean function using its OBDD representation as input are being used. Software is being developed to manipulate OBDDs as well as compute the probability values.

本文研究的是有序二叉决策图(OBDD)变量排序和重排方法的设计与实现。这项工作探索了使用内存高效的数据结构，称为决策图(DD)，来描述布尔函数的行为。正在开发一种方法，用于找到布尔函数变量的排序，从而使DD具有最小的大小。这项研究利用条件概率来进行变量排序和动态重新排序。正在使用使用布尔函数的OBDD表示作为输入来计算布尔函数的谱的有效技术。正在开发软件来处理OBDDS以及计算概率值。