src/opt/rwr/rwrEva.c File Reference

#include "rwr.h"
#include "dec.h"
Include dependency graph for rwrEva.c:

Go to the source code of this file.

Functions

static Dec_Graph_t * Rwr_CutEvaluate (Rwr_Man_t *p, Abc_Obj_t *pRoot, Cut_Cut_t *pCut, Vec_Ptr_t *vFaninsCur, int nNodesSaved, int LevelMax, int *pGainBest, int fPlaceEnable)
static int Rwr_CutIsBoolean (Abc_Obj_t *pObj, Vec_Ptr_t *vLeaves)
static int Rwr_CutCountNumNodes (Abc_Obj_t *pObj, Cut_Cut_t *pCut)
static int Rwr_NodeGetDepth_rec (Abc_Obj_t *pObj, Vec_Ptr_t *vLeaves)
int Rwr_NodeRewrite (Rwr_Man_t *p, Cut_Man_t *pManCut, Abc_Obj_t *pNode, int fUpdateLevel, int fUseZeros, int fPlaceEnable)
void Rwr_CutIsBoolean_rec (Abc_Obj_t *pObj, Vec_Ptr_t *vLeaves, int fMarkA)
void Rwr_CutCountNumNodes_rec (Abc_Obj_t *pObj, Cut_Cut_t *pCut, Vec_Ptr_t *vNodes)
void Rwr_ScoresClean (Rwr_Man_t *p)
int Rwr_ScoresCompare (int *pNum1, int *pNum2)
void Rwr_ScoresReport (Rwr_Man_t *p)

Variables

static int Gains [222]

Function Documentation

int Rwr_CutCountNumNodes ( Abc_Obj_t *  pObj,
Cut_Cut_t *  pCut 
) [static]

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

Synopsis [Count the nodes in the cut space of a node.]

Description []

SideEffects []

SeeAlso []

Definition at line 440 of file rwrEva.c.

00441 {
00442     Vec_Ptr_t * vNodes;
00443     int i, Counter;
00444     // collect all nodes
00445     vNodes = Vec_PtrAlloc( 100 );
00446     for ( pCut = pCut->pNext; pCut; pCut = pCut->pNext )
00447         Rwr_CutCountNumNodes_rec( pObj, pCut, vNodes );
00448     // clean all nodes
00449     Vec_PtrForEachEntry( vNodes, pObj, i )
00450         pObj->fMarkC = 0;
00451     // delete and return
00452     Counter = Vec_PtrSize(vNodes);
00453     Vec_PtrFree( vNodes );
00454     return Counter;
00455 }

void Rwr_CutCountNumNodes_rec ( Abc_Obj_t *  pObj,
Cut_Cut_t *  pCut,
Vec_Ptr_t *  vNodes 
)

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

Synopsis [Count the nodes in the cut space of a node.]

Description []

SideEffects []

SeeAlso []

Definition at line 403 of file rwrEva.c.

00404 {
00405     int i;
00406     for ( i = 0; i < (int)pCut->nLeaves; i++ )
00407         if ( pCut->pLeaves[i] == pObj->Id )
00408         {
00409             // check if the node is collected
00410             if ( pObj->fMarkC == 0 )
00411             {
00412                 pObj->fMarkC = 1;
00413                 Vec_PtrPush( vNodes, pObj );
00414             }
00415             return;
00416         }
00417     assert( Abc_ObjIsNode(pObj) );
00418     // check if the node is collected
00419     if ( pObj->fMarkC == 0 )
00420     {
00421         pObj->fMarkC = 1;
00422         Vec_PtrPush( vNodes, pObj );
00423     }
00424     // traverse the fanins
00425     Rwr_CutCountNumNodes_rec( Abc_ObjFanin0(pObj), pCut, vNodes );
00426     Rwr_CutCountNumNodes_rec( Abc_ObjFanin1(pObj), pCut, vNodes );
00427 }

Dec_Graph_t * Rwr_CutEvaluate ( Rwr_Man_t *  p,
Abc_Obj_t *  pRoot,
Cut_Cut_t *  pCut,
Vec_Ptr_t *  vFaninsCur,
int  nNodesSaved,
int  LevelMax,
int *  pGainBest,
int  fPlaceEnable 
) [static]

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

FileName [rwrDec.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [DAG-aware AIG rewriting package.]

Synopsis [Evaluation and decomposition procedures.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - June 20, 2005.]

Revision [

Id
rwrDec.c,v 1.00 2005/06/20 00:00:00 alanmi Exp

] DECLARATIONS ///

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

Synopsis [Evaluates the cut.]

Description []

SideEffects []

SeeAlso []

Definition at line 246 of file rwrEva.c.

00247 {
00248     Vec_Ptr_t * vSubgraphs;
00249     Dec_Graph_t * pGraphBest, * pGraphCur;
00250     Rwr_Node_t * pNode, * pFanin;
00251     int nNodesAdded, GainBest, i, k;
00252     unsigned uTruth;
00253     float CostBest;//, CostCur;
00254     // find the matching class of subgraphs
00255     uTruth = 0xFFFF & *Cut_CutReadTruth(pCut);
00256     vSubgraphs = Vec_VecEntry( p->vClasses, p->pMap[uTruth] );
00257     p->nSubgraphs += vSubgraphs->nSize;
00258     // determine the best subgraph
00259     GainBest = -1;
00260     CostBest = ABC_INFINITY;
00261     Vec_PtrForEachEntry( vSubgraphs, pNode, i )
00262     {
00263         // get the current graph
00264         pGraphCur = (Dec_Graph_t *)pNode->pNext;
00265         // copy the leaves
00266         Vec_PtrForEachEntry( vFaninsCur, pFanin, k )
00267             Dec_GraphNode(pGraphCur, k)->pFunc = pFanin;
00268         // detect how many unlabeled nodes will be reused
00269         nNodesAdded = Dec_GraphToNetworkCount( pRoot, pGraphCur, nNodesSaved, LevelMax );
00270         if ( nNodesAdded == -1 )
00271             continue;
00272         assert( nNodesSaved >= nNodesAdded );
00273 /*
00274         // evaluate the cut
00275         if ( fPlaceEnable )
00276         {
00277             extern float Abc_PlaceEvaluateCut( Abc_Obj_t * pRoot, Vec_Ptr_t * vFanins );
00278 
00279             float Alpha = 0.5; // ???
00280             float PlaceCost;
00281 
00282             // get the placement cost of the cut
00283             PlaceCost = Abc_PlaceEvaluateCut( pRoot, vFaninsCur );
00284 
00285             // get the weigted cost of the cut
00286             CostCur = nNodesSaved - nNodesAdded + Alpha * PlaceCost;
00287 
00288             // do not allow uphill moves
00289             if ( nNodesSaved - nNodesAdded < 0 )
00290                 continue;
00291 
00292             // decide what cut to use
00293             if ( CostBest > CostCur )
00294             {
00295                 GainBest   = nNodesSaved - nNodesAdded; // pure node cost
00296                 CostBest   = CostCur;                   // cost with placement
00297                 pGraphBest = pGraphCur;                 // subgraph to be used for rewriting
00298 
00299                 // score the graph
00300                 if ( nNodesSaved - nNodesAdded > 0 )
00301                 {
00302                     pNode->nScore++;
00303                     pNode->nGain += GainBest;
00304                     pNode->nAdded += nNodesAdded;
00305                 }
00306             }
00307         }
00308         else
00309 */
00310         {
00311             // count the gain at this node
00312             if ( GainBest < nNodesSaved - nNodesAdded )
00313             {
00314                 GainBest   = nNodesSaved - nNodesAdded;
00315                 pGraphBest = pGraphCur;
00316 
00317                 // score the graph
00318                 if ( nNodesSaved - nNodesAdded > 0 )
00319                 {
00320                     pNode->nScore++;
00321                     pNode->nGain += GainBest;
00322                     pNode->nAdded += nNodesAdded;
00323                 }
00324             }
00325         }
00326     }
00327     if ( GainBest == -1 )
00328         return NULL;
00329     *pGainBest = GainBest;
00330     return pGraphBest;
00331 }

int Rwr_CutIsBoolean ( Abc_Obj_t *  pObj,
Vec_Ptr_t *  vLeaves 
) [static]

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

Synopsis [Checks the type of the cut.]

Description [Returns 1(0) if the cut is Boolean (algebraic).]

SideEffects []

SeeAlso []

Definition at line 370 of file rwrEva.c.

00371 {
00372     Abc_Obj_t * pTemp;
00373     int i, RetValue;
00374     Vec_PtrForEachEntry( vLeaves, pTemp, i )
00375     {
00376         pTemp = Abc_ObjRegular(pTemp);
00377         assert( !pTemp->fMarkA && !pTemp->fMarkB );
00378     }
00379     Rwr_CutIsBoolean_rec( Abc_ObjFanin0(pObj), vLeaves, 1 );
00380     Rwr_CutIsBoolean_rec( Abc_ObjFanin1(pObj), vLeaves, 0 );
00381     RetValue = 0;
00382     Vec_PtrForEachEntry( vLeaves, pTemp, i )
00383     {
00384         pTemp = Abc_ObjRegular(pTemp);
00385         RetValue |= pTemp->fMarkA && pTemp->fMarkB;
00386         pTemp->fMarkA = pTemp->fMarkB = 0;
00387     }
00388     return RetValue;
00389 }

void Rwr_CutIsBoolean_rec ( Abc_Obj_t *  pObj,
Vec_Ptr_t *  vLeaves,
int  fMarkA 
)

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

Synopsis [Checks the type of the cut.]

Description []

SideEffects []

SeeAlso []

Definition at line 344 of file rwrEva.c.

00345 {
00346     if ( Vec_PtrFind(vLeaves, pObj) >= 0 || Vec_PtrFind(vLeaves, Abc_ObjNot(pObj)) >= 0 )
00347     {
00348         if ( fMarkA )
00349             pObj->fMarkA = 1;
00350         else
00351             pObj->fMarkB = 1;
00352         return;
00353     }
00354     assert( !Abc_ObjIsCi(pObj) );
00355     Rwr_CutIsBoolean_rec( Abc_ObjFanin0(pObj), vLeaves, fMarkA );
00356     Rwr_CutIsBoolean_rec( Abc_ObjFanin1(pObj), vLeaves, fMarkA );
00357 }

int Rwr_NodeGetDepth_rec ( Abc_Obj_t *  pObj,
Vec_Ptr_t *  vLeaves 
) [static]

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

Synopsis [Returns depth of the cut.]

Description []

SideEffects []

SeeAlso []

Definition at line 469 of file rwrEva.c.

00470 {
00471     Abc_Obj_t * pLeaf;
00472     int i, Depth0, Depth1;
00473     if ( Abc_ObjIsCi(pObj) )
00474         return 0;
00475     Vec_PtrForEachEntry( vLeaves, pLeaf, i )
00476         if ( pObj == Abc_ObjRegular(pLeaf) )
00477             return 0;
00478     Depth0 = Rwr_NodeGetDepth_rec( Abc_ObjFanin0(pObj), vLeaves );
00479     Depth1 = Rwr_NodeGetDepth_rec( Abc_ObjFanin1(pObj), vLeaves );
00480     return 1 + ABC_MAX( Depth0, Depth1 );
00481 }

int Rwr_NodeRewrite ( Rwr_Man_t *  p,
Cut_Man_t *  pManCut,
Abc_Obj_t *  pNode,
int  fUpdateLevel,
int  fUseZeros,
int  fPlaceEnable 
)

FUNCTION DEFINITIONS ///Function*************************************************************

Synopsis [Performs rewriting for one node.]

Description [This procedure considers all the cuts computed for the node and tries to rewrite each of them using the "forest" of different AIG structures precomputed and stored in the RWR manager. Determines the best rewriting and computes the gain in the number of AIG nodes in the final network. In the end, p->vFanins contains information about the best cut that can be used for rewriting, while p->pGraph gives the decomposition dag (represented using decomposition graph data structure). Returns gain in the number of nodes or -1 if node cannot be rewritten.]

SideEffects []

SeeAlso []

Definition at line 55 of file rwrEva.c.

00056 {
00057     int fVeryVerbose = 0;
00058     Dec_Graph_t * pGraph;
00059     Cut_Cut_t * pCut;//, * pTemp;
00060     Abc_Obj_t * pFanin;
00061     unsigned uPhase, uTruthBest, uTruth;
00062     char * pPerm;
00063     int Required, nNodesSaved, nNodesSaveCur;
00064     int i, GainCur, GainBest = -1;
00065     int clk, clk2;//, Counter;
00066 
00067     p->nNodesConsidered++;
00068     // get the required times
00069     Required = fUpdateLevel? Abc_ObjRequiredLevel(pNode) : ABC_INFINITY;
00070 
00071     // get the node's cuts
00072 clk = clock();
00073     pCut = (Cut_Cut_t *)Abc_NodeGetCutsRecursive( pManCut, pNode, 0, 0 );
00074     assert( pCut != NULL );
00075 p->timeCut += clock() - clk;
00076 
00077 //printf( " %d", Rwr_CutCountNumNodes(pNode, pCut) );
00078 /*
00079     Counter = 0;
00080     for ( pTemp = pCut->pNext; pTemp; pTemp = pTemp->pNext )
00081         Counter++;
00082     printf( "%d ", Counter );
00083 */
00084     // go through the cuts
00085 clk = clock();
00086     for ( pCut = pCut->pNext; pCut; pCut = pCut->pNext )
00087     {
00088         // consider only 4-input cuts
00089         if ( pCut->nLeaves < 4 )
00090             continue;
00091 //            Cut_CutPrint( pCut, 0 ), printf( "\n" );
00092 
00093         // get the fanin permutation
00094         uTruth = 0xFFFF & *Cut_CutReadTruth(pCut);
00095         pPerm = p->pPerms4[ p->pPerms[uTruth] ];
00096         uPhase = p->pPhases[uTruth];
00097         // collect fanins with the corresponding permutation/phase
00098         Vec_PtrClear( p->vFaninsCur );
00099         Vec_PtrFill( p->vFaninsCur, (int)pCut->nLeaves, 0 );
00100         for ( i = 0; i < (int)pCut->nLeaves; i++ )
00101         {
00102             pFanin = Abc_NtkObj( pNode->pNtk, pCut->pLeaves[pPerm[i]] );
00103             if ( pFanin == NULL )
00104                 break;
00105             pFanin = Abc_ObjNotCond(pFanin, ((uPhase & (1<<i)) > 0) );
00106             Vec_PtrWriteEntry( p->vFaninsCur, i, pFanin );
00107         }
00108         if ( i != (int)pCut->nLeaves )
00109         {
00110             p->nCutsBad++;
00111             continue;
00112         }
00113         p->nCutsGood++;
00114 
00115         {
00116             int Counter = 0;
00117             Vec_PtrForEachEntry( p->vFaninsCur, pFanin, i )
00118                 if ( Abc_ObjFanoutNum(Abc_ObjRegular(pFanin)) == 1 )
00119                     Counter++;
00120             if ( Counter > 2 )
00121                 continue;
00122         }
00123 
00124 clk2 = clock();
00125 /*
00126         printf( "Considering: (" );
00127         Vec_PtrForEachEntry( p->vFaninsCur, pFanin, i )
00128             printf( "%d ", Abc_ObjFanoutNum(Abc_ObjRegular(pFanin)) );
00129         printf( ")\n" );
00130 */
00131         // mark the fanin boundary 
00132         Vec_PtrForEachEntry( p->vFaninsCur, pFanin, i )
00133             Abc_ObjRegular(pFanin)->vFanouts.nSize++;
00134 
00135         // label MFFC with current ID
00136         Abc_NtkIncrementTravId( pNode->pNtk );
00137         nNodesSaved = Abc_NodeMffcLabelAig( pNode );
00138         // unmark the fanin boundary
00139         Vec_PtrForEachEntry( p->vFaninsCur, pFanin, i )
00140             Abc_ObjRegular(pFanin)->vFanouts.nSize--;
00141 p->timeMffc += clock() - clk2;
00142 
00143         // evaluate the cut
00144 clk2 = clock();
00145         pGraph = Rwr_CutEvaluate( p, pNode, pCut, p->vFaninsCur, nNodesSaved, Required, &GainCur, fPlaceEnable );
00146 p->timeEval += clock() - clk2;
00147 
00148         // check if the cut is better than the current best one
00149         if ( pGraph != NULL && GainBest < GainCur )
00150         {
00151             // save this form
00152             nNodesSaveCur = nNodesSaved;
00153             GainBest  = GainCur;
00154             p->pGraph  = pGraph;
00155             p->fCompl = ((uPhase & (1<<4)) > 0);
00156             uTruthBest = 0xFFFF & *Cut_CutReadTruth(pCut);
00157             // collect fanins in the
00158             Vec_PtrClear( p->vFanins );
00159             Vec_PtrForEachEntry( p->vFaninsCur, pFanin, i )
00160                 Vec_PtrPush( p->vFanins, pFanin );
00161         }
00162     }
00163 p->timeRes += clock() - clk;
00164 
00165     if ( GainBest == -1 )
00166         return -1;
00167 /*
00168     if ( GainBest > 0 )
00169     {
00170         printf( "Class %d  ", p->pMap[uTruthBest] );
00171         printf( "Gain = %d. Node %d : ", GainBest, pNode->Id );
00172         Vec_PtrForEachEntry( p->vFanins, pFanin, i )
00173             printf( "%d ", Abc_ObjRegular(pFanin)->Id );
00174         Dec_GraphPrint( stdout, p->pGraph, NULL, NULL );
00175         printf( "\n" );
00176     }
00177 */
00178 
00179 //    printf( "%d", nNodesSaveCur - GainBest );
00180 /*
00181     if ( GainBest > 0 )
00182     {
00183         if ( Rwr_CutIsBoolean( pNode, p->vFanins ) )
00184             printf( "b" );
00185         else
00186         {
00187             printf( "Node %d : ", pNode->Id );
00188             Vec_PtrForEachEntry( p->vFanins, pFanin, i )
00189                 printf( "%d ", Abc_ObjRegular(pFanin)->Id );
00190             printf( "a" );
00191         }
00192     }
00193 */
00194 /*
00195     if ( GainBest > 0 )
00196         if ( p->fCompl )
00197             printf( "c" );
00198         else
00199             printf( "." );
00200 */
00201 
00202     // copy the leaves
00203     Vec_PtrForEachEntry( p->vFanins, pFanin, i )
00204         Dec_GraphNode(p->pGraph, i)->pFunc = pFanin;
00205 /*
00206     printf( "(" );
00207     Vec_PtrForEachEntry( p->vFanins, pFanin, i )
00208         printf( " %d", Abc_ObjRegular(pFanin)->vFanouts.nSize - 1 );
00209     printf( " )  " );
00210 */
00211 //    printf( "%d ", Rwr_NodeGetDepth_rec( pNode, p->vFanins ) );
00212 
00213     p->nScores[p->pMap[uTruthBest]]++;
00214     p->nNodesGained += GainBest;
00215     if ( fUseZeros || GainBest > 0 )
00216     {
00217         p->nNodesRewritten++;
00218     }
00219 
00220     // report the progress
00221     if ( fVeryVerbose && GainBest > 0 )
00222     {
00223         printf( "Node %6s :   ", Abc_ObjName(pNode) );
00224         printf( "Fanins = %d. ", p->vFanins->nSize );
00225         printf( "Save = %d.  ", nNodesSaveCur );
00226         printf( "Add = %d.  ",  nNodesSaveCur-GainBest );
00227         printf( "GAIN = %d.  ", GainBest );
00228         printf( "Cone = %d.  ", p->pGraph? Dec_GraphNodeNum(p->pGraph) : 0 );
00229         printf( "Class = %d.  ", p->pMap[uTruthBest] );
00230         printf( "\n" );
00231     }
00232     return GainBest;
00233 }

void Rwr_ScoresClean ( Rwr_Man_t *  p  ) 

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 495 of file rwrEva.c.

00496 {
00497     Vec_Ptr_t * vSubgraphs;
00498     Rwr_Node_t * pNode;
00499     int i, k;
00500     for ( i = 0; i < p->vClasses->nSize; i++ )
00501     {
00502         vSubgraphs = Vec_VecEntry( p->vClasses, i );
00503         Vec_PtrForEachEntry( vSubgraphs, pNode, k )
00504             pNode->nScore = pNode->nGain = pNode->nAdded = 0;
00505     }
00506 }

int Rwr_ScoresCompare ( int *  pNum1,
int *  pNum2 
)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 521 of file rwrEva.c.

00522 {
00523     if ( Gains[*pNum1] > Gains[*pNum2] )
00524         return -1;
00525     if ( Gains[*pNum1] < Gains[*pNum2] )
00526         return 1;
00527     return 0;
00528 }

void Rwr_ScoresReport ( Rwr_Man_t *  p  ) 

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 541 of file rwrEva.c.

00542 {
00543     extern void Ivy_TruthDsdComputePrint( unsigned uTruth );
00544     int Perm[222];
00545     Vec_Ptr_t * vSubgraphs;
00546     Rwr_Node_t * pNode;
00547     int i, iNew, k;
00548     unsigned uTruth;
00549     // collect total gains
00550     assert( p->vClasses->nSize == 222 );
00551     for ( i = 0; i < p->vClasses->nSize; i++ )
00552     {
00553         Perm[i] = i;
00554         Gains[i] = 0;
00555         vSubgraphs = Vec_VecEntry( p->vClasses, i );
00556         Vec_PtrForEachEntry( vSubgraphs, pNode, k )
00557             Gains[i] += pNode->nGain;
00558     }
00559     // sort the gains
00560     qsort( Perm, 222, sizeof(int), (int (*)(const void *, const void *))Rwr_ScoresCompare );
00561 
00562     // print classes
00563     for ( i = 0; i < p->vClasses->nSize; i++ )
00564     {
00565         iNew = Perm[i];
00566         if ( Gains[iNew] == 0 )
00567             break;
00568         vSubgraphs = Vec_VecEntry( p->vClasses, iNew );
00569         printf( "CLASS %3d: Subgr = %3d. Total gain = %6d.  ", iNew, Vec_PtrSize(vSubgraphs), Gains[iNew] );
00570         uTruth = (unsigned)p->pMapInv[iNew];
00571         Extra_PrintBinary( stdout, &uTruth, 16 );
00572         printf( "  " );
00573         Ivy_TruthDsdComputePrint( (unsigned)p->pMapInv[iNew] | ((unsigned)p->pMapInv[iNew] << 16) );
00574         Vec_PtrForEachEntry( vSubgraphs, pNode, k )
00575         {
00576             if ( pNode->nScore == 0 )
00577                 continue;
00578             printf( "    %2d: S=%5d. A=%5d. G=%6d. ", k, pNode->nScore, pNode->nAdded, pNode->nGain );
00579             Dec_GraphPrint( stdout, (Dec_Graph_t *)pNode->pNext, NULL, NULL );
00580         }
00581     }
00582 }

Variable Documentation

int Gains[222] [static]

Definition at line 508 of file rwrEva.c.

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