diff options
| -rw-r--r-- | src/base/abc/abc.h | 2 | ||||
| -rw-r--r-- | src/base/abc/abcRefs.c | 10 | ||||
| -rw-r--r-- | src/base/abci/abc.c | 4 | ||||
| -rw-r--r-- | src/opt/lpk/lpkCore.c | 84 | ||||
| -rw-r--r-- | src/opt/lpk/lpkCut.c | 45 | ||||
| -rw-r--r-- | src/opt/lpk/lpkInt.h | 5 | ||||
| -rw-r--r-- | src/opt/lpk/lpkMan.c | 6 | ||||
| -rw-r--r-- | src/opt/mfs/mfsResub.c | 4 | ||||
| -rw-r--r-- | src/opt/sfm/sfmDec.c | 2 |
9 files changed, 143 insertions, 19 deletions
diff --git a/src/base/abc/abc.h b/src/base/abc/abc.h index dd189c6d..e85c74e8 100644 --- a/src/base/abc/abc.h +++ b/src/base/abc/abc.h @@ -870,7 +870,7 @@ extern ABC_DLL int Abc_NodeMffcSize( Abc_Obj_t * pNode ); extern ABC_DLL int Abc_NodeMffcSizeSupp( Abc_Obj_t * pNode ); extern ABC_DLL int Abc_NodeMffcSizeStop( Abc_Obj_t * pNode ); extern ABC_DLL int Abc_NodeMffcLabelAig( Abc_Obj_t * pNode ); -extern ABC_DLL int Abc_NodeMffcLabel( Abc_Obj_t * pNode ); +extern ABC_DLL int Abc_NodeMffcLabel( Abc_Obj_t * pNode, Vec_Ptr_t * vNodes ); extern ABC_DLL void Abc_NodeMffcConeSupp( Abc_Obj_t * pNode, Vec_Ptr_t * vCone, Vec_Ptr_t * vSupp ); extern ABC_DLL int Abc_NodeDeref_rec( Abc_Obj_t * pNode ); extern ABC_DLL int Abc_NodeRef_rec( Abc_Obj_t * pNode ); diff --git a/src/base/abc/abcRefs.c b/src/base/abc/abcRefs.c index 26ae55ab..4c5600c6 100644 --- a/src/base/abc/abcRefs.c +++ b/src/base/abc/abcRefs.c @@ -405,7 +405,7 @@ Vec_Ptr_t * Abc_NodeMffcInsideCollect( Abc_Obj_t * pNode ) SeeAlso [] ***********************************************************************/ -void Abc_NodeMffcLabel_rec( Abc_Obj_t * pNode, int fTopmost ) +void Abc_NodeMffcLabel_rec( Abc_Obj_t * pNode, int fTopmost, Vec_Ptr_t * vNodes ) { Abc_Obj_t * pFanin; int i; @@ -418,9 +418,11 @@ void Abc_NodeMffcLabel_rec( Abc_Obj_t * pNode, int fTopmost ) Abc_NodeSetTravIdCurrent(pNode); // recur on the children Abc_ObjForEachFanin( pNode, pFanin, i ) - Abc_NodeMffcLabel_rec( pFanin, 0 ); + Abc_NodeMffcLabel_rec( pFanin, 0, vNodes ); // collect the internal node // printf( "%d ", pNode->Id ); + if ( vNodes ) + Vec_PtrPush( vNodes, pNode ); } /**Function************************************************************* @@ -434,14 +436,14 @@ void Abc_NodeMffcLabel_rec( Abc_Obj_t * pNode, int fTopmost ) SeeAlso [] ***********************************************************************/ -int Abc_NodeMffcLabel( Abc_Obj_t * pNode ) +int Abc_NodeMffcLabel( Abc_Obj_t * pNode, Vec_Ptr_t * vNodes ) { int Count1, Count2; // dereference the node Count1 = Abc_NodeDeref_rec( pNode ); // collect the nodes inside the MFFC Abc_NtkIncrementTravId( pNode->pNtk ); - Abc_NodeMffcLabel_rec( pNode, 1 ); + Abc_NodeMffcLabel_rec( pNode, 1, vNodes ); // reference it back Count2 = Abc_NodeRef_rec( pNode ); assert( Count1 == Count2 ); diff --git a/src/base/abci/abc.c b/src/base/abci/abc.c index 5df604cc..09b27b36 100644 --- a/src/base/abci/abc.c +++ b/src/base/abci/abc.c @@ -4898,7 +4898,7 @@ int Abc_CommandLutpack( Abc_Frame_t * pAbc, int argc, char ** argv ) } pPars->nLutsMax = atoi(argv[globalUtilOptind]); globalUtilOptind++; - if ( pPars->nLutsMax < 2 || pPars->nLutsMax > 8 ) + if ( pPars->nLutsMax < 2 || pPars->nLutsMax > 16 ) goto usage; break; case 'Q': @@ -4988,7 +4988,7 @@ usage: Abc_Print( -2, "\t performs \"rewriting\" for LUT network;\n" ); Abc_Print( -2, "\t determines LUT size as the max fanin count of a node;\n" ); Abc_Print( -2, "\t if the network is not LUT-mapped, packs it into 6-LUTs\n" ); - Abc_Print( -2, "\t (there is another command for resynthesis after LUT mapping, \"imfs\")\n" ); + Abc_Print( -2, "\t (there is another command for resynthesis after LUT mapping, \"mfs2\")\n" ); Abc_Print( -2, "\t-N <num> : the max number of LUTs in the structure (2 <= num) [default = %d]\n", pPars->nLutsMax ); Abc_Print( -2, "\t-Q <num> : the max number of LUTs not in MFFC (0 <= num) [default = %d]\n", pPars->nLutsOver ); Abc_Print( -2, "\t-S <num> : the max number of LUT inputs shared (0 <= num <= 3) [default = %d]\n", pPars->nVarsShared ); diff --git a/src/opt/lpk/lpkCore.c b/src/opt/lpk/lpkCore.c index 27912a9a..728aa2dd 100644 --- a/src/opt/lpk/lpkCore.c +++ b/src/opt/lpk/lpkCore.c @@ -35,6 +35,82 @@ ABC_NAMESPACE_IMPL_START /**Function************************************************************* + Synopsis [Returns decomposed network.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Abc_Ntk_t * Abc_NtkDecFromTruth( word * pTruth, int nVars, int nLutSize ) +{ + extern Abc_Ntk_t * Abc_NtkLutmin( Abc_Ntk_t * pNtk, int nLutSize, int fVerbose ); + Vec_Int_t * vCover = Vec_IntAlloc( 1 << 16 ); + Abc_Ntk_t * pTemp = Abc_NtkAlloc( ABC_NTK_LOGIC, ABC_FUNC_SOP, 1 ); + char * pSopCover = Abc_SopCreateFromTruthIsop( (Mem_Flex_t *)pTemp->pManFunc, nVars, pTruth, vCover ); + Abc_Ntk_t * pNtk = Abc_NtkCreateWithNode( pSopCover ); + Abc_Ntk_t * pNew = Abc_NtkLutmin( pNtk, nLutSize, 0 ); + Abc_NtkDelete( pTemp ); + Abc_NtkDelete( pNtk ); + Vec_IntFree( vCover ); + if ( !Abc_NtkToAig(pNew) ) + { + Abc_NtkDelete( pNew ); + fprintf( stdout, "Converting to AIG has failed.\n" ); + return NULL; + } + assert( Abc_NtkHasAig(pNew) ); + return pNew; +} +Abc_Obj_t * Abc_NtkLutMinDecompose( Abc_Ntk_t * pNtk, Vec_Ptr_t * vLeaves, word * pTruth, int nLutSize, int Required ) +{ + Abc_Obj_t * pObj = NULL, * pFanin; int i, k; + Abc_Ntk_t * pNew = Abc_NtkDecFromTruth( pTruth, Vec_PtrSize(vLeaves), nLutSize ); + Vec_Ptr_t * vNodes = Abc_NtkDfs( pNew, 0 ); + assert( Abc_NtkHasAig(pNtk) ); + // levels + Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pObj, i ) + Abc_NtkCi( pNew, i )->Level = pObj->Level; + Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, i ) + { + pObj->Level = 0; + Abc_ObjForEachFanin( pObj, pFanin, k ) + if ( pObj->Level < pFanin->Level ) + pObj->Level = pFanin->Level; + pObj->Level++; + } + if ( (int)pObj->Level > Required ) + { + Vec_PtrFree( vNodes ); + Abc_NtkDelete( pNew ); + return NULL; + } + Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pObj, i ) + Abc_NtkCi( pNew, i )->pCopy = pObj; + Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, i ) + { + Abc_NtkDupObj( pNtk, pObj, 0 ); + pObj->pCopy->Level = 0; + Abc_ObjForEachFanin( pObj, pFanin, k ) + { + Abc_ObjAddFanin( pObj->pCopy, pFanin->pCopy ); + if ( pObj->pCopy->Level < pFanin->pCopy->Level ) + pObj->pCopy->Level = pFanin->pCopy->Level; + } + pObj->pCopy->Level++; + } + //printf( "Decomposed %d-input function, resulting in %d nodes.\n", Vec_PtrSize(vLeaves), Vec_PtrSize(vNodes) ); + pObj = pObj->pCopy; + Vec_PtrFree( vNodes ); + Abc_NtkDelete( pNew ); + return pObj; +} + + +/**Function************************************************************* + Synopsis [Prepares the mapping manager.] Description [] @@ -272,7 +348,7 @@ p->timeCuts += Abc_Clock() - clk; // printf( "Mffc size = %d. ", Abc_NodeMffcLabel(p->pObj) ); for ( k = 0; k < (int)pCut->nLeaves; k++ ) Abc_NtkObj(p->pNtk, pCut->pLeaves[k])->vFanouts.nSize++; - nCutNodes = Abc_NodeMffcLabel(p->pObj); + nCutNodes = Abc_NodeMffcLabel(p->pObj, NULL); // printf( "Mffc with cut = %d. ", nCutNodes ); for ( k = 0; k < (int)pCut->nLeaves; k++ ) Abc_NtkObj(p->pNtk, pCut->pLeaves[k])->vFanouts.nSize--; @@ -353,7 +429,6 @@ void Lpk_ComputeSupports( Lpk_Man_t * p, Lpk_Cut_t * pCut, unsigned * pTruth ) p->puSupps[0] = p->puSupps[1] = 0; } - /**Function************************************************************* Synopsis [Performs resynthesis for one node.] @@ -368,6 +443,7 @@ void Lpk_ComputeSupports( Lpk_Man_t * p, Lpk_Cut_t * pCut, unsigned * pTruth ) int Lpk_ResynthesizeNodeNew( Lpk_Man_t * p ) { // static int Count = 0; + int NodeCounts[16] = { 0, 0, 0, 0, 1, 3, 6, 14, 26, 57, 106, 230, 425, 1000000, 1000000, 1000000 }; Abc_Obj_t * pObjNew, * pLeaf; Lpk_Cut_t * pCut; unsigned * pTruth; @@ -405,7 +481,7 @@ p->timeCuts += Abc_Clock() - clk; // printf( "Mffc size = %d. ", Abc_NodeMffcLabel(p->pObj) ); for ( k = 0; k < (int)pCut->nLeaves; k++ ) Abc_NtkObj(p->pNtk, pCut->pLeaves[k])->vFanouts.nSize++; - nCutNodes = Abc_NodeMffcLabel(p->pObj); + nCutNodes = Abc_NodeMffcLabel(p->pObj, NULL); // printf( "Mffc with cut = %d. ", nCutNodes ); for ( k = 0; k < (int)pCut->nLeaves; k++ ) Abc_NtkObj(p->pNtk, pCut->pLeaves[k])->vFanouts.nSize--; @@ -461,6 +537,8 @@ p->timeTruth3 += Abc_Clock() - clk; clk = Abc_Clock(); pObjNew = Lpk_Decompose( p, p->pNtk, p->vLeaves, pTruth, p->puSupps, p->pPars->nLutSize, (int)pCut->nNodes - (int)pCut->nNodesDup - 1 + (int)(p->pPars->fZeroCost > 0), Required ); + if ( pObjNew == NULL && p->pPars->nLutSize == 4 && (int)pCut->nNodes > NodeCounts[Vec_PtrSize(p->vLeaves)] + !p->pPars->fZeroCost ) + pObjNew = Abc_NtkLutMinDecompose( p->pNtk, p->vLeaves, (word *)pTruth, p->pPars->nLutSize, Required ); p->timeEval += Abc_Clock() - clk; nNodesAft = Abc_NtkNodeNum(p->pNtk); diff --git a/src/opt/lpk/lpkCut.c b/src/opt/lpk/lpkCut.c index 208facf2..41cfaed5 100644 --- a/src/opt/lpk/lpkCut.c +++ b/src/opt/lpk/lpkCut.c @@ -576,6 +576,37 @@ void Lpk_NodeCutsOne( Lpk_Man_t * p, Lpk_Cut_t * pCut, int Node ) /**Function************************************************************* + Synopsis [Count support.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Lpk_CountSupp( Abc_Ntk_t * p, Vec_Ptr_t * vNodes ) +{ + Abc_Obj_t * pObj, * pFanin; + int i, k, Count = 0; + Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, i ) + { + Abc_ObjForEachFanin( pObj, pFanin, k ) + { + if ( Abc_NodeIsTravIdCurrent(pFanin) ) + continue; + Count += !pFanin->fPersist; + pFanin->fPersist = 1; + } + } + Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, i ) + Abc_ObjForEachFanin( pObj, pFanin, k ) + pFanin->fPersist = 0; + return Count; +} + +/**Function************************************************************* + Synopsis [Computes the set of all cuts.] Description [] @@ -589,13 +620,20 @@ int Lpk_NodeCuts( Lpk_Man_t * p ) { Lpk_Cut_t * pCut, * pCut2; int i, k, Temp, nMffc, fChanges; + //int nSupp; // mark the MFFC of the node with the current trav ID - nMffc = p->nMffc = Abc_NodeMffcLabel( p->pObj ); + Vec_PtrClear( p->vTemp ); + nMffc = p->nMffc = Abc_NodeMffcLabel( p->pObj, p->vTemp ); assert( nMffc > 0 ); if ( nMffc == 1 ) return 0; - +/* + // count the leaves + nSupp = Lpk_CountSupp( p->pNtk, p->vTemp ); + if ( nMffc > 10 && nSupp <= 10 ) + printf( "Obj = %4d : Supp = %4d. Mffc = %4d.\n", p->pObj->Id, nSupp, nMffc ); +*/ // initialize the first cut pCut = p->pCuts; p->nCuts = 1; pCut->nNodes = 0; @@ -650,6 +688,9 @@ int Lpk_NodeCuts( Lpk_Man_t * p ) if ( pCut->fHasDsd ) continue; p->pEvals[p->nEvals++] = i; + +// if ( pCut->nLeaves <= 9 && pCut->nNodes > 15 ) +// printf( "%5d : Obj = %4d Leaves = %4d Nodes = %4d LUTs = %4d\n", i, p->pObj->Id, pCut->nLeaves, pCut->nNodes, pCut->nLuts ); } if ( p->nEvals == 0 ) return 0; diff --git a/src/opt/lpk/lpkInt.h b/src/opt/lpk/lpkInt.h index 02181001..9285a423 100644 --- a/src/opt/lpk/lpkInt.h +++ b/src/opt/lpk/lpkInt.h @@ -44,8 +44,8 @@ ABC_NAMESPACE_HEADER_START /// BASIC TYPES /// //////////////////////////////////////////////////////////////////////// -#define LPK_SIZE_MAX 24 // the largest size of the function -#define LPK_CUTS_MAX 512 // the largest number of cuts considered +#define LPK_SIZE_MAX 100 // the largest size of the function +#define LPK_CUTS_MAX 10000 // the largest number of cuts considered typedef struct Lpk_Man_t_ Lpk_Man_t; typedef struct Lpk_Cut_t_ Lpk_Cut_t; @@ -93,6 +93,7 @@ struct Lpk_Man_t_ int pRefs[LPK_SIZE_MAX]; // fanin reference counters int pCands[LPK_SIZE_MAX]; // internal nodes pointing only to the leaves Vec_Ptr_t * vLeaves; + Vec_Ptr_t * vTemp; // truth table representation Vec_Ptr_t * vTtElems; // elementary truth tables Vec_Ptr_t * vTtNodes; // storage for temporary truth tables of the nodes diff --git a/src/opt/lpk/lpkMan.c b/src/opt/lpk/lpkMan.c index f012ab75..384741c5 100644 --- a/src/opt/lpk/lpkMan.c +++ b/src/opt/lpk/lpkMan.c @@ -54,8 +54,9 @@ Lpk_Man_t * Lpk_ManStart( Lpk_Par_t * pPars ) p->nCutsMax = LPK_CUTS_MAX; p->vTtElems = Vec_PtrAllocTruthTables( pPars->nVarsMax ); p->vTtNodes = Vec_PtrAllocSimInfo( 1024, Abc_TruthWordNum(pPars->nVarsMax) ); - p->vCover = Vec_IntAlloc( 1 << 12 ); - p->vLeaves = Vec_PtrAlloc( 32 ); + p->vCover = Vec_IntAlloc( 1 << 12 ); + p->vLeaves = Vec_PtrAlloc( 32 ); + p->vTemp = Vec_PtrAlloc( 32 ); for ( i = 0; i < 8; i++ ) p->vSets[i] = Vec_IntAlloc(100); p->pDsdMan = Kit_DsdManAlloc( pPars->nVarsMax, 64 ); @@ -112,6 +113,7 @@ void Lpk_ManStop( Lpk_Man_t * p ) if ( p->vVisited ) Vec_VecFree( p->vVisited ); Vec_PtrFree( p->vLeaves ); + Vec_PtrFree( p->vTemp ); Vec_IntFree( p->vCover ); Vec_PtrFree( p->vTtElems ); Vec_PtrFree( p->vTtNodes ); diff --git a/src/opt/mfs/mfsResub.c b/src/opt/mfs/mfsResub.c index dc73cea7..5bb2ad49 100644 --- a/src/opt/mfs/mfsResub.c +++ b/src/opt/mfs/mfsResub.c @@ -183,7 +183,7 @@ int Abc_NtkMfsSolveSatResub( Mfs_Man_t * p, Abc_Obj_t * pNode, int iFanin, int f printf( "%5d : Lev =%3d. Leaf =%3d. Node =%3d. Divs =%3d. Fanin = %4d (%d/%d), MFFC = %d\n", pNode->Id, pNode->Level, Vec_PtrSize(p->vSupp), Vec_PtrSize(p->vNodes), Vec_PtrSize(p->vDivs)-Abc_ObjFaninNum(pNode), Abc_ObjFaninId(pNode, iFanin), iFanin, Abc_ObjFaninNum(pNode), - Abc_ObjFanoutNum(Abc_ObjFanin(pNode, iFanin)) == 1 ? Abc_NodeMffcLabel(Abc_ObjFanin(pNode, iFanin)) : 0 ); + Abc_ObjFanoutNum(Abc_ObjFanin(pNode, iFanin)) == 1 ? Abc_NodeMffcLabel(Abc_ObjFanin(pNode, iFanin), NULL) : 0 ); } // try fanins without the critical fanin @@ -337,7 +337,7 @@ int Abc_NtkMfsSolveSatResub2( Mfs_Man_t * p, Abc_Obj_t * pNode, int iFanin, int printf( "Node %5d : Level = %2d. Divs = %3d. Fanins = %d/%d (out of %d). MFFC = %d\n", pNode->Id, pNode->Level, Vec_PtrSize(p->vDivs)-Abc_ObjFaninNum(pNode), iFanin, iFanin2, Abc_ObjFaninNum(pNode), - Abc_ObjFanoutNum(Abc_ObjFanin(pNode, iFanin)) == 1 ? Abc_NodeMffcLabel(Abc_ObjFanin(pNode, iFanin)) : 0 ); + Abc_ObjFanoutNum(Abc_ObjFanin(pNode, iFanin)) == 1 ? Abc_NodeMffcLabel(Abc_ObjFanin(pNode, iFanin), NULL) : 0 ); } // try fanins without the critical fanin diff --git a/src/opt/sfm/sfmDec.c b/src/opt/sfm/sfmDec.c index c5af0ac0..a558c120 100644 --- a/src/opt/sfm/sfmDec.c +++ b/src/opt/sfm/sfmDec.c @@ -1865,7 +1865,7 @@ Abc_Obj_t * Abc_NtkAreaOptOne( Sfm_Dec_t * p, int i ) Sfm_Par_t * pPars = p->pPars; Abc_Obj_t * pObj = Abc_NtkObj( p->pNtk, i ); int Limit, RetValue; - if ( pPars->nMffcMin > 1 && Abc_NodeMffcLabel(pObj) < pPars->nMffcMin ) + if ( pPars->nMffcMin > 1 && Abc_NodeMffcLabel(pObj, NULL) < pPars->nMffcMin ) return NULL; if ( pPars->iNodeOne && i != pPars->iNodeOne ) return NULL; |