From 3ef00645b879201bdfc7dbcab6279558cd4892bc Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Mon, 18 Aug 2014 22:42:48 -0700 Subject: Added command 'sparsify' to derive ISF from CSF. --- src/base/abci/abc.c | 82 +++++++++++++++++++++++++++++++ src/base/abci/abcDsd.c | 130 +++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 212 insertions(+) (limited to 'src') diff --git a/src/base/abci/abc.c b/src/base/abci/abc.c index d21c1887..e7271095 100644 --- a/src/base/abci/abc.c +++ b/src/base/abci/abc.c @@ -103,6 +103,7 @@ static int Abc_CommandSweep ( Abc_Frame_t * pAbc, int argc, cha static int Abc_CommandFastExtract ( Abc_Frame_t * pAbc, int argc, char ** argv ); static int Abc_CommandEliminate ( Abc_Frame_t * pAbc, int argc, char ** argv ); static int Abc_CommandDisjoint ( Abc_Frame_t * pAbc, int argc, char ** argv ); +static int Abc_CommandSparsify ( Abc_Frame_t * pAbc, int argc, char ** argv ); static int Abc_CommandLutpack ( Abc_Frame_t * pAbc, int argc, char ** argv ); static int Abc_CommandLutmin ( Abc_Frame_t * pAbc, int argc, char ** argv ); //static int Abc_CommandImfs ( Abc_Frame_t * pAbc, int argc, char ** argv ); @@ -690,6 +691,7 @@ void Abc_Init( Abc_Frame_t * pAbc ) Cmd_CommandAdd( pAbc, "Synthesis", "fx", Abc_CommandFastExtract, 1 ); Cmd_CommandAdd( pAbc, "Synthesis", "eliminate", Abc_CommandEliminate, 1 ); Cmd_CommandAdd( pAbc, "Synthesis", "dsd", Abc_CommandDisjoint, 1 ); + Cmd_CommandAdd( pAbc, "Synthesis", "sparsify", Abc_CommandSparsify, 1 ); Cmd_CommandAdd( pAbc, "Synthesis", "lutpack", Abc_CommandLutpack, 1 ); Cmd_CommandAdd( pAbc, "Synthesis", "lutmin", Abc_CommandLutmin, 1 ); // Cmd_CommandAdd( pAbc, "Synthesis", "imfs", Abc_CommandImfs, 1 ); @@ -4088,6 +4090,86 @@ usage: return 1; } +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_CommandSparsify( Abc_Frame_t * pAbc, int argc, char ** argv ) +{ + extern Abc_Ntk_t * Abc_NtkSparsify( Abc_Ntk_t * pNtk, int nPerc, int fVerbose ); + Abc_Ntk_t * pNtk = Abc_FrameReadNtk(pAbc), * pNtkNew; + int nPerc, fVerbose, c; + // set defaults + nPerc = 10; + fVerbose = 0; + Extra_UtilGetoptReset(); + while ( ( c = Extra_UtilGetopt( argc, argv, "Nvh" ) ) != EOF ) + { + switch ( c ) + { + case 'N': + if ( globalUtilOptind >= argc ) + { + Abc_Print( -1, "Command line switch \"-N\" should be followed by an integer.\n" ); + goto usage; + } + nPerc = atoi(argv[globalUtilOptind]); + globalUtilOptind++; + if ( nPerc < 1 || nPerc > 100 ) + goto usage; + break; + case 'v': + fVerbose ^= 1; + break; + case 'h': + goto usage; + break; + default: + goto usage; + } + } + + if ( pNtk == NULL ) + { + Abc_Print( -1, "Empty network.\n" ); + return 1; + } + if ( !Abc_NtkIsBddLogic( pNtk ) ) + { + Abc_Print( -1, "This command is only applicable to logic BDD networks (run \"bdd\").\n" ); + return 1; + } + if ( Abc_NtkCiNum(pNtk) > 16 ) + { + Abc_Print( -1, "The number of primary inputs is more than 16.\n" ); + return 1; + } + pNtkNew = Abc_NtkSparsify( pNtk, nPerc, fVerbose ); + if ( pNtkNew == NULL ) + { + Abc_Print( -1, "Command has failed.\n" ); + return 1; + } + // replace the current network + Abc_FrameReplaceCurrentNetwork( pAbc, pNtkNew ); + return 0; + +usage: + Abc_Print( -2, "usage: sparsify [-N num] [-vh]\n" ); + Abc_Print( -2, "\t creates incompletely-specified function\n" ); + Abc_Print( -2, "\t-N : the percentage of on-set and off-set minterms (1 <= num <= 100) [default = %d]\n", nPerc ); + Abc_Print( -2, "\t-v : prints verbose information [default = %s]\n", fVerbose? "yes": "no" ); + Abc_Print( -2, "\t-h : print the command usage\n"); + return 1; +} + /**Function************************************************************* Synopsis [] diff --git a/src/base/abci/abcDsd.c b/src/base/abci/abcDsd.c index 78b160e0..481639dd 100644 --- a/src/base/abci/abcDsd.c +++ b/src/base/abci/abcDsd.c @@ -554,6 +554,136 @@ int Abc_NodeFindMuxVar( DdManager * dd, DdNode * bFunc, int nVars ) } +/**Function******************************************************************** + + Synopsis [Computes the positive polarty cube composed of the first vars in the array.] + + Description [] + + SideEffects [] + + SeeAlso [] + +******************************************************************************/ +DdNode * Extra_bddComputeSum( DdManager * dd, DdNode ** pbCubes, int nCubes ) +{ + DdNode * bRes, * bTemp; + int i; + bRes = b0; Cudd_Ref( bRes ); + for ( i = 0; i < nCubes; i++ ) + { + bRes = Cudd_bddOr( dd, bTemp = bRes, pbCubes[i] ); Cudd_Ref( bRes ); + Cudd_RecursiveDeref( dd, bTemp ); + } + Cudd_Deref( bRes ); + return bRes; +} + +/**Function************************************************************* + + Synopsis [Derives network with the given percentage of on-set and off-set minterms.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +DdNode * Abc_NtkSparsifyInternalOne( DdManager * ddNew, DdNode * bFunc, int nFanins, int nPerc ) +{ + int nSpace = (int)Cudd_CountMinterm( ddNew, bFunc, nFanins ); + int i, nMints = Abc_MaxInt( 1, (int)(0.01 * nPerc * nSpace) ); + DdNode ** pbMints = Cudd_bddPickArbitraryMinterms( ddNew, bFunc, ddNew->vars, nFanins, nMints ); + DdNode * bRes; + for ( i = 0; i < nMints; i++ ) + Cudd_Ref( pbMints[i] ); + bRes = Extra_bddComputeSum( ddNew, pbMints, nMints ); Cudd_Ref( bRes ); + for ( i = 0; i < nMints; i++ ) + Cudd_RecursiveDeref( ddNew, pbMints[i] ); + Cudd_Deref( bRes ); + ABC_FREE( pbMints ); + return bRes; +} +Abc_Ntk_t * Abc_NtkSparsifyInternal( Abc_Ntk_t * pNtk, int nPerc, int fVerbose ) +{ + Abc_Ntk_t * pNtkNew; + Abc_Obj_t * pObj, * pDriver, * pFanin; + DdNode * bFunc, * bFuncOld; + DdManager * ddNew; + int i, k, c; + // start the new network + pNtkNew = Abc_NtkAlloc( ABC_NTK_LOGIC, ABC_FUNC_BDD, 1 ); + Abc_NtkForEachCi( pNtk, pObj, i ) + Abc_NtkDupObj( pNtkNew, pObj, 1 ); + // duplicate the name and the spec + pNtkNew->pName = Extra_UtilStrsav(pNtk->pName); + pNtkNew->pSpec = Extra_UtilStrsav(pNtk->pSpec); + // make sure the new manager has enough inputs + ddNew = (DdManager *)pNtkNew->pManFunc; + Cudd_bddIthVar( ddNew, Abc_NtkCiNum(pNtk)-1 ); + // go through the outputs + Abc_NtkForEachCo( pNtk, pObj, i ) + { + pDriver = Abc_ObjFanin0( pObj ); + if ( Abc_ObjIsCi(pDriver) ) + { + Abc_NtkDupObj( pNtkNew, pObj, 0 ); + Abc_ObjAddFanin( pObj->pCopy, Abc_ObjNotCond(pDriver->pCopy, Abc_ObjFaninC0(pObj)) ); + Abc_ObjAssignName( pObj->pCopy, Abc_ObjName(pObj), "_on" ); + + Abc_NtkDupObj( pNtkNew, pObj, 0 ); + Abc_ObjAddFanin( pObj->pCopy, Abc_ObjNotCond(pDriver->pCopy, !Abc_ObjFaninC0(pObj)) ); + Abc_ObjAssignName( pObj->pCopy, Abc_ObjName(pObj), "_off" ); + continue; + } + if ( Abc_ObjFaninNum(pDriver) == 0 ) + { + Abc_NtkDupObj( pNtkNew, pObj, 0 ); + Abc_ObjAddFanin( pObj->pCopy, Abc_ObjFaninC0(pObj) ? Abc_NtkCreateNodeConst0(pNtkNew) : Abc_NtkCreateNodeConst1(pNtkNew) ); + Abc_ObjAssignName( pObj->pCopy, Abc_ObjName(pObj), "_on" ); + + Abc_NtkDupObj( pNtkNew, pObj, 0 ); + Abc_ObjAddFanin( pObj->pCopy, Abc_ObjFaninC0(pObj) ? Abc_NtkCreateNodeConst1(pNtkNew) : Abc_NtkCreateNodeConst0(pNtkNew) ); + Abc_ObjAssignName( pObj->pCopy, Abc_ObjName(pObj), "_off" ); + continue; + } + assert( Abc_ObjFaninNum(pObj) > 0 ); + // onset/offset + for ( c = 0; c < 2; c++ ) + { + Abc_NtkDupObj( pNtkNew, pDriver, 0 ); + Abc_ObjForEachFanin( pDriver, pFanin, k ) + Abc_ObjAddFanin( pDriver->pCopy, pFanin->pCopy ); + bFuncOld = Cudd_NotCond( (DdNode *)pDriver->pCopy->pData, c ); + bFunc = Abc_NtkSparsifyInternalOne( ddNew, bFuncOld, Abc_ObjFaninNum(pDriver), nPerc ); Cudd_Ref( bFunc ); + Cudd_RecursiveDeref( ddNew, bFuncOld ); + pDriver->pCopy->pData = bFunc; + Abc_NtkDupObj( pNtkNew, pObj, 0 ); + Abc_ObjAddFanin( pObj->pCopy, pDriver->pCopy ); + Abc_ObjAssignName( pObj->pCopy, Abc_ObjName(pObj), c ? "_off" : "_on" ); + } + } + Abc_NtkLogicMakeSimpleCos( pNtkNew, 0 ); + return pNtkNew; +} +Abc_Ntk_t * Abc_NtkSparsify( Abc_Ntk_t * pNtk, int nPerc, int fVerbose ) +{ + Abc_Ntk_t * pNtkNew; + assert( Abc_NtkIsComb(pNtk) ); + assert( Abc_NtkIsBddLogic(pNtk) ); + pNtkNew = Abc_NtkSparsifyInternal( pNtk, nPerc, fVerbose ); + if ( pNtkNew == NULL ) + return NULL; + if ( !Abc_NtkCheck( pNtkNew ) ) + { + printf( "Abc_NtkSparsify: The network check has failed.\n" ); + Abc_NtkDelete( pNtkNew ); + return NULL; + } + return pNtkNew; +} + //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// -- cgit v1.2.3