From 4812c90424dfc40d26725244723887a2d16ddfd9 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Mon, 1 Oct 2007 08:01:00 -0700 Subject: Version abc71001 --- src/misc/espresso/reduce.c | 258 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 258 insertions(+) create mode 100644 src/misc/espresso/reduce.c (limited to 'src/misc/espresso/reduce.c') diff --git a/src/misc/espresso/reduce.c b/src/misc/espresso/reduce.c new file mode 100644 index 00000000..00e4507f --- /dev/null +++ b/src/misc/espresso/reduce.c @@ -0,0 +1,258 @@ +/* + * Revision Control Information + * + * $Source$ + * $Author$ + * $Revision$ + * $Date$ + * + */ +/* + module: reduce.c + purpose: Perform the Espresso-II reduction step + + Reduction is a technique used to explore larger regions of the + optimization space. We replace each cube of F with a smaller + cube while still maintaining a cover of the same logic function. +*/ + +#include "espresso.h" + +static bool toggle = TRUE; + + +/* + reduce -- replace each cube in F with its reduction + + The reduction of a cube is the smallest cube contained in the cube + which can replace the cube in the original cover without changing + the cover. This is equivalent to the super cube of all of the + essential points in the cube. This can be computed directly. + + The problem is that the order in which the cubes are reduced can + greatly affect the final result. We alternate between two ordering + strategies: + + (1) Order the cubes in ascending order of distance from the + largest cube breaking ties by ordering cubes of equal distance + in descending order of size (sort_reduce) + + (2) Order the cubes in descending order of the inner-product of + the cube and the column sums (mini_sort) + + The real workhorse of this section is the routine SCCC which is + used to find the Smallest Cube Containing the Complement of a cover. + Reduction as proposed by Espresso-II takes a cube and computes its + maximal reduction as the intersection between the cube and the + smallest cube containing the complement of (F u D - {c}) cofactored + against c. + + As usual, the unate-recursive paradigm is used to compute SCCC. + The SCCC of a unate cover is trivial to compute, and thus we perform + Shannon Cofactor expansion attempting to drive the cover to be unate + as fast as possible. +*/ + +pcover reduce(F, D) +INOUT pcover F; +IN pcover D; +{ + register pcube last, p, cunder, *FD; + + /* Order the cubes */ + if (use_random_order) + F = random_order(F); + else { + F = toggle ? sort_reduce(F) : mini_sort(F, descend); + toggle = ! toggle; + } + + /* Try to reduce each cube */ + FD = cube2list(F, D); + foreach_set(F, last, p) { + cunder = reduce_cube(FD, p); /* reduce the cube */ + if (setp_equal(cunder, p)) { /* see if it actually did */ + SET(p, ACTIVE); /* cube remains active */ + SET(p, PRIME); /* cube remains prime ? */ + } else { + if (debug & REDUCE) { + printf("REDUCE: %s to %s %s\n", + pc1(p), pc2(cunder), print_time(ptime())); + } + set_copy(p, cunder); /* save reduced version */ + RESET(p, PRIME); /* cube is no longer prime */ + if (setp_empty(cunder)) + RESET(p, ACTIVE); /* if null, kill the cube */ + else + SET(p, ACTIVE); /* cube is active */ + } + free_cube(cunder); + } + free_cubelist(FD); + + /* Delete any cubes of F which reduced to the empty cube */ + return sf_inactive(F); +} + +/* reduce_cube -- find the maximal reduction of a cube */ +pcube reduce_cube(FD, p) +IN pcube *FD, p; +{ + pcube cunder; + + cunder = sccc(cofactor(FD, p)); + return set_and(cunder, cunder, p); +} + + +/* sccc -- find Smallest Cube Containing the Complement of a cover */ +pcube sccc(T) +INOUT pcube *T; /* T will be disposed of */ +{ + pcube r; + register pcube cl, cr; + register int best; + static int sccc_level = 0; + + if (debug & REDUCE1) { + debug_print(T, "SCCC", sccc_level++); + } + + if (sccc_special_cases(T, &r) == MAYBE) { + cl = new_cube(); + cr = new_cube(); + best = binate_split_select(T, cl, cr, REDUCE1); + r = sccc_merge(sccc(scofactor(T, cl, best)), + sccc(scofactor(T, cr, best)), cl, cr); + free_cubelist(T); + } + + if (debug & REDUCE1) + printf("SCCC[%d]: result is %s\n", --sccc_level, pc1(r)); + return r; +} + + +pcube sccc_merge(left, right, cl, cr) +INOUT register pcube left, right; /* will be disposed of ... */ +INOUT register pcube cl, cr; /* will be disposed of ... */ +{ + INLINEset_and(left, left, cl); + INLINEset_and(right, right, cr); + INLINEset_or(left, left, right); + free_cube(right); + free_cube(cl); + free_cube(cr); + return left; +} + + +/* + sccc_cube -- find the smallest cube containing the complement of a cube + + By DeMorgan's law and the fact that the smallest cube containing a + cover is the "or" of the positional cubes, it is simple to see that + the SCCC is the universe if the cube has more than two active + variables. If there is only a single active variable, then the + SCCC is merely the bitwise complement of the cube in that + variable. A last special case is no active variables, in which + case the SCCC is empty. + + This is "anded" with the incoming cube result. +*/ +pcube sccc_cube(result, p) +register pcube result, p; +{ + register pcube temp=cube.temp[0], mask; + int var; + + if ((var = cactive(p)) >= 0) { + mask = cube.var_mask[var]; + INLINEset_xor(temp, p, mask); + INLINEset_and(result, result, temp); + } + return result; +} + +/* + * sccc_special_cases -- check the special cases for sccc + */ + +bool sccc_special_cases(T, result) +INOUT pcube *T; /* will be disposed if answer is determined */ +OUT pcube *result; /* returned only if answer determined */ +{ + register pcube *T1, p, temp = cube.temp[1], ceil, cof = T[0]; + pcube *A, *B; + + /* empty cover => complement is universe => SCCC is universe */ + if (T[2] == NULL) { + *result = set_save(cube.fullset); + free_cubelist(T); + return TRUE; + } + + /* row of 1's => complement is empty => SCCC is empty */ + for(T1 = T+2; (p = *T1++) != NULL; ) { + if (full_row(p, cof)) { + *result = new_cube(); + free_cubelist(T); + return TRUE; + } + } + + /* Collect column counts, determine unate variables, etc. */ + massive_count(T); + + /* If cover is unate (or single cube), apply simple rules to find SCCCU */ + if (cdata.vars_unate == cdata.vars_active || T[3] == NULL) { + *result = set_save(cube.fullset); + for(T1 = T+2; (p = *T1++) != NULL; ) { + (void) sccc_cube(*result, set_or(temp, p, cof)); + } + free_cubelist(T); + return TRUE; + } + + /* Check for column of 0's (which can be easily factored( */ + ceil = set_save(cof); + for(T1 = T+2; (p = *T1++) != NULL; ) { + INLINEset_or(ceil, ceil, p); + } + if (! setp_equal(ceil, cube.fullset)) { + *result = sccc_cube(set_save(cube.fullset), ceil); + if (setp_equal(*result, cube.fullset)) { + free_cube(ceil); + } else { + *result = sccc_merge(sccc(cofactor(T,ceil)), + set_save(cube.fullset), ceil, *result); + } + free_cubelist(T); + return TRUE; + } + free_cube(ceil); + + /* Single active column at this point => tautology => SCCC is empty */ + if (cdata.vars_active == 1) { + *result = new_cube(); + free_cubelist(T); + return TRUE; + } + + /* Check for components */ + if (cdata.var_zeros[cdata.best] < CUBELISTSIZE(T)/2) { + if (cubelist_partition(T, &A, &B, debug & REDUCE1) == 0) { + return MAYBE; + } else { + free_cubelist(T); + *result = sccc(A); + ceil = sccc(B); + (void) set_and(*result, *result, ceil); + set_free(ceil); + return TRUE; + } + } + + /* Not much we can do about it */ + return MAYBE; +} -- cgit v1.2.3