#include "abc.h"
#include "dec.h"
Go to the source code of this file.
Data Structures | |
struct | Abc_ManRef_t_ |
Typedefs | |
typedef struct Abc_ManRef_t_ | Abc_ManRef_t |
Functions | |
static void | Abc_NtkManRefPrintStats (Abc_ManRef_t *p) |
static Abc_ManRef_t * | Abc_NtkManRefStart (int nNodeSizeMax, int nConeSizeMax, bool fUseDcs, bool fVerbose) |
static void | Abc_NtkManRefStop (Abc_ManRef_t *p) |
static Dec_Graph_t * | Abc_NodeRefactor (Abc_ManRef_t *p, Abc_Obj_t *pNode, Vec_Ptr_t *vFanins, bool fUpdateLevel, bool fUseZeros, bool fUseDcs, bool fVerbose) |
int | Abc_NtkRefactor (Abc_Ntk_t *pNtk, int nNodeSizeMax, int nConeSizeMax, bool fUpdateLevel, bool fUseZeros, bool fUseDcs, bool fVerbose) |
typedef struct Abc_ManRef_t_ Abc_ManRef_t |
CFile****************************************************************
FileName [abcRefactor.c]
SystemName [ABC: Logic synthesis and verification system.]
PackageName [Network and node package.]
Synopsis [Resynthesis based on collapsing and refactoring.]
Author [Alan Mishchenko]
Affiliation [UC Berkeley]
Date [Ver. 1.0. Started - June 20, 2005.]
Revision [
] DECLARATIONS ///
Definition at line 28 of file abcRefactor.c.
Dec_Graph_t * Abc_NodeRefactor | ( | Abc_ManRef_t * | p, | |
Abc_Obj_t * | pNode, | |||
Vec_Ptr_t * | vFanins, | |||
bool | fUpdateLevel, | |||
bool | fUseZeros, | |||
bool | fUseDcs, | |||
bool | fVerbose | |||
) | [static] |
Function*************************************************************
Synopsis [Resynthesizes the node using refactoring.]
Description []
SideEffects []
SeeAlso []
Definition at line 184 of file abcRefactor.c.
00185 { 00186 int fVeryVerbose = 0; 00187 Abc_Obj_t * pFanin; 00188 Dec_Graph_t * pFForm; 00189 DdNode * bNodeFunc; 00190 int nNodesSaved, nNodesAdded, i, clk; 00191 char * pSop; 00192 int Required; 00193 00194 Required = fUpdateLevel? Abc_ObjRequiredLevel(pNode) : ABC_INFINITY; 00195 00196 p->nNodesConsidered++; 00197 00198 // get the function of the cut 00199 clk = clock(); 00200 bNodeFunc = Abc_NodeConeBdd( p->dd, p->dd->vars, pNode, vFanins, p->vVisited ); Cudd_Ref( bNodeFunc ); 00201 p->timeBdd += clock() - clk; 00202 00203 // if don't-care are used, transform the function into ISOP 00204 if ( fUseDcs ) 00205 { 00206 DdNode * bNodeDc, * bNodeOn, * bNodeOnDc; 00207 int nMints, nMintsDc; 00208 clk = clock(); 00209 // get the don't-cares 00210 bNodeDc = Abc_NodeConeDcs( p->dd, p->dd->vars + vFanins->nSize, p->dd->vars, p->vLeaves, vFanins, p->vVisited ); Cudd_Ref( bNodeDc ); 00211 nMints = (1 << vFanins->nSize); 00212 nMintsDc = (int)Cudd_CountMinterm( p->dd, bNodeDc, vFanins->nSize ); 00213 // printf( "Percentage of minterms = %5.2f.\n", 100.0 * nMintsDc / nMints ); 00214 // get the ISF 00215 bNodeOn = Cudd_bddAnd( p->dd, bNodeFunc, Cudd_Not(bNodeDc) ); Cudd_Ref( bNodeOn ); 00216 bNodeOnDc = Cudd_bddOr ( p->dd, bNodeFunc, bNodeDc ); Cudd_Ref( bNodeOnDc ); 00217 Cudd_RecursiveDeref( p->dd, bNodeFunc ); 00218 Cudd_RecursiveDeref( p->dd, bNodeDc ); 00219 // get the ISOP 00220 bNodeFunc = Cudd_bddIsop( p->dd, bNodeOn, bNodeOnDc ); Cudd_Ref( bNodeFunc ); 00221 Cudd_RecursiveDeref( p->dd, bNodeOn ); 00222 Cudd_RecursiveDeref( p->dd, bNodeOnDc ); 00223 p->timeDcs += clock() - clk; 00224 } 00225 00226 // always accept the case of constant node 00227 if ( Cudd_IsConstant(bNodeFunc) ) 00228 { 00229 p->nLastGain = Abc_NodeMffcSize( pNode ); 00230 p->nNodesGained += p->nLastGain; 00231 p->nNodesRefactored++; 00232 Cudd_RecursiveDeref( p->dd, bNodeFunc ); 00233 if ( Cudd_IsComplement(bNodeFunc) ) 00234 return Dec_GraphCreateConst0(); 00235 return Dec_GraphCreateConst1(); 00236 } 00237 00238 // get the SOP of the cut 00239 clk = clock(); 00240 pSop = Abc_ConvertBddToSop( NULL, p->dd, bNodeFunc, bNodeFunc, vFanins->nSize, 0, p->vCube, -1 ); 00241 p->timeSop += clock() - clk; 00242 00243 // get the factored form 00244 clk = clock(); 00245 pFForm = Dec_Factor( pSop ); 00246 free( pSop ); 00247 p->timeFact += clock() - clk; 00248 00249 // mark the fanin boundary 00250 // (can mark only essential fanins, belonging to bNodeFunc!) 00251 Vec_PtrForEachEntry( vFanins, pFanin, i ) 00252 pFanin->vFanouts.nSize++; 00253 // label MFFC with current traversal ID 00254 Abc_NtkIncrementTravId( pNode->pNtk ); 00255 nNodesSaved = Abc_NodeMffcLabelAig( pNode ); 00256 // unmark the fanin boundary and set the fanins as leaves in the form 00257 Vec_PtrForEachEntry( vFanins, pFanin, i ) 00258 { 00259 pFanin->vFanouts.nSize--; 00260 Dec_GraphNode(pFForm, i)->pFunc = pFanin; 00261 } 00262 00263 // detect how many new nodes will be added (while taking into account reused nodes) 00264 clk = clock(); 00265 nNodesAdded = Dec_GraphToNetworkCount( pNode, pFForm, nNodesSaved, Required ); 00266 p->timeEval += clock() - clk; 00267 // quit if there is no improvement 00268 if ( nNodesAdded == -1 || nNodesAdded == nNodesSaved && !fUseZeros ) 00269 { 00270 Cudd_RecursiveDeref( p->dd, bNodeFunc ); 00271 Dec_GraphFree( pFForm ); 00272 return NULL; 00273 } 00274 00275 // compute the total gain in the number of nodes 00276 p->nLastGain = nNodesSaved - nNodesAdded; 00277 p->nNodesGained += p->nLastGain; 00278 p->nNodesRefactored++; 00279 00280 // report the progress 00281 if ( fVeryVerbose ) 00282 { 00283 printf( "Node %6s : ", Abc_ObjName(pNode) ); 00284 printf( "Cone = %2d. ", vFanins->nSize ); 00285 printf( "BDD = %2d. ", Cudd_DagSize(bNodeFunc) ); 00286 printf( "FF = %2d. ", 1 + Dec_GraphNodeNum(pFForm) ); 00287 printf( "MFFC = %2d. ", nNodesSaved ); 00288 printf( "Add = %2d. ", nNodesAdded ); 00289 printf( "GAIN = %2d. ", p->nLastGain ); 00290 printf( "\n" ); 00291 } 00292 Cudd_RecursiveDeref( p->dd, bNodeFunc ); 00293 return pFForm; 00294 }
void Abc_NtkManRefPrintStats | ( | Abc_ManRef_t * | p | ) | [static] |
Function*************************************************************
Synopsis [Stops the resynthesis manager.]
Description []
SideEffects []
SeeAlso []
Definition at line 357 of file abcRefactor.c.
00358 { 00359 printf( "Refactoring statistics:\n" ); 00360 printf( "Nodes considered = %8d.\n", p->nNodesConsidered ); 00361 printf( "Nodes refactored = %8d.\n", p->nNodesRefactored ); 00362 printf( "Gain = %8d. (%6.2f %%).\n", p->nNodesBeg-p->nNodesEnd, 100.0*(p->nNodesBeg-p->nNodesEnd)/p->nNodesBeg ); 00363 PRT( "Cuts ", p->timeCut ); 00364 PRT( "Resynthesis", p->timeRes ); 00365 PRT( " BDD ", p->timeBdd ); 00366 PRT( " DCs ", p->timeDcs ); 00367 PRT( " SOP ", p->timeSop ); 00368 PRT( " FF ", p->timeFact ); 00369 PRT( " Eval ", p->timeEval ); 00370 PRT( "AIG update ", p->timeNtk ); 00371 PRT( "TOTAL ", p->timeTotal ); 00372 }
Abc_ManRef_t * Abc_NtkManRefStart | ( | int | nNodeSizeMax, | |
int | nConeSizeMax, | |||
bool | fUseDcs, | |||
bool | fVerbose | |||
) | [static] |
Function*************************************************************
Synopsis [Starts the resynthesis manager.]
Description []
SideEffects []
SeeAlso []
Definition at line 308 of file abcRefactor.c.
00309 { 00310 Abc_ManRef_t * p; 00311 p = ALLOC( Abc_ManRef_t, 1 ); 00312 memset( p, 0, sizeof(Abc_ManRef_t) ); 00313 p->vCube = Vec_StrAlloc( 100 ); 00314 p->vVisited = Vec_PtrAlloc( 100 ); 00315 p->nNodeSizeMax = nNodeSizeMax; 00316 p->nConeSizeMax = nConeSizeMax; 00317 p->fVerbose = fVerbose; 00318 // start the BDD manager 00319 if ( fUseDcs ) 00320 p->dd = Cudd_Init( p->nNodeSizeMax + p->nConeSizeMax, 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0 ); 00321 else 00322 p->dd = Cudd_Init( p->nNodeSizeMax, 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0 ); 00323 Cudd_zddVarsFromBddVars( p->dd, 2 ); 00324 return p; 00325 }
void Abc_NtkManRefStop | ( | Abc_ManRef_t * | p | ) | [static] |
Function*************************************************************
Synopsis [Stops the resynthesis manager.]
Description []
SideEffects []
SeeAlso []
Definition at line 338 of file abcRefactor.c.
00339 { 00340 Extra_StopManager( p->dd ); 00341 Vec_PtrFree( p->vVisited ); 00342 Vec_StrFree( p->vCube ); 00343 free( p ); 00344 }
int Abc_NtkRefactor | ( | Abc_Ntk_t * | pNtk, | |
int | nNodeSizeMax, | |||
int | nConeSizeMax, | |||
bool | fUpdateLevel, | |||
bool | fUseZeros, | |||
bool | fUseDcs, | |||
bool | fVerbose | |||
) |
FUNCTION DEFINITIONS ///Function*************************************************************
Synopsis [Performs incremental resynthesis of the AIG.]
Description [Starting from each node, computes a reconvergence-driven cut, derives BDD of the cut function, constructs ISOP, factors the ISOP, and replaces the current implementation of the MFFC of the node by the new factored form, if the number of AIG nodes is reduced and the total number of levels of the AIG network is not increated. Returns the number of AIG nodes saved.]
SideEffects []
SeeAlso []
Definition at line 85 of file abcRefactor.c.
00086 { 00087 ProgressBar * pProgress; 00088 Abc_ManRef_t * pManRef; 00089 Abc_ManCut_t * pManCut; 00090 Dec_Graph_t * pFForm; 00091 Vec_Ptr_t * vFanins; 00092 Abc_Obj_t * pNode; 00093 int clk, clkStart = clock(); 00094 int i, nNodes; 00095 00096 assert( Abc_NtkIsStrash(pNtk) ); 00097 // cleanup the AIG 00098 Abc_AigCleanup(pNtk->pManFunc); 00099 // start the managers 00100 pManCut = Abc_NtkManCutStart( nNodeSizeMax, nConeSizeMax, 2, 1000 ); 00101 pManRef = Abc_NtkManRefStart( nNodeSizeMax, nConeSizeMax, fUseDcs, fVerbose ); 00102 pManRef->vLeaves = Abc_NtkManCutReadCutLarge( pManCut ); 00103 // compute the reverse levels if level update is requested 00104 if ( fUpdateLevel ) 00105 Abc_NtkStartReverseLevels( pNtk, 0 ); 00106 00107 // resynthesize each node once 00108 pManRef->nNodesBeg = Abc_NtkNodeNum(pNtk); 00109 nNodes = Abc_NtkObjNumMax(pNtk); 00110 pProgress = Extra_ProgressBarStart( stdout, nNodes ); 00111 Abc_NtkForEachNode( pNtk, pNode, i ) 00112 { 00113 Extra_ProgressBarUpdate( pProgress, i, NULL ); 00114 // skip the constant node 00115 // if ( Abc_NodeIsConst(pNode) ) 00116 // continue; 00117 // skip persistant nodes 00118 if ( Abc_NodeIsPersistant(pNode) ) 00119 continue; 00120 // skip the nodes with many fanouts 00121 if ( Abc_ObjFanoutNum(pNode) > 1000 ) 00122 continue; 00123 // stop if all nodes have been tried once 00124 if ( i >= nNodes ) 00125 break; 00126 // compute a reconvergence-driven cut 00127 clk = clock(); 00128 vFanins = Abc_NodeFindCut( pManCut, pNode, fUseDcs ); 00129 pManRef->timeCut += clock() - clk; 00130 // evaluate this cut 00131 clk = clock(); 00132 pFForm = Abc_NodeRefactor( pManRef, pNode, vFanins, fUpdateLevel, fUseZeros, fUseDcs, fVerbose ); 00133 pManRef->timeRes += clock() - clk; 00134 if ( pFForm == NULL ) 00135 continue; 00136 // acceptable replacement found, update the graph 00137 clk = clock(); 00138 Dec_GraphUpdateNetwork( pNode, pFForm, fUpdateLevel, pManRef->nLastGain ); 00139 pManRef->timeNtk += clock() - clk; 00140 Dec_GraphFree( pFForm ); 00141 // { 00142 // extern int s_TotalChanges; 00143 // s_TotalChanges++; 00144 // } 00145 } 00146 Extra_ProgressBarStop( pProgress ); 00147 pManRef->timeTotal = clock() - clkStart; 00148 pManRef->nNodesEnd = Abc_NtkNodeNum(pNtk); 00149 00150 // print statistics of the manager 00151 if ( fVerbose ) 00152 Abc_NtkManRefPrintStats( pManRef ); 00153 // delete the managers 00154 Abc_NtkManCutStop( pManCut ); 00155 Abc_NtkManRefStop( pManRef ); 00156 // put the nodes into the DFS order and reassign their IDs 00157 Abc_NtkReassignIds( pNtk ); 00158 // Abc_AigCheckFaninOrder( pNtk->pManFunc ); 00159 // fix the levels 00160 if ( fUpdateLevel ) 00161 Abc_NtkStopReverseLevels( pNtk ); 00162 else 00163 Abc_NtkLevel( pNtk ); 00164 // check 00165 if ( !Abc_NtkCheck( pNtk ) ) 00166 { 00167 printf( "Abc_NtkRefactor: The network check has failed.\n" ); 00168 return 0; 00169 } 00170 return 1; 00171 }