Design of Experiments for Evaluation of BDD Packages Using Controlled Circuit Mutations

. Despite more than a decade of experience with the use of standardized benchmark circuits, meaningful comparisons of EDA algorithms remain elusive. In this paper, we introduce a new methodology for characterizing the performance of Binary Decision Diagram (BDD) algorithms. Our method involves the synthesis of large equivalence classes of functionally perturbed circuits, based on a known reference circuit. We demonstrate that such classes induce controllable distributions of BDD algorithm performance, which provide the foundation for statistically significant comparison of different algorithms. 1 Introduction We introduce methods rooted in the Design of Experiments, first formalized in [1], to evaluate the properties of programs which implement Reduced, Ordered Binary Decision Diagrams [2] (hereafter referred to as BDDs). The choice of BDD variable order has a profound impact on the size of the BDD data structure. Determining an optimal variable ordering is an NP-hard problem upon whi..