\datethis @s octa int @*Intro. This program is the twelfth in a series of exploratory studies by which I'm attempting to gain first-hand experience with OBDD structures, as I prepare Section 7.1.4 of {\sl The Art of Computer Programming}. Again it's quite different from its predecessors: This one implements a new approach to finding an optimum ordering for the variables of a given Boolean function or set of functions. The new approach is based on QDDs (quasi-reduced BDDs), which undergo the jump-up'' operation but not the normal synthesis operations of a traditional BDD package. It requires no hashing or garbage collection. The given function is specified explicitly by generating its QDD. As a demonstration, we implement the $2^m$-way multiplexer $M_m(x_1,\ldots,x_m;x_{m+1},\ldots,x_{m+2^m})$ here, because it exhibits great extremes of BDD size under different orderings. But with \.{CWEB} change files any other function can be substituted. If desired, optimization will be restricted to a subrange of the possible levels, keeping variables at the top and bottom of the BDD in place. We assume that |botvar-topvar| is at most 24. @d mm 2 /* order of MUX in this demonstration version */ @d nn (mm+(1<=1| */ @d botvar nn /* last variable whose order will be varied (must be |<=nn| */ @d nnn (botvar+1-topvar) /* variables being permuted (at most 25) */ @# @d o mems++ /* count a memory access to an octabyte */ @d oo mems+=2 /* or two */ @d ooo mems+=3 /* or three */ @d oooo mems+=4 /* or four, wow */ @c #include #include @@; @@; unsigned long long mems; @@; main () { register int h,i,j,k,l,lo,hi,jj,kk,var,cycle; octa x; @; for (cycle=1;cycle<1<<(nnn-1);cycle++) { if (cycle%interval==0) { printf("Beginning cycle %d (%llu mems so far)\n",cycle,mems); fflush(stdout); } @; } @