From 8576e4b4400da0a652b120dfcf7ba8e966e576aa Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Tue, 6 Aug 2013 22:51:39 -0700 Subject: Improvements to buffering and sizing. --- src/base/abc/abc.h | 1 + src/base/abc/abcNtk.c | 7 + src/map/scl/scl.c | 17 +- src/map/scl/sclBuffer.c | 23 ++- src/map/scl/sclLib.c | 31 ++-- src/map/scl/sclLib.h | 2 + src/map/scl/sclLoad.c | 19 ++- src/map/scl/sclSize.c | 12 +- src/map/scl/sclSize.h | 30 ++++ src/map/scl/sclUpsize.c | 404 ++++++++++++++++++++++++++++++++++++++++++++++-- 10 files changed, 510 insertions(+), 36 deletions(-) diff --git a/src/base/abc/abc.h b/src/base/abc/abc.h index a9178f38..d5f55b64 100644 --- a/src/base/abc/abc.h +++ b/src/base/abc/abc.h @@ -205,6 +205,7 @@ struct Abc_Ntk_t_ void * pData; // misc Abc_Ntk_t * pCopy; // copy of this network Vec_Int_t * vPhases; // fanins phases in the mapped netlist + char * pWLoadUsed; // wire load model used float * pLutTimes; // arrivals/requireds/slacks using LUT-delay model Vec_Ptr_t * vOnehots; // names of one-hot-encoded registers Vec_Int_t * vObjPerm; // permutation saved diff --git a/src/base/abc/abcNtk.c b/src/base/abc/abcNtk.c index 1c85efc8..39a3c9af 100644 --- a/src/base/abc/abcNtk.c +++ b/src/base/abc/abcNtk.c @@ -325,6 +325,8 @@ void Abc_NtkFinalize( Abc_Ntk_t * pNtk, Abc_Ntk_t * pNtkNew ) Abc_NtkTimeInitialize( pNtkNew, pNtk ); if ( pNtk->vPhases ) Abc_NtkTransferPhases( pNtkNew, pNtk ); + if ( pNtk->pWLoadUsed ) + pNtkNew->pWLoadUsed = Abc_UtilStrsav( pNtk->pWLoadUsed ); } /**Function************************************************************* @@ -482,6 +484,8 @@ Abc_Ntk_t * Abc_NtkDup( Abc_Ntk_t * pNtk ) Abc_NtkTimeInitialize( pNtkNew, pNtk ); if ( pNtk->vPhases ) Abc_NtkTransferPhases( pNtkNew, pNtk ); + if ( pNtk->pWLoadUsed ) + pNtkNew->pWLoadUsed = Abc_UtilStrsav( pNtk->pWLoadUsed ); // check correctness if ( !Abc_NtkCheck( pNtkNew ) ) fprintf( stdout, "Abc_NtkDup(): Network check has failed.\n" ); @@ -520,6 +524,8 @@ Abc_Ntk_t * Abc_NtkDupDfs( Abc_Ntk_t * pNtk ) Abc_NtkTimeInitialize( pNtkNew, pNtk ); if ( pNtk->vPhases ) Abc_NtkTransferPhases( pNtkNew, pNtk ); + if ( pNtk->pWLoadUsed ) + pNtkNew->pWLoadUsed = Abc_UtilStrsav( pNtk->pWLoadUsed ); // check correctness if ( !Abc_NtkCheck( pNtkNew ) ) fprintf( stdout, "Abc_NtkDup(): Network check has failed.\n" ); @@ -1346,6 +1352,7 @@ void Abc_NtkDelete( Abc_Ntk_t * pNtk ) Vec_AttFree( (Vec_Att_t *)pAttrMan, 1 ); } Vec_PtrFree( pNtk->vAttrs ); + ABC_FREE( pNtk->pWLoadUsed ); ABC_FREE( pNtk->pName ); ABC_FREE( pNtk->pSpec ); ABC_FREE( pNtk->pLutTimes ); diff --git a/src/map/scl/scl.c b/src/map/scl/scl.c index e2b3d1ce..1e47dba3 100644 --- a/src/map/scl/scl.c +++ b/src/map/scl/scl.c @@ -904,13 +904,14 @@ int Scl_CommandUpsize( Abc_Frame_t * pAbc, int argc, char **argv ) pPars->DelayGap = 0; pPars->TimeOut = 0; pPars->BuffTreeEst = 0; + pPars->BypassFreq = 0; pPars->fUseDept = 1; pPars->fUseWireLoads = 1; pPars->fDumpStats = 0; pPars->fVerbose = 0; pPars->fVeryVerbose = 0; Extra_UtilGetoptReset(); - while ( ( c = Extra_UtilGetopt( argc, argv, "IJWRNDGTXcsdvwh" ) ) != EOF ) + while ( ( c = Extra_UtilGetopt( argc, argv, "IJWRNDGTXBcsdvwh" ) ) != EOF ) { switch ( c ) { @@ -1011,6 +1012,17 @@ int Scl_CommandUpsize( Abc_Frame_t * pAbc, int argc, char **argv ) if ( pPars->BuffTreeEst < 0 ) goto usage; break; + case 'B': + if ( globalUtilOptind >= argc ) + { + Abc_Print( -1, "Command line switch \"-B\" should be followed by a positive integer.\n" ); + goto usage; + } + pPars->BypassFreq = atoi(argv[globalUtilOptind]); + globalUtilOptind++; + if ( pPars->BypassFreq < 0 ) + goto usage; + break; case 'c': pPars->fUseWireLoads ^= 1; break; @@ -1058,7 +1070,7 @@ int Scl_CommandUpsize( Abc_Frame_t * pAbc, int argc, char **argv ) return 0; usage: - fprintf( pAbc->Err, "usage: upsize [-IJWRNDGTX num] [-csdvwh]\n" ); + fprintf( pAbc->Err, "usage: upsize [-IJWRNDGTXB num] [-csdvwh]\n" ); fprintf( pAbc->Err, "\t selectively increases gate sizes on the critical path\n" ); fprintf( pAbc->Err, "\t-I : the number of upsizing iterations to perform [default = %d]\n", pPars->nIters ); fprintf( pAbc->Err, "\t-J : the number of iterations without improvement to stop [default = %d]\n", pPars->nIterNoChange ); @@ -1069,6 +1081,7 @@ usage: fprintf( pAbc->Err, "\t-G : delay gap during updating, in picoseconds [default = %d]\n", pPars->DelayGap ); fprintf( pAbc->Err, "\t-T : approximate timeout in seconds [default = %d]\n", pPars->TimeOut ); fprintf( pAbc->Err, "\t-X : ratio for buffer tree estimation [default = %d]\n", pPars->BuffTreeEst ); + fprintf( pAbc->Err, "\t-B : frequency of bypass transforms [default = %d]\n", pPars->BypassFreq ); fprintf( pAbc->Err, "\t-c : toggle using wire-loads if specified [default = %s]\n", pPars->fUseWireLoads? "yes": "no" ); fprintf( pAbc->Err, "\t-s : toggle using slack based on departure times [default = %s]\n", pPars->fUseDept? "yes": "no" ); fprintf( pAbc->Err, "\t-d : toggle dumping statistics into a file [default = %s]\n", pPars->fDumpStats? "yes": "no" ); diff --git a/src/map/scl/sclBuffer.c b/src/map/scl/sclBuffer.c index 83a305bd..e9060f7b 100644 --- a/src/map/scl/sclBuffer.c +++ b/src/map/scl/sclBuffer.c @@ -113,7 +113,7 @@ static inline int Abc_SclObjIsBufInv( Abc_Obj_t * pObj ) { return Abc_ObjIsNode(pObj) && Abc_ObjFaninNum(pObj) == 1; } -static inline int Abc_SclIsInv( Abc_Obj_t * pObj ) +int Abc_SclIsInv( Abc_Obj_t * pObj ) { assert( Abc_ObjIsNode(pObj) ); return Mio_GateReadTruth((Mio_Gate_t *)pObj->pData) == ABC_CONST(0x5555555555555555); @@ -315,7 +315,7 @@ int Abc_SclCheckNtk( Abc_Ntk_t * p, int fVerbose ) SeeAlso [] ***********************************************************************/ -void Abc_NodeInvUpdateFanPolarity( Abc_Obj_t * pObj ) +void Abc_NodeInvUpdateFanPolarity( Abc_Obj_t * pObj, int fVerbose ) { Abc_Obj_t * pFanout; int i; @@ -323,12 +323,23 @@ void Abc_NodeInvUpdateFanPolarity( Abc_Obj_t * pObj ) Abc_ObjForEachFanout( pObj, pFanout, i ) { if ( Abc_SclObjIsBufInv(pFanout) ) - Abc_NodeInvUpdateFanPolarity( pFanout ); + Abc_NodeInvUpdateFanPolarity( pFanout, fVerbose ); else + { Abc_ObjFaninFlipPhase( pFanout, Abc_NodeFindFanin(pFanout, pObj) ); +// if ( fVerbose ) +// printf( "Flipping fanin %d of node %d.\n", Abc_NodeFindFanin(pFanout, pObj), Abc_ObjId(pFanout) ); + } } } - +void Abc_NodeInvUpdateObjFanoutPolarity( Abc_Obj_t * pObj, Abc_Obj_t * pFanout ) +{ + if ( Abc_SclObjIsBufInv(pFanout) ) + Abc_NodeInvUpdateFanPolarity( pFanout, 1 ); + else + Abc_ObjFaninFlipPhase( pFanout, Abc_NodeFindFanin(pFanout, pObj) ); +// printf( "\n" ); +} int Abc_NodeCompareLevels( Abc_Obj_t ** pp1, Abc_Obj_t ** pp2 ) { int Diff = Abc_ObjLevel(*pp1) - Abc_ObjLevel(*pp2); @@ -402,7 +413,7 @@ Abc_Obj_t * Abc_SclPerformBufferingOne( Abc_Obj_t * pObj, int Degree, int fUseIn Abc_ObjAddFanin( pBuffer, pObj ); pBuffer->Level = Abc_SclComputeReverseLevel( pBuffer ); if ( fUseInvs ) - Abc_NodeInvUpdateFanPolarity( pBuffer ); + Abc_NodeInvUpdateFanPolarity( pBuffer, 0 ); return pBuffer; } void Abc_SclPerformBuffering_rec( Abc_Obj_t * pObj, int DegreeR, int Degree, int fUseInvs, int fVerbose ) @@ -440,7 +451,7 @@ void Abc_SclPerformBuffering_rec( Abc_Obj_t * pObj, int DegreeR, int Degree, int Abc_ObjAddFanin( pBuffer, pObj ); pBuffer->Level = Abc_SclComputeReverseLevel( pBuffer ); if ( fUseInvs ) - Abc_NodeInvUpdateFanPolarity( pBuffer ); + Abc_NodeInvUpdateFanPolarity( pBuffer, 0 ); } // compute the new level of the node pObj->Level = Abc_SclComputeReverseLevel( pObj ); diff --git a/src/map/scl/sclLib.c b/src/map/scl/sclLib.c index 099350c8..d3ac29df 100644 --- a/src/map/scl/sclLib.c +++ b/src/map/scl/sclLib.c @@ -807,9 +807,25 @@ void Abc_SclLinkCells( SC_Lib * p ) SeeAlso [] ***********************************************************************/ -SC_WireLoad * Abc_SclFindWireLoadModel( SC_Lib * p, float Area ) +SC_WireLoad * Abc_SclFetchWireLoadModel( SC_Lib * p, char * pWLoadUsed ) { SC_WireLoad * pWL = NULL; + int i; + // Get the actual table and reformat it for 'wire_cap' output: + assert( pWLoadUsed != NULL ); + SC_LibForEachWireLoad( p, pWL, i ) + if ( !strcmp(pWL->pName, pWLoadUsed) ) + break; + if ( i == Vec_PtrSize(p->vWireLoads) ) + { + Abc_Print( -1, "Cannot find wire load model \"%s\".\n", pWLoadUsed ); + exit(1); + } +// printf( "Using wireload model \"%s\".\n", pWL->pName ); + return pWL; +} +SC_WireLoad * Abc_SclFindWireLoadModel( SC_Lib * p, float Area ) +{ char * pWLoadUsed = NULL; int i; if ( p->default_wire_load_sel && strlen(p->default_wire_load_sel) ) @@ -839,18 +855,7 @@ SC_WireLoad * Abc_SclFindWireLoadModel( SC_Lib * p, float Area ) Abc_Print( 0, "No wire model given.\n" ); return NULL; } - // Get the actual table and reformat it for 'wire_cap' output: - assert( pWLoadUsed != NULL ); - SC_LibForEachWireLoad( p, pWL, i ) - if ( !strcmp(pWL->pName, pWLoadUsed) ) - break; - if ( i == Vec_PtrSize(p->vWireLoads) ) - { - Abc_Print( -1, "Cannot find wire load model \"%s\".\n", pWLoadUsed ); - exit(1); - } -// printf( "Using wireload model \"%s\".\n", pWL->pName ); - return pWL; + return Abc_SclFetchWireLoadModel( p, pWLoadUsed ); } /**Function************************************************************* diff --git a/src/map/scl/sclLib.h b/src/map/scl/sclLib.h index 146d75ca..5084997e 100644 --- a/src/map/scl/sclLib.h +++ b/src/map/scl/sclLib.h @@ -71,6 +71,7 @@ struct SC_SizePars_ int DelayGap; int TimeOut; int BuffTreeEst; // ratio for buffer tree estimation + int BypassFreq; // frequency to try bypassing int fUseDept; int fDumpStats; int fUseWireLoads; @@ -550,6 +551,7 @@ extern int Abc_SclClassCellNum( SC_Cell * pClass ); extern void Abc_SclLinkCells( SC_Lib * p ); extern void Abc_SclPrintCells( SC_Lib * p, float Slew, float Gain ); extern SC_WireLoad * Abc_SclFindWireLoadModel( SC_Lib * p, float Area ); +extern SC_WireLoad * Abc_SclFetchWireLoadModel( SC_Lib * p, char * pName ); extern void Abc_SclDumpGenlib( char * pFileName, SC_Lib * p, float Slew, float Gain, int nGatesMin ); ABC_NAMESPACE_HEADER_END diff --git a/src/map/scl/sclLoad.c b/src/map/scl/sclLoad.c index 3cbb34ef..7ea13db2 100644 --- a/src/map/scl/sclLoad.c +++ b/src/map/scl/sclLoad.c @@ -37,7 +37,7 @@ ABC_NAMESPACE_IMPL_START Description [] - SideEffects [] + SideEffects []` SeeAlso [] @@ -187,6 +187,23 @@ void Abc_SclUpdateLoad( SC_Man * p, Abc_Obj_t * pObj, SC_Cell * pOld, SC_Cell * pLoad->fall += pPinNew->fall_cap - pPinOld->fall_cap; } } +void Abc_SclUpdateLoadSplit( SC_Man * p, Abc_Obj_t * pBuffer, Abc_Obj_t * pFanout ) +{ + SC_Pin * pPin; + SC_Pair * pLoad; + int iFanin = Abc_NodeFindFanin( pFanout, pBuffer ); + assert( iFanin >= 0 ); + assert( Abc_ObjFaninNum(pBuffer) == 1 ); + pPin = SC_CellPin( Abc_SclObjCell(p, pFanout), iFanin ); + // update load of the buffer + pLoad = Abc_SclObjLoad( p, pBuffer ); + pLoad->rise -= pPin->rise_cap; + pLoad->fall -= pPin->fall_cap; + // update load of the fanin + pLoad = Abc_SclObjLoad( p, Abc_ObjFanin0(pBuffer) ); + pLoad->rise += pPin->rise_cap; + pLoad->fall += pPin->fall_cap; +} //////////////////////////////////////////////////////////////////////// /// END OF FILE /// diff --git a/src/map/scl/sclSize.c b/src/map/scl/sclSize.c index 86c81589..18c520c3 100644 --- a/src/map/scl/sclSize.c +++ b/src/map/scl/sclSize.c @@ -419,7 +419,7 @@ void Abc_SclManReadSlewAndLoad( SC_Man * p, Abc_Ntk_t * pNtk ) } } } - + /**Function************************************************************* Synopsis [Prepare timing manager.] @@ -443,7 +443,15 @@ SC_Man * Abc_SclManStart( SC_Lib * pLib, Abc_Ntk_t * pNtk, int fUseWireLoads, in p->vGates = Abc_SclManFindGates( pLib, pNtk ); Abc_SclManReadSlewAndLoad( p, pNtk ); if ( fUseWireLoads ) - p->pWLoadUsed = Abc_SclFindWireLoadModel( pLib, Abc_SclGetTotalArea(p) ); + { + if ( pNtk->pWLoadUsed == NULL ) + { + p->pWLoadUsed = Abc_SclFindWireLoadModel( pLib, Abc_SclGetTotalArea(p) ); + pNtk->pWLoadUsed = Abc_UtilStrsav( p->pWLoadUsed->pName ); + } + else + p->pWLoadUsed = Abc_SclFetchWireLoadModel( pLib, pNtk->pWLoadUsed ); + } Abc_SclTimeNtkRecompute( p, &p->SumArea0, &p->MaxDelay0, fDept, DUser ); p->SumArea = p->SumArea0; return p; diff --git a/src/map/scl/sclSize.h b/src/map/scl/sclSize.h index 9656b55a..1f97bc8a 100644 --- a/src/map/scl/sclSize.h +++ b/src/map/scl/sclSize.h @@ -50,9 +50,11 @@ struct SC_Man_ Vec_Int_t * vGates; // mapping of objId into gateId Vec_Int_t * vGatesBest; // best gate sizes found so far Vec_Int_t * vUpdates; // sizing updates in this round + Vec_Int_t * vUpdates2; // sizing updates in this round // timing information SC_Pair * pLoads; // loads for each gate SC_Pair * pLoads2; // loads for each gate + SC_Pair * pLoads3; // loads for each gate SC_Pair * pDepts; // departures for each gate SC_Pair * pTimes; // arrivals for each gate SC_Pair * pSlews; // slews for each gate @@ -60,6 +62,7 @@ struct SC_Man_ SC_Pair * pSlews2; // slews for each gate float * pSlack; // slacks for each gatt float * pInDrive; // maximum input drive strength + Vec_Int_t * vBestFans; // best fanouts Vec_Flt_t * vTimesOut; // output arrival times Vec_Que_t * vQue; // outputs by their time SC_WireLoad * pWLoadUsed; // name of the used WireLoad model @@ -101,6 +104,7 @@ static inline void Abc_SclObjSetCell( SC_Man * p, Abc_Obj_t * pObj, SC_Cell static inline SC_Pair * Abc_SclObjLoad( SC_Man * p, Abc_Obj_t * pObj ) { return p->pLoads + Abc_ObjId(pObj); } static inline SC_Pair * Abc_SclObjLoad2( SC_Man * p, Abc_Obj_t * pObj ) { return p->pLoads2 + Abc_ObjId(pObj); } +static inline SC_Pair * Abc_SclObjLoad3( SC_Man * p, Abc_Obj_t * pObj ) { return p->pLoads3 + Abc_ObjId(pObj); } static inline SC_Pair * Abc_SclObjDept( SC_Man * p, Abc_Obj_t * pObj ) { return p->pDepts + Abc_ObjId(pObj); } static inline SC_Pair * Abc_SclObjTime( SC_Man * p, Abc_Obj_t * pObj ) { return p->pTimes + Abc_ObjId(pObj); } static inline SC_Pair * Abc_SclObjSlew( SC_Man * p, Abc_Obj_t * pObj ) { return p->pSlews + Abc_ObjId(pObj); } @@ -150,18 +154,21 @@ static inline SC_Man * Abc_SclManAlloc( SC_Lib * pLib, Abc_Ntk_t * pNtk ) p->nObjs = Abc_NtkObjNumMax(pNtk); p->pLoads = ABC_CALLOC( SC_Pair, p->nObjs ); p->pLoads2 = ABC_CALLOC( SC_Pair, p->nObjs ); + p->pLoads3 = ABC_CALLOC( SC_Pair, p->nObjs ); p->pDepts = ABC_CALLOC( SC_Pair, p->nObjs ); p->pTimes = ABC_CALLOC( SC_Pair, p->nObjs ); p->pSlews = ABC_CALLOC( SC_Pair, p->nObjs ); p->pTimes2 = ABC_CALLOC( SC_Pair, p->nObjs ); p->pSlews2 = ABC_CALLOC( SC_Pair, p->nObjs ); p->pSlack = ABC_FALLOC( float, p->nObjs ); + p->vBestFans = Vec_IntStart( p->nObjs ); p->vTimesOut = Vec_FltStart( Abc_NtkCoNum(pNtk) ); p->vQue = Vec_QueAlloc( Abc_NtkCoNum(pNtk) ); Vec_QueSetCosts( p->vQue, Vec_FltArrayP(p->vTimesOut) ); for ( i = 0; i < Abc_NtkCoNum(pNtk); i++ ) Vec_QuePush( p->vQue, i ); p->vUpdates = Vec_IntAlloc( 1000 ); + p->vUpdates2 = Vec_IntAlloc( 1000 ); // intermediate data p->vNode2Gain = Vec_FltStart( p->nObjs ); p->vNode2Gate = Vec_IntStart( p->nObjs ); @@ -178,14 +185,17 @@ static inline void Abc_SclManFree( SC_Man * p ) Vec_IntFreeP( &p->vNode2Gate ); // intermediate data Vec_IntFreeP( &p->vUpdates ); + Vec_IntFreeP( &p->vUpdates2 ); Vec_IntFreeP( &p->vGatesBest ); // Vec_QuePrint( p->vQue ); Vec_QueCheck( p->vQue ); Vec_QueFreeP( &p->vQue ); Vec_FltFreeP( &p->vTimesOut ); Vec_IntFreeP( &p->vGates ); + Vec_IntFreeP( &p->vBestFans ); ABC_FREE( p->pLoads ); ABC_FREE( p->pLoads2 ); + ABC_FREE( p->pLoads3 ); ABC_FREE( p->pDepts ); ABC_FREE( p->pTimes ); ABC_FREE( p->pSlews ); @@ -289,6 +299,23 @@ static inline void Abc_SclLoadRestore( SC_Man * p, Abc_Obj_t * pObj ) *Abc_SclObjLoad(p, pFanin) = *Abc_SclObjLoad2(p, pFanin); } +static inline void Abc_SclLoadStore3( SC_Man * p, Abc_Obj_t * pObj ) +{ + Abc_Obj_t * pFanin; + int i; + *Abc_SclObjLoad3(p, pObj) = *Abc_SclObjLoad(p, pObj); + Abc_ObjForEachFanin( pObj, pFanin, i ) + *Abc_SclObjLoad3(p, pFanin) = *Abc_SclObjLoad(p, pFanin); +} +static inline void Abc_SclLoadRestore3( SC_Man * p, Abc_Obj_t * pObj ) +{ + Abc_Obj_t * pFanin; + int i; + *Abc_SclObjLoad(p, pObj) = *Abc_SclObjLoad3(p, pObj); + Abc_ObjForEachFanin( pObj, pFanin, i ) + *Abc_SclObjLoad(p, pFanin) = *Abc_SclObjLoad3(p, pFanin); +} + /**Function************************************************************* Synopsis [] @@ -394,6 +421,8 @@ static inline void Abc_SclDumpStats( SC_Man * p, char * pFileName, abctime Time /*=== sclBuffer.c ===============================================================*/ +extern int Abc_SclIsInv( Abc_Obj_t * pObj ); +extern void Abc_NodeInvUpdateObjFanoutPolarity( Abc_Obj_t * pObj, Abc_Obj_t * pFanout ); extern Abc_Ntk_t * Abc_SclUnBufferPerform( Abc_Ntk_t * pNtk, int fVerbose ); extern Abc_Ntk_t * Abc_SclUnBufferPhase( Abc_Ntk_t * pNtk, int fVerbose ); extern Abc_Ntk_t * Abc_SclBufferPhase( Abc_Ntk_t * pNtk, int fVerbose ); @@ -405,6 +434,7 @@ extern void Abc_SclDnsizePerform( SC_Lib * pLib, Abc_Ntk_t * pNtk, SC_S /*=== sclLoad.c ===============================================================*/ extern void Abc_SclComputeLoad( SC_Man * p ); extern void Abc_SclUpdateLoad( SC_Man * p, Abc_Obj_t * pObj, SC_Cell * pOld, SC_Cell * pNew ); +extern void Abc_SclUpdateLoadSplit( SC_Man * p, Abc_Obj_t * pBuffer, Abc_Obj_t * pFanout ); /*=== sclSize.c ===============================================================*/ extern Abc_Obj_t * Abc_SclFindCriticalCo( SC_Man * p, int * pfRise ); extern Abc_Obj_t * Abc_SclFindMostCriticalFanin( SC_Man * p, int * pfRise, Abc_Obj_t * pNode ); diff --git a/src/map/scl/sclUpsize.c b/src/map/scl/sclUpsize.c index 75911278..5891fb55 100644 --- a/src/map/scl/sclUpsize.c +++ b/src/map/scl/sclUpsize.c @@ -252,13 +252,290 @@ void Abc_SclFindNodesToUpdate( Abc_Obj_t * pPivot, Vec_Int_t ** pvNodes, Vec_Int SeeAlso [] ***********************************************************************/ -int Abc_SclFindUpsizes( SC_Man * p, Vec_Int_t * vPathNodes, int Ratio, int Notches, int iIter, int DelayGap ) +int Abc_SclFindBypasses( SC_Man * p, Vec_Int_t * vPathNodes, int Ratio, int Notches, int iIter, int DelayGap, int fVeryVerbose ) { SC_Cell * pCellOld, * pCellNew; + Vec_Ptr_t * vFanouts; Vec_Int_t * vRecalcs, * vEvals; + Abc_Obj_t * pObj, * pTemp, * pBuffer, * pFanout; + float dGain, dGainBest, dGainBest2; + int i, j, k, n, gateBest, gateBest2, fanBest, Counter = 0; + + // compute savings due to bypassing buffers + vFanouts = Vec_PtrAlloc( 100 ); + vRecalcs = Vec_IntAlloc( 100 ); + vEvals = Vec_IntAlloc( 100 ); + Vec_QueClear( p->vNodeByGain ); + Abc_NtkForEachObjVec( vPathNodes, p->pNtk, pBuffer, i ) + { + assert( pBuffer->fMarkC == 0 ); + if ( Abc_ObjFaninNum(pBuffer) != 1 ) + continue; + pObj = Abc_ObjFanin0(pBuffer); + if ( !Abc_ObjIsNode(pObj) ) + continue; + // here we have pBuffer and its fanin pObj, which is a logic node + + // compute nodes to recalculate timing and nodes to evaluate afterwards + Abc_SclFindNodesToUpdate( pObj, &vRecalcs, &vEvals ); + assert( Vec_IntSize(vEvals) > 0 ); + //printf( "%d -> %d\n", Vec_IntSize(vRecalcs), Vec_IntSize(vEvals) ); + + // consider fanouts of this node + fanBest = -1; + gateBest2 = -1; + dGainBest2 = 0; + Abc_NodeCollectFanouts( pBuffer, vFanouts ); + Vec_PtrForEachEntry( Abc_Obj_t *, vFanouts, pFanout, j ) + { + // skip COs + if ( Abc_ObjIsCo(pFanout) ) + continue; + // skip non-critical fanouts + if ( !pFanout->fMarkA ) + continue; + // skip if fanin already has fanout as a fanout + if ( Abc_NodeFindFanin(pFanout, pObj) >= 0 ) + continue; + // prepare + Abc_SclLoadStore3( p, pBuffer ); + Abc_SclUpdateLoadSplit( p, pBuffer, pFanout ); + Abc_ObjPatchFanin( pFanout, pBuffer, pObj ); + // size the fanin + // save old gate, timing, fanin load + pCellOld = Abc_SclObjCell( p, pObj ); + Abc_SclConeStore( p, vRecalcs ); + Abc_SclLoadStore( p, pObj ); + // try different gate sizes for the fanin + gateBest = -1; + dGainBest = -SC_LibTimeFromPs(p->pLib, (float)DelayGap); + SC_RingForEachCell( pCellOld, pCellNew, k ) + { + if ( pCellNew == pCellOld ) + continue; + if ( k > Notches ) + break; + if ( p->pInDrive && !Abc_SclInputDriveOk( p, pObj, pCellNew ) ) + continue; + // set new cell + Abc_SclObjSetCell( p, pObj, pCellNew ); + Abc_SclUpdateLoad( p, pObj, pCellOld, pCellNew ); + // recompute timing + Abc_SclTimeCone( p, vRecalcs ); + // set old cell + Abc_SclObjSetCell( p, pObj, pCellOld ); + Abc_SclLoadRestore( p, pObj ); + // evaluate gain + dGain = 0.0; + Abc_NtkForEachObjVec( vEvals, p->pNtk, pTemp, n ) + dGain += Abc_SclObjGain( p, pTemp ); + dGain /= Vec_IntSize(vEvals); + // save best gain + if ( dGainBest < dGain ) + { + dGainBest = dGain; + gateBest = pCellNew->Id; + } + } + // put back old cell and timing + Abc_SclObjSetCell( p, pObj, pCellOld ); + Abc_SclConeRestore( p, vRecalcs ); + + // compare gain + if ( dGainBest2 < dGainBest ) + { + dGainBest2 = dGainBest; + gateBest2 = gateBest; + fanBest = Abc_ObjId(pFanout); + } + + Abc_SclLoadRestore3( p, pBuffer ); + Abc_ObjPatchFanin( pFanout, pObj, pBuffer ); + } + + // remember savings + if ( gateBest2 >= 0 ) + { + assert( dGainBest2 > 0.0 ); + Vec_FltWriteEntry( p->vNode2Gain, Abc_ObjId(pBuffer), dGainBest2 ); + Vec_IntWriteEntry( p->vNode2Gate, Abc_ObjId(pBuffer), gateBest2 ); + Vec_QuePush( p->vNodeByGain, Abc_ObjId(pBuffer) ); + Vec_IntWriteEntry( p->vBestFans, Abc_ObjId(pBuffer), fanBest ); + } + + if ( ++Counter == 17 ) + break; + + } + Vec_PtrFree( vFanouts ); + Vec_IntFree( vRecalcs ); + Vec_IntFree( vEvals ); + if ( Vec_QueSize(p->vNodeByGain) == 0 ) + return 0; + + // accept changes for that are half above the average and do not overlap + Counter = 0; + dGainBest2 = -1; + vFanouts = Vec_PtrAlloc( 100 ); + while ( Vec_QueSize(p->vNodeByGain) ) + { + int iNode = Vec_QuePop(p->vNodeByGain); + Abc_Obj_t * pObj = Abc_NtkObj( p->pNtk, iNode ); + Abc_Obj_t * pFanout = Abc_NtkObj( p->pNtk, Vec_IntEntry(p->vBestFans, iNode) ); + Abc_Obj_t * pFanin = Abc_ObjFanin0(pObj); + if ( pObj->fMarkC || pFanout->fMarkC || pFanin->fMarkC ) + continue; + pObj->fMarkC = 1; + pFanout->fMarkC = 1; + pFanin->fMarkC = 1; + Vec_PtrPush( vFanouts, pObj ); + Vec_PtrPush( vFanouts, pFanout ); + Vec_PtrPush( vFanouts, pFanin ); + // remember gain + if ( dGainBest2 == -1 ) + dGainBest2 = Vec_FltEntry(p->vNode2Gain, iNode); + else if ( dGainBest2 > 2*Vec_FltEntry(p->vNode2Gain, iNode) ) + break; + // redirect + Abc_ObjPatchFanin( pFanout, pObj, pFanin ); + // remember + Vec_IntPush( p->vUpdates2, Abc_ObjId(pFanout) ); + Vec_IntPush( p->vUpdates2, Abc_ObjId(pFanin) ); + Vec_IntPush( p->vUpdates2, Abc_ObjId(pObj) ); + // find old and new gates + pCellOld = Abc_SclObjCell( p, pFanin ); + pCellNew = SC_LibCell( p->pLib, Vec_IntEntry(p->vNode2Gate, iNode) ); + // update cell + p->SumArea += pCellNew->area - pCellOld->area; + Abc_SclObjSetCell( p, pFanin, pCellNew ); + // record the update + Vec_IntPush( p->vUpdates, Abc_ObjId(pFanin) ); + Vec_IntPush( p->vUpdates, pCellNew->Id ); + // remember when this node was upsized + Vec_IntWriteEntry( p->vNodeIter, Abc_ObjId(pFanout), 0 ); + Vec_IntWriteEntry( p->vNodeIter, Abc_ObjId(pFanin), 0 ); + Vec_IntWriteEntry( p->vNodeIter, Abc_ObjId(pObj), 0 ); + // update polarity + if ( p->pNtk->vPhases && Abc_SclIsInv(pObj) ) + Abc_NodeInvUpdateObjFanoutPolarity( pFanin, pFanout ); + // report + if ( fVeryVerbose ) + printf( "Node %6d Redir fanout %6d to fanin %6d. Gain = %7.1f ps. Replacing gate %12s by gate %12s.\n", + Abc_ObjId(pObj), Abc_ObjId(pFanout), Abc_ObjId(pFanin), + Vec_FltEntry(p->vNode2Gain, iNode), pCellOld->pName, pCellNew->pName ); +/* + // check if the node became useless + if ( Abc_ObjFanoutNum(pObj) == 0 ) + { + pCellOld = Abc_SclObjCell( p, pObj ); + p->SumArea -= pCellOld->area; + Abc_NtkDeleteObj_rec( pObj, 1 ); + printf( "Removed node %d.\n", iNode ); + } +*/ + Counter++; + } + Vec_PtrForEachEntry( Abc_Obj_t *, vFanouts, pFanout, j ) + pFanout->fMarkC = 0; + Vec_PtrFree( vFanouts ); + +/* + Limit = Abc_MinInt( Vec_QueSize(p->vNodeByGain), Abc_MaxInt((int)(0.01 * Ratio * Vec_IntSize(vPathNodes)), 1) ); + //printf( "\nSelecting %d out of %d\n", Limit, Vec_QueSize(p->vNodeByGain) ); + for ( i = 0; i < Limit; i++ ) + { + // get the object + pObj = Abc_NtkObj( p->pNtk, Vec_QuePop(p->vNodeByGain) ); + assert( pObj->fMarkA ); + // find old and new gates + pCellOld = Abc_SclObjCell( p, pObj ); + pCellNew = SC_LibCell( p->pLib, Vec_IntEntry(p->vNode2Gate, Abc_ObjId(pObj)) ); + assert( pCellNew != NULL ); + //printf( "%6d %20s -> %20s ", Abc_ObjId(pObj), pCellOld->pName, pCellNew->pName ); + //printf( "gain is %f\n", Vec_FltEntry(p->vNode2Gain, Abc_ObjId(pObj)) ); + // update gate + Abc_SclUpdateLoad( p, pObj, pCellOld, pCellNew ); + p->SumArea += pCellNew->area - pCellOld->area; + Abc_SclObjSetCell( p, pObj, pCellNew ); + // record the update + Vec_IntPush( p->vUpdates, Abc_ObjId(pObj) ); + Vec_IntPush( p->vUpdates, pCellNew->Id ); + // remember when this node was upsized + Vec_IntWriteEntry( p->vNodeIter, Abc_ObjId(pObj), iIter ); + } +*/ + return Counter; +} + +/**Function************************************************************* + + Synopsis [Check marked fanin/fanouts.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_SclObjCheckMarkedFanFans( Abc_Obj_t * pObj ) +{ + Abc_Obj_t * pNext; + int i; + if ( pObj->fMarkC ) + return 1; + Abc_ObjForEachFanin( pObj, pNext, i ) + if ( pNext->fMarkC ) + return 1; + Abc_ObjForEachFanout( pObj, pNext, i ) + if ( pNext->fMarkC ) + return 1; + return 0; +} +void Abc_SclObjMarkFanFans( Abc_Obj_t * pObj, Vec_Ptr_t * vNodes ) +{ +// Abc_Obj_t * pNext; +// int i; + if ( pObj->fMarkC == 0 ) + { + Vec_PtrPush( vNodes, pObj ); + pObj->fMarkC = 1; + } +/* + Abc_ObjForEachFanin( pObj, pNext, i ) + if ( pNext->fMarkC == 0 ) + { + Vec_PtrPush( vNodes, pNext ); + pNext->fMarkC = 1; + } + Abc_ObjForEachFanout( pObj, pNext, i ) + if ( pNext->fMarkC == 0 ) + { + Vec_PtrPush( vNodes, pNext ); + pNext->fMarkC = 1; + } +*/ +} + +/**Function************************************************************* + + Synopsis [Computes the set of gates to upsize.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_SclFindUpsizes( SC_Man * p, Vec_Int_t * vPathNodes, int Ratio, int Notches, int iIter, int DelayGap, int fMoreConserf ) +{ + SC_Cell * pCellOld, * pCellNew; + Vec_Int_t * vRecalcs, * vEvals; + Vec_Ptr_t * vFanouts; Abc_Obj_t * pObj, * pTemp; - float dGain, dGainBest; - int i, k, n, gateBest, Limit, iIterLast; + float dGain, dGainBest, dGainBest2; + int i, k, n, gateBest, Limit, Counter, iIterLast; // compute savings due to upsizing each node vRecalcs = Vec_IntAlloc( 100 ); @@ -266,6 +543,7 @@ int Abc_SclFindUpsizes( SC_Man * p, Vec_Int_t * vPathNodes, int Ratio, int Notch Vec_QueClear( p->vNodeByGain ); Abc_NtkForEachObjVec( vPathNodes, p->pNtk, pObj, i ) { + assert( pObj->fMarkC == 0 ); iIterLast = Vec_IntEntry(p->vNodeIter, Abc_ObjId(pObj)); if ( iIterLast >= 0 && iIterLast + 5 > iIter ) continue; @@ -308,6 +586,9 @@ int Abc_SclFindUpsizes( SC_Man * p, Vec_Int_t * vPathNodes, int Ratio, int Notch gateBest = pCellNew->Id; } } + // put back old cell and timing + Abc_SclObjSetCell( p, pObj, pCellOld ); + Abc_SclConeRestore( p, vRecalcs ); // remember savings if ( gateBest >= 0 ) { @@ -316,15 +597,12 @@ int Abc_SclFindUpsizes( SC_Man * p, Vec_Int_t * vPathNodes, int Ratio, int Notch Vec_IntWriteEntry( p->vNode2Gate, Abc_ObjId(pObj), gateBest ); Vec_QuePush( p->vNodeByGain, Abc_ObjId(pObj) ); } - // put back old cell and timing - Abc_SclObjSetCell( p, pObj, pCellOld ); - Abc_SclConeRestore( p, vRecalcs ); } Vec_IntFree( vRecalcs ); Vec_IntFree( vEvals ); if ( Vec_QueSize(p->vNodeByGain) == 0 ) return 0; - +/* Limit = Abc_MinInt( Vec_QueSize(p->vNodeByGain), Abc_MaxInt((int)(0.01 * Ratio * Vec_IntSize(vPathNodes)), 1) ); //printf( "\nSelecting %d out of %d\n", Limit, Vec_QueSize(p->vNodeByGain) ); for ( i = 0; i < Limit; i++ ) @@ -348,18 +626,85 @@ int Abc_SclFindUpsizes( SC_Man * p, Vec_Int_t * vPathNodes, int Ratio, int Notch // remember when this node was upsized Vec_IntWriteEntry( p->vNodeIter, Abc_ObjId(pObj), iIter ); } - return Limit; +return Limit; +*/ + + Limit = Abc_MinInt( Vec_QueSize(p->vNodeByGain), Abc_MaxInt((int)(0.01 * Ratio * Vec_IntSize(vPathNodes)), 1) ); + dGainBest2 = -1; + Counter = 0; + vFanouts = Vec_PtrAlloc( 100 ); + while ( Vec_QueSize(p->vNodeByGain) ) + { + int iNode = Vec_QuePop(p->vNodeByGain); + Abc_Obj_t * pObj = Abc_NtkObj( p->pNtk, iNode ); + assert( pObj->fMarkA ); + if ( Abc_SclObjCheckMarkedFanFans( pObj ) ) + continue; + Abc_SclObjMarkFanFans( pObj, vFanouts ); + // remember gain + if ( dGainBest2 == -1 ) + dGainBest2 = Vec_FltEntry(p->vNode2Gain, iNode); +// else if ( dGainBest2 > (fMoreConserf ? 1.5 : 3)*Vec_FltEntry(p->vNode2Gain, iNode) ) + else if ( dGainBest2 > 3*Vec_FltEntry(p->vNode2Gain, iNode) ) + break; +// printf( "%.1f ", Vec_FltEntry(p->vNode2Gain, iNode) ); + + // find old and new gates + pCellOld = Abc_SclObjCell( p, pObj ); + pCellNew = SC_LibCell( p->pLib, Vec_IntEntry(p->vNode2Gate, Abc_ObjId(pObj)) ); + assert( pCellNew != NULL ); + //printf( "%6d %20s -> %20s ", Abc_ObjId(pObj), pCellOld->pName, pCellNew->pName ); + //printf( "gain is %f\n", Vec_FltEntry(p->vNode2Gain, Abc_ObjId(pObj)) ); + // update gate + Abc_SclUpdateLoad( p, pObj, pCellOld, pCellNew ); + p->SumArea += pCellNew->area - pCellOld->area; + Abc_SclObjSetCell( p, pObj, pCellNew ); + // record the update + Vec_IntPush( p->vUpdates, Abc_ObjId(pObj) ); + Vec_IntPush( p->vUpdates, pCellNew->Id ); + // remember when this node was upsized + Vec_IntWriteEntry( p->vNodeIter, Abc_ObjId(pObj), iIter ); + Counter++; + if ( Counter == Limit ) + break; + } +// printf( "\n" ); + + Vec_PtrForEachEntry( Abc_Obj_t *, vFanouts, pObj, i ) + pObj->fMarkC = 0; + Vec_PtrFree( vFanouts ); + return Counter; } -void Abc_SclApplyUpdateToBest( Vec_Int_t * vGates, Vec_Int_t * vGatesBest, Vec_Int_t * vUpdate ) +void Abc_SclApplyUpdateToBest( Vec_Int_t * vGatesBest, Vec_Int_t * vGates, Vec_Int_t * vUpdate ) { int i, ObjId, GateId, GateId2; Vec_IntForEachEntryDouble( vUpdate, ObjId, GateId, i ) Vec_IntWriteEntry( vGatesBest, ObjId, GateId ); Vec_IntClear( vUpdate ); - Vec_IntForEachEntryTwo( vGates, vGatesBest, GateId, GateId2, i ) + Vec_IntForEachEntryTwo( vGatesBest, vGates, GateId, GateId2, i ) assert( GateId == GateId2 ); +// Vec_IntClear( vGatesBest ); +// Vec_IntAppend( vGatesBest, vGates ); } +void Abc_SclUndoRecentChanges( Abc_Ntk_t * pNtk, Vec_Int_t * vTrans ) +{ + int i; + assert( Vec_IntSize(vTrans) % 3 == 0 ); + for ( i = Vec_IntSize(vTrans)/3 - 1; i >= 0; i-- ) + { + Abc_Obj_t * pFanout = Abc_NtkObj( pNtk, Vec_IntEntry(vTrans, 3*i+0) ); + Abc_Obj_t * pFanin = Abc_NtkObj( pNtk, Vec_IntEntry(vTrans, 3*i+1) ); + Abc_Obj_t * pObj = Abc_NtkObj( pNtk, Vec_IntEntry(vTrans, 3*i+2) ); + Abc_ObjPatchFanin( pFanout, pFanin, pObj ); +// printf( "Node %6d Redir fanout %6d from fanin %6d. \n", +// Abc_ObjId(pObj), Abc_ObjId(pFanout), Abc_ObjId(pFanin) ); + + // update polarity + if ( pNtk->vPhases && Abc_SclIsInv(pObj) ) + Abc_NodeInvUpdateObjFanoutPolarity( pObj, pFanout ); + } +} /**Function************************************************************* @@ -452,6 +797,33 @@ void Abc_SclUpsizePrint( SC_Man * p, int Iter, int win, int nPathPos, int nPathN printf( "%c", fVerbose ? '\n' : '\r' ); } +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_SclUpsizeRemoveDangling( SC_Man * p, Abc_Ntk_t * pNtk ) +{ + SC_Cell * pCell; + Abc_Obj_t * pObj; + int i; + Abc_NtkForEachNode( pNtk, pObj, i ) + if ( Abc_ObjFanoutNum(pObj) == 0 ) + { + pCell = Abc_SclObjCell( p, pObj ); + p->SumArea -= pCell->area; + Abc_NtkDeleteObj_rec( pObj, 1 ); + printf( "Removed node %d.\n", i ); + } + +} + /**Function************************************************************* Synopsis [] @@ -511,7 +883,10 @@ void Abc_SclUpsizePerform( SC_Lib * pLib, Abc_Ntk_t * pNtk, SC_SizePars * pPars // selectively upsize the nodes clk = Abc_Clock(); - nUpsizes = Abc_SclFindUpsizes( p, vPathNodes, pPars->Ratio, pPars->Notches, i, pPars->DelayGap ); + if ( pPars->BypassFreq && i && (i % pPars->BypassFreq) == 0 ) + nUpsizes = Abc_SclFindBypasses( p, vPathNodes, pPars->Ratio, pPars->Notches, i, pPars->DelayGap, pPars->fVeryVerbose ); + else + nUpsizes = Abc_SclFindUpsizes( p, vPathNodes, pPars->Ratio, pPars->Notches, i, pPars->DelayGap, (pPars->BypassFreq > 0) ); p->timeSize += Abc_Clock() - clk; // unmark critical path @@ -547,7 +922,8 @@ void Abc_SclUpsizePerform( SC_Lib * pLib, Abc_Ntk_t * pNtk, SC_SizePars * pPars if ( p->BestDelay > p->MaxDelay ) { p->BestDelay = p->MaxDelay; - Abc_SclApplyUpdateToBest( p->vGates, p->vGatesBest, p->vUpdates ); + Abc_SclApplyUpdateToBest( p->vGatesBest, p->vGates, p->vUpdates ); + Vec_IntClear( p->vUpdates2 ); nFramesNoChange = 0; } else @@ -574,6 +950,10 @@ void Abc_SclUpsizePerform( SC_Lib * pLib, Abc_Ntk_t * pNtk, SC_SizePars * pPars } // update for best gates and recompute timing ABC_SWAP( Vec_Int_t *, p->vGatesBest, p->vGates ); + if ( pPars->BypassFreq != 0 ) + Abc_SclUndoRecentChanges( p->pNtk, p->vUpdates2 ); + if ( pPars->BypassFreq != 0 ) + Abc_SclUpsizeRemoveDangling( p, pNtk ); Abc_SclTimeNtkRecompute( p, &p->SumArea, &p->MaxDelay, 0, 0 ); if ( pPars->fVerbose ) Abc_SclUpsizePrint( p, i, pPars->Window, nAllPos/(i?i:1), nAllNodes/(i?i:1), nAllUpsizes/(i?i:1), nAllTfos/(i?i:1), 1 ); -- cgit v1.2.3