Experiment with technology mapping.

1 files changed, 178 insertions, 95 deletions

diff --git a/src/base/abci/abcIfif.c b/src/base/abci/abcIfif.c
index 146e2b5c..33f1299c 100644
--- a/src/base/abci/abcIfif.c
+++ b/src/base/abci/abcIfif.c
@@ -19,6 +19,7 @@
 ***********************************************************************/
 
 #include "src/base/abc/abc.h"
+#include "src/map/if/if.h"
 
 ABC_NAMESPACE_IMPL_START
 
@@ -26,28 +27,29 @@ ABC_NAMESPACE_IMPL_START
 ///                        DECLARATIONS                              ///
 ////////////////////////////////////////////////////////////////////////
 
+#define IFIF_MAX_LEAVES 6
+
+
 typedef struct Abc_IffObj_t_       Abc_IffObj_t;
 struct Abc_IffObj_t_ 
 {
-    int              Delay0;       // separate delay 
-    int              Delay1;       // combined delay
-    int              nLeaves;
-    int              pLeaves[6];
+    float            Delay[IFIF_MAX_LEAVES+1];     // separate delay
+//    int              nLeaves;
+//    int              pLeaves[IFIF_MAX_LEAVES];
 };
 
 typedef struct Abc_IffMan_t_       Abc_IffMan_t;
 struct Abc_IffMan_t_ 
 {
     Abc_Ntk_t *      pNtk;
-    int              nObjs;
-    int              nDelayLut;
-    int              nDegree;
-    int              fVerbose;
+    Ifif_Par_t *     pPars;
     // internal data
+    int              nObjs;
     Abc_IffObj_t *   pObjs;
 };
 
-static inline Abc_IffObj_t *  Abc_IffObj( Abc_IffMan_t * p, int i )      { assert( i >= 0 && i < p->nObjs ); return p->pObjs + i;   }
+static inline Abc_IffObj_t *  Abc_IffObj( Abc_IffMan_t * p, int i )                             { assert( i >= 0 && i < p->nObjs ); return p->pObjs + i;   }
+static inline float           Abc_IffDelay( Abc_IffMan_t * p, Abc_Obj_t * pObj, int fDelay1 )   { return Abc_IffObj(p, Abc_ObjId(pObj))->Delay[fDelay1];   }
 
 ////////////////////////////////////////////////////////////////////////
 ///                     FUNCTION DEFINITIONS                         ///
@@ -64,16 +66,14 @@ static inline Abc_IffObj_t *  Abc_IffObj( Abc_IffMan_t * p, int i )      { asser
   SeeAlso     []
 
 ***********************************************************************/
-Abc_IffMan_t * Abc_NtkIfifStart( Abc_Ntk_t * pNtk, int nDelayLut, int nDegree, int fVerbose )
+Abc_IffMan_t * Abc_NtkIfifStart( Abc_Ntk_t * pNtk, Ifif_Par_t * pPars )
 {
     Abc_IffMan_t * p;
     p = ABC_CALLOC( Abc_IffMan_t, 1 );
     p->pNtk       = pNtk;
-    p->nObjs      = Abc_NtkObjNumMax( pNtk );
-    p->nDelayLut  = nDelayLut;
-    p->nDegree    = nDegree; 
-    p->fVerbose   = fVerbose;
+    p->pPars      = pPars;
     // internal data
+    p->nObjs      = Abc_NtkObjNumMax( pNtk );
     p->pObjs      = ABC_CALLOC( Abc_IffObj_t, p->nObjs );
     return p;
 }
@@ -84,10 +84,9 @@ void Abc_NtkIfifStop( Abc_IffMan_t * p )
     ABC_FREE( p );
 }
 
-
 /**Function*************************************************************
 
-  Synopsis    [Compare nodes by Delay1 stored in pObj->iTemp.]
+  Synopsis    [Collects fanins into ppNodes in decreasing order.]
 
   Description []
                
@@ -96,17 +95,34 @@ void Abc_NtkIfifStop( Abc_IffMan_t * p )
   SeeAlso     []
 
 ***********************************************************************/
-int Abc_ObjIfifCompare( Abc_Obj_t ** pp1, Abc_Obj_t ** pp2 )
+void Abc_ObjSortByDelay( Abc_IffMan_t * p, Abc_Obj_t * pObj, int fDelay1, Abc_Obj_t ** ppNodes )
 {
-    Abc_Obj_t * pObj1 = *pp1;
-    Abc_Obj_t * pObj2 = *pp2;
-    assert( Abc_ObjIsNode(pObj1) && Abc_ObjIsNode(pObj2) );
-    return (int)pObj2->iTemp - (int)pObj1->iTemp;
+    Abc_Obj_t * pFanin;
+    int i, a, k = 0;
+    Abc_ObjForEachFanin( pObj, pFanin, i )
+    {
+        ppNodes[k++] = pFanin;
+        if ( Abc_ObjIsCi(pFanin) )
+            continue;
+        for ( a = k-1; a > 0; a-- )
+            if ( Abc_IffDelay(p, ppNodes[a-1], fDelay1) + p->pPars->pLutDelays[a-1] < Abc_IffDelay(p, ppNodes[a], fDelay1) + p->pPars->pLutDelays[a] )
+                ABC_SWAP( Abc_Obj_t *, ppNodes[a-1], ppNodes[a] );
+    }
+/*
+    for ( a = 1; a < k; a++ )
+    {
+        float D1 = Abc_IffDelay(p, ppNodes[a-1], fDelay1);
+        float D2 = Abc_IffDelay(p, ppNodes[a], fDelay1);
+        if ( Abc_ObjIsCi(ppNodes[a-1]) || Abc_ObjIsCi(ppNodes[a]) )
+            continue;
+        assert( Abc_IffDelay(p, ppNodes[a-1], fDelay1) + p->pPars->pLutDelays[a-1] >= Abc_IffDelay(p, ppNodes[a], fDelay1) + p->pPars->pLutDelays[a] - 0.01 );
+    }
+*/
 }
 
 /**Function*************************************************************
 
-  Synopsis    [This is the delay which object may have all by itself.]
+  Synopsis    [This is the delay which object has all by itself.]
 
   Description [This delay is stored in Delay0.]
                
@@ -115,86 +131,114 @@ int Abc_ObjIfifCompare( Abc_Obj_t ** pp1, Abc_Obj_t ** pp2 )
   SeeAlso     []
 
 ***********************************************************************/
-int Abc_ObjDelay0( Abc_IffMan_t * p, Abc_Obj_t * pObj )
+float Abc_ObjDelay0( Abc_IffMan_t * p, Abc_Obj_t * pObj )
 {
-    Abc_Obj_t * pFanin;
-    int i, Delay0 = 0;
-    Abc_ObjForEachFanin( pObj, pFanin, i )
-        Delay0 = Abc_MaxInt( Delay0, Abc_IffObj(p, Abc_ObjId(pFanin))->Delay1 );
-    return p->nDelayLut + Delay0;
+    int i;
+    float Delay0 = 0;
+    Abc_Obj_t * ppNodes[6];
+    Abc_ObjSortByDelay( p, pObj, 1, ppNodes );
+    for ( i = 0; i < Abc_ObjFaninNum(pObj); i++ )
+        Delay0 = Abc_MaxFloat( Delay0, Abc_IffDelay(p, ppNodes[i], 1) + p->pPars->pLutDelays[i] );
+    return Delay0;
 }
 
 /**Function*************************************************************
 
-  Synopsis    [This is the delay object may have in a group.]
+  Synopsis    [This is the delay object has in the structure.]
 
-  Description [This delay is stored in Delay1 and pObj->iTemp.]
+  Description [This delay is stored in Delay1.]
                
   SideEffects []
 
   SeeAlso     []
 
 ***********************************************************************/
-int Abc_ObjDelay1( Abc_IffMan_t * p, Abc_Obj_t * pObj )
+float Abc_ObjDelay1( Abc_IffMan_t * p, Abc_Obj_t * pObj )
 {
-    Abc_IffObj_t * pIfif;
-    Abc_Obj_t * pNodes[6], * pFanin;
-    int i, nNodes, Delay1, DelayWorst;
+    int i, fVeryVerbose = 0;
+//    Abc_IffObj_t * pIfif = Abc_IffObj( p, Abc_ObjId(pObj) );
+    Abc_Obj_t * ppNodes[6];
+    float Delay1, DelayNew;
 
-    // find the object structure
-    pIfif = Abc_IffObj( p, Abc_ObjId(pObj) );
+    if ( Abc_ObjFaninNum(pObj) == 0 )
+        return 0;
 
-    // collect relevant nodes
-    nNodes = 0;
-    Abc_ObjForEachFanin( pObj, pFanin, i )
-        if ( Abc_ObjIsNode(pFanin) )
+    // sort fanins by delay1+LutDelay
+    Abc_ObjSortByDelay( p, pObj, 1, ppNodes );
+
+    // print verbose results
+    if ( fVeryVerbose )
+    {
+        printf( "Object %d   Level %d\n", Abc_ObjId(pObj), Abc_ObjLevel(pObj) );
+        for ( i = 0; i < Abc_ObjFaninNum(pObj); i++ )
         {
-            assert( pFanin->iTemp >= p->nDelayLut );
-            pNodes[nNodes++] = pFanin;
+            printf( "Fanin %d : ", i );
+            printf( "D0 %3.2f  ",      Abc_IffDelay(p, ppNodes[i], 0) );
+            printf( "D0* %3.2f     ",  Abc_IffDelay(p, ppNodes[i], 0) + p->pPars->pLutDelays[i] - p->pPars->DelayWire );
+            printf( "D1 %3.2f",        Abc_IffDelay(p, ppNodes[i], 1) + p->pPars->pLutDelays[i] );
+            printf( "\n" );
         }
-
-    // process the result
+        printf( "\n" );
+    }
+/*
+    // for the first nDegree delays, sort them by the minimum Delay1+LutDelay and Delay0-Wire+LutDelay
     Delay1 = 0;
     pIfif->nLeaves = 0;
-    if ( nNodes > 0 )
+    for ( i = 0; i < Abc_ObjFaninNum(pObj); i++ )
     {
-        int fVerbose = 0;
-
-        // sort fanins by delay
-        qsort( (void *)pNodes, nNodes, sizeof(Abc_Obj_t *), (int (*)(const void *, const void *)) Abc_ObjIfifCompare );
-        assert( pNodes[0]->iTemp >= pNodes[nNodes-1]->iTemp );
-
-        if ( fVerbose )
+        if ( Abc_ObjIsNode(ppNodes[i]) && pIfif->nLeaves < p->pPars->nDegree )
         {
-            for ( i = 0; i < nNodes; i++ )
-            {
-                printf( "Fanin %d : ", i );
-                printf( "D0 %4d  ",    Abc_IffObj(p, Abc_ObjId(pNodes[i]))->Delay0 );
-                printf( "D0* %4d    ", Abc_IffObj(p, Abc_ObjId(pNodes[0]))->Delay0 - (p->nDelayLut-1) );
-                printf( "D1 %4d  ",    Abc_IffObj(p, Abc_ObjId(pNodes[i]))->Delay1 );
-                printf( "\n" );
-            }
-            printf( "\n" );
+            DelayNew = Abc_MinFloat( Abc_IffDelay(p, ppNodes[i], 1) + p->pPars->pLutDelays[i], 
+                                     Abc_IffDelay(p, ppNodes[i], 0) + p->pPars->pLutDelays[i] - p->pPars->DelayWire );
+            pIfif->pLeaves[pIfif->nLeaves++] = Abc_ObjId(ppNodes[i]);
         }
+        else
+            DelayNew = Abc_IffDelay(p, ppNodes[i], 1) + p->pPars->pLutDelays[i];
+        Delay1 = Abc_MaxFloat( Delay1, DelayNew );
+    }
+*/
+    // for the first nDegree delays, sort them by the minimum Delay1+LutDelay and Delay0-Wire+LutDelay
+    Delay1 = 0;
+    for ( i = 0; i < Abc_ObjFaninNum(pObj); i++ )
+    {
+        if ( i < p->pPars->nDegree )
+            DelayNew = Abc_MinFloat( Abc_IffDelay(p, ppNodes[i], 1) + p->pPars->pLutDelays[i], 
+                                     Abc_IffDelay(p, ppNodes[i], 0) + p->pPars->pLutDelays[i] - p->pPars->DelayWire );
+        else
+            DelayNew = Abc_IffDelay(p, ppNodes[i], 1) + p->pPars->pLutDelays[i];
+        Delay1 = Abc_MaxFloat( Delay1, DelayNew );
+    }
+    assert( Delay1 > 0 );
+    return Delay1;
+}
 
-        // get the worst-case fanin delay
-//        DelayWorst = Abc_IffObj(p, Abc_ObjId(pNodes[0]))->Delay0 - (p->nDelayLut-1);
-        DelayWorst = -1;
-        // find the delay and remember fanins
-        for ( i = 0; i < nNodes; i++ )
-        {
-            if ( pIfif->nLeaves < p->nDegree && Abc_IffObj(p, Abc_ObjId(pNodes[i]))->Delay1 > DelayWorst )
-            {
-                Delay1 = Abc_MaxInt( Delay1, Abc_IffObj(p, Abc_ObjId(pNodes[i]))->Delay0 - (p->nDelayLut-1) );
-                pIfif->pLeaves[pIfif->nLeaves++] = Abc_ObjId(pNodes[i]);
-            }
-            else
-                Delay1 = Abc_MaxInt( Delay1, Abc_IffObj(p, Abc_ObjId(pNodes[i]))->Delay1 );
-        }
-//        assert( pIfif->nLeaves > 0 );
-        assert( Delay1 > 0 );
+
+/**Function*************************************************************
+
+  Synopsis    [This is the delay which object has all by itself.]
+
+  Description [This delay is stored in Delay0.]
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+float Abc_ObjDelayDegree( Abc_IffMan_t * p, Abc_Obj_t * pObj, int d )
+{
+    int i;
+    float Delay0 = 0, DelayNew;
+    Abc_Obj_t * ppNodes[6];
+    assert( d >= 0 && d <= p->pPars->nDegree );
+    Abc_ObjSortByDelay( p, pObj, p->pPars->nDegree, ppNodes );
+    for ( i = 0; i < Abc_ObjFaninNum(pObj); i++ )
+    {
+        DelayNew = Abc_IffDelay(p, ppNodes[i], p->pPars->nDegree) + p->pPars->pLutDelays[i];
+        if ( i == 0 && d > 0 )
+            DelayNew = Abc_MinFloat(DelayNew, Abc_IffDelay(p, ppNodes[i], d-1) + p->pPars->pLutDelays[i] - p->pPars->DelayWire );
+        Delay0 = Abc_MaxFloat( Delay0, DelayNew );
     }
-    return p->nDelayLut + Delay1;
+    return Delay0;
 }
 
 /**Function*************************************************************
@@ -208,26 +252,36 @@ int Abc_ObjDelay1( Abc_IffMan_t * p, Abc_Obj_t * pObj )
   SeeAlso     []
 
 ***********************************************************************/
-void Abc_NtkPerformIfif( Abc_Ntk_t * pNtk, int nDelayLut, int nDegree, int fVerbose )
+void Abc_NtkPerformIfif( Abc_Ntk_t * pNtk, Ifif_Par_t * pPars )
 {
     Abc_IffMan_t * p;
     Abc_IffObj_t * pIffObj;
     Vec_Ptr_t * vNodes;
     Abc_Obj_t * pObj;
-    int i, Delay, nLutSize = Abc_NtkGetFaninMax( pNtk );
-    if ( nLutSize > 6 )
-    {
-        printf( "LUT size (%d) is more than 6.\n", nLutSize );
-        return;
-    }
+    float Delay, Delay10, DegreeFinal;
+    int i, d, Count10;
+    assert( pPars->pLutLib->LutMax >= 0 && pPars->pLutLib->LutMax <= IFIF_MAX_LEAVES );
+    assert( pPars->nLutSize >= 0 && pPars->nLutSize <= IFIF_MAX_LEAVES );
+    assert( pPars->nDegree >= 0 && pPars->nDegree <= IFIF_MAX_LEAVES );
     // convert to AIGs
     Abc_NtkToAig( pNtk );
+    Abc_NtkLevel( pNtk );
 
-    assert( nDegree >= 0 && nDegree <= 6 );
+    // print parameters
+    if ( pPars->fVerbose )
+    {
+        printf( "Running mapper into LUT structures with the following parameters:\n" );
+        printf( "Pin+Wire: {" );
+        for ( i = 0; i < pPars->pLutLib->LutMax; i++ )
+            printf( " %3.2f", pPars->pLutDelays[i] );
+        printf( " }  " );    
+        printf( "Wire %3.2f  Degree %d  Type: %s\n", 
+            pPars->DelayWire, pPars->nDegree, pPars->fCascade? "Cascade" : "Cluster" );
+    }
 
     // start manager
-    p = Abc_NtkIfifStart( pNtk, nDelayLut, nDegree, fVerbose );
-//    printf( "Running experiment with LUT delay %d and degree %d (LUT size is %d).\n", nDelayLut, nDegree, nLutSize );
+    p = Abc_NtkIfifStart( pNtk, pPars );
+//    printf( "Running experiment with LUT delay %d and degree %d (LUT size is %d).\n", DelayWire, nDegree, nLutSize );
 
     // compute the delay
     vNodes = Abc_NtkDfs( pNtk, 0 );
@@ -235,21 +289,50 @@ void Abc_NtkPerformIfif( Abc_Ntk_t * pNtk, int nDelayLut, int nDegree, int fVerb
     {
         assert( Abc_ObjIsNode(pObj) );
         pIffObj = Abc_IffObj( p, Abc_ObjId(pObj) );
-        pIffObj->Delay0 = Abc_ObjDelay0( p, pObj );
-        pIffObj->Delay1 = Abc_ObjDelay1( p, pObj );
-        pObj->iTemp = pIffObj->Delay1;
 
-//        printf( "Node %3d : Lev =%3d  Delay0 =%4d  Delay1 =%4d  Leaves =%3d.\n", 
-//            Abc_ObjId(pObj), Abc_ObjLevel(pObj), pIffObj->Delay0, pIffObj->Delay1, pIffObj->nLeaves );
+        if ( pPars->fCascade )
+        {
+            for ( d = 0; d <= pPars->nDegree; d++ )
+                pIffObj->Delay[d] = Abc_ObjDelayDegree( p, pObj, d );
+        }
+        else
+        {
+            pIffObj->Delay[0] = Abc_ObjDelay0( p, pObj );
+            pIffObj->Delay[1] = Abc_ObjDelay1( p, pObj );
+        }
+    }
+
+    // get final degree number
+    if ( pPars->fCascade )
+        DegreeFinal = pPars->nDegree;
+    else
+        DegreeFinal = 1;
+
+    if ( p->pPars->fVeryVerbose )
+    Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, i )
+    {
+        printf( "Node %3d : Lev =%3d   ",  Abc_ObjId(pObj), Abc_ObjLevel(pObj) );
+        for ( d = 0; d <= DegreeFinal; d++ )
+            printf( "Del%d =%4.2f  ", d, Abc_IffDelay(p, pObj, d) );
+        printf( "\n" );
     }
     Vec_PtrFree( vNodes );
 
+
     // consider delay at the outputs
     Delay = 0;
     Abc_NtkForEachCo( pNtk, pObj, i )
-        Delay = Abc_MaxInt( Delay, Abc_IffObj(p, Abc_ObjId(Abc_ObjFanin0(pObj)))->Delay1 );
+        Delay = Abc_MaxFloat( Delay, Abc_IffDelay(p, Abc_ObjFanin0(pObj), DegreeFinal) );
+    Delay10 = 0.9 * Delay;
+
+    // consider delay at the outputs
+    Count10 = 0;
+    Abc_NtkForEachCo( pNtk, pObj, i )
+        if ( Abc_IffDelay(p, Abc_ObjFanin0(pObj), DegreeFinal) >= Delay10 )
+            Count10++;
 
-    printf( "Critical delay is %5d (%7.2f).\n", Delay, 1.0 * Delay / nDelayLut );
+    printf( "Critical delay %5.2f. Critical outputs %5.2f %%\n", Delay, 100.0 * Count10 / Abc_NtkCoNum(pNtk) );
+//    printf( "%.2f %.2f\n", Delay, 100.0 * Count10 / Abc_NtkCoNum(pNtk) );
 
     // derive a new network