src/bdd/reo/reoSift.c File Reference

#include "reo.h"

Include dependency graph for reoSift.c:

Functions
void	reoReorderSift (reo_man *p)

Function Documentation

void reoReorderSift ( reo_man * p )

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.0 2002/15/10 03:00:00 alanmi Exp

] 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 []

Definition at line 41 of file reoSift.c.

00043 00044 00045 00046 00047 00048 00049 00050 00051 00052 00053 00054 00055 00056 00057 00058 00059 00060 00061 00062 00063 00064 00065 00066 00067         { 00068 00069 00070 00071 00072 00073 00074 00075 00076 00077 00078 00079 00080 00081 00082 00083 00084 00085 00086 00087 00088 00089 00090 00091 00092 00093 00094 00095 00096 00097 00098 00099 00100 00101 00102 00103 00104 00105 00106 00107 00108 00109 00110 00111 00112 00113 00114 00115 00116 00117 00118 00119 00120 00121 00122 00123 00124 00125 00126 00127 00128 00129 00130 00131 00132 00133 00134 00135 00136 00137 00138 00139 00140 00141 00142 00143 00144 00145 00146 00147 00148 00149 00150 00151 00152 00153 00154 00155 00156 00157 00158 00159 00160 00161 00162 00163 00164 00165 00166 00167 00168 00169 00170 00171 00172 00173 00174 00175 00176 00177 00178 00179 00180 00181 00182 00183 00184 00185 00186 00187 00188 00189 00190 00191 00192 00193 00194 00195 00196 00197 00198 00199 00200 00201 00202 00203 00204 00205 00206 00207 00208 00209 00210 00211 00212 00213 00214 00215 00216 00217 00218 00219 00220 00221 00222 00223 00224 00225 00226 00227 00228 00229 00230 00231 00232 00233 00234 00235 00236 00237 00238 00239 00240 00241 00242 00243 00244 00245 00246 00247 00248 00249 00250 00251 00252 00253 00254 00255 00256 00257 00258 00259 00260 00261 00262 00263 00264 00265 00266 00267 00268 00269 00270 00271 00272 00273 00274 00275 00276 00277 00278 00279 00280 00281 00282 00283 00284 00285 00286 00287 00288 00289 00290 00291 00292 00293 00294 00295 00296 00297 00298 00299 00300 00301 00302 00303 00304 00305 00306 00307 00308 00309 00310 00311 00312 00313 00314 00315 00316 00317 00318 00319 00320 00321 00322 00323 00324 00325 00326 00327 00328 00329 00330 00331         } 00332 00333 00334 00335 00336 }

class="fragment">00042 { 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;

src/bdd/reo/reoSift.c File Reference

Functions

Function Documentation