From 5a009b677411e34c94b4bf379d2f01a0f1487de0 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Thu, 30 Aug 2012 21:46:31 -0700 Subject: Improvements to gate-sizing. --- src/map/scl/scl.c | 38 ++++++++++++++++++++++++++++++++------ src/map/scl/sclInt.h | 2 +- src/map/scl/sclMan.h | 17 +++++++++++------ src/map/scl/sclSize.c | 49 +++++++++++++++++++++++++++++++++++-------------- 4 files changed, 79 insertions(+), 27 deletions(-) (limited to 'src/map/scl') diff --git a/src/map/scl/scl.c b/src/map/scl/scl.c index a6b429eb..a730322c 100644 --- a/src/map/scl/scl.c +++ b/src/map/scl/scl.c @@ -371,15 +371,17 @@ usage: int Scl_CommandGsize( Abc_Frame_t * pAbc, int argc, char **argv ) { int c; - int nSteps = 100000; - int nRange = 0; - int fTryAll = 1; + int nSteps = 1000000; + int nRange = 0; + int nRangeF = 10; + int nTimeOut = 300; + int fTryAll = 1; int fPrintCP = 0; int fVerbose = 0; int fVeryVerbose = 0; Extra_UtilGetoptReset(); - while ( ( c = Extra_UtilGetopt( argc, argv, "NWapvwh" ) ) != EOF ) + while ( ( c = Extra_UtilGetopt( argc, argv, "NWUTapvwh" ) ) != EOF ) { switch ( c ) { @@ -405,6 +407,28 @@ int Scl_CommandGsize( Abc_Frame_t * pAbc, int argc, char **argv ) if ( nRange < 0 ) goto usage; break; + case 'U': + if ( globalUtilOptind >= argc ) + { + Abc_Print( -1, "Command line switch \"-U\" should be followed by a positive integer.\n" ); + goto usage; + } + nRangeF = atoi(argv[globalUtilOptind]); + globalUtilOptind++; + if ( nRangeF < 0 ) + goto usage; + break; + case 'T': + if ( globalUtilOptind >= argc ) + { + Abc_Print( -1, "Command line switch \"-T\" should be followed by a positive integer.\n" ); + goto usage; + } + nTimeOut = atoi(argv[globalUtilOptind]); + globalUtilOptind++; + if ( nTimeOut < 0 ) + goto usage; + break; case 'a': fTryAll ^= 1; break; @@ -445,14 +469,16 @@ 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, fVeryVerbose ); + Abc_SclSizingPerform( pAbc->pLibScl, Abc_FrameReadNtk(pAbc), nSteps, nRange, nRangeF, nTimeOut, fTryAll, fPrintCP, fVerbose, fVeryVerbose ); return 0; usage: - fprintf( pAbc->Err, "usage: gsize [-NW num] [-apvwh]\n" ); + fprintf( pAbc->Err, "usage: gsize [-NWUT 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-U : delay window (in percents) of near-critical fanins [default = %d]\n", nRangeF ); + fprintf( pAbc->Err, "\t-T : an approximate timeout, in seconds [default = %d]\n", nTimeOut ); 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" ); diff --git a/src/map/scl/sclInt.h b/src/map/scl/sclInt.h index 736ac530..baf1d146 100644 --- a/src/map/scl/sclInt.h +++ b/src/map/scl/sclInt.h @@ -415,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, int fVeryVerbose ); +extern void Abc_SclSizingPerform( SC_Lib * pLib, Abc_Ntk_t * pNtk, int nSteps, int nRange, int nRangeF, int nTimeOut, 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/sclMan.h b/src/map/scl/sclMan.h index 9a500a9a..3798152c 100644 --- a/src/map/scl/sclMan.h +++ b/src/map/scl/sclMan.h @@ -189,14 +189,19 @@ static inline float Abc_SclGetMaxDelay( SC_Man * p ) { float fMaxArr = 0; Abc_Obj_t * pObj; - SC_Pair * pArr; int i; Abc_NtkForEachCo( p->pNtk, pObj, i ) - { - pArr = Abc_SclObjTime( p, pObj ); - if ( fMaxArr < pArr->rise ) fMaxArr = pArr->rise; - if ( fMaxArr < pArr->fall ) fMaxArr = pArr->fall; - } + fMaxArr = Abc_MaxFloat( fMaxArr, Abc_SclObjTimeMax(p, pObj) ); + return fMaxArr; +} +static inline float Abc_SclGetMaxDelayNode( SC_Man * p, Abc_Obj_t * pNode ) +{ + float fMaxArr = 0; + Abc_Obj_t * pObj; + int i; + assert( Abc_ObjIsNode(pNode) ); + Abc_ObjForEachFanin( pNode, pObj, i ) + fMaxArr = Abc_MaxFloat( fMaxArr, Abc_SclObjTimeMax(p, pObj) ); return fMaxArr; } diff --git a/src/map/scl/sclSize.c b/src/map/scl/sclSize.c index 633e7331..3baeb2c2 100644 --- a/src/map/scl/sclSize.c +++ b/src/map/scl/sclSize.c @@ -67,18 +67,19 @@ Vec_Int_t * Abc_SclCollectNodes( Abc_Ntk_t * p ) ***********************************************************************/ Vec_Int_t * Abc_SclFindCriticalCoRange( SC_Man * p, int Range ) { - float fMaxArr = Abc_SclGetMaxDelay( p ); + float fMaxArr = Abc_SclGetMaxDelay( p ) * (100.0 - Range) / 100.0; Vec_Int_t * vPivots; Abc_Obj_t * pObj; int i; vPivots = Vec_IntAlloc( 100 ); Abc_NtkForEachCo( p->pNtk, pObj, i ) - if ( Abc_SclObjTimeMax(p, pObj) >= fMaxArr * (100 - Range) / 100 ) + if ( Abc_SclObjTimeMax(p, pObj) >= fMaxArr ) Vec_IntPush( vPivots, Abc_ObjId(pObj) ); assert( Vec_IntSize(vPivots) > 0 ); return vPivots; } + /**Function************************************************************* Synopsis [Collect nodes in cone.] @@ -90,9 +91,10 @@ Vec_Int_t * Abc_SclFindCriticalCoRange( SC_Man * p, int Range ) SeeAlso [] ***********************************************************************/ -void Abc_SclFindCriticalCone_rec( Abc_Obj_t * pObj, Vec_Int_t * vVisited ) +void Abc_SclFindCriticalCone_rec( SC_Man * p, Abc_Obj_t * pObj, Vec_Int_t * vVisited, int RangeF ) { Abc_Obj_t * pNext; + float fArrMax; int i; if ( Abc_ObjIsCi(pObj) ) return; @@ -100,11 +102,15 @@ void Abc_SclFindCriticalCone_rec( Abc_Obj_t * pObj, Vec_Int_t * vVisited ) return; Abc_NodeSetTravIdCurrent( pObj ); assert( Abc_ObjIsNode(pObj) ); + // compute timing critical fanin + fArrMax = Abc_SclGetMaxDelayNode( p, pObj ) * (100.0 - RangeF) / 100.0; + // traverse all fanins whose arrival times are within a window Abc_ObjForEachFanin( pObj, pNext, i ) - Abc_SclFindCriticalCone_rec( pNext, vVisited ); + if ( Abc_SclObjTimeMax(p, pNext) >= fArrMax ) + Abc_SclFindCriticalCone_rec( p, pNext, vVisited, RangeF ); Vec_IntPush( vVisited, Abc_ObjId(pObj) ); } -Vec_Int_t * Abc_SclFindCriticalCone( SC_Man * p, int Range, Vec_Int_t ** pvPivots ) +Vec_Int_t * Abc_SclFindCriticalCone( SC_Man * p, int Range, int RangeF, Vec_Int_t ** pvPivots ) { Vec_Int_t * vPivots = Abc_SclFindCriticalCoRange( p, Range ); Vec_Int_t * vPath = Vec_IntAlloc( 100 ); @@ -112,7 +118,7 @@ Vec_Int_t * Abc_SclFindCriticalCone( SC_Man * p, int Range, Vec_Int_t ** pvPivot int i; Abc_NtkIncrementTravId( p->pNtk ); Abc_NtkForEachObjVec( vPivots, p->pNtk, pObj, i ) - Abc_SclFindCriticalCone_rec( Abc_ObjFanin0(pObj), vPath ); + Abc_SclFindCriticalCone_rec( p, Abc_ObjFanin0(pObj), vPath, RangeF ); if ( pvPivots ) *pvPivots = vPivots; else @@ -131,12 +137,13 @@ Vec_Int_t * Abc_SclFindCriticalCone( SC_Man * p, int Range, Vec_Int_t ** pvPivot SeeAlso [] ***********************************************************************/ -Vec_Int_t * Abc_SclFindCriticalPath( SC_Man * p, int Range, Vec_Int_t ** pvPivots ) +Vec_Int_t * Abc_SclFindCriticalPath2( SC_Man * p, int Range, Vec_Int_t ** pvPivots ) { Vec_Int_t * vPivots = Abc_SclFindCriticalCoRange( p, Range ); Vec_Int_t * vPath = Vec_IntAlloc( 100 ); Abc_Obj_t * pObj; int i, fRise = 0; + //Vec_IntShrink( vPivots, 1 ); Abc_NtkForEachObjVec( vPivots, p->pNtk, pObj, i ) { pObj = Abc_ObjFanin0(pObj); @@ -153,6 +160,10 @@ Vec_Int_t * Abc_SclFindCriticalPath( SC_Man * p, int Range, Vec_Int_t ** pvPivot Vec_IntFree( vPivots ); return vPath; } +Vec_Int_t * Abc_SclFindCriticalPath( SC_Man * p, int Range, Vec_Int_t ** pvPivots ) +{ + return Abc_SclFindCriticalCone( p, Range, 1, pvPivots ); +} /**Function************************************************************* @@ -289,10 +300,9 @@ Abc_Obj_t * Abc_SclChooseBiggestGain( SC_Man * p, Vec_Int_t * vPath, Vec_Int_t * 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) ); gateId = Vec_IntEntry(p->vGates, Abc_ObjId(pObj)); Vec_IntWriteEntry( p->vGates, Abc_ObjId(pObj), Abc_SclCellFind(p->pLib, pNew->pName) ); - +//printf( "changing %s for %s at node %d ", pOld->pName, pNew->pName, Abc_ObjId(pObj) ); Abc_SclUpdateLoad( p, pObj, pOld, pNew ); dGain = Abc_SclSizingGain( p, pObj, vPivots, fUpsize ); Abc_SclUpdateLoad( p, pObj, pNew, pOld ); @@ -354,12 +364,13 @@ void Abc_SclUpdateNetwork( SC_Man * p, Abc_Obj_t * pObj, int nCone, int fUpsize, SeeAlso [] ***********************************************************************/ -void Abc_SclSizingPerform( SC_Lib * pLib, Abc_Ntk_t * pNtk, int nSteps, int nRange, int fTryAll, int fPrintCP, int fVerbose, int fVeryVerbose ) +void Abc_SclSizingPerform( SC_Lib * pLib, Abc_Ntk_t * pNtk, int nSteps, int nRange, int nRangeF, int nTimeOut, int fTryAll, int fPrintCP, int fVerbose, int fVeryVerbose ) { int nIters = 1; SC_Man * p; Vec_Int_t * vPath, * vPivots; Abc_Obj_t * pBest; + clock_t nRuntimeLimit = nTimeOut ? nTimeOut * CLOCKS_PER_SEC + clock() : 0; int r, i, nNodes, nCones = 0, nDownSize = 0; p = Abc_SclManStart( pLib, pNtk ); if ( fPrintCP ) @@ -391,7 +402,7 @@ void Abc_SclSizingPerform( SC_Lib * pLib, Abc_Ntk_t * pNtk, int nSteps, int nRan { if ( fTryAll ) { - vPath = Abc_SclFindCriticalCone( p, nRange, &vPivots ); + vPath = Abc_SclFindCriticalCone( p, nRange, nRangeF, &vPivots ); pBest = Abc_SclChooseBiggestGain( p, vPath, vPivots, 1, nThresh1 ); nNodes = Vec_IntSize(vPath); Vec_IntFree( vPath ); @@ -405,11 +416,15 @@ void Abc_SclSizingPerform( SC_Lib * pLib, Abc_Ntk_t * pNtk, int nSteps, int nRan // recompute loads every 100 steps if ( i && i % 100 == 0 ) Abc_SclComputeLoad( p ); + if ( (i & 15) == 0 && nRuntimeLimit && clock() > nRuntimeLimit ) // timeout + break; } - if ( fVeryVerbose ) - printf( "\n" ); if ( r == nIters - 1 ) break; + if ( nRuntimeLimit && clock() > nRuntimeLimit ) // timeout + break; + if ( fVeryVerbose ) + printf( "\n" ); // try downsizing for ( ; i < nSteps; i++ ) { @@ -424,7 +439,7 @@ void Abc_SclSizingPerform( SC_Lib * pLib, Abc_Ntk_t * pNtk, int nSteps, int nRan if ( fTryAll ) { - vPath = Abc_SclFindCriticalCone( p, nRange, &vPivots ); + vPath = Abc_SclFindCriticalCone( p, nRange, nRangeF, &vPivots ); // pBest = Abc_SclChooseBiggestGain( p, vPath, vPivots, 0, -p->MaxDelay0/100000 ); pBest = Abc_SclChooseBiggestGain( p, vPath, NULL, 0, nThresh2 ); nNodes = Vec_IntSize(vPath); @@ -439,8 +454,12 @@ void Abc_SclSizingPerform( SC_Lib * pLib, Abc_Ntk_t * pNtk, int nSteps, int nRan // recompute loads every 100 steps if ( i && i % 100 == 0 ) Abc_SclComputeLoad( p ); + if ( (i & 15) == 0 && nRuntimeLimit && clock() > nRuntimeLimit ) // timeout + break; nDownSize++; } + if ( nRuntimeLimit && clock() > nRuntimeLimit ) // timeout + break; if ( fVeryVerbose ) printf( "\n" ); } @@ -448,6 +467,8 @@ void Abc_SclSizingPerform( SC_Lib * pLib, Abc_Ntk_t * pNtk, int nSteps, int nRan p->MaxDelay = Abc_SclGetMaxDelay(p); if ( fPrintCP ) Abc_SclTimeNtkPrint( p, 0 ); + if ( nRuntimeLimit && clock() > nRuntimeLimit ) + printf( "Timeout was reached after %d seconds.\n", nTimeOut ); // print cumulative statistics printf( "Cones: %d. ", nCones ); printf( "Resized: %d(%d). ", i, nDownSize ); -- cgit v1.2.3