From 69c36f426cbe6d6a7aeff9130326abcd1c202ac7 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Thu, 30 Aug 2012 12:34:53 -0700 Subject: Improvements to gate-sizing. --- src/map/scl/scl.c | 16 ++++-- src/map/scl/sclInt.h | 3 +- src/map/scl/sclSize.c | 137 ++++++++++++++++++++++++++++++++++++-------------- src/map/scl/sclUtil.c | 2 + 4 files changed, 114 insertions(+), 44 deletions(-) (limited to 'src/map') diff --git a/src/map/scl/scl.c b/src/map/scl/scl.c index c0b87a1d..5ed4f6d7 100644 --- a/src/map/scl/scl.c +++ b/src/map/scl/scl.c @@ -370,14 +370,16 @@ usage: ***********************************************************************/ int Scl_CommandGsize( Abc_Frame_t * pAbc, int argc, char **argv ) { - int c, fVerbose = 0; - int fPrintCP = 0; + int c; int nSteps = 100000; int nRange = 0; int fTryAll = 0; + int fPrintCP = 0; + int fVerbose = 0; + int fVeryVerbose = 0; Extra_UtilGetoptReset(); - while ( ( c = Extra_UtilGetopt( argc, argv, "NWvaph" ) ) != EOF ) + while ( ( c = Extra_UtilGetopt( argc, argv, "NWapvwh" ) ) != EOF ) { switch ( c ) { @@ -412,6 +414,9 @@ int Scl_CommandGsize( Abc_Frame_t * pAbc, int argc, char **argv ) case 'v': fVerbose ^= 1; break; + case 'w': + fVeryVerbose ^= 1; + break; case 'h': goto usage; default: @@ -440,17 +445,18 @@ int Scl_CommandGsize( Abc_Frame_t * pAbc, int argc, char **argv ) return 1; } - Abc_SclSizingPerform( pAbc->pLibScl, Abc_FrameReadNtk(pAbc), nSteps, nRange, fTryAll, fPrintCP, fVerbose ); + Abc_SclSizingPerform( pAbc->pLibScl, Abc_FrameReadNtk(pAbc), nSteps, nRange, fTryAll, fPrintCP, fVerbose, fVeryVerbose ); return 0; usage: - fprintf( pAbc->Err, "usage: gsize [-NW num] [-apvh]\n" ); + fprintf( pAbc->Err, "usage: gsize [-NW num] [-apvwh]\n" ); fprintf( pAbc->Err, "\t performs gate sizing using Liberty library\n" ); fprintf( pAbc->Err, "\t-N : the number of gate-sizing steps performed [default = %d]\n", nSteps ); fprintf( pAbc->Err, "\t-W : delay window (in percents) of near-critical COs [default = %d]\n", nRange ); fprintf( pAbc->Err, "\t-a : try resizing all gates (not only critical) [default = %s]\n", fTryAll? "yes": "no" ); fprintf( pAbc->Err, "\t-p : toggle printing critical path before and after sizing [default = %s]\n", fPrintCP? "yes": "no" ); fprintf( pAbc->Err, "\t-v : toggle printing verbose information [default = %s]\n", fVerbose? "yes": "no" ); + fprintf( pAbc->Err, "\t-w : toggle printing even more information [default = %s]\n", fVeryVerbose? "yes": "no" ); fprintf( pAbc->Err, "\t-h : print the help massage\n" ); return 1; } diff --git a/src/map/scl/sclInt.h b/src/map/scl/sclInt.h index 9d19910a..736ac530 100644 --- a/src/map/scl/sclInt.h +++ b/src/map/scl/sclInt.h @@ -150,6 +150,7 @@ struct SC_Cell_ int n_outputs; // -- 'pins[n_inputs .. n_inputs+n_outputs-1]' are output pins SC_Cell * pNext; // same-functionality cells linked into a ring by area SC_Cell * pPrev; // same-functionality cells linked into a ring by area + int Order; // order of the gate in the list }; struct SC_Lib_ @@ -414,7 +415,7 @@ extern void Abc_SclSave( char * pFileName, SC_Lib * pScl ); /*=== sclTime.c =============================================================*/ extern void Abc_SclTimePerform( SC_Lib * pLib, Abc_Ntk_t * pNtk, int fShowAll ); /*=== sclSize.c =============================================================*/ -extern void Abc_SclSizingPerform( SC_Lib * pLib, Abc_Ntk_t * pNtk, int nSteps, int nRange, int fTryAll, int fPrintCP, int fVerbose ); +extern void Abc_SclSizingPerform( SC_Lib * pLib, Abc_Ntk_t * pNtk, int nSteps, int nRange, int fTryAll, int fPrintCP, int fVerbose, int fVeryVerbose ); /*=== sclUtil.c =============================================================*/ extern void Abc_SclHashCells( SC_Lib * p ); extern int Abc_SclCellFind( SC_Lib * p, char * pName ); diff --git a/src/map/scl/sclSize.c b/src/map/scl/sclSize.c index 1339dafb..6c561bd3 100644 --- a/src/map/scl/sclSize.c +++ b/src/map/scl/sclSize.c @@ -234,12 +234,15 @@ Vec_Int_t * Abc_SclCollectTfo( Abc_Ntk_t * p, Abc_Obj_t * pObj, Vec_Int_t * vPiv SeeAlso [] ***********************************************************************/ -SC_Cell * Abc_SclObjResiable( SC_Man * p, Abc_Obj_t * pObj ) +SC_Cell * Abc_SclObjResiable( SC_Man * p, Abc_Obj_t * pObj, int fUpsize ) { SC_Cell * pOld = Abc_SclObjCell( p, pObj ); - return pOld->pNext != pOld ? pOld->pNext : NULL; + if ( fUpsize ) + return pOld->pNext->Order > pOld->Order ? pOld->pNext : NULL; + else + return pOld->pPrev->Order < pOld->Order ? pOld->pPrev : NULL; } -float Abc_SclSizingGain( SC_Man * p, Abc_Obj_t * pPivot, Vec_Int_t * vPivots ) +float Abc_SclSizingGain( SC_Man * p, Abc_Obj_t * pPivot, Vec_Int_t * vPivots, int fUpsize ) { double dGain = 0; Vec_Int_t * vCone; @@ -249,29 +252,40 @@ float Abc_SclSizingGain( SC_Man * p, Abc_Obj_t * pPivot, Vec_Int_t * vPivots ) vCone = Abc_SclCollectTfo( p->pNtk, pPivot, vPivots ); Abc_SclConeStore( p, vCone ); Abc_SclTimeCone( p, vCone ); -// Abc_NtkForEachObjVec( vCone, p->pNtk, pObj, i ) - Abc_NtkForEachObjVec( vPivots, p->pNtk, pObj, i ) - if ( Abc_ObjIsCo(pObj) ) - { - Abc_SclObjDupFanin( p, pObj ); - dGain += Abc_SclObjGain( p, pObj ); - } + if ( vPivots ) + { + Abc_NtkForEachObjVec( vPivots, p->pNtk, pObj, i ) + if ( Abc_ObjIsCo(pObj) ) + { + Abc_SclObjDupFanin( p, pObj ); + dGain += Abc_SclObjGain( p, pObj ); + } + } + else + { + Abc_NtkForEachObjVec( vCone, p->pNtk, pObj, i ) + if ( Abc_ObjIsCo(pObj) ) + { + Abc_SclObjDupFanin( p, pObj ); + dGain += Abc_SclObjGain( p, pObj ); + } + } Abc_SclConeRestore( p, vCone ); Vec_IntFree( vCone ); return dGain; } -Abc_Obj_t * Abc_SclChooseBiggestGain( SC_Man * p, Vec_Int_t * vPath, Vec_Int_t * vPivots ) +Abc_Obj_t * Abc_SclChooseBiggestGain( SC_Man * p, Vec_Int_t * vPath, Vec_Int_t * vPivots, int fUpsize, float GainThresh ) { SC_Cell * pOld, * pNew; Abc_Obj_t * pPivot = NULL, * pObj; - double dGainBest = 0.00001, dGain; + double dGain, dGainBest = GainThresh; //0.00001; int i, gateId; Abc_NtkForEachObjVec( vPath, p->pNtk, pObj, i ) { if ( Abc_ObjIsCo(pObj) ) continue; pOld = Abc_SclObjCell( p, pObj ); - pNew = Abc_SclObjResiable( p, pObj ); + pNew = Abc_SclObjResiable( p, pObj, fUpsize ); if ( pNew == NULL ) continue; //printf( "changing %s for %s at node %d ", pOld->pName, pNew->pName, Abc_ObjId(pObj) ); @@ -279,7 +293,7 @@ Abc_Obj_t * Abc_SclChooseBiggestGain( SC_Man * p, Vec_Int_t * vPath, Vec_Int_t * Vec_IntWriteEntry( p->vGates, Abc_ObjId(pObj), Abc_SclCellFind(p->pLib, pNew->pName) ); Abc_SclUpdateLoad( p, pObj, pOld, pNew ); - dGain = Abc_SclSizingGain( p, pObj, vPivots ); + dGain = Abc_SclSizingGain( p, pObj, vPivots, fUpsize ); Abc_SclUpdateLoad( p, pObj, pNew, pOld ); //printf( "gain is %f\n", dGain ); Vec_IntWriteEntry( p->vGates, Abc_ObjId(pObj), Abc_SclCellFind(p->pLib, pOld->pName) ); @@ -290,15 +304,16 @@ Abc_Obj_t * Abc_SclChooseBiggestGain( SC_Man * p, Vec_Int_t * vPath, Vec_Int_t * pPivot = pObj; } } +//printf( "thresh = %8.2f ps best gain = %8.2f ps \n", SC_LibTimePs(p->pLib, GainThresh), SC_LibTimePs(p->pLib, dGainBest) ); return pPivot; } -void Abc_SclUpdateNetwork( SC_Man * p, Abc_Obj_t * pObj, int iStep, int fVerbose ) +void Abc_SclUpdateNetwork( SC_Man * p, Abc_Obj_t * pObj, int fUpsize, int iStep, int fVerbose, int fVeryVerbose ) { Vec_Int_t * vCone; SC_Cell * pOld, * pNew; // find new gate pOld = Abc_SclObjCell( p, pObj ); - pNew = Abc_SclObjResiable( p, pObj ); + pNew = Abc_SclObjResiable( p, pObj, fUpsize ); assert( pNew != NULL ); // update gate Abc_SclUpdateLoad( p, pObj, pOld, pNew ); @@ -318,7 +333,11 @@ void Abc_SclUpdateNetwork( SC_Man * p, Abc_Obj_t * pObj, int iStep, int fVerbose printf( "delay =%8.2f ps ", SC_LibTimePs(p->pLib, Abc_SclGetMaxDelay(p)) ); printf( "area =%10.2f ", p->SumArea ); // Abc_PrintTime( 1, "Time", clock() - p->clkStart ); - ABC_PRTr( "Time", clock() - p->clkStart ); +// ABC_PRTr( "Time", clock() - p->clkStart ); + if ( fVeryVerbose ) + ABC_PRT( "Time", clock() - p->clkStart ); + else + ABC_PRTr( "Time", clock() - p->clkStart ); } } @@ -333,12 +352,13 @@ void Abc_SclUpdateNetwork( SC_Man * p, Abc_Obj_t * pObj, int iStep, int fVerbose SeeAlso [] ***********************************************************************/ -void Abc_SclSizingPerform( SC_Lib * pLib, Abc_Ntk_t * pNtk, int nSteps, int nRange, int fTryAll, int fPrintCP, int fVerbose ) +void Abc_SclSizingPerform( SC_Lib * pLib, Abc_Ntk_t * pNtk, int nSteps, int nRange, int fTryAll, int fPrintCP, int fVerbose, int fVeryVerbose ) { + int nIters = 3; SC_Man * p; Vec_Int_t * vPath, * vPivots; Abc_Obj_t * pBest; - int i, nCones = 0; + int r, i, nCones = 0, nDownSize = 0; p = Abc_SclManStart( pLib, pNtk ); if ( fPrintCP ) Abc_SclTimeNtkPrint( p, 0 ); @@ -352,37 +372,78 @@ void Abc_SclSizingPerform( SC_Lib * pLib, Abc_Ntk_t * pNtk, int nSteps, int nRan printf( "area =%10.2f ", p->SumArea ); Abc_PrintTime( 1, "Time", clock() - p->clkStart ); } - for ( i = 0; i < nSteps; i++ ) + for ( r = i = 0; r < nIters; r++ ) { - vPath = Abc_SclFindCriticalPath( p, nRange, &vPivots ); - pBest = Abc_SclChooseBiggestGain( p, vPath, vPivots ); - Vec_IntFree( vPath ); - Vec_IntFree( vPivots ); - if ( pBest == NULL ) + float nThresh1 = p->MaxDelay0/100000; + float nThresh2 = p->MaxDelay0/1000; + // try upsizing + for ( ; i < nSteps; i++ ) { - if ( fTryAll ) + vPath = Abc_SclFindCriticalPath( p, nRange, &vPivots ); + pBest = Abc_SclChooseBiggestGain( p, vPath, vPivots, 1, nThresh1 ); + Vec_IntFree( vPath ); + Vec_IntFree( vPivots ); + if ( pBest == NULL ) { - vPath = Abc_SclFindCriticalCone( p, nRange, &vPivots ); -// vPath = Abc_SclFindCriticalPath( p, nRange+5, &vPivots ); - pBest = Abc_SclChooseBiggestGain( p, vPath, vPivots ); - Vec_IntFree( vPath ); - Vec_IntFree( vPivots ); - nCones++; + if ( fTryAll ) + { + vPath = Abc_SclFindCriticalCone( p, nRange, &vPivots ); + pBest = Abc_SclChooseBiggestGain( p, vPath, vPivots, 1, nThresh1 ); + Vec_IntFree( vPath ); + Vec_IntFree( vPivots ); + nCones++; + } + if ( pBest == NULL ) + break; } + Abc_SclUpdateNetwork( p, pBest, 1, i+1, fVerbose, fVeryVerbose ); + // recompute loads every 100 steps + if ( i && i % 100 == 0 ) + Abc_SclComputeLoad( p ); + } + if ( fVeryVerbose ) + printf( "\n" ); + if ( r == nIters - 1 ) + break; + // try downsizing + for ( ; i < nSteps; i++ ) + { + vPath = Abc_SclFindCriticalPath( p, nRange, &vPivots ); +// pBest = Abc_SclChooseBiggestGain( p, vPath, vPivots, 0, -p->MaxDelay0/100000 ); + pBest = Abc_SclChooseBiggestGain( p, vPath, NULL, 0, nThresh2 ); + Vec_IntFree( vPath ); + Vec_IntFree( vPivots ); if ( pBest == NULL ) - break; + { + + if ( fTryAll ) + { + vPath = Abc_SclFindCriticalCone( p, nRange, &vPivots ); +// pBest = Abc_SclChooseBiggestGain( p, vPath, vPivots, 0, -p->MaxDelay0/100000 ); + pBest = Abc_SclChooseBiggestGain( p, vPath, NULL, 0, nThresh2 ); + Vec_IntFree( vPath ); + Vec_IntFree( vPivots ); + nCones++; + } + if ( pBest == NULL ) + break; + } + Abc_SclUpdateNetwork( p, pBest, 0, i+1, fVerbose, fVeryVerbose ); + // recompute loads every 100 steps + if ( i && i % 100 == 0 ) + Abc_SclComputeLoad( p ); + nDownSize++; } - Abc_SclUpdateNetwork( p, pBest, i+1, fVerbose ); - // recompute loads every 100 steps - if ( i && i % 100 == 0 ) - Abc_SclComputeLoad( p ); + if ( fVeryVerbose ) + printf( "\n" ); } + p->MaxDelay = Abc_SclGetMaxDelay(p); if ( fPrintCP ) Abc_SclTimeNtkPrint( p, 0 ); // print cumulative statistics printf( "Cones: %d. ", nCones ); - printf( "Resized: %d. ", i ); + printf( "Resized: %d(%d). ", i, nDownSize ); printf( "Delay: " ); printf( "%.2f -> %.2f ps ", SC_LibTimePs(p->pLib, p->MaxDelay0), SC_LibTimePs(p->pLib, p->MaxDelay) ); printf( "(%+.1f %%). ", 100.0 * (p->MaxDelay - p->MaxDelay0)/ p->MaxDelay0 ); diff --git a/src/map/scl/sclUtil.c b/src/map/scl/sclUtil.c index 0356e83d..b541bfc8 100644 --- a/src/map/scl/sclUtil.c +++ b/src/map/scl/sclUtil.c @@ -137,11 +137,13 @@ void Abc_SclLinkCells( SC_Lib * p ) // create new representative pRepr = Vec_PtrEntry( vList, 0 ); pRepr->pNext = pRepr->pPrev = pRepr; + pRepr->Order = 0; // relink cells Vec_PtrForEachEntryStart( SC_Cell *, vList, pCell, i, 1 ) { pRepr->pPrev->pNext = pCell; pCell->pNext = pRepr; pCell->pPrev = pRepr->pPrev; pRepr->pPrev = pCell; + pCell->Order = i; } // update list Vec_PtrWriteEntry( p->vCellOrder, k, pRepr ); -- cgit v1.2.3