From 227b0c775b0d61aee54423cc22a3f6644b2c2bb7 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Wed, 6 Oct 2021 20:33:41 -0700 Subject: New command &stochsyn for stochastic synthesis. --- abclib.dsp | 4 + src/aig/gia/giaStoch.c | 321 ++++++++++++++++++++++++++++++++++++++++++++++++ src/aig/gia/module.make | 1 + src/base/abci/abc.c | 103 ++++++++++++++++ 4 files changed, 429 insertions(+) create mode 100644 src/aig/gia/giaStoch.c 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 ); @@ -47541,6 +47543,107 @@ usage: return 1; } +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + 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 ] [-tvh]