espresso.c 3.66 KB
Newer Older
Alan Mishchenko committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
/*
 * Revision Control Information
 *
 * $Source$
 * $Author$
 * $Revision$
 * $Date$
 *
 */
/*
 *  Module: espresso.c
 *  Purpose: The main espresso algorithm
 *
 *  Returns a minimized version of the ON-set of a function
 *
 *  The following global variables affect the operation of Espresso:
 *
 *  MISCELLANEOUS:
 *      trace
 *          print trace information as the minimization progresses
 *
 *      remove_essential
 *          remove essential primes
 *
 *      single_expand
 *          if true, stop after first expand/irredundant
 *
 *  LAST_GASP or SUPER_GASP strategy:
 *      use_super_gasp
 *          uses the super_gasp strategy rather than last_gasp
 *
 *  SETUP strategy:
 *      recompute_onset
 *          recompute onset using the complement before starting
 *
 *      unwrap_onset
 *          unwrap the function output part before first expand
 *
 *  MAKE_SPARSE strategy:
 *      force_irredundant
 *          iterates make_sparse to force a minimal solution (used
 *          indirectly by make_sparse)
 *
 *      skip_make_sparse
 *          skip the make_sparse step (used by opo only)
 */

#include "espresso.h"

50 51 52
ABC_NAMESPACE_IMPL_START


Alan Mishchenko committed
53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142
pcover espresso(F, D1, R)
pcover F, D1, R;
{
    pcover E, D, Fsave;
    pset last, p;
    cost_t cost, best_cost;

begin:
    Fsave = sf_save(F);        /* save original function */
    D = sf_save(D1);        /* make a scratch copy of D */

    /* Setup has always been a problem */
    if (recompute_onset) {
    EXEC(E = simplify(cube1list(F)),     "SIMPLIFY   ", E);
    free_cover(F);
    F = E;
    }
    cover_cost(F, &cost);
    if (unwrap_onset && (cube.part_size[cube.num_vars - 1] > 1)
      && (cost.out != cost.cubes*cube.part_size[cube.num_vars-1])
      && (cost.out < 5000))
    EXEC(F = sf_contain(unravel(F, cube.num_vars - 1)), "SETUP      ", F);

    /* Initial expand and irredundant */
    foreach_set(F, last, p) {
    RESET(p, PRIME);
    }
    EXECUTE(F = expand(F, R, FALSE), EXPAND_TIME, F, cost);
    EXECUTE(F = irredundant(F, D), IRRED_TIME, F, cost);

    if (! single_expand) {
    if (remove_essential) {
        EXECUTE(E = essential(&F, &D), ESSEN_TIME, E, cost);
    } else {
        E = new_cover(0);
    }

    cover_cost(F, &cost);
    do {

        /* Repeat inner loop until solution becomes "stable" */
        do {
        copy_cost(&cost, &best_cost);
        EXECUTE(F = reduce(F, D), REDUCE_TIME, F, cost);
        EXECUTE(F = expand(F, R, FALSE), EXPAND_TIME, F, cost);
        EXECUTE(F = irredundant(F, D), IRRED_TIME, F, cost);
        } while (cost.cubes < best_cost.cubes);

        /* Perturb solution to see if we can continue to iterate */
        copy_cost(&cost, &best_cost);
        if (use_super_gasp) {
        F = super_gasp(F, D, R, &cost);
        if (cost.cubes >= best_cost.cubes)
            break;
        } else {
        F = last_gasp(F, D, R, &cost);
        }

    } while (cost.cubes < best_cost.cubes ||
        (cost.cubes == best_cost.cubes && cost.total < best_cost.total));

    /* Append the essential cubes to F */
    F = sf_append(F, E);                /* disposes of E */
    if (trace) size_stamp(F, "ADJUST     ");
    }

    /* Free the D which we used */
    free_cover(D);

    /* Attempt to make the PLA matrix sparse */
    if (! skip_make_sparse) {
    F = make_sparse(F, D1, R);
    }

    /*
     *  Check to make sure function is actually smaller !!
     *  This can only happen because of the initial unravel.  If we fail,
     *  then run the whole thing again without the unravel.
     */
    if (Fsave->count < F->count) {
    free_cover(F);
    F = Fsave;
    unwrap_onset = FALSE;
    goto begin;
    } else {
    free_cover(Fsave);
    }

    return F;
}
143 144
ABC_NAMESPACE_IMPL_END