minimize.c

主要进行大规模的电路综合

/*
 * Revision Control Information
 *
 * $Source: /projects/mvsis/Repository/mvsis-1.3/src/sis/minimize/minimize.c,v $
 * $Author: wjiang $
 * $Revision: 1.1.1.1 $
 * $Date: 2003/02/24 22:24:09 $
 *
 */
/******************************************************************************
 * This module has been written by Abdul A. Malik                             *
 * Please forward all feedback, comments, bugs etc to:                        *
 *                                                                            *
 * ABDUL A. MALIK                                                             *
 * [e-mail]                                                      *
 *                                                                            *
 * Department of Electrical Engineering and Computer Sciences                 *
 * University of California at Berkeley                                       *
 * Berkeley, CA 94704.                                                        *
 *                                                                            *
 * Telephone: [phone]                                                  *
 ******************************************************************************/

/*
 *  Module: minimize.c
 *
 *  Purpose: To do minimization without evaluating the complement of (FUD).
 *           This module contains two routines for minimization: nocomp()
 *	     and snocomp(). nocomp() is similar to espresso() except that
 *	     it uses reduced offset rather than the entire offset. snocomp()
 *	     also uses reduced offsets rather than entire offset but it does
 * 	     a single pass consisting of essential(), reduce(), expand(),
 *	     and irredundant().
 *
 *	     The subroutine minimize(F, D, single_pass) is written to decide
 *	     whether nocomp() or snocomp() is to be used. If the third 
 *	     argument single_pass is TRUE sncomp(F, D) is passed, otherwise
 *	     nocomp(F, D) is called. F and D are the Onset and the Don't Care
 *	     sets.
 *
 *
 *  Returns a minimized version of the ON-set of a function
 *
 *  The following global variables affect the operation of nocomp:
 *
 *  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 "sis.h"
#define extern  
#include "min_int.h"
#undef extern
#include "minimize.h"

static pset_family ncp_abs_covered_many();
static pset_family ncp_abs_covered();
static int ncp_abs_select_restricted();

static bool toggle = TRUE;

/*
 * minimize -- choose between nocomp(), snocomp(), dc_simplify().
 */

pcover
minimize(F, D, type)
pcover F;
pcover D;
int type;

{

    if (type == SNOCOMP)
        return(snocomp(F, D));

    else if (type == NOCOMP)
        return(nocomp(F, D));

    else if (type == DCSIMPLIFY)
        return(dcsimp(F, D));

    else {
	fail("Wrong minimize type");
	exit(-1);
	return(F);
    }

}

/*
 * nocomp(): Do minimization whithout computing complement of (F U D).
 */

pcover
nocomp(F, D1)
pcover F, D1;

{
    pcover E, D, Fsave, Fold, Fbest_save;
    pset last, p;
    cost_t cost, best_cost, best_save_cost;
    bool skip_gasp = FALSE;

    /* Skip make_sparse if single output binary function */
    if ((cube.size - 2*cube.num_binary_vars) <= 1) {
	skip_make_sparse = TRUE;
	unwrap_onset = FALSE;
    }

    
begin:
    Fsave = sf_save(F);		/* Save the original cover */
    D = sf_save(D1);		/* make a scratch copy of D */

    /* Initialize variables to collect statistics about ROS */
    init_ROS(F, D, 1, 3, cube.size);

    /* 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);
    }

    if (F->count > 6) {
	EXECUTE(F = ncp_expand(F, (pcover)NULL, FALSE), EXPAND_TIME, F, cost);
    } else {
	EXECUTE(F = nc_first_expand(F, 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);
	copy_cost(&cost, &best_save_cost);
	Fbest_save = sf_save(F);
	do {

	    /* Repeat inner loop until solution becomes "stable" */
	    do {
		copy_cost(&cost, &best_cost);
		EXECUTE(F = nc_reduce(F, &Fold, D), REDUCE_TIME, F, cost);
		EXECUTE(F = ncp_expand(F, Fold, FALSE),
						    EXPAND_TIME, F, cost);

		if (F->count == 1) { /* No need iterate any more */
		    goto done;
		}

		EXECUTE(F = irredundant(F, D), IRRED_TIME, F, cost);

		/* Save the literal minimum solution */
		if ((best_save_cost.cubes > cost.cubes) || 
		    (best_save_cost.cubes == cost.cubes) && 
		        (best_save_cost.in > cost.in)) {
		    sf_free(Fbest_save);
		    Fbest_save = sf_save(F);
		}

	    } while (cost.cubes < best_cost.cubes);

	    if (skip_gasp) /* Skip last_gasp and super_gasp if TRUE */
	       goto done;

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

	    if ((best_save_cost.cubes > cost.cubes) || 
	        (best_save_cost.cubes == cost.cubes) && 
		    (best_save_cost.in > cost.in)) {
		sf_free(Fbest_save);
		Fbest_save = sf_save(F);
	    }

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

done:
	/* Save the literal minimum solution */
        if ((best_save_cost.cubes > cost.cubes) || 
	    (best_save_cost.cubes == cost.cubes) && 
	        (best_save_cost.in > cost.in)) {
	    sf_free(Fbest_save);
	    Fbest_save = sf_save(F);
	}


	/* Append the essential cubes to F */
	sf_free(F);
	F = sf_append(Fbest_save, 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 = nc_make_sparse(F, D1);
    }

    /* Close out all stuff about reduced offsets */
    close_ROS();

    /*
     *  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) && (!unwrap_onset)) {
	free_cover(F);
	F = Fsave;
	unwrap_onset = FALSE;
	goto begin;
    } else {
	free_cover(Fsave);
    }

    return F;
}

/*
 * Do a single pass consisting of essential, reduce, expand, irredundant.
 * The purpose is to do some reasonable amount of optimization in a short time.
 */

pcover
snocomp(F, D1)
pcover F, D1;

{
    pcover E, D, Fold;
    cost_t cost;
    pcube p, last;

    D = sf_save(D1);

    /* Initialize variables to collect statistics about ROS */
    init_ROS(F, D, 1, 3, cube.size);

    foreach_set(F, last, p) {
	SET(p, RELESSEN);
	RESET(p, NONESSEN);
    }

    EXECUTE(E = essential(&F, &D), ESSEN_TIME, E, cost);
    EXECUTE(F = nc_reduce(F, &Fold, D), REDUCE_TIME, F, cost);

    /* Since the initial expand that is done in espresso is not done
       here, any cube that could not be reduced by "reduce" is not 
       necessarily prime. Make sure that no cube has PRIME flag set
       before "expand" is called. */

    foreach_set(F, last, p) {
	RESET(p, PRIME);
    }

    EXEC(F = ncp_expand(F, Fold, FALSE), "PRIMES     ", F);
    if (F->count > 1)
	EXEC(F = irredundant(F, D), "IRRED_TIME     ", F);

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

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

    /* Close out all stuff about reduced offsets */
    close_ROS();

    return F;

}

/*
 *  unate_compl
 */

pset_family
ncp_unate_compl(A, max_lit)
pset_family A;
int max_lit;

{
    register pset p, last;

    foreach_set(A, last, p) {
	PUTSIZE(p, set_ord(p));
    }

    /* Recursively find the complement */
    A = ncp_unate_complement(A, max_lit);

    /* Now, we can guarantee a minimal result by containing the result */
    A = sf_rev_contain(A);
    return A;
}


/*
 *  Assume SIZE(p) records the size of each set
 */

pset_family
ncp_unate_complement(A, max_lit)
pset_family A;			/* disposes of A */
int max_lit;

{
    pset_family Abar;
    register pset p, p1, restrict;
    register int i;
    int max_i, min_set_ord, j;

    /* Check for no sets in the matrix -- complement is the universe */
    if (A->count == 0) {
	sf_free(A);
	Abar = sf_new(1, A->sf_size);
	(void) set_clear(GETSET(Abar, Abar->count++), A->sf_size);

    /* If the number of literals used so far is larger than or equal to
       the number of literals allowed then return */
    }else if (max_lit <= 0) {
	Abar = A;
	Abar->count = 0;

    /* Check for a single set in the maxtrix -- compute de Morgan complement */
    } else if (A->count == 1) {
	p = A->data;
	Abar = sf_new(A->sf_size, A->sf_size);
	for(i = 0; i < A->sf_size; i++) {
	    if (is_in_set(p, i)) {
		p1 = set_clear(GETSET(Abar, Abar->count++), A->sf_size);
		set_insert(p1, i);
	    }
	}
	sf_free(A);

    } else {

	/* Select splitting variable as the variable which belongs to a set
	 * of the smallest size, and which has greatest column count
	 */
	restrict = set_new(A->sf_size);
	min_set_ord = A->sf_size + 1;
	foreachi_set(A, i, p) {
	    if (SIZE(p) < min_set_ord) {
		(void) set_copy(restrict, p);
		min_set_ord = SIZE(p);
	    } else if (SIZE(p) == min_set_ord) {
		(void) set_or(restrict, restrict, p);
	    }
	}

	/* Check for no data (shouldn't happen ?) */
	if (min_set_ord == 0) {
	    A->count = 0;
	    Abar = A;

	/* Check for "essential" columns */
	} else if (min_set_ord == 1) {
	    i = set_ord(restrict);
	    if (i > max_lit) {
		Abar = A;
		Abar->count = 0;
	    } else {
		Abar = ncp_unate_complement(ncp_abs_covered_many(A, restrict),
							    max_lit-i);
		sf_free(A);
		foreachi_set(Abar, i, p) {
		    (void) set_or(p, p, restrict);
		}
	    }

	/* else, recur as usual */
	} else {
	    max_i = ncp_abs_select_restricted(A, restrict);

	    /* Select those rows of A which are not covered by max_i,
	     * recursively find all minimal covers of these rows, and
	     * then add back in max_i
	     */
	    Abar = ncp_unate_complement(ncp_abs_covered(A, max_i), max_lit-1);
	    foreachi_set(Abar, i, p) {
		set_insert(p, max_i);
	    }

	    /* Now recur on A with all zero's on column max_i */
	    foreachi_set(A, i, p) {
		if (is_in_set(p, max_i)) {
		    set_remove(p, max_i);
		    j = SIZE(p) - 1;
		    PUTSIZE(p, j);
		}
	    }

	    Abar = sf_append(Abar, ncp_unate_complement(A, max_lit));
	}
	set_free(restrict);
    }

    return Abar;
}

/*
 *  ncp_abs_covered_many -- after selecting many columns for ther selected set,
 *  create a new matrix which is only those rows which are still uncovered
 */
static pset_family
ncp_abs_covered_many(A, pick_set)
pset_family A;
register pset pick_set;
{
    register pset last, p, pdest;
    register pset_family Aprime;

    Aprime = sf_new(A->count, A->sf_size);
    pdest = Aprime->data;
    foreach_set(A, last, p)
	if (setp_disjoint(p, pick_set)) {
	    INLINEset_copy(pdest, p);
	    Aprime->count++;
	    pdest += Aprime->wsize;
	}
    return Aprime;
}


/*
 *  ncp_abs_select_restricted -- select the column of maximum column count which
 *  also belongs to the set "restrict"; weight each column of a set as
 *  1 / (set_ord(p) - 1).
 */
static int
ncp_abs_select_restricted(A, restrict)
pset_family A;
pset restrict;
{
    register int i, best_var, best_count, *count;

    /* Sum the elements in these columns */
    count = sf_count_restricted(A, restrict);

    /* Find which variable has maximum weight */
    best_var = -1;
    best_count = 0;
    for(i = 0; i < A->sf_size; i++) {
	if (count[i] > best_count) {
	    best_var = i;
	    best_count = count[i];
	}
    }
    FREE(count);

    if (best_var == -1)
	fatal("ncp_abs_select_restricted: should not have best_var == -1");

    return best_var;
}

/*
 *  abs_covered -- after selecting a new column for the selected set,
 *  create a new matrix which is only those rows which are still uncovered
 */
static pset_family
ncp_abs_covered(A, pick)
pset_family A;
register int pick;
{
    register pset last, p, pdest;
    register pset_family Aprime;

    Aprime = sf_new(A->count, A->sf_size);
    pdest = Aprime->data;
    foreach_set(A, last, p)
	if (! is_in_set(p, pick)) {
	    INLINEset_copy(pdest, p);