Improvements to gate-sizing.

4 files changed, 79 insertions, 27 deletions

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 <num> : the number of gate-sizing steps performed [default = %d]\n", nSteps );
     fprintf( pAbc->Err, "\t-W <num> : delay window (in percents) of near-critical COs [default = %d]\n", nRange );
+    fprintf( pAbc->Err, "\t-U <num> : delay window (in percents) of near-critical fanins [default = %d]\n", nRangeF );
+    fprintf( pAbc->Err, "\t-T <num> : 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 );