reosift.c

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

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

  FileName    [reoSift.c]

  PackageName [REO: A specialized DD reordering engine.]

  Synopsis    [Implementation of the sifting algorihtm.]

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]

  Date        [Ver. 1.0. Started - October 15, 2002.]

  Revision    [$Id: reoSift.c,v 1.2 2003/05/26 15:46:33 alanmi Exp $]

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

#include "reo.h"

////////////////////////////////////////////////////////////////////////
///                        DECLARATIONS                              ///
////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////
///                    FUNCTION DEFINITIONS                          ///
////////////////////////////////////////////////////////////////////////

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

  Synopsis    [Implements the variable sifting algorithm.]

  Description [Performs a sequence of adjacent variable swaps known as "sifting".
  Uses the cost functions determined by the flag.]

  SideEffects []

  SeeAlso     []

***********************************************************************/
void reoReorderSift( reo_man * p )
{
	double CostCurrent;  // the cost of the current permutation
	double CostLimit;    // the maximum increase in cost that can be tolerated
	double CostBest;     // the best cost
	int BestQ;           // the best position
	int VarCurrent;      // the current variable to move   
	int q;               // denotes the current position of the variable
	int c;               // performs the loops over variables until all of them are sifted
	int v;               // used for other purposes

	assert( p->nSupp > 0 );

	// set the current cost depending on the minimization criteria
	if ( p->fMinWidth )
		CostCurrent = p->nWidthCur;
	else if ( p->fMinApl )
		CostCurrent = p->nAplCur;
	else
		CostCurrent = p->nNodesCur;

	// find the upper bound on tbe cost growth
	CostLimit = 1 + (int)(REO_REORDER_LIMIT * CostCurrent);

	// perform sifting for each of p->nSupp variables
	for ( c = 0; c < p->nSupp; c++ )
	{
		// select the current variable to be the one with the largest number of nodes that is not sifted yet
		VarCurrent = -1;
		CostBest   = -1.0;
		for ( v = 0; v < p->nSupp; v++ )
		{
			p->pVarCosts[v] = REO_HIGH_VALUE;
			if ( !p->pPlanes[v].fSifted )
			{
//				VarCurrent = v;
//				if ( CostBest < p->pPlanes[v].statsCost )
				if ( CostBest < p->pPlanes[v].statsNodes )
				{
//					CostBest   = p->pPlanes[v].statsCost;
					CostBest   = p->pPlanes[v].statsNodes;
					VarCurrent = v;
				}

			}
		}
		assert( VarCurrent != -1 );
		// mark this variable as sifted
		p->pPlanes[VarCurrent].fSifted = 1;

		// set the current value
		p->pVarCosts[VarCurrent] = CostCurrent;

		// set the best cost
		CostBest = CostCurrent;
		BestQ    = VarCurrent; 

		// determine which way to move the variable first (up or down)
		// the rationale is that if we move the shorter way first
		// it is more likely that the best position will be found on the longer way
		// and the reverse movement (to take the best position) will be faster
		if ( VarCurrent < p->nSupp/2 ) // move up first, then down
		{
			// set the total cost on all levels above the current level
			p->pPlanes[0].statsCostAbove = 0;
			for ( v = 1; v <= VarCurrent; v++ )
				p->pPlanes[v].statsCostAbove = p->pPlanes[v-1].statsCostAbove + p->pPlanes[v-1].statsCost;
			// set the total cost on all levels below the current level
			p->pPlanes[p->nSupp].statsCostBelow = 0;
			for ( v = p->nSupp - 1; v >= VarCurrent; v-- )
				p->pPlanes[v].statsCostBelow = p->pPlanes[v+1].statsCostBelow + p->pPlanes[v+1].statsCost;

			assert( CostCurrent == p->pPlanes[VarCurrent].statsCostAbove + 
									p->pPlanes[VarCurrent].statsCost +
				                    p->pPlanes[VarCurrent].statsCostBelow );

			// move up
			for ( q = VarCurrent-1; q >= 0; q-- )
			{
				CostCurrent -= reoReorderSwapAdjacentVars( p, q, 1 );
				// now q points to the position of this var in the order
				p->pVarCosts[q] = CostCurrent;
				// update the lower bound (assuming that for level q+1 it is set correctly)
				p->pPlanes[q].statsCostBelow = p->pPlanes[q+1].statsCostBelow + p->pPlanes[q+1].statsCost;
				// check the upper bound
				if ( CostCurrent >= CostLimit )
					break;
				// check the lower bound
				if ( p->pPlanes[q].statsCostBelow + (REO_QUAL_PAR-1)*p->pPlanes[q].statsCostAbove/REO_QUAL_PAR >= CostBest )
					break;
				// update the best cost
				if ( CostBest > CostCurrent )
				{
					CostBest = CostCurrent;
					BestQ    = q;
					// adjust node limit
					CostLimit = ddMin( CostLimit, 1 + (int)(REO_REORDER_LIMIT * CostCurrent) );
				}

				// when we are reordering for width or APL, it may happen that
				// the number of nodes has grown above certain limit,
				// in which case we have to resize the data structures
				if ( p->fMinWidth || p->fMinApl )
				{
					if ( p->nNodesCur >= 2 * p->nNodesMaxAlloc )
					{
//						printf( "Resizing data structures. Old size = %6d. New size = %6d.\n",  p->nNodesMaxAlloc, p->nNodesCur );
						reoResizeStructures( p, 0, p->nNodesCur, 0 );
					}
				}
			}
			// fix the plane index
			if ( q == -1 )
				q++;
			// now p points to the position of this var in the order

			// move down
			for ( ; q < p->nSupp-1; )
			{
				CostCurrent -= reoReorderSwapAdjacentVars( p, q, 0 );
				q++;    // change q to point to the position of this var in the order
				// sanity check: the number of nodes on the back pass should be the same
				if ( p->pVarCosts[q] != REO_HIGH_VALUE && fabs( p->pVarCosts[q] - CostCurrent ) > REO_COST_EPSILON )
					printf("reoReorderSift(): Error! On the backward move, the costs are different.\n");
				p->pVarCosts[q] = CostCurrent;
				// update the lower bound (assuming that for level q-1 it is set correctly)
				p->pPlanes[q].statsCostAbove = p->pPlanes[q-1].statsCostAbove + p->pPlanes[q-1].statsCost;
				// check the bounds only if the variable already reached its previous position
				if ( q >= BestQ )
				{
					// check the upper bound
					if ( CostCurrent >= CostLimit )
						break;
					// check the lower bound
					if ( p->pPlanes[q].statsCostAbove + (REO_QUAL_PAR-1)*p->pPlanes[q].statsCostBelow/REO_QUAL_PAR >= CostBest )
						break;
				}
				// update the best cost
				if ( CostBest >= CostCurrent )
				{
					CostBest = CostCurrent;
					BestQ    = q;
					// adjust node limit
					CostLimit = ddMin( CostLimit, 1 + (int)(REO_REORDER_LIMIT * CostCurrent) );
				}

				// when we are reordering for width or APL, it may happen that
				// the number of nodes has grown above certain limit,
				// in which case we have to resize the data structures
				if ( p->fMinWidth || p->fMinApl )
				{
					if ( p->nNodesCur >= 2 * p->nNodesMaxAlloc )
					{
//						printf( "Resizing data structures. Old size = %6d. New size = %6d.\n",  p->nNodesMaxAlloc, p->nNodesCur );
						reoResizeStructures( p, 0, p->nNodesCur, 0 );
					}
				}
			}
			// move the variable up from the given position (q) to the best position (BestQ)
			assert( q >= BestQ );
			for ( ; q > BestQ; q-- )
			{
				CostCurrent -= reoReorderSwapAdjacentVars( p, q-1, 1 );
				// sanity check: the number of nodes on the back pass should be the same
				if ( fabs( p->pVarCosts[q-1] - CostCurrent ) > REO_COST_EPSILON )
				{
					printf("reoReorderSift():  Error! On the return move, the costs are different.\n" );
					fflush(stdout);
				}
			}
		}
		else // move down first, then up
		{
			// set the current number of nodes on all levels above the given level
			p->pPlanes[0].statsCostAbove = 0;
			for ( v = 1; v <= VarCurrent; v++ )
				p->pPlanes[v].statsCostAbove = p->pPlanes[v-1].statsCostAbove + p->pPlanes[v-1].statsCost;
			// set the current number of nodes on all levels below the given level
			p->pPlanes[p->nSupp].statsCostBelow = 0;
			for ( v = p->nSupp - 1; v >= VarCurrent; v-- )
				p->pPlanes[v].statsCostBelow = p->pPlanes[v+1].statsCostBelow + p->pPlanes[v+1].statsCost;
			
			assert( CostCurrent == p->pPlanes[VarCurrent].statsCostAbove + 
									p->pPlanes[VarCurrent].statsCost +
				                    p->pPlanes[VarCurrent].statsCostBelow );

			// move down
			for ( q = VarCurrent; q < p->nSupp-1; )
			{
				CostCurrent -= reoReorderSwapAdjacentVars( p, q, 0 );
				q++;    // change q to point to the position of this var in the order
				p->pVarCosts[q] = CostCurrent;
				// update the lower bound (assuming that for level q-1 it is set correctly)
				p->pPlanes[q].statsCostAbove = p->pPlanes[q-1].statsCostAbove + p->pPlanes[q-1].statsCost;
				// check the upper bound
				if ( CostCurrent >= CostLimit )
					break;
				// check the lower bound
				if ( p->pPlanes[q].statsCostAbove + (REO_QUAL_PAR-1)*p->pPlanes[q].statsCostBelow/REO_QUAL_PAR >= CostBest )
					break;
				// update the best cost
				if ( CostBest > CostCurrent )
				{
					CostBest = CostCurrent;
					BestQ    = q;
					// adjust node limit
					CostLimit = ddMin( CostLimit, 1 + (int)(REO_REORDER_LIMIT * CostCurrent) );
				}

				// when we are reordering for width or APL, it may happen that
				// the number of nodes has grown above certain limit,
				// in which case we have to resize the data structures
				if ( p->fMinWidth || p->fMinApl )
				{
					if ( p->nNodesCur >= 2 * p->nNodesMaxAlloc )
					{
//						printf( "Resizing data structures. Old size = %6d. New size = %6d.\n",  p->nNodesMaxAlloc, p->nNodesCur );
						reoResizeStructures( p, 0, p->nNodesCur, 0 );
					}
				}
			}

			// move up
			for ( --q; q >= 0; q-- )
			{
				CostCurrent -= reoReorderSwapAdjacentVars( p, q, 1 );
				// now q points to the position of this var in the order
				// sanity check: the number of nodes on the back pass should be the same
				if ( p->pVarCosts[q] != REO_HIGH_VALUE && fabs( p->pVarCosts[q] - CostCurrent ) > REO_COST_EPSILON )
					printf("reoReorderSift(): Error! On the backward move, the costs are different.\n");
				p->pVarCosts[q] = CostCurrent;
				// update the lower bound (assuming that for level q+1 it is set correctly)
				p->pPlanes[q].statsCostBelow = p->pPlanes[q+1].statsCostBelow + p->pPlanes[q+1].statsCost;
				// check the bounds only if the variable already reached its previous position
				if ( q <= BestQ )
				{
					// check the upper bound
					if ( CostCurrent >= CostLimit )
						break;
					// check the lower bound
					if ( p->pPlanes[q].statsCostBelow + (REO_QUAL_PAR-1)*p->pPlanes[q].statsCostAbove/REO_QUAL_PAR >= CostBest )
						break;
				}
				// update the best cost
				if ( CostBest >= CostCurrent )
				{
					CostBest = CostCurrent;
					BestQ    = q;
					// adjust node limit
					CostLimit = ddMin( CostLimit, 1 + (int)(REO_REORDER_LIMIT * CostCurrent) );
				}

				// when we are reordering for width or APL, it may happen that
				// the number of nodes has grown above certain limit,
				// in which case we have to resize the data structures
				if ( p->fMinWidth || p->fMinApl )
				{
					if ( p->nNodesCur >= 2 * p->nNodesMaxAlloc )
					{
//						printf( "Resizing data structures. Old size = %6d. New size = %6d.\n",  p->nNodesMaxAlloc, p->nNodesCur );
						reoResizeStructures( p, 0, p->nNodesCur, 0 );
					}
				}
			}
			// fix the plane index
			if ( q == -1 )
				q++;
			// now q points to the position of this var in the order
			// move the variable down from the given position (q) to the best position (BestQ)
			assert( q <= BestQ );
			for ( ; q < BestQ; q++ )
			{
				CostCurrent -= reoReorderSwapAdjacentVars( p, q, 0 );
				// sanity check: the number of nodes on the back pass should be the same
				if ( fabs( p->pVarCosts[q+1] - CostCurrent ) > REO_COST_EPSILON )
				{
					printf("reoReorderSift(): Error! On the return move, the costs are different.\n" );
					fflush(stdout);
				}
			}
		}
		assert( fabs( CostBest - CostCurrent ) < REO_COST_EPSILON );

		// update the cost 
		if ( p->fMinWidth )
			p->nWidthCur = (int)CostBest;
		else if ( p->fMinApl )
			p->nAplCur = CostCurrent;
		else
			p->nNodesCur = (int)CostBest;
	}

	// remove the sifted attributes if any
	for ( v = 0; v < p->nSupp; v++ )
		p->pPlanes[v].fSifted = 0;
}

////////////////////////////////////////////////////////////////////////
///                         END OF FILE                              ///
////////////////////////////////////////////////////////////////////////