From 633db0f4ad4b4d2dc7a29d26eff752f1861eccdd Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Fri, 9 Aug 2013 17:54:18 -0700 Subject: Improvements to buffering and sizing. --- src/map/scl/scl.c | 2 +- src/map/scl/sclDnsize.c | 13 ++-- src/map/scl/sclLib.h | 11 +++- src/map/scl/sclLoad.c | 4 +- src/map/scl/sclSize.c | 167 ++++++++++++++++++++++++++++++++++++++++-------- src/map/scl/sclSize.h | 44 ++++++++----- src/map/scl/sclUpsize.c | 86 +++++++++++++++---------- 7 files changed, 242 insertions(+), 85 deletions(-) (limited to 'src/map/scl') diff --git a/src/map/scl/scl.c b/src/map/scl/scl.c index aa93136a..bf1424fe 100644 --- a/src/map/scl/scl.c +++ b/src/map/scl/scl.c @@ -1001,7 +1001,7 @@ int Scl_CommandUpsize( Abc_Frame_t * pAbc, int argc, char **argv ) memset( pPars, 0, sizeof(SC_SizePars) ); pPars->nIters = 1000; pPars->nIterNoChange = 50; - pPars->Window = 2; + pPars->Window = 1; pPars->Ratio = 10; pPars->Notches = 1000; pPars->DelayUser = 0; diff --git a/src/map/scl/sclDnsize.c b/src/map/scl/sclDnsize.c index e6e5e982..511659c1 100644 --- a/src/map/scl/sclDnsize.c +++ b/src/map/scl/sclDnsize.c @@ -121,7 +121,7 @@ clk = Abc_Clock(); continue; if ( i > Notches ) break; - if ( p->pInDrive && !Abc_SclInputDriveOk( p, pObj, pCellNew ) ) + if ( p->vInDrive && !Abc_SclInputDriveOk( p, pObj, pCellNew ) ) continue; // set new cell Abc_SclObjSetCell( pObj, pCellNew ); @@ -156,7 +156,9 @@ p->timeSize += Abc_Clock() - clk; // mark used nodes with the current trav ID Abc_NtkForEachObjVec( vNodes, p->pNtk, pTemp, k ) Abc_NodeSetTravIdCurrent( pTemp ); - // to need to update load and timing... + // update load and timing... + Abc_SclUpdateLoad( p, pObj, pCellOld, pCellNew ); + Abc_SclTimeIncInsert( p, pObj ); return 1; } return 0; @@ -223,7 +225,7 @@ void Abc_SclDnsizePrint( SC_Man * p, int Iter, int nAttempts, int nOverlaps, int printf( "D: " ); printf( "%.2f ps ", SC_LibTimePs(p->pLib, p->MaxDelay) ); printf( "(%+5.1f %%) ", 100.0 * (p->MaxDelay - p->MaxDelay0)/ p->MaxDelay0 ); - printf( "%8.2f sec", 1.0*(Abc_Clock() - p->timeTotal)/(CLOCKS_PER_SEC) ); + printf( "%8.2f sec ", 1.0*(Abc_Clock() - p->timeTotal)/(CLOCKS_PER_SEC) ); printf( "%c", fVerbose ? '\n' : '\r' ); } @@ -294,7 +296,10 @@ void Abc_SclDnsizePerform( SC_Lib * pLib, Abc_Ntk_t * pNtk, SC_SizePars * pPars Vec_QuePush( p->vNodeByGain, Abc_ObjId(pObj) ); clk = Abc_Clock(); - Abc_SclTimeNtkRecompute( p, &p->SumArea, &p->MaxDelay, pPars->fUseDept, pPars->DelayUser ); + if ( p->nIncUpdates ) + Abc_SclTimeIncUpdate( p ); + else + Abc_SclTimeNtkRecompute( p, &p->SumArea, &p->MaxDelay, pPars->fUseDept, pPars->DelayUser ); p->timeTime += Abc_Clock() - clk; p->MaxDelay = Abc_SclReadMaxDelay( p ); diff --git a/src/map/scl/sclLib.h b/src/map/scl/sclLib.h index fa80e1f0..ada96d40 100644 --- a/src/map/scl/sclLib.h +++ b/src/map/scl/sclLib.h @@ -210,6 +210,15 @@ struct SC_Lib_ /// MACRO DEFINITIONS /// //////////////////////////////////////////////////////////////////////// +static inline void SC_PairClean( SC_Pair * d ) { d->rise = d->fall = 0; } +static inline float SC_PairMax( SC_Pair * d ) { return Abc_MaxFloat(d->rise, d->fall); } +static inline float SC_PairMin( SC_Pair * d ) { return Abc_MinFloat(d->rise, d->fall); } +static inline float SC_PairAve( SC_Pair * d ) { return 0.5 * d->rise + 0.5 * d->fall; } +static inline void SC_PairDup( SC_Pair * d, SC_Pair * s ) { *d = *s; } +static inline void SC_PairMove( SC_Pair * d, SC_Pair * s ) { *d = *s; s->rise = s->fall = 0; } +static inline int SC_PairEqual( SC_Pair * d, SC_Pair * s ) { return d->rise == s->rise && d->fall == s->fall; } +static inline int SC_PairEqualE( SC_Pair * d, SC_Pair * s, float E ) { return d->rise - s->rise < E && s->rise - d->rise < E && d->fall - s->fall < E && s->fall - d->fall < E; } + static inline SC_Cell * SC_LibCell( SC_Lib * p, int i ) { return (SC_Cell *)Vec_PtrEntry(p->vCells, i); } static inline SC_Pin * SC_CellPin( SC_Cell * p, int i ) { return (SC_Pin *)Vec_PtrEntry(p->vPins, i); } static inline Vec_Wrd_t * SC_CellFunc( SC_Cell * p ) { return SC_CellPin(p, p->n_inputs)->vFunc; } @@ -223,8 +232,6 @@ static inline double SC_LibCapFromFf( SC_Lib * p, double cap ) { return cap static inline double SC_LibTimePs( SC_Lib * p, double time ) { return time * pow(10.0, 12 - p->unit_time); } static inline double SC_LibTimeFromPs( SC_Lib * p, double ps ) { return ps / pow(10.0, 12 - p->unit_time); } - - #define SC_LibForEachCell( p, pCell, i ) Vec_PtrForEachEntry( SC_Cell *, p->vCells, pCell, i ) #define SC_LibForEachCellClass( p, pCell, i ) Vec_PtrForEachEntry( SC_Cell *, p->vCellClasses, pCell, i ) #define SC_LibForEachWireLoad( p, pWL, i ) Vec_PtrForEachEntry( SC_WireLoad *, p->vWireLoads, pWL, i ) diff --git a/src/map/scl/sclLoad.c b/src/map/scl/sclLoad.c index 282fd7ee..10b5d8f1 100644 --- a/src/map/scl/sclLoad.c +++ b/src/map/scl/sclLoad.c @@ -132,12 +132,12 @@ void Abc_SclComputeLoad( SC_Man * p ) Vec_FltFree( vWireCaps ); } // check input loads - if ( p->pInDrive != NULL ) + if ( p->vInDrive != NULL ) { Abc_NtkForEachPi( p->pNtk, pObj, i ) { SC_Pair * pLoad = Abc_SclObjLoad( p, pObj ); - if ( p->pInDrive[Abc_ObjId(pObj)] != 0 && (pLoad->rise > p->pInDrive[Abc_ObjId(pObj)] || pLoad->fall > p->pInDrive[Abc_ObjId(pObj)]) ) + if ( Abc_SclObjInDrive(p, pObj) != 0 && (pLoad->rise > Abc_SclObjInDrive(p, pObj) || pLoad->fall > Abc_SclObjInDrive(p, pObj)) ) printf( "Maximum input drive strength is exceeded at primary input %d.\n", i ); } } diff --git a/src/map/scl/sclSize.c b/src/map/scl/sclSize.c index e95a7336..82d4fa39 100644 --- a/src/map/scl/sclSize.c +++ b/src/map/scl/sclSize.c @@ -82,9 +82,9 @@ Abc_Obj_t * Abc_SclFindMostCriticalFanin( SC_Man * p, int * pfRise, Abc_Obj_t * *pfRise = 0; // find min-slack node Abc_ObjForEachFanin( pNode, pFanin, i ) - if ( fMinSlack > Abc_SclObjSlack( p, pFanin ) ) + if ( fMinSlack > Abc_SclObjGetSlack( p, pFanin, p->MaxDelay0 ) ) { - fMinSlack = Abc_SclObjSlack( p, pFanin ); + fMinSlack = Abc_SclObjGetSlack( p, pFanin, p->MaxDelay0 ); pPivot = pFanin; } if ( pPivot == NULL ) @@ -122,7 +122,7 @@ static inline void Abc_SclTimeNodePrint( SC_Man * p, Abc_Obj_t * pObj, int fRise printf( "Cout =%5.0f ff ", Abc_SclObjLoadFf(p, pObj, fRise >= 0 ? fRise : 0 ) ); printf( "Cmax =%5.0f ff ", pCell ? SC_CellPin(pCell, pCell->n_inputs)->max_out_cap : 0.0 ); printf( "G =%5.1f ", pCell ? Abc_SclObjLoadAve(p, pObj) / SC_CellPinCap(pCell, 0) : 0.0 ); - printf( "SL =%5.1f ps", Abc_SclObjSlackPs(p, pObj) ); + printf( "SL =%5.1f ps", Abc_SclObjSlackPs(p, pObj, p->MaxDelay0) ); printf( "\n" ); } void Abc_SclTimeNtkPrint( SC_Man * p, int fShowAll, int fPrintPath ) @@ -207,14 +207,15 @@ static inline void Abc_SclDeptFanin( SC_Man * p, SC_Timing * pTime, Abc_Obj_t * } static inline void Abc_SclDeptObj( SC_Man * p, Abc_Obj_t * pObj ) { - SC_Cell * pCell; SC_Timing * pTime; Abc_Obj_t * pFanout; int i; - pCell = Abc_SclObjCell( pObj ); + SC_PairClean( Abc_SclObjDept(p, pObj) ); Abc_ObjForEachFanout( pObj, pFanout, i ) { - pTime = Scl_CellPinTime( pCell, Abc_NodeFindFanin(pFanout, pObj) ); + if ( Abc_ObjIsCo(pFanout) ) + continue; + pTime = Scl_CellPinTime( Abc_SclObjCell(pFanout), Abc_NodeFindFanin(pFanout, pObj) ); Abc_SclDeptFanin( p, pTime, pFanout, pObj ); } } @@ -238,7 +239,11 @@ void Abc_SclTimeNode( SC_Man * p, Abc_Obj_t * pObj, int fDept ) if ( Abc_ObjIsCo(pObj) ) { if ( !fDept ) + { Abc_SclObjDupFanin( p, pObj ); + Vec_FltWriteEntry( p->vTimesOut, pObj->iData, Abc_SclObjTimeMax(p, pObj) ); + Vec_QueUpdate( p->vQue, pObj->iData ); + } return; } assert( Abc_ObjIsNode(pObj) ); @@ -293,7 +298,7 @@ void Abc_SclTimeCone( SC_Man * p, Vec_Int_t * vCone ) int fVerbose = 0; Abc_Obj_t * pObj; int i; - Abc_SclConeClear( p, vCone ); + Abc_SclConeClean( p, vCone ); Abc_NtkForEachObjVec( vCone, p->pNtk, pObj, i ) { if ( fVerbose && Abc_ObjIsNode(pObj) ) @@ -316,11 +321,7 @@ void Abc_SclTimeNtkRecompute( SC_Man * p, float * pArea, float * pDelay, int fRe Abc_NtkForEachNode1( p->pNtk, pObj, i ) Abc_SclTimeNode( p, pObj, 0 ); Abc_NtkForEachCo( p->pNtk, pObj, i ) - { - Abc_SclObjDupFanin( p, pObj ); - Vec_FltWriteEntry( p->vTimesOut, i, Abc_SclObjTimeMax(p, pObj) ); - Vec_QueUpdate( p->vQue, i ); - } + Abc_SclTimeNode( p, pObj, 0 ); D = Abc_SclReadMaxDelay( p ); if ( fReverse && DUser > 0 && D < DUser ) D = DUser; @@ -333,14 +334,124 @@ void Abc_SclTimeNtkRecompute( SC_Man * p, float * pArea, float * pDelay, int fRe p->nEstNodes = 0; Abc_NtkForEachNodeReverse1( p->pNtk, pObj, i ) Abc_SclTimeNode( p, pObj, 1 ); - Abc_NtkForEachObj( p->pNtk, pObj, i ) + } +} + +/**Function************************************************************* + + Synopsis [Incremental timing update.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void Abc_SclTimeIncUpdateClean( SC_Man * p ) +{ + Vec_Int_t * vLevel; + Abc_Obj_t * pObj; + int i, k; + Vec_WecForEachLevel( p->vLevels, vLevel, i ) + { + Abc_NtkForEachObjVec( vLevel, p->pNtk, pObj, k ) { -// if ( Abc_SclObjGetSlack(p, pObj, D) < 0 ) -// printf( "%.2f ", Abc_SclObjGetSlack(p, pObj, D) ); - p->pSlack[i] = Abc_MaxFloat( 0.0, Abc_SclObjGetSlack(p, pObj, D) ); + assert( pObj->fMarkC == 1 ); + pObj->fMarkC = 0; } + Vec_IntClear( vLevel ); } } +static inline void Abc_SclTimeIncAddNode( SC_Man * p, Abc_Obj_t * pObj ) +{ + assert( pObj->fMarkC == 0 ); + pObj->fMarkC = 1; + Vec_IntPush( Vec_WecEntry(p->vLevels, Abc_ObjLevel(pObj)), Abc_ObjId(pObj) ); + p->nIncUpdates++; +} +static inline void Abc_SclTimeIncAddFanins( SC_Man * p, Abc_Obj_t * pObj ) +{ + Abc_Obj_t * pFanin; + int i; + Abc_ObjForEachFanin( pObj, pFanin, i ) + if ( !pFanin->fMarkC && Abc_ObjIsNode(pFanin) ) + Abc_SclTimeIncAddNode( p, pFanin ); +} +static inline void Abc_SclTimeIncAddFanouts( SC_Man * p, Abc_Obj_t * pObj ) +{ + Abc_Obj_t * pFanout; + int i; + Abc_ObjForEachFanout( pObj, pFanout, i ) + if ( !pFanout->fMarkC ) + Abc_SclTimeIncAddNode( p, pFanout ); +} +static inline void Abc_SclTimeIncUpdateArrival( SC_Man * p ) +{ + Vec_Int_t * vLevel; + SC_Pair ArrOut, SlewOut; + SC_Pair * pArrOut, *pSlewOut; + Abc_Obj_t * pObj; + float E = (float)0.1; + int i, k; + Vec_WecForEachLevel( p->vLevels, vLevel, i ) + { + Abc_NtkForEachObjVec( vLevel, p->pNtk, pObj, k ) + { + if ( Abc_ObjIsCo(pObj) ) + { + Abc_SclObjDupFanin( p, pObj ); + Vec_FltWriteEntry( p->vTimesOut, pObj->iData, Abc_SclObjTimeMax(p, pObj) ); + Vec_QueUpdate( p->vQue, pObj->iData ); + continue; + } + pArrOut = Abc_SclObjTime( p, pObj ); + pSlewOut = Abc_SclObjSlew( p, pObj ); + SC_PairMove( &ArrOut, pArrOut ); + SC_PairMove( &SlewOut, pSlewOut ); + Abc_SclTimeNode( p, pObj, 0 ); +// if ( !SC_PairEqual(&ArrOut, pArrOut) || !SC_PairEqual(&SlewOut, pSlewOut) ) + if ( !SC_PairEqualE(&ArrOut, pArrOut, E) || !SC_PairEqualE(&SlewOut, pSlewOut, E) ) + Abc_SclTimeIncAddFanouts( p, pObj ); + } + } + p->MaxDelay = Abc_SclReadMaxDelay( p ); +} +static inline void Abc_SclTimeIncUpdateDeparture( SC_Man * p ) +{ + Vec_Int_t * vLevel; + SC_Pair DepOut, * pDepOut; + Abc_Obj_t * pObj; + float E = (float)0.1; + int i, k; + Vec_WecForEachLevelReverse( p->vLevels, vLevel, i ) + { + Abc_NtkForEachObjVec( vLevel, p->pNtk, pObj, k ) + { + pDepOut = Abc_SclObjDept( p, pObj ); + SC_PairMove( &DepOut, pDepOut ); + Abc_SclDeptObj( p, pObj ); +// if ( !SC_PairEqual(&DepOut, pDepOut) ) + if ( !SC_PairEqualE(&DepOut, pDepOut, E) ) + Abc_SclTimeIncAddFanins( p, pObj ); + } + } + p->MaxDelay = Abc_SclReadMaxDelay( p ); +} +void Abc_SclTimeIncUpdate( SC_Man * p ) +{ + if ( p->nIncUpdates == 0 ) + return; + Abc_SclTimeIncUpdateArrival( p ); + Abc_SclTimeIncUpdateDeparture( p ); + Abc_SclTimeIncUpdateClean( p ); + p->nIncUpdates = 0; +} +void Abc_SclTimeIncInsert( SC_Man * p, Abc_Obj_t * pObj ) +{ + Abc_SclTimeIncAddFanins( p, pObj ); + Abc_SclTimeIncAddNode( p, pObj ); +} /**Function************************************************************* @@ -389,20 +500,20 @@ void Abc_SclManReadSlewAndLoad( SC_Man * p, Abc_Ntk_t * pNtk ) if ( Abc_MaxFloat(pTime->Rise, pTime->Fall) != 0 ) { printf( "Default input drive strength is specified (%.2f ff; %.2f ff).\n", pTime->Rise, pTime->Fall ); - if ( p->pInDrive == NULL ) - p->pInDrive = ABC_CALLOC( float, Abc_NtkObjNumMax(pNtk) ); + if ( p->vInDrive == NULL ) + p->vInDrive = Vec_FltStart( Abc_NtkCiNum(pNtk) ); Abc_NtkForEachPi( pNtk, pObj, i ) - p->pInDrive[Abc_ObjId(pObj)] = SC_LibCapFromFf( p->pLib, 0.5 * pTime->Rise + 0.5 * pTime->Fall ); + Abc_SclObjSetInDrive( p, pObj, SC_LibCapFromFf( p->pLib, 0.5 * pTime->Rise + 0.5 * pTime->Fall ) ); } if ( Abc_NodeReadInputDrive(pNtk, 0) != NULL ) { printf( "Input drive strengths for some primary inputs are specified.\n" ); - if ( p->pInDrive == NULL ) - p->pInDrive = ABC_CALLOC( float, Abc_NtkObjNumMax(pNtk) ); + if ( p->vInDrive == NULL ) + p->vInDrive = Vec_FltStart( Abc_NtkCiNum(pNtk) ); Abc_NtkForEachPi( pNtk, pObj, i ) { pTime = Abc_NodeReadInputDrive(pNtk, i); - p->pInDrive[Abc_ObjId(pObj)] = SC_LibCapFromFf( p->pLib, 0.5 * pTime->Rise + 0.5 * pTime->Fall ); + Abc_SclObjSetInDrive( p, pObj, SC_LibCapFromFf( p->pLib, 0.5 * pTime->Rise + 0.5 * pTime->Fall ) ); } } // read output load @@ -462,7 +573,8 @@ SC_Man * Abc_SclManStart( SC_Lib * pLib, Abc_Ntk_t * pNtk, int fUseWireLoads, in p->pWLoadUsed = Abc_SclFetchWireLoadModel( pLib, pNtk->pWLoadUsed ); } Abc_SclTimeNtkRecompute( p, &p->SumArea0, &p->MaxDelay0, fDept, DUser ); - p->SumArea = p->SumArea0; + p->SumArea = p->SumArea0; + p->MaxDelay = p->MaxDelay0; return p; } @@ -646,7 +758,7 @@ void Abc_SclPrintBuffersOne( SC_Man * p, Abc_Obj_t * pObj, int nOffset ) printf( "%6.0f ps) ", Abc_SclObjTimePs(p, pObj, 0) ); printf( "l =%5.0f ff ", Abc_SclObjLoadFf(p, pObj, 0 ) ); printf( "s =%5.0f ps ", Abc_SclObjSlewPs(p, pObj, 0 ) ); - printf( "sl =%5.0f ps ", Abc_SclObjSlackPs(p, pObj) ); + printf( "sl =%5.0f ps ", Abc_SclObjSlackPs(p, pObj, p->MaxDelay0) ); if ( nOffset == 0 ) { printf( "L =%5.0f ff ", SC_LibCapFf( p->pLib, Abc_SclCountNonBufferLoad(p, pObj) ) ); @@ -711,9 +823,8 @@ int Abc_SclInputDriveOk( SC_Man * p, Abc_Obj_t * pObj, SC_Cell * pCell ) int i; assert( Abc_ObjFaninNum(pObj) == pCell->n_inputs ); Abc_ObjForEachFanin( pObj, pFanin, i ) - if ( Abc_ObjIsPi(pFanin) && p->pInDrive[Abc_ObjId(pFanin)] > 0 && - (p->pInDrive[Abc_ObjId(pFanin)] / Abc_ObjFanoutNum(pFanin)) < - Abc_MaxFloat(SC_CellPin(pCell, i)->rise_cap, SC_CellPin(pCell, i)->fall_cap) ) + if ( Abc_ObjIsPi(pFanin) && Abc_SclObjInDrive(p, pFanin) > 0 && + (Abc_SclObjInDrive(p, pFanin) / Abc_ObjFanoutNum(pFanin)) < SC_CellPinCap( pCell, i ) ) return 0; return 1; } @@ -759,7 +870,7 @@ Vec_Wec_t * Abc_SclSelectSplitNodes( SC_Man * p, Abc_Ntk_t * pNtk ) Vec_IntClear( vCrits ); Vec_IntClear( vNonCrits ); Abc_ObjForEachFanout( pObj, pFanout, k ) - if ( Abc_SclObjSlack(p, pFanout) < 100 ) + if ( Abc_SclObjGetSlack(p, pFanout, p->MaxDelay0) < 100 ) Vec_IntPush( vCrits, Abc_ObjId(pFanout) ); else Vec_IntPush( vNonCrits, Abc_ObjId(pFanout) ); diff --git a/src/map/scl/sclSize.h b/src/map/scl/sclSize.h index b3835bf5..a01aac83 100644 --- a/src/map/scl/sclSize.h +++ b/src/map/scl/sclSize.h @@ -28,6 +28,7 @@ #include "base/abc/abc.h" #include "misc/vec/vecQue.h" +#include "misc/vec/vecWec.h" #include "sclLib.h" ABC_NAMESPACE_HEADER_START @@ -56,10 +57,9 @@ struct SC_Man_ SC_Pair * pDepts; // departures for each gate SC_Pair * pTimes; // arrivals for each gate SC_Pair * pSlews; // slews for each gate - float * pSlack; // slacks for each gatt - float * pInDrive; // maximum input drive strength - Vec_Que_t * vQue; // outputs by their time + Vec_Flt_t * vInDrive; // maximum input drive strength Vec_Flt_t * vTimesOut; // output arrival times + Vec_Que_t * vQue; // outputs by their time // backup information Vec_Flt_t * vLoads2; // backup storage for loads Vec_Flt_t * vLoads3; // backup storage for loads @@ -76,6 +76,9 @@ struct SC_Man_ Vec_Int_t * vNode2Gate; // mapping node into its best gate Vec_Int_t * vNodeIter; // the last iteration the node was upsized Vec_Int_t * vBestFans; // best fanouts + // incremental timing update + Vec_Wec_t * vLevels; + int nIncUpdates; // optimization parameters float SumArea; // total area float MaxDelay; // max delay @@ -111,16 +114,17 @@ static inline SC_Pair * Abc_SclObjSlew( SC_Man * p, Abc_Obj_t * pObj ) static inline float Abc_SclObjTimeMax( SC_Man * p, Abc_Obj_t * pObj ) { return Abc_MaxFloat(Abc_SclObjTime(p, pObj)->rise, Abc_SclObjTime(p, pObj)->fall); } static inline float Abc_SclObjDepthMax( SC_Man * p, Abc_Obj_t * pObj ) { return Abc_MaxFloat(Abc_SclObjDept(p, pObj)->rise, Abc_SclObjDept(p, pObj)->fall); } static inline float Abc_SclObjGetSlack( SC_Man * p, Abc_Obj_t * pObj, float D ) { return D - Abc_MaxFloat(Abc_SclObjTime(p, pObj)->rise + Abc_SclObjDept(p, pObj)->rise, Abc_SclObjTime(p, pObj)->fall + Abc_SclObjDept(p, pObj)->fall); } -static inline float Abc_SclObjGetSlackR( SC_Man * p, Abc_Obj_t * pObj, float D ){ return D - (Abc_SclObjTime(p, pObj)->rise + Abc_SclObjDept(p, pObj)->rise); } -static inline float Abc_SclObjGetSlackF( SC_Man * p, Abc_Obj_t * pObj, float D ){ return D - (Abc_SclObjTime(p, pObj)->fall + Abc_SclObjDept(p, pObj)->fall); } -static inline float Abc_SclObjSlack( SC_Man * p, Abc_Obj_t * pObj ) { return p->pSlack[Abc_ObjId(pObj)]; } -static inline float Abc_SclObjLoadAve( SC_Man * p, Abc_Obj_t * pObj ) { return 0.5 * Abc_SclObjLoad(p, pObj)->rise + 0.5 * Abc_SclObjLoad(p, pObj)->fall; } +static inline float Abc_SclObjGetSlackR( SC_Man * p, Abc_Obj_t * pObj, float D ){ return D - (Abc_SclObjTime(p, pObj)->rise + Abc_SclObjDept(p, pObj)->rise); } +static inline float Abc_SclObjGetSlackF( SC_Man * p, Abc_Obj_t * pObj, float D ){ return D - (Abc_SclObjTime(p, pObj)->fall + Abc_SclObjDept(p, pObj)->fall); } +static inline float Abc_SclObjLoadAve( SC_Man * p, Abc_Obj_t * pObj ) { return 0.5 * Abc_SclObjLoad(p, pObj)->rise + 0.5 * Abc_SclObjLoad(p, pObj)->fall; } static inline void Abc_SclObjDupFanin( SC_Man * p, Abc_Obj_t * pObj ) { assert( Abc_ObjIsCo(pObj) ); *Abc_SclObjTime(p, pObj) = *Abc_SclObjTime(p, Abc_ObjFanin0(pObj)); } +static inline float Abc_SclObjInDrive( SC_Man * p, Abc_Obj_t * pObj ) { return Vec_FltEntry( p->vInDrive, pObj->iData ); } +static inline void Abc_SclObjSetInDrive( SC_Man * p, Abc_Obj_t * pObj, float c){ Vec_FltWriteEntry( p->vInDrive, pObj->iData, c ); } static inline double Abc_SclObjLoadFf( SC_Man * p, Abc_Obj_t * pObj, int fRise ) { return SC_LibCapFf( p->pLib, fRise ? Abc_SclObjLoad(p, pObj)->rise : Abc_SclObjLoad(p, pObj)->fall); } static inline double Abc_SclObjTimePs( SC_Man * p, Abc_Obj_t * pObj, int fRise ) { return SC_LibTimePs(p->pLib, fRise ? Abc_SclObjTime(p, pObj)->rise : Abc_SclObjTime(p, pObj)->fall); } static inline double Abc_SclObjSlewPs( SC_Man * p, Abc_Obj_t * pObj, int fRise ) { return SC_LibTimePs(p->pLib, fRise ? Abc_SclObjSlew(p, pObj)->rise : Abc_SclObjSlew(p, pObj)->fall); } -static inline double Abc_SclObjSlackPs( SC_Man * p, Abc_Obj_t * pObj ) { return SC_LibTimePs(p->pLib, Abc_SclObjSlack(p, pObj)); } +static inline double Abc_SclObjSlackPs( SC_Man * p, Abc_Obj_t * pObj, float D ) { return SC_LibTimePs(p->pLib, Abc_SclObjGetSlack(p, pObj, D)); } //////////////////////////////////////////////////////////////////////// /// FUNCTION DEFINITIONS /// @@ -140,6 +144,7 @@ static inline double Abc_SclObjSlackPs( SC_Man * p, Abc_Obj_t * pObj ) static inline SC_Man * Abc_SclManAlloc( SC_Lib * pLib, Abc_Ntk_t * pNtk ) { SC_Man * p; + Abc_Obj_t * pObj; int i; assert( Abc_NtkHasMapping(pNtk) ); p = ABC_CALLOC( SC_Man, 1 ); @@ -150,7 +155,6 @@ static inline SC_Man * Abc_SclManAlloc( SC_Lib * pLib, Abc_Ntk_t * pNtk ) 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->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) ); @@ -169,6 +173,14 @@ static inline SC_Man * Abc_SclManAlloc( SC_Lib * pLib, Abc_Ntk_t * pNtk ) p->vNodeByGain = Vec_QueAlloc( p->nObjs ); Vec_QueSetCosts( p->vNodeByGain, Vec_FltArrayP(p->vNode2Gain) ); p->vNodeIter = Vec_IntStartFull( p->nObjs ); + p->vLevels = Vec_WecStart( 2 * Abc_NtkLevel(pNtk) ); + Abc_NtkForEachCo( pNtk, pObj, i ) + pObj->Level = Abc_ObjFanin0(pObj)->Level; + // set CI/CO ids + Abc_NtkForEachCi( pNtk, pObj, i ) + pObj->iData = i; + Abc_NtkForEachCo( pNtk, pObj, i ) + pObj->iData = i; return p; } static inline void Abc_SclManFree( SC_Man * p ) @@ -187,17 +199,17 @@ static inline void Abc_SclManFree( SC_Man * p ) Vec_IntFreeP( &p->vUpdates ); Vec_IntFreeP( &p->vUpdates2 ); Vec_IntFreeP( &p->vGatesBest ); + Vec_WecFreeP( &p->vLevels ); // Vec_QuePrint( p->vQue ); Vec_QueCheck( p->vQue ); Vec_QueFreeP( &p->vQue ); Vec_FltFreeP( &p->vTimesOut ); Vec_IntFreeP( &p->vBestFans ); + Vec_FltFreeP( &p->vInDrive ); ABC_FREE( p->pLoads ); ABC_FREE( p->pDepts ); ABC_FREE( p->pTimes ); ABC_FREE( p->pSlews ); - ABC_FREE( p->pSlack ); - ABC_FREE( p->pInDrive ); ABC_FREE( p ); } static inline void Abc_SclManCleanTime( SC_Man * p ) @@ -325,7 +337,7 @@ static inline void Abc_SclEvalStore( SC_Man * p, Vec_Int_t * vCone ) static inline float Abc_SclEvalPerform( SC_Man * p, Vec_Int_t * vCone ) { Abc_Obj_t * pObj; - float Diff, Multi = 2.0, Eval = 0; + float Diff, Multi = 1.5, Eval = 0; int i, k = 0; Abc_NtkForEachObjVec( vCone, p->pNtk, pObj, i ) { @@ -339,20 +351,20 @@ static inline float Abc_SclEvalPerform( SC_Man * p, Vec_Int_t * vCone ) static inline float Abc_SclEvalPerformLegal( SC_Man * p, Vec_Int_t * vCone, float D ) { Abc_Obj_t * pObj; - float Rise, Fall, Eval = 0; + float Rise, Fall, Multi = 1.0, Eval = 0; int i, k = 0; Abc_NtkForEachObjVec( vCone, p->pNtk, pObj, i ) { Rise = Vec_FltEntry(p->vTimes3, k++) - Abc_SclObjTime(p, pObj)->rise; Fall = Vec_FltEntry(p->vTimes3, k++) - Abc_SclObjTime(p, pObj)->fall; - if ( Rise + Abc_SclObjGetSlackR(p, pObj, D) < 0 || Fall + Abc_SclObjGetSlackF(p, pObj, D) < 0 ) + if ( Rise + Multi * Abc_SclObjGetSlackR(p, pObj, D) < 0 || Fall + Multi * Abc_SclObjGetSlackF(p, pObj, D) < 0 ) return -1; Eval += 0.5 * Rise + 0.5 * Fall; } assert( Vec_FltSize(p->vTimes3) == k ); return Eval / Vec_IntSize(vCone); } -static inline void Abc_SclConeClear( SC_Man * p, Vec_Int_t * vCone ) +static inline void Abc_SclConeClean( SC_Man * p, Vec_Int_t * vCone ) { SC_Pair Zero = { 0.0, 0.0 }; Abc_Obj_t * pObj; @@ -493,6 +505,8 @@ extern void Abc_SclTimeNtkPrint( SC_Man * p, int fShowAll, int fPrintPa extern SC_Man * Abc_SclManStart( SC_Lib * pLib, Abc_Ntk_t * pNtk, int fUseWireLoads, int fDept, float DUser, int nTreeCRatio ); extern void Abc_SclTimeCone( SC_Man * p, Vec_Int_t * vCone ); extern void Abc_SclTimeNtkRecompute( SC_Man * p, float * pArea, float * pDelay, int fReverse, float DUser ); +extern void Abc_SclTimeIncUpdate( SC_Man * p ); +extern void Abc_SclTimeIncInsert( SC_Man * p, Abc_Obj_t * pObj ); extern void Abc_SclTimePerform( SC_Lib * pLib, Abc_Ntk_t * pNtk, int nTreeCRatio, int fUseWireLoads, int fShowAll, int fPrintPath, int fDumpStats ); extern void Abc_SclPrintBuffers( SC_Lib * pLib, Abc_Ntk_t * pNtk, int fVerbose ); extern int Abc_SclInputDriveOk( SC_Man * p, Abc_Obj_t * pObj, SC_Cell * pCell ); diff --git a/src/map/scl/sclUpsize.c b/src/map/scl/sclUpsize.c index f706cc7a..a3294ebb 100644 --- a/src/map/scl/sclUpsize.c +++ b/src/map/scl/sclUpsize.c @@ -133,10 +133,12 @@ void Abc_SclFindCriticalNodeWindow_rec( SC_Man * p, Abc_Obj_t * pObj, Vec_Int_t assert( Abc_ObjIsNode(pObj) ); // compute the max arrival time of the fanins if ( fDept ) - fArrMax = p->pSlack[Abc_ObjId(pObj)]; +// fArrMax = p->pSlack[Abc_ObjId(pObj)]; + fArrMax = Abc_SclObjGetSlack(p, pObj, p->MaxDelay); else fArrMax = Abc_SclGetMaxDelayNodeFanins( p, pObj ); - assert( fArrMax >= 0 ); + assert( fArrMax >= -1 ); + fArrMax = Abc_MaxFloat( fArrMax, 0 ); // traverse all fanins whose arrival times are within a window Abc_ObjForEachFanin( pObj, pNext, i ) { @@ -144,7 +146,8 @@ void Abc_SclFindCriticalNodeWindow_rec( SC_Man * p, Abc_Obj_t * pObj, Vec_Int_t continue; assert( Abc_ObjIsNode(pNext) ); if ( fDept ) - fSlackFan = fSlack - (p->pSlack[Abc_ObjId(pNext)] - fArrMax); +// fSlackFan = fSlack - (p->pSlack[Abc_ObjId(pNext)] - fArrMax); + fSlackFan = fSlack - (Abc_SclObjGetSlack(p, pNext, p->MaxDelay) - fArrMax); else fSlackFan = fSlack - (fArrMax - Abc_SclObjTimeMax(p, pNext)); if ( fSlackFan >= 0 ) @@ -272,7 +275,7 @@ int Abc_SclFindBestCell( SC_Man * p, Abc_Obj_t * pObj, Vec_Int_t * vRecalcs, Vec { SC_Cell * pCellOld, * pCellNew; float dGain, dGainBest; - int k, gateBest; + int k, gateBest, NoChange = 0; // save old gate, timing, fanin load pCellOld = Abc_SclObjCell( pObj ); Abc_SclConeStore( p, vRecalcs ); @@ -287,7 +290,7 @@ int Abc_SclFindBestCell( SC_Man * p, Abc_Obj_t * pObj, Vec_Int_t * vRecalcs, Vec continue; if ( k > Notches ) break; - if ( p->pInDrive && !Abc_SclInputDriveOk( p, pObj, pCellNew ) ) + if ( p->vInDrive && !Abc_SclInputDriveOk( p, pObj, pCellNew ) ) continue; // set new cell Abc_SclObjSetCell( pObj, pCellNew ); @@ -303,8 +306,16 @@ int Abc_SclFindBestCell( SC_Man * p, Abc_Obj_t * pObj, Vec_Int_t * vRecalcs, Vec { dGainBest = dGain; gateBest = pCellNew->Id; + NoChange = 1; } + else if ( NoChange ) + NoChange++; + if ( NoChange == 4 ) + break; +// printf( "%.2f ", dGain ); } +// printf( "Best = %.2f ", dGainBest ); +// printf( "\n" ); // put back old cell and timing Abc_SclObjSetCell( pObj, pCellOld ); Abc_SclConeRestore( p, vRecalcs ); @@ -339,7 +350,7 @@ int Abc_SclFindBypasses( SC_Man * p, Vec_Int_t * vPathNodes, int Ratio, int Notc Vec_QueClear( p->vNodeByGain ); Abc_NtkForEachObjVec( vPathNodes, p->pNtk, pBuf, i ) { - assert( pBuf->fMarkC == 0 ); + assert( pBuf->fMarkB == 0 ); if ( Abc_ObjFaninNum(pBuf) != 1 ) continue; pFanin = Abc_ObjFanin0(pBuf); @@ -425,11 +436,12 @@ int Abc_SclFindBypasses( SC_Man * p, Vec_Int_t * vPathNodes, int Ratio, int Notc pFanout = Abc_NtkObj( p->pNtk, Vec_IntEntry(p->vBestFans, iNode) ); pBuf = Abc_NtkObj( p->pNtk, iNode ); pFanin = Abc_ObjFanin0(pBuf); - if ( pFanout->fMarkC || pBuf->fMarkC || pFanin->fMarkC ) + assert( p->pNtk->vPhases == NULL ); // problem! + if ( pFanout->fMarkB || pBuf->fMarkB || pFanin->fMarkB ) continue; - pFanout->fMarkC = 1; - pBuf->fMarkC = 1; - pFanin->fMarkC = 1; + pFanout->fMarkB = 1; + pBuf->fMarkB = 1; + pFanin->fMarkB = 1; Vec_PtrPush( vFanouts, pFanout ); Vec_PtrPush( vFanouts, pBuf ); Vec_PtrPush( vFanouts, pFanin ); @@ -450,9 +462,11 @@ int Abc_SclFindBypasses( SC_Man * p, Vec_Int_t * vPathNodes, int Ratio, int Notc // update cell p->SumArea += pCellNew->area - pCellOld->area; Abc_SclObjSetCell( pFanin, pCellNew ); + Abc_SclUpdateLoad( p, pFanin, pCellOld, pCellNew ); // record the update Vec_IntPush( p->vUpdates, Abc_ObjId(pFanin) ); Vec_IntPush( p->vUpdates, pCellNew->Id ); + Abc_SclTimeIncInsert( p, pFanin ); // remember when this node was upsized Vec_IntWriteEntry( p->vNodeIter, Abc_ObjId(pFanout), -1 ); Vec_IntWriteEntry( p->vNodeIter, Abc_ObjId(pBuf), -1 ); @@ -478,7 +492,7 @@ int Abc_SclFindBypasses( SC_Man * p, Vec_Int_t * vPathNodes, int Ratio, int Notc Counter++; } Vec_PtrForEachEntry( Abc_Obj_t *, vFanouts, pFanout, j ) - pFanout->fMarkC = 0; + pFanout->fMarkB = 0; Vec_PtrFree( vFanouts ); return Counter; } @@ -498,13 +512,13 @@ int Abc_SclObjCheckMarkedFanFans( Abc_Obj_t * pObj ) { Abc_Obj_t * pNext; int i; - if ( pObj->fMarkC ) + if ( pObj->fMarkB ) return 1; Abc_ObjForEachFanin( pObj, pNext, i ) - if ( pNext->fMarkC ) + if ( pNext->fMarkB ) return 1; Abc_ObjForEachFanout( pObj, pNext, i ) - if ( pNext->fMarkC ) + if ( pNext->fMarkB ) return 1; return 0; } @@ -512,23 +526,23 @@ void Abc_SclObjMarkFanFans( Abc_Obj_t * pObj, Vec_Ptr_t * vNodes ) { // Abc_Obj_t * pNext; // int i; - if ( pObj->fMarkC == 0 ) + if ( pObj->fMarkB == 0 ) { Vec_PtrPush( vNodes, pObj ); - pObj->fMarkC = 1; + pObj->fMarkB = 1; } /* Abc_ObjForEachFanin( pObj, pNext, i ) - if ( pNext->fMarkC == 0 ) + if ( pNext->fMarkB == 0 ) { Vec_PtrPush( vNodes, pNext ); - pNext->fMarkC = 1; + pNext->fMarkB = 1; } Abc_ObjForEachFanout( pObj, pNext, i ) - if ( pNext->fMarkC == 0 ) + if ( pNext->fMarkB == 0 ) { Vec_PtrPush( vNodes, pNext ); - pNext->fMarkC = 1; + pNext->fMarkB = 1; } */ } @@ -559,7 +573,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 ); + assert( pObj->fMarkB == 0 ); iIterLast = Vec_IntEntry(p->vNodeIter, Abc_ObjId(pObj)); if ( iIterLast >= 0 && iIterLast + 5 > iIter ) continue; @@ -598,10 +612,11 @@ int Abc_SclFindUpsizes( SC_Man * p, Vec_Int_t * vPathNodes, int Ratio, int Notch // update gate Abc_SclUpdateLoad( p, pObj, pCellOld, pCellNew ); p->SumArea += pCellNew->area - pCellOld->area; - Abc_SclObjSetCell( p, pObj, pCellNew ); + Abc_SclObjSetCell( pObj, pCellNew ); // record the update Vec_IntPush( p->vUpdates, Abc_ObjId(pObj) ); Vec_IntPush( p->vUpdates, pCellNew->Id ); + Abc_SclTimeIncInsert( p, pObj ); // remember when this node was upsized Vec_IntWriteEntry( p->vNodeIter, Abc_ObjId(pObj), iIter ); } @@ -623,9 +638,8 @@ return Limit; // 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; +// else if ( dGainBest2 > 3*Vec_FltEntry(p->vNode2Gain, iNode) ) +// break; // printf( "%.1f ", Vec_FltEntry(p->vNode2Gain, iNode) ); // find old and new gates @@ -634,13 +648,16 @@ return Limit; 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)) ); +// if ( pCellOld->Order > 0 ) +// printf( "%.2f %d -> %d(%d) ", Vec_FltEntry(p->vNode2Gain, iNode), pCellOld->Order, pCellNew->Order, pCellNew->nGates ); // update gate - Abc_SclUpdateLoad( p, pObj, pCellOld, pCellNew ); p->SumArea += pCellNew->area - pCellOld->area; Abc_SclObjSetCell( pObj, pCellNew ); + Abc_SclUpdateLoad( p, pObj, pCellOld, pCellNew ); // record the update Vec_IntPush( p->vUpdates, Abc_ObjId(pObj) ); Vec_IntPush( p->vUpdates, pCellNew->Id ); + Abc_SclTimeIncInsert( p, pObj ); // remember when this node was upsized Vec_IntWriteEntry( p->vNodeIter, Abc_ObjId(pObj), iIter ); Counter++; @@ -650,7 +667,7 @@ return Limit; // printf( "\n" ); Vec_PtrForEachEntry( Abc_Obj_t *, vFanouts, pObj, i ) - pObj->fMarkC = 0; + pObj->fMarkB = 0; Vec_PtrFree( vFanouts ); return Counter; } @@ -772,7 +789,7 @@ void Abc_SclUpsizePrint( SC_Man * p, int Iter, int win, int nPathPos, int nPathN printf( "B: " ); printf( "%.2f ps ", SC_LibTimePs(p->pLib, p->BestDelay) ); printf( "(%+5.1f %%)", 100.0 * (p->BestDelay - p->MaxDelay0)/ p->MaxDelay0 ); - printf( "%8.2f sec", 1.0*(Abc_Clock() - p->timeTotal)/(CLOCKS_PER_SEC) ); + printf( "%8.2f sec ", 1.0*(Abc_Clock() - p->timeTotal)/(CLOCKS_PER_SEC) ); printf( "%c", fVerbose ? '\n' : '\r' ); } @@ -822,7 +839,6 @@ void Abc_SclUpsizePerform( SC_Lib * pLib, Abc_Ntk_t * pNtk, SC_SizePars * pPars abctime clk, nRuntimeLimit = pPars->TimeOut ? pPars->TimeOut * CLOCKS_PER_SEC + Abc_Clock() : 0; int i = 0, win, nUpsizes = -1, nFramesNoChange = 0; int nAllPos, nAllNodes, nAllTfos, nAllUpsizes; - if ( pPars->fVerbose ) { printf( "Parameters: " ); @@ -836,14 +852,15 @@ void Abc_SclUpsizePerform( SC_Lib * pLib, Abc_Ntk_t * pNtk, SC_SizePars * pPars printf( "Timeout =%4d sec", pPars->TimeOut ); printf( "\n" ); } - + // increase window for larger networks + if ( pPars->Window == 1 ) + pPars->Window += (Abc_NtkNodeNum(pNtk) > 40000); // prepare the manager; collect init stats p = Abc_SclManStart( pLib, pNtk, pPars->fUseWireLoads, pPars->fUseDept, 0, pPars->BuffTreeEst ); p->timeTotal = Abc_Clock(); assert( p->vGatesBest == NULL ); p->vGatesBest = Vec_IntDup( p->pNtk->vGates ); p->BestDelay = p->MaxDelay0; - // perform upsizing nAllPos = nAllNodes = nAllTfos = nAllUpsizes = 0; if ( p->BestDelay <= SC_LibTimeFromPs(p->pLib, (float)pPars->DelayUser) ) @@ -851,7 +868,7 @@ void Abc_SclUpsizePerform( SC_Lib * pLib, Abc_Ntk_t * pNtk, SC_SizePars * pPars else for ( i = 0; i < pPars->nIters; i++ ) { - for ( win = pPars->Window; win <= 100; win *= 2 ) + for ( win = pPars->Window + ((i % 7) == 6); win <= 100; win *= 2 ) { // detect critical path clk = Abc_Clock(); @@ -885,7 +902,10 @@ void Abc_SclUpsizePerform( SC_Lib * pLib, Abc_Ntk_t * pNtk, SC_SizePars * pPars if ( pPars->fUseDept ) { vTFO = Vec_IntAlloc( 0 ); - Abc_SclTimeNtkRecompute( p, NULL, NULL, pPars->fUseDept, 0 ); + if ( p->nIncUpdates ) + Abc_SclTimeIncUpdate( p ); + else + Abc_SclTimeNtkRecompute( p, NULL, NULL, pPars->fUseDept, 0 ); } else { -- cgit v1.2.3