opo.c

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

/*
 * Revision Control Information
 *
 * $Source: /projects/mvsis/Repository/mvsis-1.3/src/sis/espresso/opo.c,v $
 * $Author: wjiang $
 * $Revision: 1.1.1.1 $
 * $Date: 2003/02/24 22:24:08 $
 *
 */
#include "espresso.h"

/*
 *   Phase assignment technique (T. Sasao):
 *
 *      1. create a function with 2*m outputs which implements the
 *      original function and its complement for each output
 *
 *      2. minimize this function
 *
 *      3. choose the minimum number of prime implicants from the
 *      result of step 2 which are needed to realize either a function
 *      or its complement for each output
 *
 *  Step 3 is performed in a rather crude way -- by simply multiplying
 *  out a large expression of the form:
 *
 *      I = (ab + cdef)(acd + bgh) ...
 *
 *  which is a product of m expressions where each expression has two
 *  product terms -- one representing which primes are needed for the
 *  function, and one representing which primes are needed for the
 *  complement.  The largest product term resulting shows which primes
 *  to keep to implement one function or the other for each output.
 *  For problems with many outputs, this may grind to a
 *  halt.
 *
 *  Untried: form complement of I and use unate_complement ...
 *
 *  I have unsuccessfully tried several modifications to the basic
 *  algorithm.  The first is quite simple: use Sasao's technique, but
 *  only commit to a single output at a time (rather than all
 *  outputs).  The goal would be that the later minimizations can "take
 *  into account" the partial assignment at each step.  This is
 *  expensive (m+1 minimizations rather than 2), and the results are
 *  discouraging.
 *
 *  The second modification is rather complicated.  The result from the
 *  minimization in step 2 is guaranteed to be minimal.  Hence, for
 *  each output, the set of primes with a 1 in that output are both
 *  necessary and sufficient to implement the function.  Espresso
 *  achieves the minimality using the routine MAKE_SPARSE.  The
 *  modification is to prevent MAKE_SPARSE from running.  Hence, there
 *  are potentially many subsets of the set of primes with a 1 in a
 *  column which can be used to implement that output.  We use
 *  IRREDUNDANT to enumerate all possible subsets and then proceed as
 *  before.
 */

static int opo_no_make_sparse;
static int opo_repeated;
static int opo_exact;
static void esp_minimize();

void phase_assignment(PLA, opo_strategy)
pPLA PLA;
int opo_strategy;
{
    opo_no_make_sparse = opo_strategy % 2;
    skip_make_sparse = opo_no_make_sparse;
    opo_repeated = (opo_strategy / 2) % 2;
    opo_exact = (opo_strategy / 4) % 2;

    /* Determine a phase assignment */
    if (PLA->phase != NULL) {
	FREE(PLA->phase);
    }

    if (opo_repeated) {
	PLA->phase = set_save(cube.fullset);
	repeated_phase_assignment(PLA);
    } else {
	PLA->phase = find_phase(PLA, 0, (pcube) NULL);
    }

    /* Now minimize with this assignment */
    skip_make_sparse = FALSE;
    (void) set_phase(PLA);
    esp_minimize(PLA);
}

/*
 *  repeated_phase_assignment -- an alternate strategy which commits
 *  to a single phase assignment a step at a time.  Performs m + 1
 *  minimizations !
 */
void repeated_phase_assignment(PLA)
pPLA PLA;
{
    int i;
    pcube phase;

    for(i = 0; i < cube.part_size[cube.output]; i++) {

	/* Find best assignment for all undecided outputs */
	phase = find_phase(PLA, i, PLA->phase);

	/* Commit for only a single output ... */
	if (! is_in_set(phase, cube.first_part[cube.output] + i)) {
	    set_remove(PLA->phase, cube.first_part[cube.output] + i);
	}

	if (trace || summary) {
	    (void) printf("\nOPO loop for output #%d\n", i);
	    (void) printf("PLA->phase is %s\n", pc1(PLA->phase));
	    (void) printf("phase      is %s\n", pc1(phase));
	}
	set_free(phase);
    }
}


/*
 *  find_phase -- find a phase assignment for the PLA for all outputs starting
 *  with output number first_output.
 */
pcube find_phase(PLA, first_output, phase1)
pPLA PLA;
int first_output;
pcube phase1;
{
    pcube phase;
    pPLA PLA1;

    phase = set_save(cube.fullset);

    /* setup the double-phase characteristic function, resize the cube */
    PLA1 = new_PLA();
    PLA1->F = sf_save(PLA->F);
    PLA1->R = sf_save(PLA->R);
    PLA1->D = sf_save(PLA->D);
    if (phase1 != NULL) {
	PLA1->phase = set_save(phase1);
	(void) set_phase(PLA1);
    }
    EXEC_S(output_phase_setup(PLA1, first_output), "OPO-SETUP ", PLA1->F);

    /* minimize the double-phase function */
    esp_minimize(PLA1);

    /* set the proper phases according to what gives a minimum solution */
    EXEC_S(PLA1->F = opo(phase, PLA1->F, PLA1->D, PLA1->R, first_output),
	    "OPO       ", PLA1->F);
    free_PLA(PLA1);

    /* set the cube structure to reflect the old size */
    setdown_cube();
    cube.part_size[cube.output] -=
	(cube.part_size[cube.output] - first_output) / 2;
    cube_setup();

    return phase;
}

/*
 *  opo -- multiply the expression out to determine a minimum subset of
 *  primes.
 */

/*ARGSUSED*/
pcover opo(phase, T, D, R, first_output)
pcube phase;
pcover T, D, R;
int first_output;
{
    int offset, output, i, last_output, ind;
    pset pdest, select, p, p1, last, last1, not_covered, tmp;
    pset_family temp, T1, T2;

    /* must select all primes for outputs [0 .. first_output-1] */
    select = set_full(T->count);
    for(output = 0; output < first_output; output++) {
	ind = cube.first_part[cube.output] + output;
	foreachi_set(T, i, p) {
	    if (is_in_set(p, ind)) {
		set_remove(select, i);
	    }
	}
    }

    /* Recursively perform the intersections */
    offset = (cube.part_size[cube.output] - first_output) / 2;
    last_output = first_output + offset - 1;
    temp = opo_recur(T, D, select, offset, first_output, last_output);

    /* largest set is on top -- select primes which are inferred from it */
    pdest = temp->data;
    T1 = new_cover(T->count);
    foreachi_set(T, i, p) {
	if (! is_in_set(pdest, i)) {
	    T1 = sf_addset(T1, p);
	}
    }

    set_free(select);
    sf_free(temp);

    /* finding phases is difficult -- see which functions are not covered */
    T2 = complement(cube1list(T1));
    not_covered = new_cube();
    tmp = new_cube();
    foreach_set(T, last, p) {
	foreach_set(T2, last1, p1) {
	    if (cdist0(p, p1)) {
		(void) set_or(not_covered, not_covered, set_and(tmp, p, p1));
	    }
	}
    }
    free_cover(T);
    free_cover(T2);
    set_free(tmp);

    /* Now reflect the phase choice in a single cube */
    for(output = first_output; output <= last_output; output++) {
	ind = cube.first_part[cube.output] + output;
	if (is_in_set(not_covered, ind)) {
	    if (is_in_set(not_covered, ind + offset)) {
		fatal("error in output phase assignment");
	    } else {
		set_remove(phase, ind);
	    }
	}
    }
    set_free(not_covered);
    return T1;
}

pset_family opo_recur(T, D, select, offset, first, last)
pcover T, D;
pcube select;
int offset, first, last;
{
    static int level = 0;
    int middle;
    pset_family sl, sr, temp;

    level++;
    if (first == last) {
#if 0
	if (opo_no_make_sparse) {
	    temp = form_cover_table(T, D, select, first, first + offset);
	} else {
	    temp = opo_leaf(T, select, first, first + offset);
	}
#else
	temp = opo_leaf(T, select, first, first + offset);
#endif
    } else {
	middle = (first + last) / 2;
	sl = opo_recur(T, D, select, offset, first, middle);
	sr = opo_recur(T, D, select, offset, middle+1, last);
	temp = unate_intersect(sl, sr, level == 1);
	if (trace) {
	    (void) printf("# OPO[%d]: %4d = %4d x %4d, time = %s\n", level - 1,
		temp->count, sl->count, sr->count, print_time(ptime()));
	    (void) fflush(stdout);
	}
	free_cover(sl);
	free_cover(sr);
    }
    level--;
    return temp;
}


pset_family opo_leaf(T, select, out1, out2)
register pcover T;
pset select;
int out1, out2;
{
    register pset_family temp;
    register pset p, pdest;
    register int i;

    out1 += cube.first_part[cube.output];
    out2 += cube.first_part[cube.output];

    /* Allocate space for the result */
    temp = sf_new(2, T->count);

    /* Find which primes are needed for the ON-set of this fct */
    pdest = GETSET(temp, temp->count++);
    (void) set_copy(pdest, select);
    foreachi_set(T, i, p) {
	if (is_in_set(p, out1)) {
	    set_remove(pdest, i);
	}
    }

    /* Find which primes are needed for the OFF-set of this fct */
    pdest = GETSET(temp, temp->count++);
    (void) set_copy(pdest, select);
    foreachi_set(T, i, p) {
	if (is_in_set(p, out2)) {
	    set_remove(pdest, i);
	}
    }

    return temp;
}

#if 0
pset_family form_cover_table(F, D, select, f, fbar)
pcover F, D;