Added generation of MFFC for the network (improvements).

2 files changed, 124 insertions, 25 deletions

diff --git a/src/base/abci/abc.c b/src/base/abci/abc.c
index d1e2b0f2..ea041f67 100644
--- a/src/base/abci/abc.c
+++ b/src/base/abci/abc.c
@@ -8678,6 +8678,7 @@ int Abc_CommandTest( Abc_Frame_t * pAbc, int argc, char ** argv )
 */
 
 //    Abc_NtkHelloWorld( pNtk );
+//    Abc_NktMffcTest( pNtk );
     Abc_NktMffcServerTest( pNtk );
     return 0;
 usage:
diff --git a/src/base/abci/abcMffc.c b/src/base/abci/abcMffc.c
index ec43b71d..1d33c89e 100644
--- a/src/base/abci/abcMffc.c
+++ b/src/base/abci/abcMffc.c
@@ -149,6 +149,26 @@ void Abc_MffcCollectLeaves( Vec_Ptr_t * vNodes, Vec_Ptr_t * vLeaves )
 
 /**Function*************************************************************
 
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Vec_IntPrint( Vec_Int_t * vVec )
+{
+    int i, Entry;
+    Vec_IntForEachEntry( vVec, Entry, i )
+        printf( "%d ", Entry );
+    printf( "\n" );
+}
+
+
+/**Function*************************************************************
+
   Synopsis    [Collects internal nodes that are roots of MFFCs.]
 
   Description []
@@ -169,7 +189,8 @@ Vec_Ptr_t * Abc_NktMffcMarkRoots( Abc_Ntk_t * pNtk, int fSkipPis )
     Abc_NtkForEachCo( pNtk, pObj, i )
     {
         pObj = Abc_ObjFanin0( pObj );
-        if ( Abc_ObjIsCi(pObj) || Abc_ObjFaninNum(pObj) == 0 || pObj->fMarkA )
+//        if ( Abc_ObjIsCi(pObj) || Abc_ObjFaninNum(pObj) == 0 || pObj->fMarkA )
+        if ( Abc_ObjIsCi(pObj) || pObj->fMarkA )
             continue;
         pObj->fMarkA = 1;
         Vec_PtrPush( vRoots, pObj );
@@ -435,6 +456,47 @@ void Abc_NktMffcPrint( char * pFileName, Abc_Obj_t ** pNodes, int nNodes, Vec_Pt
   SeeAlso     []
 
 ***********************************************************************/
+void Abc_NktMffcPrintInt( char * pFileName, Abc_Ntk_t * pNtk, Vec_Int_t * vRoots, Vec_Int_t * vNodes, Vec_Int_t * vLeaves )
+{
+    FILE * pFile;
+    Abc_Obj_t * pObj, * pFanin;
+    int i, k;
+    // convert the network
+    Abc_NtkToSop( pNtk, 0 );
+    // write the file
+    pFile = fopen( pFileName, "wb" );
+    fprintf( pFile, ".model %s_part\n", pNtk->pName );
+    fprintf( pFile, ".inputs" );
+    Abc_NtkForEachObjVec( pNtk, vLeaves, pObj, i )
+        fprintf( pFile, " %s", Abc_ObjName(pObj) );
+    fprintf( pFile, "\n" );
+    fprintf( pFile, ".outputs" );
+    Abc_NtkForEachObjVec( pNtk, vRoots, pObj, i )
+        fprintf( pFile, " %s", Abc_ObjName(pObj) );
+    fprintf( pFile, "\n" );
+    Abc_NtkForEachObjVec( pNtk, vNodes, pObj, i )
+    {
+        fprintf( pFile, ".names" );
+        Abc_ObjForEachFanin( pObj, pFanin, k )
+            fprintf( pFile, " %s", Abc_ObjName(pFanin) );
+        fprintf( pFile, " %s", Abc_ObjName(pObj) );
+        fprintf( pFile, "\n%s", (char *)pObj->pData );
+    }
+    fprintf( pFile, ".end\n" );
+    fclose( pFile );
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Testbench.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
 void Abc_NktMffcTest( Abc_Ntk_t * pNtk )
 {
     char pFileName[1000];
@@ -947,12 +1009,13 @@ void Abc_NktMffcFree( Vec_Ptr_t * vRoots, Vec_Ptr_t * vFanins, Vec_Ptr_t * vFano
   SeeAlso     []
 
 ***********************************************************************/
-int Abc_NktMffcCostTwo( Vec_Int_t * vSupp1, Vec_Int_t * vSupp2, int Limit )
+double Abc_NktMffcCostTwo( Vec_Int_t * vSupp1, Vec_Int_t * vSupp2, int Volume, int Limit )
 {
     int nCommon = Vec_IntTwoCountCommon( vSupp1, vSupp2 );
+//printf( "s1=%2d s2=%2d c=%2d v=%2d   ", Vec_IntSize(vSupp1), Vec_IntSize(vSupp2), nCommon, Volume );
     if ( Vec_IntSize(vSupp1) + Vec_IntSize(vSupp2) - nCommon > Limit )
-        return -ABC_INFINITY;
-    return 3 * nCommon - Vec_IntSize(vSupp1) - Vec_IntSize(vSupp2);
+        return (double)-ABC_INFINITY;
+    return 0.6 * nCommon - 1.2 * Vec_IntSize(vSupp2) + 0.8 * Volume;
 }
 
 /**Function*************************************************************
@@ -971,7 +1034,6 @@ Vec_Int_t * Abc_NktMffcSupport( Vec_Ptr_t * vThis, Vec_Ptr_t * vFanins )
     Vec_Int_t * vIns, * vIns2, * vTemp;
     Abc_Obj_t * pObj;
     int i;
-//    int Entry;
     vIns = Vec_IntAlloc( 100 );
     Vec_PtrForEachEntry( Abc_Obj_t *, vThis, pObj, i )
     {
@@ -979,9 +1041,6 @@ Vec_Int_t * Abc_NktMffcSupport( Vec_Ptr_t * vThis, Vec_Ptr_t * vFanins )
         vIns  = Vec_IntTwoMerge( vTemp = vIns, vIns2 );
         Vec_IntFree( vTemp );
     }
-//Vec_IntForEachEntry( vIns, Entry, i )
-//printf( "%d ", Entry );
-//printf( "\n" );
     return vIns;
 }
 
@@ -996,11 +1055,12 @@ Vec_Int_t * Abc_NktMffcSupport( Vec_Ptr_t * vThis, Vec_Ptr_t * vFanins )
   SeeAlso     []
 
 ***********************************************************************/
-Abc_Obj_t * Abc_NktMffcFindBest( Abc_Ntk_t * pNtk, Vec_Int_t * vMarks, Vec_Int_t * vIns, Vec_Ptr_t * vFanins, Vec_Ptr_t * vFanouts, int Limit )
+Abc_Obj_t * Abc_NktMffcFindBest( Abc_Ntk_t * pNtk, Vec_Int_t * vMarks, Vec_Int_t * vIns, Vec_Ptr_t * vFanins, Vec_Ptr_t * vFanouts, Vec_Ptr_t * vVolumes, int Limit )
 {
     Vec_Int_t * vIns2, * vOuts, * vOuts2, * vTemp;
     Abc_Obj_t * pPivot2, * pObj, * pObjBest = NULL;
-    int i, Cost, CostBest = -ABC_INFINITY;
+    double Cost, CostBest = (double)-ABC_INFINITY;
+    int i, Volume;
     // collect the fanouts of the fanins
     vOuts = Vec_IntAlloc( 100 );
     Abc_NtkForEachObjVec( pNtk, vIns, pObj, i )
@@ -1016,9 +1076,11 @@ Abc_Obj_t * Abc_NktMffcFindBest( Abc_Ntk_t * pNtk, Vec_Int_t * vMarks, Vec_Int_t
     {       
         if ( Vec_IntEntry(vMarks, Abc_ObjId(pPivot2)) == 0 )
             continue;
-        vIns2 = (Vec_Int_t *)Vec_PtrEntry( vFanins, Abc_ObjId(pPivot2) );
-        Cost  = Abc_NktMffcCostTwo( vIns, vIns2, Limit );
-        if ( Cost == -ABC_INFINITY )
+        vIns2  = (Vec_Int_t *)Vec_PtrEntry( vFanins, Abc_ObjId(pPivot2) );
+        Volume = Vec_IntSize((Vec_Int_t *)Vec_PtrEntry(vVolumes, Abc_ObjId(pPivot2)));
+        Cost   = Abc_NktMffcCostTwo( vIns, vIns2, Volume, Limit );
+//printf( "%5d  %2d\n", Abc_ObjId(pPivot2), Cost  );
+        if ( Cost == (double)-ABC_INFINITY )
             continue;
         if ( pObjBest == NULL || CostBest < Cost )
         {
@@ -1026,6 +1088,7 @@ Abc_Obj_t * Abc_NktMffcFindBest( Abc_Ntk_t * pNtk, Vec_Int_t * vMarks, Vec_Int_t
             CostBest = Cost;
         }
     }    
+//printf( "Choosing %d\n", pObjBest->Id );
     Vec_IntFree( vOuts );
     return pObjBest;
 }
@@ -1051,17 +1114,34 @@ Vec_Int_t * Abc_NktMffcSaveOne( Vec_Ptr_t * vThis, Vec_Ptr_t * vVolumes )
     {
         vVolume = (Vec_Int_t *)Vec_PtrEntry( vVolumes, Abc_ObjId(pObj) );
         Vec_IntForEachEntry( vVolume, Entry, k )
-        {
             Vec_IntPush( vResult, Entry );
-//printf( "%d ", Entry );
-        }
     }
-//printf( "\n" );
     return vResult;
 }
 
 /**Function*************************************************************
 
+  Synopsis    [Procedure used for sorting the nodes in decreasing order of levels.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int Abc_NodeCompareVolumeDecrease( Abc_Obj_t ** pp1, Abc_Obj_t ** pp2 )
+{
+    int Diff = Abc_ObjRegular(*pp1)->iTemp - Abc_ObjRegular(*pp2)->iTemp;
+    if ( Diff > 0 )
+        return -1;
+    if ( Diff < 0 ) 
+        return 1;
+    return 0; 
+}
+
+/**Function*************************************************************
+
   Synopsis    [Create the network of supernodes.]
 
   Description [Returns array of interger arrays of IDs of nodes
@@ -1083,15 +1163,21 @@ Vec_Ptr_t * Abc_NktMffcServer( Abc_Ntk_t * pNtk, int nInMax, int nOutMax )
     vResult = Vec_PtrAlloc( 100 );
     // create fanins/fanouts
     vPivots = Abc_NktMffcDerive( pNtk, &vFanins, &vFanouts, &vVolumes );
+    // sort by their MFFC size
+    Vec_PtrForEachEntry( Abc_Obj_t *, vPivots, pObj, i )
+        pObj->iTemp = Vec_IntSize((Vec_Int_t *)Vec_PtrEntry(vVolumes, Abc_ObjId(pObj)));
+    Vec_PtrSort( vPivots, (int (*)(void))Abc_NodeCompareVolumeDecrease ); 
     // create marks
     vMarks = Vec_IntStart( Abc_NtkObjNumMax(pNtk) );
     Vec_PtrForEachEntry( Abc_Obj_t *, vPivots, pObj, i )
-        if ( Abc_ObjIsNode(pObj) )
+        if ( Abc_ObjIsNode(pObj) && Vec_IntSize((Vec_Int_t *)Vec_PtrEntry(vVolumes, Abc_ObjId(pObj))) > 1 )
             Vec_IntWriteEntry( vMarks, Abc_ObjId(pObj), 1 );
     // consider nodes in the order of the marks
     vThis = Vec_PtrAlloc( 10 );
+//    while ( 1 )
     Vec_PtrForEachEntry( Abc_Obj_t *, vPivots, pObj, i )
     {
+//        pObj = Abc_NtkObj( pNtk, 589 );
         if ( Vec_IntEntry(vMarks, Abc_ObjId(pObj)) == 0 )
             continue;
         // start the set
@@ -1111,7 +1197,7 @@ Vec_Ptr_t * Abc_NktMffcServer( Abc_Ntk_t * pNtk, int nInMax, int nOutMax )
             // quit if exceeded the limit
             vLeaves = Abc_NktMffcSupport( vThis, vFanins );
             assert( Vec_IntSize(vLeaves) <= nInMax );
-            pObj2 = Abc_NktMffcFindBest( pNtk, vMarks, vLeaves, vFanins, vFanouts, nInMax );
+            pObj2 = Abc_NktMffcFindBest( pNtk, vMarks, vLeaves, vFanins, vFanouts, vVolumes, nInMax );
             Vec_IntFree( vLeaves );
             // quit if there is no extension
             if ( pObj2 == NULL )
@@ -1120,6 +1206,7 @@ Vec_Ptr_t * Abc_NktMffcServer( Abc_Ntk_t * pNtk, int nInMax, int nOutMax )
             Vec_IntWriteEntry( vMarks, Abc_ObjId(pObj2), 0 );
         }
         Vec_PtrPush( vResult, Abc_NktMffcSaveOne(vThis, vVolumes) );
+//        break;
     }
     Vec_PtrFree( vThis );
     Vec_IntFree( vMarks );
@@ -1141,10 +1228,11 @@ Vec_Ptr_t * Abc_NktMffcServer( Abc_Ntk_t * pNtk, int nInMax, int nOutMax )
 ***********************************************************************/
 void Abc_NktMffcServerTest( Abc_Ntk_t * pNtk )
 {
+    char pFileName[1000];
     Vec_Ptr_t * vGlobs;
     Vec_Int_t * vGlob, * vLeaves, * vRoots;
-    double Cost;
-    int i, nNodes = 0, clk = clock();
+    double Cost, CostAll = 0.0;
+    int i, k, Entry, nNodes = 0, clk = clock();
     vGlobs  = Abc_NktMffcServer( pNtk, 18, 3 );
     vLeaves = Vec_IntAlloc( 100 );
     vRoots  = Vec_IntAlloc( 100 );
@@ -1152,12 +1240,22 @@ void Abc_NktMffcServerTest( Abc_Ntk_t * pNtk )
     {
         nNodes += Vec_IntSize(vGlob);
         Abc_NktMffCollectLeafRootInt( pNtk, vGlob, vLeaves, vRoots );
+        if ( Vec_IntSize(vGlob) <= Vec_IntSize(vRoots) )
+            continue;
         Cost = 1.0 * Vec_IntSize(vGlob)/(Vec_IntSize(vLeaves) + Vec_IntSize(vRoots));
-        if ( Cost < 0.3 || Vec_IntSize(vGlob) < 5 )
+        CostAll += Cost;
+        if ( Cost < 0.4 )
             continue;
-        printf( "%4d : Root =%3d. Leaf =%3d. Node =%4d. ", 
+
+        printf( "%6d : Root =%3d. Leaf =%3d. Node =%4d. ", 
             i, Vec_IntSize(vRoots), Vec_IntSize(vLeaves), Vec_IntSize(vGlob) );
-        printf( "Cost =%6.2f\n", Cost );
+        printf( "Cost =%6.2f     ", Cost );
+        Vec_IntForEachEntry( vRoots, Entry, k )
+            printf( "%d ", Entry );
+        printf( "\n" );
+
+        sprintf( pFileName, "%s_mffc%04d_%02d.blif", Abc_NtkName(pNtk), i, Vec_IntSize(vGlob) );
+        Abc_NktMffcPrintInt( pFileName, pNtk, vRoots, vGlob, vLeaves );
     }
     Vec_IntFree( vLeaves );
     Vec_IntFree( vRoots );
@@ -1165,10 +1263,10 @@ void Abc_NktMffcServerTest( Abc_Ntk_t * pNtk )
         Vec_IntFree( vGlob );
     Vec_PtrFree( vGlobs );
     printf( "Total = %6d.  Nodes = %6d.  ", Abc_NtkNodeNum(pNtk), nNodes );
+    printf( "Cost = %6.2f  ", CostAll );
     Abc_PrintTime( 1, "Time", clock() - clk );
 }
 
-
 ABC_NAMESPACE_IMPL_END
 
 ////////////////////////////////////////////////////////////////////////