cuddgenetic.c

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

/**CFile***********************************************************************

  FileName    [cuddGenetic.c]

  PackageName [cudd]

  Synopsis    [Genetic algorithm for variable reordering.]

  Description [Internal procedures included in this file:
		<ul>
		<li> cuddGa()
		</ul>
	Static procedures included in this module:
		<ul>
		<li> make_random()
		<li> sift_up()
		<li> build_dd()
		<li> largest()
		<li> rand_int()
		<li> array_hash()
		<li> array_compare()
		<li> find_best()
		<li> find_average_fitness()
		<li> PMX()
		<li> roulette()
		</ul>

  The genetic algorithm implemented here is as follows.  We start with
  the current DD order.  We sift this order and use this as the
  reference DD.  We only keep 1 DD around for the entire process and
  simply rearrange the order of this DD, storing the various orders
  and their corresponding DD sizes.  We generate more random orders to
  build an initial population. This initial population is 3 times the
  number of variables, with a maximum of 120. Each random order is
  built (from the reference DD) and its size stored.  Each random
  order is also sifted to keep the DD sizes fairly small.  Then a
  crossover is performed between two orders (picked randomly) and the
  two resulting DDs are built and sifted.  For each new order, if its
  size is smaller than any DD in the population, it is inserted into
  the population and the DD with the largest number of nodes is thrown
  out. The crossover process happens up to 50 times, and at this point
  the DD in the population with the smallest size is chosen as the
  result.  This DD must then be built from the reference DD.]

  SeeAlso     []

  Author      [Curt Musfeldt, Alan Shuler, Fabio Somenzi]

  Copyright [This file was created at the University of Colorado at
  Boulder.  The University of Colorado at Boulder makes no warranty
  about the suitability of this software for any purpose.  It is
  presented on an AS IS basis.]

******************************************************************************/

#include "util.h"
#include "cuddInt.h"

/*---------------------------------------------------------------------------*/
/* Constant declarations                                                     */
/*---------------------------------------------------------------------------*/

/*---------------------------------------------------------------------------*/
/* Stucture declarations                                                     */
/*---------------------------------------------------------------------------*/

/*---------------------------------------------------------------------------*/
/* Type declarations                                                         */
/*---------------------------------------------------------------------------*/

/*---------------------------------------------------------------------------*/
/* Variable declarations                                                     */
/*---------------------------------------------------------------------------*/

#ifndef lint
static char rcsid[] DD_UNUSED = "$Id: cuddGenetic.c,v 1.1.1.1 2003/02/24 22:23:52 wjiang Exp $";
#endif

static int popsize;		/* the size of the population */
static int numvars;		/* the number of input variables in the ckt. */
/* storedd stores the population orders and sizes. This table has two
** extra rows and one extras column. The two extra rows are used for the
** offspring produced by a crossover. Each row stores one order and its
** size. The order is stored by storing the indices of variables in the
** order in which they appear in the order. The table is in reality a
** one-dimensional array which is accessed via a macro to give the illusion
** it is a two-dimensional structure.
*/
static int *storedd;
static st_table *computed;	/* hash table to identify existing orders */
static int *repeat;		/* how many times an order is present */
static int large;		/* stores the index of the population with
				** the largest number of nodes in the DD */
static int result;
static int cross;		/* the number of crossovers to perform */

/*---------------------------------------------------------------------------*/
/* Macro declarations                                                        */
/*---------------------------------------------------------------------------*/

/* macro used to access the population table as if it were a
** two-dimensional structure.
*/
#define STOREDD(i,j)	storedd[(i)*(numvars+1)+(j)]


/**AutomaticStart*************************************************************/

/*---------------------------------------------------------------------------*/
/* Static function prototypes                                                */
/*---------------------------------------------------------------------------*/

static int make_random ARGS((DdManager *table, int lower));
static int sift_up ARGS((DdManager *table, int x, int x_low));
static int build_dd ARGS((DdManager *table, int num, int lower, int upper));
static int largest ARGS(());
static int rand_int ARGS((int a));
static int array_hash ARGS((char *array, int modulus));
static int array_compare ARGS((const char *array1, const char *array2));
static int find_best ARGS(());
static double find_average_fitness ARGS(());
static int PMX ARGS((int maxvar));
static int roulette ARGS((int *p1, int *p2));

/**AutomaticEnd***************************************************************/


/*---------------------------------------------------------------------------*/
/* Definition of exported functions                                          */
/*---------------------------------------------------------------------------*/

/*---------------------------------------------------------------------------*/
/* Definition of internal functions                                          */
/*---------------------------------------------------------------------------*/


/**Function********************************************************************

  Synopsis    [Genetic algorithm for DD reordering.]

  Description [Genetic algorithm for DD reordering.
  The two children of a crossover will be stored in
  storedd[popsize] and storedd[popsize+1] --- the last two slots in the
  storedd array.  (This will make comparisons and replacement easy.)
  Returns 1 in case of success; 0 otherwise.]

  SideEffects [None]

  SeeAlso     []

******************************************************************************/
int
cuddGa(
  DdManager * table /* manager */,
  int  lower /* lowest level to be reordered */,
  int  upper /* highest level to be reorderded */)
{
    int 	i,n,m;		/* dummy/loop vars */
    int		index;
    double	average_fitness;
    int		small;		/* index of smallest DD in population */

    /* Do an initial sifting to produce at least one reasonable individual. */
    if (!cuddSifting(table,lower,upper)) return(0);

    /* Get the initial values. */
    numvars = upper - lower + 1; /* number of variables to be reordered */
    if (table->populationSize == 0) {
	popsize = 3 * numvars;  /* population size is 3 times # of vars */
	if (popsize > 120) {
	    popsize = 120;	/* Maximum population size is 120 */
	}
    } else {
	popsize = table->populationSize;  /* user specified value */
    }
    if (popsize < 4) popsize = 4;	/* enforce minimum population size */

    /* Allocate population table. */
    storedd = ALLOC(int,(popsize+2)*(numvars+1));
    if (storedd == NULL) {
	table->errorCode = CUDD_MEMORY_OUT;
	return(0);
    }

    /* Initialize the computed table. This table is made up of two data
    ** structures: A hash table with the key given by the order, which says
    ** if a given order is present in the population; and the repeat
    ** vector, which says how many copies of a given order are stored in
    ** the population table. If there are multiple copies of an order, only
    ** one has a repeat count greater than 1. This copy is the one pointed
    ** by the computed table.
    */
    repeat = ALLOC(int,popsize);
    if (repeat == NULL) {
	table->errorCode = CUDD_MEMORY_OUT;
	FREE(storedd);
	return(0);
    }
    for (i = 0; i < popsize; i++) {
	repeat[i] = 0;
    }
    computed = st_init_table(array_compare,array_hash);
    if (computed == NULL) {
	table->errorCode = CUDD_MEMORY_OUT;
	FREE(storedd);
	FREE(repeat);
	return(0);
    }

    /* Copy the current DD and its size to the population table. */
    for (i = 0; i < numvars; i++) {
	STOREDD(0,i) = table->invperm[i+lower]; /* order of initial DD */
    }
    STOREDD(0,numvars) = table->keys - table->isolated; /* size of initial DD */

    /* Store the initial order in the computed table. */
    if (st_insert(computed,(char *)storedd,(char *) 0) == ST_OUT_OF_MEM) {
	FREE(storedd);
	FREE(repeat);
	st_free_table(computed);
	return(0);
    }
    repeat[0]++;

    /* Insert the reverse order as second element of the population. */
    for (i = 0; i < numvars; i++) {
	STOREDD(1,numvars-1-i) = table->invperm[i+lower]; /* reverse order */
    }

    /* Now create the random orders. make_random fills the population
    ** table with random permutations. The successive loop builds and sifts
    ** the DDs for the reverse order and each random permutation, and stores
    ** the results in the computed table.
    */
    if (!make_random(table,lower)) {
	table->errorCode = CUDD_MEMORY_OUT;
	FREE(storedd);
	FREE(repeat);
	st_free_table(computed);
	return(0);
    }
    for (i = 1; i < popsize; i++) {
	result = build_dd(table,i,lower,upper);	/* build and sift order */
	if (!result) {
	    FREE(storedd);
	    FREE(repeat);
	    st_free_table(computed);
	    return(0);
	}
	if (st_lookup(computed,(char *)&STOREDD(i,0),(char **)&index)) {
	    repeat[index]++;
	} else {
	    if (st_insert(computed,(char *)&STOREDD(i,0),(char *)(long)i) ==
	    ST_OUT_OF_MEM) {
		FREE(storedd);
		FREE(repeat);
		st_free_table(computed);
		return(0);
	    }
	    repeat[i]++;
	}
    }

#if 0
#ifdef DD_STATS
    /* Print the initial population. */
    (void) fprintf(table->out,"Initial population after sifting\n");
    for (m = 0; m < popsize; m++) {
	for (i = 0; i < numvars; i++) {
	    (void) fprintf(table->out," %2d",STOREDD(m,i));
	}
	(void) fprintf(table->out," : %3d (%d)\n",
		       STOREDD(m,numvars),repeat[m]);
    }
#endif
#endif

    small = find_best();
    average_fitness = find_average_fitness();
#ifdef DD_STATS
    (void) fprintf(table->out,"\nInitial population: best fitness = %d, average fitness %8.3f",STOREDD(small,numvars),average_fitness);
#endif

    /* Decide how many crossovers should be tried. */
    if (table->numberXovers == 0) {
	cross = 3*numvars;
	if (cross > 60) {	/* do a maximum of 50 crossovers */
	    cross = 60;
	}
    } else {
	cross = table->numberXovers;      /* use user specified value */
    }

    /* Perform the crossovers to get the best order. */
    for (m = 0; m < cross; m++) {
	if (!PMX(table->size)) {	/* perform one crossover */
	    table->errorCode = CUDD_MEMORY_OUT;
	    FREE(storedd);
	    FREE(repeat);
	    st_free_table(computed);
	    return(0);
	}
	/* The offsprings are left in the last two entries of the
	** population table. These are now considered in turn.
	*/
	for (i = popsize; i <= popsize+1; i++) {
	    result = build_dd(table,i,lower,upper); /* build and sift child */
	    if (!result) {
		FREE(storedd);
		FREE(repeat);
		st_free_table(computed);
		return(0);
	    }
	    large = largest();	/* find the largest DD in population */

	    /* If the new child is smaller than the largest DD in the current
	    ** population, enter it into the population in place of the
	    ** largest DD.
	    */
	    if (STOREDD(i,numvars) < STOREDD(large,numvars)) {
		/* Look up the largest DD in the computed table.
		** Decrease its repetition count. If the repetition count
		** goes to 0, remove the largest DD from the computed table.
		*/
		result = st_lookup(computed,(char *)&STOREDD(large,0),(char
		**)&index);
		if (!result) {
		    FREE(storedd);
		    FREE(repeat);
		    st_free_table(computed);
		    return(0);
		}
		repeat[index]--;
		if (repeat[index] == 0) {
		    int *pointer = &STOREDD(index,0);
		    result = st_delete(computed, (char **)&pointer,NULL);
		    if (!result) {
			FREE(storedd);
			FREE(repeat);
			st_free_table(computed);
			return(0);
		    }
		}
		/* Copy the new individual to the entry of the
		** population table just made available and update the
		** computed table.
		*/
		for (n = 0; n <= numvars; n++) {
		    STOREDD(large,n) = STOREDD(i,n);
		}
		if (st_lookup(computed,(char *)&STOREDD(large,0),(char
		**)&index)) {
		    repeat[index]++;
		} else {
		    if (st_insert(computed,(char *)&STOREDD(large,0),
		    (char *)(long)large) == ST_OUT_OF_MEM) {
			FREE(storedd);
			FREE(repeat);
			st_free_table(computed);
			return(0);
		    }
		    repeat[large]++;
		}
	    }
	}
    }

    /* Find the smallest DD in the population and build it;
    ** that will be the result.
    */
    small = find_best();

    /* Print stats on the final population. */
#ifdef DD_STATS
    average_fitness = find_average_fitness();
    (void) fprintf(table->out,"\nFinal population: best fitness = %d, average fitness %8.3f",STOREDD(small,numvars),average_fitness);
#endif

    /* Clean up, build the result DD, and return. */
    st_free_table(computed);
    computed = NULL;
    result = build_dd(table,small,lower,upper);
    FREE(storedd);
    FREE(repeat);
    return(result);

} /* end of cuddGa */


/*---------------------------------------------------------------------------*/
/* Definition of static functions                                            */
/*---------------------------------------------------------------------------*/

/**Function********************************************************************

  Synopsis    [Generates the random sequences for the initial population.]

  Description [Generates the random sequences for the initial population.
  The sequences are permutations of the indices between lower and
  upper in the current order.]

  SideEffects [None]

  SeeAlso     []

******************************************************************************/
static int
make_random(
  DdManager * table,
  int  lower)
{
    int i,j;		/* loop variables */
    int	*used;		/* is a number already in a permutation */
    int	next;		/* next random number without repetitions */

    used = ALLOC(int,numvars);
    if (used == NULL) {
	table->errorCode = CUDD_MEMORY_OUT;
	return(0);
    }
#if 0
#ifdef DD_STATS
    (void) fprintf(table->out,"Initial population before sifting\n");
    for (i = 0; i < 2; i++) {
	for (j = 0; j < numvars; j++) {
	    (void) fprintf(table->out," %2d",STOREDD(i,j));
	}
	(void) fprintf(table->out,"\n");
    }
#endif
#endif
    for (i = 2; i < popsize; i++) {
       	for (j = 0; j < numvars; j++) {
	    used[j] = 0;
	}
	/* Generate a permutation of {0...numvars-1} and use it to
	** permute the variables in the layesr from lower to upper.
	*/
       	for (j = 0; j < numvars; j++) {
	    do {
		next = rand_int(numvars-1);
	    } while (used[next] != 0);
	    used[next] = 1;
	    STOREDD(i,j) = table->invperm[next+lower];
       	}
#if 0
#ifdef DD_STATS
	/* Print the order just generated. */
	for (j = 0; j < numvars; j++) {
	    (void) fprintf(table->out," %2d",STOREDD(i,j));
	}
	(void) fprintf(table->out,"\n");
#endif
#endif
    }
    FREE(used);
    return(1);

} /* end of make_random */