Mirror, mirror, on the wall... is the new release any different at All?

摘要

Reduced, Ordered Binary Decision Diagrams (here, simply BDDs) have been adopted as an important data structure for a number of applications, ranging from logic design verification to logic minimization and technology mapping. However, for a number of functions that arise in practical applications, the size of the BDD data structure depends critically on the choice of the variable order: a poor order may lead to a data structure whose size grows exponentially with the number of variables. Finding an order that minimizes the size of BDDs is NP-hard; the development of heuristics for computing better variable orders is an ongoing area of research. In this paper, a Design of Experiments methodology is applied to the study of the behavior of softwarepackages which construct and manipulate BDDs.