src/bdd/reo/reoTest.c File Reference

#include "reo.h"
Include dependency graph for reoTest.c:

Go to the source code of this file.

Functions

void Extra_ReorderTest (DdManager *dd, DdNode *Func)
void Extra_ReorderTestArray (DdManager *dd, DdNode *Funcs[], int nFuncs)
DdNode * Extra_ReorderCudd (DdManager *dd, DdNode *aFunc, int pPermuteReo[])
int Extra_bddReorderTest (DdManager *dd, DdNode *bF)
int Extra_addReorderTest (DdManager *dd, DdNode *aF)

Function Documentation

int Extra_addReorderTest ( DdManager *  dd,
DdNode *  aF 
)

Function*************************************************************

Synopsis []

Description [Transfers the ADD into another manager minimizes it and returns the min number of nodes; disposes of the BDD in the new manager. Useful for debugging or comparing the performance of other reordering procedures.]

SideEffects []

SeeAlso []

Definition at line 214 of file reoTest.c.

00215 {
00216         static DdManager * s_ddmin;
00217         DdNode * bF;
00218         DdNode * bFmin;
00219         DdNode * aFmin;
00220         int  nNodesBeg;
00221         int  nNodesEnd;
00222         int clk1;
00223 
00224         if ( s_ddmin == NULL )
00225                 s_ddmin = Cudd_Init( dd->size, 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0);
00226 
00227 //      Cudd_ShuffleHeap( s_ddmin, dd->invperm );
00228 
00229         clk1 = clock();
00230         bF    = Cudd_addBddPattern( dd, aF );         Cudd_Ref( bF );
00231         bFmin = Cudd_bddTransfer( dd, s_ddmin, bF );  Cudd_Ref( bFmin );
00232         Cudd_RecursiveDeref( dd, bF );
00233         aFmin = Cudd_BddToAdd( s_ddmin, bFmin );      Cudd_Ref( aFmin );
00234         Cudd_RecursiveDeref( s_ddmin, bFmin );
00235 
00236         nNodesBeg = Cudd_DagSize( aFmin );
00237         Cudd_ReduceHeap(s_ddmin,CUDD_REORDER_SIFT,1);
00238 //      Cudd_ReduceHeap(s_ddmin,CUDD_REORDER_SYMM_SIFT,1);
00239         nNodesEnd = Cudd_DagSize( aFmin );
00240         Cudd_RecursiveDeref( s_ddmin, aFmin );
00241 
00242         printf( "Classical reordering of ADDs: Before = %d. After = %d.\n", nNodesBeg, nNodesEnd );
00243         printf( "Classical variable reordering time = %.2f sec\n", (float)(clock() - clk1)/(float)(CLOCKS_PER_SEC) );
00244         return nNodesEnd;
00245 }

int Extra_bddReorderTest ( DdManager *  dd,
DdNode *  bF 
)

Function*************************************************************

Synopsis []

Description [Transfers the BDD into another manager minimizes it and returns the min number of nodes; disposes of the BDD in the new manager. Useful for debugging or comparing the performance of other reordering procedures.]

SideEffects []

SeeAlso []

Definition at line 177 of file reoTest.c.

00178 {
00179         static DdManager * s_ddmin;
00180         DdNode * bFmin;
00181         int  nNodes;
00182 //      int clk1;
00183 
00184         if ( s_ddmin == NULL )
00185                 s_ddmin = Cudd_Init( dd->size, 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0);
00186 
00187 //      Cudd_ShuffleHeap( s_ddmin, dd->invperm );
00188 
00189 //      clk1 = clock();
00190         bFmin = Cudd_bddTransfer( dd, s_ddmin, bF );  Cudd_Ref( bFmin );
00191         Cudd_ReduceHeap(s_ddmin,CUDD_REORDER_SIFT,1);
00192 //      Cudd_ReduceHeap(s_ddmin,CUDD_REORDER_SYMM_SIFT,1);
00193         nNodes = Cudd_DagSize( bFmin );
00194         Cudd_RecursiveDeref( s_ddmin, bFmin );
00195 
00196 //      printf( "Classical variable reordering time = %.2f sec\n", (float)(clock() - clk1)/(float)(CLOCKS_PER_SEC) );
00197         return nNodes;
00198 }

DdNode* Extra_ReorderCudd ( DdManager *  dd,
DdNode *  aFunc,
int  pPermuteReo[] 
)

Function*************************************************************

Synopsis [Reorders the DD using CUDD package.]

Description [Transfers the DD into a temporary manager in such a way that the level correspondence is preserved. Reorders the manager and transfers the DD back into the original manager using the topmost levels of the manager, in such a way that the ordering of levels is preserved. The resulting permutation is returned in the array given by the user.]

SideEffects []

SeeAlso []

Definition at line 106 of file reoTest.c.

00107 {
00108         static DdManager * ddReorder = NULL;
00109         static int * Permute     = NULL;
00110         static int * PermuteReo1 = NULL;
00111         static int * PermuteReo2 = NULL;
00112         DdNode * aFuncReorder, * aFuncNew;
00113         int lev, var;
00114 
00115         // start the reordering manager
00116         if ( ddReorder == NULL )
00117         {
00118                 Permute       = ALLOC( int, dd->size );
00119                 PermuteReo1   = ALLOC( int, dd->size );
00120                 PermuteReo2   = ALLOC( int, dd->size );
00121                 ddReorder = Cudd_Init( dd->size, 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0 );
00122                 Cudd_AutodynDisable(ddReorder);
00123         }
00124 
00125         // determine the permutation of variable to make sure that var order in bFunc
00126         // will not change when this function is transfered into the new manager
00127         for ( lev = 0; lev < dd->size; lev++ )
00128         {
00129                 Permute[ dd->invperm[lev] ] = ddReorder->invperm[lev];
00130                 PermuteReo1[ ddReorder->invperm[lev] ] = dd->invperm[lev];
00131         }
00132         // transfer this function into the new manager in such a way that ordering of vars does not change
00133         aFuncReorder = Extra_TransferPermute( dd, ddReorder, aFunc, Permute );  Cudd_Ref( aFuncReorder );
00134 //      assert( Cudd_DagSize(aFunc) == Cudd_DagSize(aFuncReorder)  );
00135 
00136         // perform the reordering
00137 printf( "Nodes before = %d.\n", Cudd_DagSize(aFuncReorder) );
00138         Cudd_ReduceHeap( ddReorder, CUDD_REORDER_SYMM_SIFT, 1 );
00139 printf( "Nodes before = %d.\n", Cudd_DagSize(aFuncReorder) );
00140 
00141         // determine the reverse variable permutation
00142         for ( lev = 0; lev < dd->size; lev++ )
00143         {
00144                 Permute[ ddReorder->invperm[lev] ] = dd->invperm[lev];
00145                 PermuteReo2[ dd->invperm[lev] ] = ddReorder->invperm[lev];
00146         }
00147 
00148         // transfer this function into the new manager in such a way that ordering of vars does not change
00149         aFuncNew = Extra_TransferPermute( ddReorder, dd, aFuncReorder, Permute );  Cudd_Ref( aFuncNew );
00150 //      assert( Cudd_DagSize(aFuncNew) == Cudd_DagSize(aFuncReorder)  );
00151         Cudd_RecursiveDeref( ddReorder, aFuncReorder );
00152 
00153         // derive the resulting variable ordering
00154         if ( pPermuteReo )
00155                 for ( var = 0; var < dd->size; var++ )
00156                         pPermuteReo[var] = PermuteReo1[ PermuteReo2[var] ];
00157 
00158         Cudd_Deref( aFuncNew );
00159         return aFuncNew;
00160 }

void Extra_ReorderTest ( DdManager *  dd,
DdNode *  Func 
)

CFile****************************************************************

FileName [reoTest.c]

PackageName [REO: A specialized DD reordering engine.]

Synopsis [Various testing procedures (may be outdated).]

Author [Alan Mishchenko <alanmi@ece.pdx.edu>]

Affiliation [ECE Department. Portland State University, Portland, Oregon.]

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

Revision [

Id
reoTest.c,v 1.0 2002/15/10 03:00:00 alanmi Exp

] DECLARATIONS /// FUNCTION DEFINITIONS ///Function*************************************************************

Synopsis [Reorders the DD using REO and CUDD.]

Description [This function can be used to test the performance of the reordering package.]

SideEffects []

SeeAlso []

Definition at line 40 of file reoTest.c.

00041 {
00042         reo_man * pReo;
00043         DdNode * Temp, * Temp1;
00044         int pOrder[1000];
00045 
00046         pReo = Extra_ReorderInit( 100, 100 );
00047 
00048 //Extra_DumpDot( dd, &Func, 1, "beforReo.dot", 0 );
00049         Temp  = Extra_Reorder( pReo, dd, Func, pOrder );  Cudd_Ref( Temp );
00050 //Extra_DumpDot( dd, &Temp, 1, "afterReo.dot", 0 );
00051 
00052         Temp1 = Extra_ReorderCudd(dd, Func, NULL );           Cudd_Ref( Temp1 );
00053 printf( "Initial = %d. Final = %d. Cudd = %d.\n", Cudd_DagSize(Func), Cudd_DagSize(Temp), Cudd_DagSize(Temp1)  );
00054         Cudd_RecursiveDeref( dd, Temp1 );
00055         Cudd_RecursiveDeref( dd, Temp );
00056  
00057         Extra_ReorderQuit( pReo );
00058 }

void Extra_ReorderTestArray ( DdManager *  dd,
DdNode *  Funcs[],
int  nFuncs 
)

Function*************************************************************

Synopsis [Reorders the DD using REO and CUDD.]

Description [This function can be used to test the performance of the reordering package.]

SideEffects []

SeeAlso []

Definition at line 72 of file reoTest.c.

00073 {
00074         reo_man * pReo;
00075         DdNode * FuncsRes[1000];
00076         int pOrder[1000];
00077         int i;
00078 
00079         pReo = Extra_ReorderInit( 100, 100 );
00080         Extra_ReorderArray( pReo, dd, Funcs, FuncsRes, nFuncs, pOrder );  
00081         Extra_ReorderQuit( pReo );
00082 
00083 printf( "Initial = %d. Final = %d.\n", Cudd_SharingSize(Funcs,nFuncs), Cudd_SharingSize(FuncsRes,nFuncs) );
00084 
00085         for ( i = 0; i < nFuncs; i++ )
00086                 Cudd_RecursiveDeref( dd, FuncsRes[i] );
00087 
00088 }

Generated on Tue Jan 5 12:19:01 2010 for abc70930 by  doxygen 1.6.1