Version abc61210

1 files changed, 300 insertions, 57 deletions

diff --git a/src/map/if/ifSeq.c b/src/map/if/ifSeq.c
index ac2754c0..ddc74a49 100644
--- a/src/map/if/ifSeq.c
+++ b/src/map/if/ifSeq.c
@@ -24,9 +24,11 @@
 ///                        DECLARATIONS                              ///
 ////////////////////////////////////////////////////////////////////////
 
-static void If_ObjPerformMappingLI( If_Man_t * p, If_Obj_t * pLatch );
-static void If_ObjPerformMappingLO( If_Man_t * p, If_Obj_t * pLatch, If_Obj_t * pObj );
-static int  If_ManMappingSeqConverged( If_Man_t * p );
+static int  If_ManBinarySearchPeriod( If_Man_t * p, int Mode );
+static int  If_ManBinarySearch_rec( If_Man_t * p, int Mode, int FiMin, int FiMax );
+static int  If_ManPerformMappingRoundSeq( If_Man_t * p, int Mode, int nIter, char * pLabel );
+static int  If_ManPrepareMappingSeq( If_Man_t * p );
+static int  If_ObjPerformMappingLatch( If_Man_t * p, If_Obj_t * pObj );
 
 ////////////////////////////////////////////////////////////////////////
 ///                     FUNCTION DEFINITIONS                         ///
@@ -45,46 +47,100 @@ static int  If_ManMappingSeqConverged( If_Man_t * p );
 ***********************************************************************/
 int If_ManPerformMappingSeq( If_Man_t * p )
 {
-    If_Obj_t * pObj, * pLatch;
-    int i, clkTotal = clock();
-    // set the number of cuts used
+    int PeriodBest, Mode = 0;
+
+    // collect nodes in the sequential order
+    If_ManPrepareMappingSeq( p );
+
+    // perform combinational mapping to get the upper bound on the clock period
+    If_ManPerformMappingRound( p, 2, 0, 0, NULL );
+    p->RequiredGlo = If_ManDelayMax( p, 0 );
+
+    // set parameters
     p->nCutsUsed = p->pPars->nCutsMax;
-    // set arrival times and trivial cuts at const 1 and PIs
-    If_ManConst1(p)->Cuts[0].Delay = 0.0;
-    If_ManForEachPi( p, pObj, i )
-        pObj->Cuts[0].Delay = p->pPars->pTimesArr[i];
-    // set the fanout estimates of the PIs
-    If_ManForEachPi( p, pObj, i )
-        pObj->EstRefs = (float)1.0;
-    // delay oriented mapping
-    p->pPars->fFancy = 1;
-    If_ManPerformMappingRound( p, p->pPars->nCutsMax, 0, 0, NULL );
-    p->pPars->fFancy = 0;
-
-    // perform iterations over the circuit
-    while ( !If_ManMappingSeqConverged( p ) )
+    p->nAttempts = 0;
+    p->nMaxIters = 50;
+    p->Period    = (int)p->RequiredGlo;
+
+    // make sure the clock period words
+    if ( !If_ManBinarySearchPeriod( p, Mode ) )
     {
-        // assign cuts to latches
-        If_ManForEachLatch( p, pLatch, i )
-            If_ObjPerformMappingLI( p, pLatch );
-        // assign cuts to primary inputs
-        If_ManForEachLatch( p, pLatch, i )
-            If_ObjPerformMappingLO( p, pLatch, If_ManPi(p, If_ManPiNum(p) - If_ManPoNum(p) + i) );
-        // map the nodes
-        If_ManForEachNode( p, pObj, i )
-            If_ObjPerformMapping( p, pObj, 0 );
+        printf( "If_ManPerformMappingSeq(): The upper bound on the clock period cannot be computed.\n" );
+        return 0;
     }
 
-    if ( p->pPars->fVerbose )
+    // perform binary search
+    PeriodBest = If_ManBinarySearch_rec( p, Mode, 0, p->Period );
+
+    // recompute the best l-values
+    if ( p->Period != PeriodBest )
     {
-        PRT( "Total time", clock() - clkTotal );
+        p->Period = PeriodBest;
+        if ( !If_ManBinarySearchPeriod( p, Mode ) )
+        {
+            printf( "If_ManPerformMappingSeq(): The final clock period cannot be confirmed.\n" );
+            return 0;
+        }
     }
+/*
+    // fix the problem with non-converged delays
+    If_ManForEachNode( p, pObj, i )
+        if ( pObj->LValue < -ABC_INFINITY/2 )
+            pObj->LValue = (float)0.0;
+    // write the retiming lags
+    p->vLags = Vec_IntStart( If_ManObjNum(p) + 1 );
+    If_ManForEachNode( p, pObj, i )
+        Vec_IntWriteEntry( vLags, i, Abc_NodeComputeLag(pObj->LValue, p->Period) );
+*/
+/*
+    // print the statistic into a file
+    {
+        FILE * pTable;
+        pTable = fopen( "a/seqmap__stats.txt", "a+" );
+        fprintf( pTable, "%d ", p->Period );
+        fprintf( pTable, "\n" );
+        fclose( pTable );
+    }
+*/
+    // print the result
+    if ( p->pPars->fLiftLeaves )
+    {
+//        if ( p->pPars->fVerbose )   
+            printf( "The best clock period is %3d. (Currently, network is not modified, so mapping will fail.)\n", p->Period );
+        return 0;
+    }
+//    if ( p->pPars->fVerbose )   
+        printf( "The best clock period is %3d.\n", p->Period );
     return 1;
 }
 
 /**Function*************************************************************
 
-  Synopsis    [Performs sequential mapping.]
+  Synopsis    [Performs binary search for the optimal clock period.]
+
+  Description [Assumes that FiMin is infeasible while FiMax is feasible.]
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int If_ManBinarySearch_rec( If_Man_t * p, int Mode, int FiMin, int FiMax )
+{
+    assert( FiMin < FiMax );
+    if ( FiMin + 1 == FiMax )
+        return FiMax;
+    // compute the median
+    p->Period = FiMin + (FiMax - FiMin)/2;
+    if ( If_ManBinarySearchPeriod( p, Mode ) )
+        return If_ManBinarySearch_rec( p, Mode, FiMin, p->Period ); // Median is feasible
+    else 
+        return If_ManBinarySearch_rec( p, Mode, p->Period, FiMax ); // Median is infeasible
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Returns 1 if retiming with this clock period is feasible.]
 
   Description []
                
@@ -93,16 +149,153 @@ int If_ManPerformMappingSeq( If_Man_t * p )
   SeeAlso     []
 
 ***********************************************************************/
-void If_CutLift( If_Cut_t * pCut )
+int If_ManBinarySearchPeriod( If_Man_t * p, int Mode )
 {
-    unsigned i;
-    for ( i = 0; i < pCut->nLeaves; i++ )
-        pCut->pLeaves[i] = ((pCut->pLeaves[i] >> 8) << 8) | ((pCut->pLeaves[i] & 255) + 1);
+    If_Obj_t * pObj;
+    int i, c, fConverged;
+    int fResetRefs = 0;
+
+    p->nAttempts++;
+
+    // set l-values of all nodes to be minus infinity, except PIs and constants
+    If_ManForEachObj( p, pObj, i )
+    {
+        pObj->nCuts = 1;
+        If_ObjSetLValue( pObj, -IF_FLOAT_LARGE );
+        if ( fResetRefs )
+            pObj->nRefs = 0;
+    }
+    If_ObjSetLValue( If_ManConst1(p), (float)0.0 );
+    If_ManForEachPi( p, pObj, i )
+        If_ObjSetLValue( pObj, (float)0.0 );
+
+    // reset references to their original state
+    if ( fResetRefs )
+    {
+        If_ManForEachObj( p, pObj, i )
+        {
+            if ( If_ObjIsCo(pObj) )
+                continue;
+            if ( pObj->pFanin0 ) pObj->pFanin0->nRefs++;
+            if ( pObj->pFanin1 ) pObj->pFanin1->nRefs++;
+        }
+    }
+
+    // update all values iteratively
+    fConverged = 0;
+    for ( c = 1; c <= p->nMaxIters; c++ )
+    {
+        if ( !If_ManPerformMappingRoundSeq( p, Mode, c, NULL ) )
+        {
+            fConverged = 1;
+            break;
+        }
+        p->RequiredGlo = If_ManDelayMax( p, 1 );
+        if ( p->RequiredGlo > p->Period + p->fEpsilon )
+            break; 
+    }
+
+    // report the results
+    if ( p->pPars->fVerbose )
+    {
+        p->AreaGlo = p->pPars->fLiftLeaves? If_ManScanMappingSeq(p) : If_ManScanMapping(p);
+        printf( "Attempt = %2d.  Iters = %3d.  Area = %10.2f.  Fi = %6.2f.  ", p->nAttempts, c, p->AreaGlo, (float)p->Period );
+        if ( fConverged )
+            printf( "  Feasible" );
+        else if ( c > p->nMaxIters )
+            printf( "Infeasible (timeout)" );
+        else
+            printf( "Infeasible" );
+        printf( "\n" );
+    }
+    return fConverged;
 }
 
 /**Function*************************************************************
 
-  Synopsis    [Performs sequential mapping.]
+  Synopsis    [Performs one pass of l-value computation over all nodes.]
+
+  Description [Experimentally it was found that checking POs changes
+  is not enough to detect the convergence of l-values in the network.]
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int If_ManPerformMappingRoundSeq( If_Man_t * p, int Mode, int nIter, char * pLabel )
+{
+    ProgressBar * pProgress;
+    If_Obj_t * pObj;
+    int i, clk = clock();
+    int fVeryVerbose = 0;
+    int fChange = 0;
+    assert( Mode >= 0 && Mode <= 2 );
+    if ( !p->pPars->fVerbose )
+        pProgress = Extra_ProgressBarStart( stdout, If_ManObjNum(p) );
+    // map the internal nodes
+    p->nCutsMerged = 0;
+    If_ManForEachNode( p, pObj, i )
+    {
+        if ( !p->pPars->fVerbose )
+            Extra_ProgressBarUpdate( pProgress, i, pLabel );
+        // consider the camse of an AND gate
+        assert( If_ObjIsAnd(pObj) );
+        If_ObjPerformMappingAnd( p, pObj, Mode );
+        if ( pObj->fRepr )
+            If_ObjPerformMappingChoice( p, pObj, Mode );
+        // check if updating happens
+        if ( If_ObjLValue(pObj) < If_ObjCutBest(pObj)->Delay - p->fEpsilon )
+        {
+            If_ObjSetLValue( pObj, If_ObjCutBest(pObj)->Delay );
+            fChange = 1;
+        }
+//if ( If_ObjLValue(pObj) > -1000.0 )
+//printf( "Node %d %.2f  ", pObj->Id, If_ObjLValue(pObj) );
+    }
+    if ( !p->pPars->fVerbose )
+        Extra_ProgressBarStop( pProgress );
+    // propagate arrival times from the registers
+    Vec_PtrForEachEntry( p->vLatchOrder, pObj, i )
+        fChange |= If_ObjPerformMappingLatch( p, pObj );
+//printf( "\n\n" );
+    // compute area and delay
+    if ( fVeryVerbose )
+    {
+        p->RequiredGlo = If_ManDelayMax( p, 1 );
+        p->AreaGlo = p->pPars->fLiftLeaves? If_ManScanMappingSeq(p) : If_ManScanMapping(p);
+        printf( "S%d:  Fi = %6.2f. Del = %6.2f. Area = %8.2f. Cuts = %8d. Lim = %2d. Ave = %5.2f. ", 
+             nIter, (float)p->Period, p->RequiredGlo, p->AreaGlo, p->nCutsMerged, p->nCutsUsed, 1.0 * p->nCutsMerged / If_ManAndNum(p) );
+        PRT( "T", clock() - clk );
+    }
+    return fChange;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Collects latches in the topological order.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+ 
+***********************************************************************/
+void If_ManCollectLatches_rec( If_Obj_t * pObj, Vec_Ptr_t * vLatches )
+{
+    if ( !If_ObjIsLatch(pObj) )
+        return;
+    if ( pObj->fMark )
+        return;
+    pObj->fMark = 1;
+    If_ManCollectLatches_rec( pObj->pFanin0, vLatches );
+    Vec_PtrPush( vLatches, pObj );
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Collects latches in the topological order.]
 
   Description []
                
@@ -111,19 +304,25 @@ void If_CutLift( If_Cut_t * pCut )
   SeeAlso     []
 
 ***********************************************************************/
-void If_ObjPerformMappingLI( If_Man_t * p, If_Obj_t * pLatch )
+Vec_Ptr_t * If_ManCollectLatches( If_Man_t * p )
 {
-    If_Obj_t * pFanin;
-    int c;
-    assert( If_ObjIsPo(pLatch) );
-    pFanin = If_ObjFanin0(pLatch);
-    for ( c = 0; c < pFanin->nCuts; c++ )
-        If_CutCopy( pLatch->Cuts + c, pFanin->Cuts + c );
+    Vec_Ptr_t * vLatches;
+    If_Obj_t * pObj;
+    int i;
+    // collect latches 
+    vLatches = Vec_PtrAlloc( p->pPars->nLatches );
+    Vec_PtrForEachEntryStart( p->vCis, pObj, i, If_ManCiNum(p) - p->pPars->nLatches )
+        If_ManCollectLatches_rec( pObj, vLatches );
+    // clean marks
+    Vec_PtrForEachEntry( vLatches, pObj, i )
+        pObj->fMark = 0;
+    assert( Vec_PtrSize(vLatches) == p->pPars->nLatches );
+    return vLatches;
 }
 
 /**Function*************************************************************
 
-  Synopsis    [Performs sequential mapping.]
+  Synopsis    [Prepares for sequential mapping by linking the latches.]
 
   Description []
                
@@ -132,23 +331,43 @@ void If_ObjPerformMappingLI( If_Man_t * p, If_Obj_t * pLatch )
   SeeAlso     []
 
 ***********************************************************************/
-void If_ObjPerformMappingLO( If_Man_t * p, If_Obj_t * pLatch, If_Obj_t * pObj )
+int If_ManPrepareMappingSeq( If_Man_t * p )
 {
+    If_Obj_t * pObj, * pObjLi, * pObjLo, * pTemp;
     If_Cut_t * pCut;
-    int c, Limit = IF_MIN( p->nCuts + 1, p->nCutsUsed );
-    assert( If_ObjIsPo(pLatch) );
-    for ( c = 1; c < Limit; c++ )
+    int i;
+    // link the latch outputs (PIs) directly to the drivers of latch inputs (POs)
+    for ( i = 0; i < p->pPars->nLatches; i++ )
+    {
+        pObjLo = If_ManCi( p, If_ManCiNum(p) - p->pPars->nLatches + i );
+        pObjLi = If_ManCo( p, If_ManCoNum(p) - p->pPars->nLatches + i );
+        pObjLo->pFanin0 = If_ObjFanin0( pObjLi );
+        pObjLo->fCompl0 = If_ObjFaninC0( pObjLi );
+//        pObjLo->pFanin0 = pObjLi;
+    }
+    // collect latches
+    p->vLatchOrder = If_ManCollectLatches( p );
+    // propagate elementary cuts 
+    if ( p->pPars->fLiftLeaves )
     {
-        pCut = pObj->Cuts + c;
-        If_CutCopy( pCut, pLatch->Cuts + c - 1 );
-        If_CutLift( pCut );
-        pCut->Delay -= p->Fi;
+        Vec_PtrForEachEntry( p->vLatchOrder, pObj, i )
+        {
+            pCut = If_ObjCutTriv(pObj);
+            If_CutCopy( pCut, If_ObjFanin0(pObj)->Cuts );
+            If_CutLift( pCut );
+            pCut->Delay  -= p->Period;
+            pCut->fCompl ^= pObj->fCompl0;
+
+            pTemp = If_ManObj(p, pCut->pLeaves[0] >> 8);
+            assert( !If_ObjIsLatch(pTemp) );
+        }
     }
+    return 1;
 }
 
 /**Function*************************************************************
 
-  Synopsis    [Performs sequential mapping.]
+  Synopsis    [Performs mapping of the latches.]
 
   Description []
                
@@ -157,12 +376,36 @@ void If_ObjPerformMappingLO( If_Man_t * p, If_Obj_t * pLatch, If_Obj_t * pObj )
   SeeAlso     []
 
 ***********************************************************************/
-int If_ManMappingSeqConverged( If_Man_t * p )
+int If_ObjPerformMappingLatch( If_Man_t * p, If_Obj_t * pObj )
 {
-    return 0;
+    If_Obj_t * pFanin;
+    If_Cut_t * pCut;
+    float LValueOld;
+    int i;
+    assert( If_ObjIsLatch(pObj) );
+    // save old l-value
+    LValueOld = If_ObjLValue(pObj);
+    pFanin = If_ObjFanin0(pObj);
+    assert( pFanin->nCuts > 0 );
+    if ( !p->pPars->fLiftLeaves )
+    {
+        pObj->nCuts = 1;
+        If_ObjSetLValue( pObj, If_ObjLValue(pFanin) - p->Period );
+    }
+    else
+    {
+        pObj->nCuts = pFanin->nCuts;
+        If_ObjForEachCut( pObj, pCut, i )
+        {
+            If_CutCopy( pCut, pFanin->Cuts + i );
+            If_CutLift( pCut );
+            pCut->Delay  -= p->Period;
+            pCut->fCompl ^= pObj->fCompl0;
+        }
+    }
+    return LValueOld != If_ObjLValue(pObj);
 }
 
-
 ////////////////////////////////////////////////////////////////////////
 ///                       END OF FILE                                ///
 ////////////////////////////////////////////////////////////////////////