New command &stochsyn for stochastic synthesis.

4 files changed, 429 insertions, 0 deletions

diff --git a/abclib.dsp b/abclib.dsp
index 1726fb18..974d14dd 100644
--- a/abclib.dsp
+++ b/abclib.dsp
@@ -5203,6 +5203,10 @@ SOURCE=.\src\aig\gia\giaStg.c
 # End Source File
 # Begin Source File
 
+SOURCE=.\src\aig\gia\giaStoch.c
+# End Source File
+# Begin Source File
+
 SOURCE=.\src\aig\gia\giaStr.c
 # End Source File
 # Begin Source File
diff --git a/src/aig/gia/giaStoch.c b/src/aig/gia/giaStoch.c
new file mode 100644
index 00000000..390deb26
--- /dev/null
+++ b/src/aig/gia/giaStoch.c
@@ -0,0 +1,321 @@
+/**CFile****************************************************************
+
+  FileName    [giaDeep.c]
+
+  SystemName  [ABC: Logic synthesis and verification system.]
+
+  PackageName [Scalable AIG package.]
+
+  Synopsis    [Experiments with synthesis.]
+
+  Author      [Alan Mishchenko]
+  
+  Affiliation [UC Berkeley]
+
+  Date        [Ver. 1.0. Started - June 20, 2005.]
+
+  Revision    [$Id: giaDeep.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include "gia.h"
+#include "base/main/main.h"
+#include "base/cmd/cmd.h"
+
+ABC_NAMESPACE_IMPL_START
+
+////////////////////////////////////////////////////////////////////////
+///                        DECLARATIONS                              ///
+////////////////////////////////////////////////////////////////////////
+
+////////////////////////////////////////////////////////////////////////
+///                     FUNCTION DEFINITIONS                         ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+static void Vec_PtrFreeFunc( Vec_Ptr_t * p, void (*pFuncItemFree)(void *) ) ___unused;
+static void Vec_PtrFreeFunc( Vec_Ptr_t * p, void (*pFuncItemFree)(void *) )
+{
+    void * pItem; int i;
+    Vec_PtrForEachEntry( void *, p, pItem, i )
+        pFuncItemFree( pItem );
+    Vec_PtrFree( p );
+}
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Gia_ManStochSynthesis( Vec_Ptr_t * vAigs, char * pScript )
+{
+    Gia_Man_t * pGia, * pNew; int i;
+    Vec_PtrForEachEntry( Gia_Man_t *, vAigs, pGia, i )
+    {
+        Gia_Man_t * pCopy = Gia_ManDup(pGia);
+        Abc_FrameUpdateGia( Abc_FrameGetGlobalFrame(), pGia );
+        if ( Abc_FrameIsBatchMode() )
+        {
+            if ( Cmd_CommandExecute(Abc_FrameGetGlobalFrame(), pScript) )
+            {
+                Abc_Print( 1, "Something did not work out with the command \"%s\".\n", pScript );
+                return;
+            }
+        }
+        else
+        {
+            Abc_FrameSetBatchMode( 1 );
+            if ( Cmd_CommandExecute(Abc_FrameGetGlobalFrame(), pScript) )
+            {
+                Abc_Print( 1, "Something did not work out with the command \"%s\".\n", pScript );
+                Abc_FrameSetBatchMode( 0 );
+                return;
+            }
+            Abc_FrameSetBatchMode( 0 );
+        }
+        pNew = Abc_FrameReadGia(Abc_FrameGetGlobalFrame());
+        if ( Gia_ManAndNum(pNew) < Gia_ManAndNum(pCopy) )
+        {
+            Gia_ManStop( pCopy );
+            pCopy = Gia_ManDup( pNew );
+        }
+        Vec_PtrWriteEntry( vAigs, i, pCopy );
+    }
+}
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+Gia_Man_t * Gia_ManDupDivideOne( Gia_Man_t * p, Vec_Int_t * vCis, Vec_Int_t * vAnds, Vec_Int_t * vCos )
+{
+    Gia_Man_t * pNew;
+    Gia_Obj_t * pObj; int i;
+    pNew = Gia_ManStart( 1+Vec_IntSize(vCis)+Vec_IntSize(vAnds)+Vec_IntSize(vCos) );
+    pNew->pName = Abc_UtilStrsav( p->pName );
+    Gia_ManConst0(p)->Value = 0;
+    Gia_ManForEachObjVec( vCis, p, pObj, i )
+        pObj->Value = Gia_ManAppendCi( pNew );
+    Gia_ManForEachObjVec( vAnds, p, pObj, i )
+        pObj->Value = Gia_ManAppendAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
+    Gia_ManForEachObjVec( vCos, p, pObj, i )
+        Gia_ManAppendCo( pNew, pObj->Value );
+    assert( Gia_ManCiNum(pNew) > 0 && Gia_ManCoNum(pNew) > 0 );
+    return pNew;
+}
+Vec_Ptr_t * Gia_ManDupDivide( Gia_Man_t * p, Vec_Wec_t * vCis, Vec_Wec_t * vAnds, Vec_Wec_t * vCos, char * pScript )
+{
+    Vec_Ptr_t * vAigs = Vec_PtrAlloc( Vec_WecSize(vCis) );  int i;
+    for ( i = 0; i < Vec_WecSize(vCis); i++ )
+        Vec_PtrPush( vAigs, Gia_ManDupDivideOne(p, Vec_WecEntry(vCis, i), Vec_WecEntry(vAnds, i), Vec_WecEntry(vCos, i)) );
+    Gia_ManStochSynthesis( vAigs, pScript );
+    return vAigs;
+}
+Gia_Man_t * Gia_ManDupStitch( Gia_Man_t * p, Vec_Wec_t * vCis, Vec_Wec_t * vAnds, Vec_Wec_t * vCos, Vec_Ptr_t * vAigs )
+{
+    Gia_Man_t * pGia, * pNew;
+    Gia_Obj_t * pObj; int i, k;
+    pNew = Gia_ManStart( Gia_ManObjNum(p) );
+    pNew->pName = Abc_UtilStrsav( p->pName );
+    pNew->pSpec = Abc_UtilStrsav( p->pSpec );
+    Gia_ManCleanValue( p );
+    Gia_ManConst0(p)->Value = 0;
+    Gia_ManForEachCi( p, pObj, i )
+        pObj->Value = Gia_ManAppendCi( pNew );
+    Gia_ManHashAlloc( pNew );
+    Vec_PtrForEachEntry( Gia_Man_t *, vAigs, pGia, i )
+    {
+        Vec_Int_t * vCi = Vec_WecEntry( vCis, i );
+        Vec_Int_t * vCo = Vec_WecEntry( vCos, i );
+        Gia_ManCleanValue( pGia );
+        Gia_ManConst0(pGia)->Value = 0;
+        Gia_ManForEachObjVec( vCi, p, pObj, k )
+            Gia_ManCi(pGia, k)->Value = pObj->Value;
+        Gia_ManForEachAnd( pGia, pObj, k )
+            pObj->Value = Gia_ManHashAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
+        Gia_ManForEachObjVec( vCo, p, pObj, k )
+            pObj->Value = Gia_ObjFanin0Copy(Gia_ManCo(pGia, k));
+    }
+    Gia_ManForEachCo( p, pObj, i )
+        Gia_ManAppendCo( pNew, Gia_ObjFanin0Copy(pObj) );
+    pNew = Gia_ManCleanup( pGia = pNew );
+    Gia_ManStop( pGia );
+    Gia_ManSetRegNum( pNew, Gia_ManRegNum(p) );
+    return pNew;
+}
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Gia_ManStochCollect_rec( Gia_Man_t * p, int iObj, Vec_Int_t * vAnds )
+{
+    Gia_Obj_t * pObj;
+    if ( Gia_ObjUpdateTravIdCurrentId( p, iObj ) )
+        return;
+    pObj = Gia_ManObj( p, iObj );
+    if ( Gia_ObjIsCi(pObj) || iObj == 0 )
+        return;
+    assert( Gia_ObjIsAnd(pObj) );
+    Gia_ManStochCollect_rec( p, Gia_ObjFaninId0(pObj, iObj), vAnds );
+    Gia_ManStochCollect_rec( p, Gia_ObjFaninId1(pObj, iObj), vAnds );
+    Vec_IntPush( vAnds, iObj );
+}
+Vec_Wec_t * Gia_ManStochNodes( Gia_Man_t * p, int nMaxSize, int Seed )
+{
+    Vec_Wec_t * vRes = Vec_WecAlloc( 100 ); 
+    Vec_Int_t * vPart = Vec_WecPushLevel( vRes );
+    int i, iStart = Seed % Gia_ManCoNum(p);
+    //Gia_ManLevelNum( p );
+    Gia_ManIncrementTravId( p );
+    for ( i = 0; i < Gia_ManCoNum(p); i++ )
+    {
+        Gia_Obj_t * pObj = Gia_ManCo( p, (iStart+i) % Gia_ManCoNum(p) );
+        if ( Vec_IntSize(vPart) > nMaxSize )
+            vPart = Vec_WecPushLevel( vRes );
+        Gia_ManStochCollect_rec( p, Gia_ObjFaninId0p(p, pObj), vPart );
+    }
+    if ( Vec_IntSize(vPart) == 0 )
+        Vec_WecShrink( vRes, Vec_WecSize(vRes)-1 );
+    //Vec_WecPrint( vRes, 0 );
+    return vRes;
+}
+Vec_Wec_t * Gia_ManStochInputs( Gia_Man_t * p, Vec_Wec_t * vAnds )
+{
+    Vec_Wec_t * vRes = Vec_WecAlloc( 100 ); 
+    Vec_Int_t * vLevel; Gia_Obj_t * pObj; int i, k, iObj;
+    Vec_WecForEachLevel( vAnds, vLevel, i )
+    {
+        Vec_Int_t * vVec = Vec_WecPushLevel( vRes );
+        Gia_ManIncrementTravId( p );
+        Vec_IntForEachEntry( vLevel, iObj, k )
+            Gia_ObjSetTravIdCurrentId( p, iObj );
+        Gia_ManForEachObjVec( vLevel, p, pObj, k )
+        {
+            iObj = Gia_ObjFaninId0p(p, pObj);
+            if ( !Gia_ObjUpdateTravIdCurrentId(p, iObj) )
+                Vec_IntPush( vVec, iObj );
+            iObj = Gia_ObjFaninId1p(p, pObj);
+            if ( !Gia_ObjUpdateTravIdCurrentId(p, iObj) )
+                Vec_IntPush( vVec, iObj );
+        }
+    }
+    return vRes;
+}
+Vec_Wec_t * Gia_ManStochOutputs( Gia_Man_t * p, Vec_Wec_t * vAnds )
+{
+    Vec_Wec_t * vRes = Vec_WecAlloc( 100 ); 
+    Vec_Int_t * vLevel; Gia_Obj_t * pObj; int i, k;
+    Gia_ManCreateRefs( p );
+    Vec_WecForEachLevel( vAnds, vLevel, i )
+    {
+        Vec_Int_t * vVec = Vec_WecPushLevel( vRes );
+        Gia_ManForEachObjVec( vLevel, p, pObj, k )
+        {
+            Gia_ObjRefDecId( p, Gia_ObjFaninId0p(p, pObj) );
+            Gia_ObjRefDecId( p, Gia_ObjFaninId1p(p, pObj) );
+        }
+        Gia_ManForEachObjVec( vLevel, p, pObj, k )
+            if ( Gia_ObjRefNum(p, pObj) )
+                Vec_IntPush( vVec, Gia_ObjId(p, pObj) );
+        Gia_ManForEachObjVec( vLevel, p, pObj, k )
+        {
+            Gia_ObjRefIncId( p, Gia_ObjFaninId0p(p, pObj) );
+            Gia_ObjRefIncId( p, Gia_ObjFaninId1p(p, pObj) );
+        }
+    }
+    return vRes;
+}
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Gia_ManStochSyn( int nMaxSize, int nIters, int TimeOut, int Seed, int fVerbose, char * pScript )
+{
+    abctime nTimeToStop = TimeOut ? Abc_Clock() + TimeOut * CLOCKS_PER_SEC : 0;
+    abctime clkStart    = Abc_Clock();
+    int i, nEnd, nBeg   = Gia_ManAndNum(Abc_FrameReadGia(Abc_FrameGetGlobalFrame()));
+    Abc_Random(1);
+    for ( i = 0; i < 10+Seed; i++ )
+        Abc_Random(0);
+    if ( fVerbose )
+    printf( "Running %d iterations of script \"%s\".\n", nIters, pScript );
+    for ( i = 0; i < nIters; i++ )
+    {
+        abctime clk = Abc_Clock();
+        Gia_Man_t * pGia  = Gia_ManDup( Abc_FrameReadGia(Abc_FrameGetGlobalFrame()) );
+        Vec_Wec_t * vAnds = Gia_ManStochNodes( pGia, nMaxSize, Abc_Random(0) & 0x7FFFFFFF );
+        Vec_Wec_t * vIns  = Gia_ManStochInputs( pGia, vAnds );
+        Vec_Wec_t * vOuts = Gia_ManStochOutputs( pGia, vAnds );
+        Vec_Ptr_t * vAigs = Gia_ManDupDivide( pGia, vIns, vAnds, vOuts, pScript );
+        Gia_Man_t * pNew  = Gia_ManDupStitch( pGia, vIns, vAnds, vOuts, vAigs );
+        Abc_FrameUpdateGia( Abc_FrameGetGlobalFrame(), pNew );
+        if ( fVerbose )
+        printf( "Iteration %3d : Using %3d partitions. Reducing %6d nodes to %6d nodes.  ", 
+            i, Vec_PtrSize(vAigs), Gia_ManAndNum(pGia), Gia_ManAndNum(pNew) ); 
+        if ( fVerbose )
+        Abc_PrintTime( 0, "Time", Abc_Clock() - clk );
+        Gia_ManStop( pGia );
+        Vec_PtrFreeFunc( vAigs, (void (*)(void *)) Gia_ManStop );
+        Vec_WecFree( vAnds );
+        Vec_WecFree( vIns );
+        Vec_WecFree( vOuts );
+        if ( nTimeToStop && Abc_Clock() > nTimeToStop )
+        {
+            printf( "Runtime limit (%d sec) is reached after %d iterations.\n", TimeOut, i );
+            break;
+        }
+    }
+    nEnd = Gia_ManAndNum(Abc_FrameReadGia(Abc_FrameGetGlobalFrame()));
+    if ( fVerbose )
+    printf( "Cumulatively reduced %d AIG nodes after %d iterations.  ", 
+        nBeg - nEnd, nIters, (float)1.0*(Abc_Clock() - clkStart)/CLOCKS_PER_SEC );
+    if ( fVerbose )
+    Abc_PrintTime( 0, "Total time", Abc_Clock() - clkStart );
+}
+
+////////////////////////////////////////////////////////////////////////
+///                       END OF FILE                                ///
+////////////////////////////////////////////////////////////////////////
+
+
+ABC_NAMESPACE_IMPL_END
+
diff --git a/src/aig/gia/module.make b/src/aig/gia/module.make
index 0786ce44..b767c49a 100644
--- a/src/aig/gia/module.make
+++ b/src/aig/gia/module.make
@@ -87,6 +87,7 @@ SRC +=    src/aig/gia/giaAig.c \
     src/aig/gia/giaSpeedup.c \
     src/aig/gia/giaSplit.c \
     src/aig/gia/giaStg.c \
+    src/aig/gia/giaStoch.c \
     src/aig/gia/giaStr.c \
     src/aig/gia/giaSupMin.c \
     src/aig/gia/giaSupp.c \
diff --git a/src/base/abci/abc.c b/src/base/abci/abc.c
index 43d91cfd..fd7b572c 100644
--- a/src/base/abci/abc.c
+++ b/src/base/abci/abc.c
@@ -555,6 +555,7 @@ static int Abc_CommandAbc9Exorcism           ( Abc_Frame_t * pAbc, int argc, cha
 static int Abc_CommandAbc9Mfs                ( Abc_Frame_t * pAbc, int argc, char ** argv );
 static int Abc_CommandAbc9Mfsd               ( Abc_Frame_t * pAbc, int argc, char ** argv );
 static int Abc_CommandAbc9DeepSyn            ( Abc_Frame_t * pAbc, int argc, char ** argv );
+static int Abc_CommandAbc9StochSyn           ( Abc_Frame_t * pAbc, int argc, char ** argv );
 //static int Abc_CommandAbc9PoPart2            ( Abc_Frame_t * pAbc, int argc, char ** argv );
 //static int Abc_CommandAbc9CexCut             ( Abc_Frame_t * pAbc, int argc, char ** argv );
 //static int Abc_CommandAbc9CexMerge           ( Abc_Frame_t * pAbc, int argc, char ** argv );
@@ -1297,6 +1298,7 @@ void Abc_Init( Abc_Frame_t * pAbc )
     Cmd_CommandAdd( pAbc, "ABC9",         "&mfs",          Abc_CommandAbc9Mfs,          0 );
     Cmd_CommandAdd( pAbc, "ABC9",         "&mfsd",         Abc_CommandAbc9Mfsd,         0 );
     Cmd_CommandAdd( pAbc, "ABC9",         "&deepsyn",      Abc_CommandAbc9DeepSyn,      0 );
+    Cmd_CommandAdd( pAbc, "ABC9",         "&stochsyn",     Abc_CommandAbc9StochSyn,     0 );
 //    Cmd_CommandAdd( pAbc, "ABC9",         "&popart2",      Abc_CommandAbc9PoPart2,      0 );
 //    Cmd_CommandAdd( pAbc, "ABC9",         "&cexcut",       Abc_CommandAbc9CexCut,       0 );
 //    Cmd_CommandAdd( pAbc, "ABC9",         "&cexmerge",     Abc_CommandAbc9CexMerge,     0 );
@@ -47552,6 +47554,107 @@ usage:
   SeeAlso     []
 
 ***********************************************************************/
+int Abc_CommandAbc9StochSyn( Abc_Frame_t * pAbc, int argc, char ** argv )
+{
+    extern void Gia_ManStochSyn( int nMaxSize, int nIters, int TimeOut, int Seed, int fVerbose, char * pScript );
+    int c, nMaxSize = 1000, nIters = 10, TimeOut = 0, Seed = 0, fVerbose = 0; char * pScript;
+    Extra_UtilGetoptReset();
+    while ( ( c = Extra_UtilGetopt( argc, argv, "NITSvh" ) ) != EOF )
+    {
+        switch ( c )
+        {
+        case 'N':
+            if ( globalUtilOptind >= argc )
+            {
+                Abc_Print( -1, "Command line switch \"-N\" should be followed by an integer.\n" );
+                goto usage;
+            }
+            nMaxSize = atoi(argv[globalUtilOptind]);
+            globalUtilOptind++;
+            if ( nMaxSize < 0 )
+                goto usage;
+            break;
+        case 'I':
+            if ( globalUtilOptind >= argc )
+            {
+                Abc_Print( -1, "Command line switch \"-I\" should be followed by an integer.\n" );
+                goto usage;
+            }
+            nIters = atoi(argv[globalUtilOptind]);
+            globalUtilOptind++;
+            if ( nIters < 0 )
+                goto usage;
+            break;
+        case 'T':
+            if ( globalUtilOptind >= argc )
+            {
+                Abc_Print( -1, "Command line switch \"-T\" should be followed by an integer.\n" );
+                goto usage;
+            }
+            TimeOut = atoi(argv[globalUtilOptind]);
+            globalUtilOptind++;
+            if ( TimeOut < 0 )
+                goto usage;
+            break;
+        case 'S':
+            if ( globalUtilOptind >= argc )
+            {
+                Abc_Print( -1, "Command line switch \"-S\" should be followed by an integer.\n" );
+                goto usage;
+            }
+            Seed = atoi(argv[globalUtilOptind]);
+            globalUtilOptind++;
+            if ( Seed < 0 )
+                goto usage;
+            break;
+        case 'v':
+            fVerbose ^= 1;
+            break;
+        case 'h':
+            goto usage;
+        default:
+            goto usage;
+        }
+    }
+    if ( pAbc->pGia == NULL )
+    {
+        Abc_Print( -1, "Abc_CommandAbc9StochSyn(): There is no AIG.\n" );
+        return 0;
+    }
+    if ( argc != globalUtilOptind + 1 )
+    {
+        printf( "Expecting a synthesis script in quotes on the command line (for example: \"&st; &dch; &if\").\n" );
+        goto usage;
+    }
+    pScript = Abc_UtilStrsav( argv[globalUtilOptind] );
+    Gia_ManStochSyn( nMaxSize, nIters, TimeOut, Seed, fVerbose, pScript );
+    ABC_FREE( pScript );
+    return 0;
+
+usage:
+    Abc_Print( -2, "usage: &stochsyn [-NITS <num>] [-tvh] <script>\n" );
+    Abc_Print( -2, "\t           performs stochastic synthesis\n" );
+    Abc_Print( -2, "\t-N <num> : the max partition size (in AIG nodes or LUTs) [default = %d]\n", nMaxSize );
+    Abc_Print( -2, "\t-I <num> : the number of iterations [default = %d]\n",                   nIters  );
+    Abc_Print( -2, "\t-T <num> : the timeout in seconds (0 = no timeout) [default = %d]\n",    TimeOut );
+    Abc_Print( -2, "\t-S <num> : user-specified random seed (0 <= num <= 100) [default = %d]\n", Seed  );
+    Abc_Print( -2, "\t-v       : toggle printing optimization summary [default = %s]\n",       fVerbose? "yes": "no" );
+    Abc_Print( -2, "\t-h       : print the command usage\n");
+    Abc_Print( -2, "\t<script> : synthesis script to use for each partition\n");
+    return 1;
+}
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
 int Abc_CommandAbc9CexCut( Abc_Frame_t * pAbc, int argc, char ** argv )
 {
     return -1;