Sampling schemes for computing OBDD variable orderings
Jawahar Jain, William W. Adams, Masahiro Fujita · 1998
: We suggest some novel variable ordering techniques based upon the notion of sampling. Such techniques can produce highly e#ective static variable orders, and can thus be employed in numerous problems where current static variable ordering techniques prove totally inadequate. They can also augmentvarious reordering techniques thereby helping to produce far superior variable orders in a comparable, or lesser, amount of time. Importantly,wehave been able to build BDDs of circuits which could not be represented previously using numerous other reordering packages. 1 Introduction Ordered Binary Decision Diagrams #3# have found extensive use in various algorithms for analyzing Boolean functions, and thus play an important role in numerous CAD related applications. Unfortunately, in many applications, very large sized BDDs can be generated which can render a BDD based analysis scheme impractical or ine#cient. In particular, OBDD sizes are very sensitive to the order chosen on input variabl...