cuddanneal.c

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

	} else {
	    size = cuddSwapInPlace(table,x,x_next);
	    if (size == 0) goto ddExchangeOutOfMem;
	    move = (Move *)cuddDynamicAllocNode(table);
	    if (move == NULL) goto ddExchangeOutOfMem;
	    move->x = x;
	    move->y = x_next;
	    move->size = size;
	    move->next = moves;
	    moves = move;
	    size = cuddSwapInPlace(table,y_next,y);
	    if (size == 0) goto ddExchangeOutOfMem;
	    move = (Move *)cuddDynamicAllocNode(table);
	    if (move == NULL) goto ddExchangeOutOfMem;
	    move->x = y_next;
	    move->y = y;
	    move->size = size;
	    move->next = moves;
	    moves = move;
	    x = x_next;
	    y = y_next;
	}

	x_next = cuddNextHigh(table,x);
	y_next = cuddNextLow(table,y);
	if (x_next > y_ref) break;

	if ((double) size > DD_MAX_REORDER_GROWTH * (double) limit_size) {
	    break;
	} else if (size < limit_size) {
	    limit_size = size;
	}
    }

    if (y_next>=x_ref) {
        size = cuddSwapInPlace(table,y_next,y);
        if (size == 0) goto ddExchangeOutOfMem;
        move = (Move *)cuddDynamicAllocNode(table);
        if (move == NULL) goto ddExchangeOutOfMem;
        move->x = y_next;
        move->y = y;
        move->size = size;
        move->next = moves;
        moves = move;
    }

    /* move backward and stop at best position or accept uphill move */
    result = siftBackwardProb(table,moves,initial_size,temp);
    if (!result) goto ddExchangeOutOfMem;

    while (moves != NULL) {
	move = moves->next;
	cuddDeallocNode(table, (DdNode *) moves);
	moves = move;
    }
    return(1);

ddExchangeOutOfMem:
    while (moves != NULL) {
        move = moves->next;
        cuddDeallocNode(table,(DdNode *) moves);
        moves = move;
    }
    return(0);

} /* end of ddExchange */


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

  Synopsis    [Moves a variable to a specified position.]

  Description [If x==x_low, it executes jumping_down. If x==x_high, it
  executes jumping_up. This funcion is similar to ddSiftingAux. Returns
  1 in case of success; 0 otherwise.]

  SideEffects [None]

  SeeAlso     []

******************************************************************************/
static int
ddJumpingAux(
  DdManager * table,
  int  x,
  int  x_low,
  int  x_high,
  double  temp)
{
    Move       *move;
    Move       *moves;        /* list of moves */
    int        initial_size;
    int        result;

    initial_size = table->keys - table->isolated;

#ifdef DD_DEBUG
    assert(table->subtables[x].keys > 0);
#endif

    moves = NULL;

    if (cuddNextLow(table,x) < x_low) {
	if (cuddNextHigh(table,x) > x_high) return(1);
	moves = ddJumpingDown(table,x,x_high,initial_size);
	/* after that point x --> x_high unless early termination */
	if (moves == NULL) goto ddJumpingAuxOutOfMem;
	/* move backward and stop at best position or accept uphill move */
	result = siftBackwardProb(table,moves,initial_size,temp);
	if (!result) goto ddJumpingAuxOutOfMem;
    } else if (cuddNextHigh(table,x) > x_high) {
	moves = ddJumpingUp(table,x,x_low,initial_size);
	/* after that point x --> x_low unless early termination */
	if (moves == NULL) goto ddJumpingAuxOutOfMem;
	/* move backward and stop at best position or accept uphill move */
	result = siftBackwardProb(table,moves,initial_size,temp);
	if (!result) goto ddJumpingAuxOutOfMem;
    } else {
	(void) fprintf(table->err,"Unexpected condition in ddJumping\n");
	goto ddJumpingAuxOutOfMem;
    }
    while (moves != NULL) {
	move = moves->next;
	cuddDeallocNode(table, (DdNode *) moves);
	moves = move;
    }
    return(1);

ddJumpingAuxOutOfMem:
    while (moves != NULL) {
	move = moves->next;
	cuddDeallocNode(table, (DdNode *) moves);
	moves = move;
    }
    return(0);

} /* end of ddJumpingAux */


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

  Synopsis    [This function is for jumping up.]

  Description [This is a simplified version of ddSiftingUp. It does not
  use lower bounding. Returns the set of moves in case of success; NULL
  if memory is full.]

  SideEffects [None]

  SeeAlso     []

******************************************************************************/
static Move *
ddJumpingUp(
  DdManager * table,
  int  x,
  int  x_low,
  int  initial_size)
{
    Move       *moves;
    Move       *move;
    int        y;
    int        size;
    int        limit_size = initial_size;

    moves = NULL;
    y = cuddNextLow(table,x);
    while (y >= x_low) {
	size = cuddSwapInPlace(table,y,x);
	if (size == 0) goto ddJumpingUpOutOfMem;
	move = (Move *)cuddDynamicAllocNode(table);
	if (move == NULL) goto ddJumpingUpOutOfMem;
	move->x = y;
	move->y = x;
	move->size = size;
	move->next = moves;
	moves = move;
	if ((double) size > table->maxGrowth * (double) limit_size) {
	    break;
	} else if (size < limit_size) {
	    limit_size = size;
	}
	x = y;
	y = cuddNextLow(table,x);
    }
    return(moves);

ddJumpingUpOutOfMem:
    while (moves != NULL) {
	move = moves->next;
	cuddDeallocNode(table, (DdNode *) moves);
	moves = move;
    }
    return(NULL);

} /* end of ddJumpingUp */


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

  Synopsis    [This function is for jumping down.]

  Description [This is a simplified version of ddSiftingDown. It does not
  use lower bounding. Returns the set of moves in case of success; NULL
  if memory is full.]

  SideEffects [None]

  SeeAlso     []

******************************************************************************/
static Move *
ddJumpingDown(
  DdManager * table,
  int  x,
  int  x_high,
  int  initial_size)
{
    Move       *moves;
    Move       *move;
    int        y;
    int        size;
    int        limit_size = initial_size;

    moves = NULL;
    y = cuddNextHigh(table,x);
    while (y <= x_high) {
	size = cuddSwapInPlace(table,x,y);
	if (size == 0) goto ddJumpingDownOutOfMem;
	move = (Move *)cuddDynamicAllocNode(table);
	if (move == NULL) goto ddJumpingDownOutOfMem;
	move->x = x;
	move->y = y;
	move->size = size;
	move->next = moves;
	moves = move;
	if ((double) size > table->maxGrowth * (double) limit_size) {
	    break;
	} else if (size < limit_size) {
	    limit_size = size;
	}
	x = y;
	y = cuddNextHigh(table,x);
    }
    return(moves);

ddJumpingDownOutOfMem:
    while (moves != NULL) {
	move = moves->next;
	cuddDeallocNode(table, (DdNode *) moves);
	moves = move;
    }
    return(NULL);

} /* end of ddJumpingDown */


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

  Synopsis [Returns the DD to the best position encountered during
  sifting if there was improvement.]

  Description [Otherwise, "tosses a coin" to decide whether to keep
  the current configuration or return the DD to the original
  one. Returns 1 in case of success; 0 otherwise.]

  SideEffects [None]

  SeeAlso     []

******************************************************************************/
static int
siftBackwardProb(
  DdManager * table,
  Move * moves,
  int  size,
  double  temp)
{
    Move   *move;
    int    res;
    int    best_size = size;
    double coin, threshold;

    /* Look for best size during the last sifting */
    for (move = moves; move != NULL; move = move->next) {
	if (move->size < best_size) {
	    best_size = move->size;
	}
    }
    
    /* If best_size equals size, the last sifting did not produce any
    ** improvement. We now toss a coin to decide whether to retain
    ** this change or not.
    */
    if (best_size == size) {
	coin = random_generator();
#ifdef DD_STATS
	tosses++;
#endif
	threshold = exp(-((double)(table->keys - table->isolated - size))/temp);
	if (coin < threshold) {
#ifdef DD_STATS
	    acceptances++;
#endif
	    return(1);
	}
    }

    /* Either there was improvement, or we have decided not to
    ** accept the uphill move. Go to best position.
    */
    res = table->keys - table->isolated;
    for (move = moves; move != NULL; move = move->next) {
	if (res == best_size) return(1);
	res = cuddSwapInPlace(table,(int)move->x,(int)move->y);
	if (!res) return(0);
    }

    return(1);

} /* end of sift_backward_prob */


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

  Synopsis    [Copies the current variable order to array.]

  Description [Copies the current variable order to array.
  At the same time inverts the permutation.]

  SideEffects [None]

  SeeAlso     []

******************************************************************************/
static void
copyOrder(
  DdManager * table,
  int * array,
  int  lower,
  int  upper)
{
    int i;
    int nvars;

    nvars = upper - lower + 1;
    for (i = 0; i < nvars; i++) {
	array[i] = table->invperm[i+lower];
    }

} /* end of copyOrder */


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

  Synopsis    [Restores the variable order in array by a series of sifts up.]

  Description [Restores the variable order in array by a series of sifts up.
  Returns 1 in case of success; 0 otherwise.]

  SideEffects [None]

  SeeAlso     []

******************************************************************************/
static int
restoreOrder(
  DdManager * table,
  int * array,
  int  lower,
  int  upper)
{
    int i, x, y, size;
    int nvars = upper - lower + 1;

    for (i = 0; i < nvars; i++) {
	x = table->perm[array[i]];
#ifdef DD_DEBUG
    assert(x >= lower && x <= upper);
#endif
	y = cuddNextLow(table,x);
	while (y >= i + lower) {
	    size = cuddSwapInPlace(table,y,x);
	    if (size == 0) return(0);
	    x = y;
	    y = cuddNextLow(table,x);
	}
    }

    return(1);

} /* end of restoreOrder */