diff options
author | Alan Mishchenko <alanmi@berkeley.edu> | 2007-09-06 08:01:00 -0700 |
---|---|---|
committer | Alan Mishchenko <alanmi@berkeley.edu> | 2007-09-06 08:01:00 -0700 |
commit | 9be1b076934b0410689c857cd71ef7d21a714b5f (patch) | |
tree | c342242ad3c5ea9d35e6e682f9026534ec73fcbe /src/opt | |
parent | b2470dd3da962026fd874e13c2cf78c10099fe68 (diff) | |
download | abc-9be1b076934b0410689c857cd71ef7d21a714b5f.tar.gz abc-9be1b076934b0410689c857cd71ef7d21a714b5f.tar.bz2 abc-9be1b076934b0410689c857cd71ef7d21a714b5f.zip |
Version abc70906
Diffstat (limited to 'src/opt')
-rw-r--r-- | src/opt/lpk/lpkAbcDec.c | 132 | ||||
-rw-r--r-- | src/opt/lpk/lpkAbcDsd.c | 129 | ||||
-rw-r--r-- | src/opt/lpk/lpkAbcMux.c | 123 | ||||
-rw-r--r-- | src/opt/lpk/lpkAbcUtil.c | 16 | ||||
-rw-r--r-- | src/opt/lpk/lpkCore.c | 11 | ||||
-rw-r--r-- | src/opt/lpk/lpkCut.c | 9 | ||||
-rw-r--r-- | src/opt/lpk/lpkInt.h | 16 | ||||
-rw-r--r-- | src/opt/lpk/lpkMux.c | 3 |
8 files changed, 284 insertions, 155 deletions
diff --git a/src/opt/lpk/lpkAbcDec.c b/src/opt/lpk/lpkAbcDec.c index 831097b0..e9f8d0df 100644 --- a/src/opt/lpk/lpkAbcDec.c +++ b/src/opt/lpk/lpkAbcDec.c @@ -17,7 +17,7 @@ Revision [$Id: lpkAbcDec.c,v 1.00 2007/04/28 00:00:00 alanmi Exp $] ***********************************************************************/ - + #include "lpkInt.h" //////////////////////////////////////////////////////////////////////// @@ -41,24 +41,29 @@ ***********************************************************************/ Abc_Obj_t * Lpk_ImplementFun( Abc_Ntk_t * pNtk, Vec_Ptr_t * vLeaves, Lpk_Fun_t * p ) { + extern Hop_Obj_t * Kit_TruthToHop( Hop_Man_t * pMan, unsigned * pTruth, int nVars, Vec_Int_t * vMemory ); + unsigned * pTruth; Abc_Obj_t * pObjNew; int i; + // create the new node pObjNew = Abc_NtkCreateNode( pNtk ); for ( i = 0; i < (int)p->nVars; i++ ) Abc_ObjAddFanin( pObjNew, Vec_PtrEntry(vLeaves, p->pFanins[i]) ); Abc_ObjLevelNew( pObjNew ); - // create the logic function + // assign the node's function + pTruth = Lpk_FunTruth(p, 0); + if ( p->nVars == 0 ) { - extern Hop_Obj_t * Kit_GraphToHop( Hop_Man_t * pMan, Kit_Graph_t * pGraph ); - // allocate memory for the ISOP - Vec_Int_t * vCover = Vec_IntAlloc( 0 ); - // transform truth table into the decomposition tree - Kit_Graph_t * pGraph = Kit_TruthToGraph( Lpk_FunTruth(p, 0), p->nVars, vCover ); - // derive the AIG for the decomposition tree - pObjNew->pData = Kit_GraphToHop( pNtk->pManFunc, pGraph ); - Kit_GraphFree( pGraph ); - Vec_IntFree( vCover ); + pObjNew->pData = Hop_NotCond( Hop_ManConst1(pNtk->pManFunc), !(pTruth[0] & 1) ); + return pObjNew; } + if ( p->nVars == 1 ) + { + pObjNew->pData = Hop_NotCond( Hop_ManPi(pNtk->pManFunc, 0), (pTruth[0] & 1) ); + return pObjNew; + } + // create the logic function + pObjNew->pData = Kit_TruthToHop( pNtk->pManFunc, pTruth, p->nVars, NULL ); return pObjNew; } @@ -85,6 +90,7 @@ Abc_Obj_t * Lpk_Implement( Abc_Ntk_t * pNtk, Vec_Ptr_t * vLeaves, int nLeavesOld Vec_PtrWriteEntry( vLeaves, i, pRes ); Lpk_FunFree( pFun ); } + Vec_PtrShrink( vLeaves, nLeavesOld ); return pRes; } @@ -92,7 +98,9 @@ Abc_Obj_t * Lpk_Implement( Abc_Ntk_t * pNtk, Vec_Ptr_t * vLeaves, int nLeavesOld Synopsis [Decomposes the function using recursive MUX decomposition.] - Description [] + Description [Returns the ID of the top-most decomposition node + implementing this function, or 0 if there is no decomposition satisfying + the constraints on area and delay.] SideEffects [] @@ -101,22 +109,78 @@ Abc_Obj_t * Lpk_Implement( Abc_Ntk_t * pNtk, Vec_Ptr_t * vLeaves, int nLeavesOld ***********************************************************************/ int Lpk_Decompose_rec( Lpk_Fun_t * p ) { + Lpk_Res_t * pResMux, * pResDsd; Lpk_Fun_t * p2; - int VarPol; - assert( p->nAreaLim > 0 ); - if ( p->nVars <= p->nLutK ) - return 1; - // check if decomposition exists - VarPol = Lpk_MuxAnalize( p ); - if ( VarPol == -1 ) + // is only called for non-trivial blocks + assert( p->nLutK >= 3 && p->nLutK <= 6 ); + assert( p->nVars > p->nLutK ); + // skip if area bound is exceeded + if ( Lpk_LutNumLuts(p->nVars, p->nLutK) > (int)p->nAreaLim ) return 0; - // split and call recursively - p2 = Lpk_MuxSplit( p, VarPol ); - if ( !Lpk_Decompose_rec( p2 ) ) + // skip if delay bound is exceeded + if ( Lpk_SuppDelay(p->uSupp, p->pDelays) > (int)p->nDelayLim ) return 0; - return Lpk_Decompose_rec( p ); + // check MUX decomposition + pResMux = Lpk_MuxAnalize( p ); + assert( !pResMux || (pResMux->DelayEst <= (int)p->nDelayLim && pResMux->AreaEst <= (int)p->nAreaLim) ); + // accept MUX decomposition if it is "good" + if ( pResMux && pResMux->nSuppSizeS <= (int)p->nLutK && pResMux->nSuppSizeL <= (int)p->nLutK ) + pResDsd = NULL; + else + { + pResDsd = Lpk_DsdAnalize( p ); + assert( !pResDsd || (pResDsd->DelayEst <= (int)p->nDelayLim && pResDsd->AreaEst <= (int)p->nAreaLim) ); + } + if ( pResMux && pResDsd ) + { + // compare two decompositions + if ( pResMux->AreaEst < pResDsd->AreaEst || + (pResMux->AreaEst == pResDsd->AreaEst && pResMux->nSuppSizeL < pResDsd->nSuppSizeL) || + (pResMux->AreaEst == pResDsd->AreaEst && pResMux->nSuppSizeL == pResDsd->nSuppSizeL && pResMux->DelayEst < pResDsd->DelayEst) ) + pResDsd = NULL; + else + pResMux = NULL; + } + assert( pResMux == NULL || pResDsd == NULL ); + if ( pResMux ) + { + p2 = Lpk_MuxSplit( p, pResMux->pCofVars[0], pResMux->Polarity ); + if ( p2->nVars > p->nLutK && !Lpk_Decompose_rec( p2 ) ) + return 0; + if ( p->nVars > p->nLutK && !Lpk_Decompose_rec( p ) ) + return 0; + return 1; + } + if ( pResDsd ) + { + p2 = Lpk_DsdSplit( p, pResDsd->pCofVars, pResDsd->nCofVars, pResDsd->BSVars ); + assert( p2->nVars <= (int)p->nLutK ); + if ( p->nVars > p->nLutK && !Lpk_Decompose_rec( p ) ) + return 0; + return 1; + } + return 0; } +/**Function************************************************************* + + Synopsis [Removes decomposed nodes from the array of fanins.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Lpk_DecomposeClean( Vec_Ptr_t * vLeaves, int nLeavesOld ) +{ + Lpk_Fun_t * pFunc; + int i; + Vec_PtrForEachEntryStart( vLeaves, pFunc, i, nLeavesOld ) + Lpk_FunFree( pFunc ); + Vec_PtrShrink( vLeaves, nLeavesOld ); +} /**Function************************************************************* @@ -131,22 +195,16 @@ int Lpk_Decompose_rec( Lpk_Fun_t * p ) ***********************************************************************/ Abc_Obj_t * Lpk_Decompose( Abc_Ntk_t * pNtk, Vec_Ptr_t * vLeaves, unsigned * pTruth, int nLutK, int AreaLim, int DelayLim ) { - Lpk_Fun_t * p; + Lpk_Fun_t * pFun; Abc_Obj_t * pObjNew = NULL; - int i, nLeaves; - // create the starting function - nLeaves = Vec_PtrSize( vLeaves ); - p = Lpk_FunCreate( pNtk, vLeaves, pTruth, nLutK, AreaLim, DelayLim ); - Lpk_FunSuppMinimize( p ); - // decompose the function - if ( Lpk_Decompose_rec(p) ) + int nLeaves = Vec_PtrSize( vLeaves ); + pFun = Lpk_FunCreate( pNtk, vLeaves, pTruth, nLutK, AreaLim, DelayLim ); + Lpk_FunSuppMinimize( pFun ); + if ( pFun->nVars <= pFun->nLutK ) + pObjNew = Lpk_ImplementFun( pNtk, vLeaves, pFun ); + else if ( Lpk_Decompose_rec(pFun) ) pObjNew = Lpk_Implement( pNtk, vLeaves, nLeaves ); - else - { - for ( i = Vec_PtrSize(vLeaves) - 1; i >= nLeaves; i-- ) - Lpk_FunFree( Vec_PtrEntry(vLeaves, i) ); - } - Vec_PtrShrink( vLeaves, nLeaves ); + Lpk_DecomposeClean( vLeaves, nLeaves ); return pObjNew; } diff --git a/src/opt/lpk/lpkAbcDsd.c b/src/opt/lpk/lpkAbcDsd.c index 8de8391f..f2e19945 100644 --- a/src/opt/lpk/lpkAbcDsd.c +++ b/src/opt/lpk/lpkAbcDsd.c @@ -30,9 +30,11 @@ /**Function************************************************************* - Synopsis [Returns the variable whose cofs have min sum of supp sizes.] + Synopsis [Cofactors TTs w.r.t. all vars and finds the best var.] - Description [] + Description [The best variable is the variable with the minimum + sum total of the support sizes of all truth tables. This procedure + computes and returns cofactors w.r.t. the best variable.] SideEffects [] @@ -42,6 +44,7 @@ int Lpk_FunComputeMinSuppSizeVar( Lpk_Fun_t * p, unsigned ** ppTruths, int nTruths, unsigned ** ppCofs ) { int i, Var, VarBest, nSuppSize0, nSuppSize1, nSuppTotalMin, nSuppTotalCur, nSuppMaxMin, nSuppMaxCur; + assert( nTruths > 0 ); VarBest = -1; Lpk_SuppForEachVar( p->uSupp, Var ) { @@ -85,7 +88,7 @@ int Lpk_FunComputeMinSuppSizeVar( Lpk_Fun_t * p, unsigned ** ppTruths, int nTrut SeeAlso [] ***********************************************************************/ -unsigned Lpk_ComputeBoundSets_rec( Kit_DsdNtk_t * p, int iLit, Vec_Int_t * vSets ) +unsigned Lpk_ComputeBoundSets_rec( Kit_DsdNtk_t * p, int iLit, Vec_Int_t * vSets, int nSizeMax ) { unsigned i, iLitFanin, uSupport, uSuppCur; Kit_DsdObj_t * pObj; @@ -99,7 +102,7 @@ unsigned Lpk_ComputeBoundSets_rec( Kit_DsdNtk_t * p, int iLit, Vec_Int_t * vSets uSupport = 0; Kit_DsdObjForEachFanin( p, pObj, iLitFanin, i ) { - uSupps[i] = Lpk_ComputeBoundSets_rec( p, iLitFanin, vSets ); + uSupps[i] = Lpk_ComputeBoundSets_rec( p, iLitFanin, vSets, nSizeMax ); uSupport |= uSupps[i]; } // create all subsets, except empty and full @@ -110,7 +113,8 @@ unsigned Lpk_ComputeBoundSets_rec( Kit_DsdNtk_t * p, int iLit, Vec_Int_t * vSets for ( i = 0; i < pObj->nFans; i++ ) if ( s & (1 << i) ) uSuppCur |= uSupps[i]; - Vec_IntPush( vSets, uSuppCur ); + if ( Kit_WordCountOnes(uSuppCur) <= nSizeMax ) + Vec_IntPush( vSets, uSuppCur ); } return uSupport; } @@ -119,9 +123,10 @@ unsigned Lpk_ComputeBoundSets_rec( Kit_DsdNtk_t * p, int iLit, Vec_Int_t * vSets uSupport = 0; Kit_DsdObjForEachFanin( p, pObj, iLitFanin, i ) { - uSuppCur = Lpk_ComputeBoundSets_rec( p, iLitFanin, vSets ); + uSuppCur = Lpk_ComputeBoundSets_rec( p, iLitFanin, vSets, nSizeMax ); uSupport |= uSuppCur; - Vec_IntPush( vSets, uSuppCur ); + if ( Kit_WordCountOnes(uSuppCur) <= nSizeMax ) + Vec_IntPush( vSets, uSuppCur ); } return uSupport; } @@ -150,12 +155,15 @@ Vec_Int_t * Lpk_ComputeBoundSets( Kit_DsdNtk_t * p, int nSizeMax ) if ( Kit_DsdNtkRoot(p)->Type == KIT_DSD_VAR ) { uSupport = ( 1 << Kit_DsdLit2Var(Kit_DsdNtkRoot(p)->pFans[0]) ); - Vec_IntPush( vSets, uSupport ); + if ( Kit_WordCountOnes(uSupport) <= nSizeMax ) + Vec_IntPush( vSets, uSupport ); return vSets; } - uSupport = Lpk_ComputeBoundSets_rec( p, p->Root, vSets ); + uSupport = Lpk_ComputeBoundSets_rec( p, p->Root, vSets, nSizeMax ); assert( (uSupport & 0xFFFF0000) == 0 ); - Vec_IntPush( vSets, uSupport ); + // add the total support of the network + if ( Kit_WordCountOnes(uSupport) <= nSizeMax ) + Vec_IntPush( vSets, uSupport ); // set the remaining variables Vec_IntForEachEntry( vSets, Number, i ) { @@ -176,7 +184,7 @@ Vec_Int_t * Lpk_ComputeBoundSets( Kit_DsdNtk_t * p, int nSizeMax ) SeeAlso [] ***********************************************************************/ -Vec_Int_t * Lpk_MergeBoundSets( Vec_Int_t * vSets0, Vec_Int_t * vSets1 ) +Vec_Int_t * Lpk_MergeBoundSets( Vec_Int_t * vSets0, Vec_Int_t * vSets1, int nSizeMax ) { Vec_Int_t * vSets; int Entry0, Entry1, Entry; @@ -188,7 +196,8 @@ Vec_Int_t * Lpk_MergeBoundSets( Vec_Int_t * vSets0, Vec_Int_t * vSets1 ) Entry = Entry0 | Entry1; if ( (Entry & (Entry >> 16)) ) continue; - Vec_IntPush( vSets, Entry ); + if ( Kit_WordCountOnes(Entry) <= nSizeMax ) + Vec_IntPush( vSets, Entry ); } return vSets; } @@ -266,14 +275,15 @@ void Lpk_FunFreeTruthTables( Lpk_Fun_t * p, int nCofDepth, unsigned * ppTruths[5 SeeAlso [] ***********************************************************************/ -Lpk_Res_t * Lpk_DsdAnalize( Lpk_Fun_t * p, int nCofDepth ) +void Lpk_DsdAnalizeOne( Lpk_Fun_t * p, int nCofDepth, Lpk_Res_t * pRes ) { - static Lpk_Res_t Res, * pRes = &Res; unsigned * ppTruths[5][16]; Vec_Int_t * pvBSets[4][8]; Kit_DsdNtk_t * pNtkDec, * pTemp; unsigned uBoundSet; int i, k, nVarsBS, nVarsRem, Delay, Area; + assert( nCofDepth >= 0 && nCofDepth < 4 ); + assert( nCofDepth < (int)p->nLutK - 1 ); Lpk_FunAllocTruthTables( p, nCofDepth, ppTruths ); // find the best cofactors memset( pRes, 0, sizeof(Lpk_Res_t) ); @@ -291,7 +301,7 @@ Lpk_Res_t * Lpk_DsdAnalize( Lpk_Fun_t * p, int nCofDepth ) // derive the set of feasible boundsets for ( i = nCofDepth - 1; i >= 0; i-- ) for ( k = 0; k < (1<<i); k++ ) - pvBSets[i][k] = Lpk_MergeBoundSets( pvBSets[i+1][2*k+0], pvBSets[i+1][2*k+1] ); + pvBSets[i][k] = Lpk_MergeBoundSets( pvBSets[i+1][2*k+0], pvBSets[i+1][2*k+1], p->nLutK - nCofDepth ); // compare the resulting boundsets Vec_IntForEachEntry( pvBSets[0][0], uBoundSet, i ) { @@ -299,12 +309,13 @@ Lpk_Res_t * Lpk_DsdAnalize( Lpk_Fun_t * p, int nCofDepth ) continue; assert( (uBoundSet & (uBoundSet >> 16)) == 0 ); nVarsBS = Kit_WordCountOnes( uBoundSet & 0xFFFF ); + assert( nVarsBS <= (int)p->nLutK - nCofDepth ); nVarsRem = p->nVars - nVarsBS + nCofDepth + 1; - Delay = 1 + Lpk_SuppDelay( uBoundSet & 0xFFFF, p->pDelays ); Area = 1 + Lpk_LutNumLuts( nVarsRem, p->nLutK ); - if ( Delay > (int)p->nDelayLim || Area > (int)p->nAreaLim ) + Delay = 1 + Lpk_SuppDelay( uBoundSet & 0xFFFF, p->pDelays ); + if ( Area > (int)p->nAreaLim || Delay > (int)p->nDelayLim ) continue; - if ( uBoundSet == 0 || pRes->DelayEst > Delay || pRes->DelayEst == Delay && pRes->nSuppSizeL > nVarsRem ) + if ( pRes->BSVars == 0 || pRes->DelayEst > Delay || pRes->DelayEst == Delay && pRes->nSuppSizeL > nVarsRem ) { pRes->nBSVars = nVarsBS; pRes->BSVars = uBoundSet; @@ -316,7 +327,60 @@ Lpk_Res_t * Lpk_DsdAnalize( Lpk_Fun_t * p, int nCofDepth ) } // free cofactor storage Lpk_FunFreeTruthTables( p, nCofDepth, ppTruths ); - return pRes; +} + +/**Function************************************************************* + + Synopsis [Performs DSD-based decomposition of the function.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Lpk_Res_t * Lpk_DsdAnalize( Lpk_Fun_t * p ) +{ + static Lpk_Res_t Res0, * pRes0 = &Res0; + static Lpk_Res_t Res1, * pRes1 = &Res1; + static Lpk_Res_t Res2, * pRes2 = &Res2; + static Lpk_Res_t Res3, * pRes3 = &Res3; + memset( pRes0, 0, sizeof(Lpk_Res_t) ); + memset( pRes1, 0, sizeof(Lpk_Res_t) ); + memset( pRes2, 0, sizeof(Lpk_Res_t) ); + memset( pRes3, 0, sizeof(Lpk_Res_t) ); + assert( p->uSupp == Kit_BitMask(p->nVars) ); + + // try decomposition without cofactoring + Lpk_DsdAnalizeOne( p, 0, pRes0 ); + if ( pRes0->nBSVars == (int)p->nLutK && pRes0->AreaEst <= (int)p->nAreaLim && pRes0->DelayEst <= (int)p->nDelayLim ) + return pRes0; + + // cofactor 1 time + if ( p->nLutK >= 3 ) + Lpk_DsdAnalizeOne( p, 1, pRes1 ); + assert( pRes1->nBSVars <= (int)p->nLutK - 1 ); + if ( pRes1->nBSVars == (int)p->nLutK - 1 && pRes1->AreaEst <= (int)p->nAreaLim && pRes1->DelayEst <= (int)p->nDelayLim ) + return pRes1; + + // cofactor 2 times + if ( p->nLutK >= 4 ) + Lpk_DsdAnalizeOne( p, 2, pRes2 ); + assert( pRes2->nBSVars <= (int)p->nLutK - 2 ); + if ( pRes2->nBSVars == (int)p->nLutK - 2 && pRes2->AreaEst <= (int)p->nAreaLim && pRes2->DelayEst <= (int)p->nDelayLim ) + return pRes2; + + // cofactor 3 times + if ( p->nLutK >= 5 ) + Lpk_DsdAnalizeOne( p, 3, pRes3 ); + assert( pRes3->nBSVars <= (int)p->nLutK - 3 ); + if ( pRes3->nBSVars == (int)p->nLutK - 3 && pRes3->AreaEst <= (int)p->nAreaLim && pRes3->DelayEst <= (int)p->nDelayLim ) + return pRes3; + + // choose the best under these conditions + + return NULL; } /**Function************************************************************* @@ -332,19 +396,21 @@ Lpk_Res_t * Lpk_DsdAnalize( Lpk_Fun_t * p, int nCofDepth ) ***********************************************************************/ Lpk_Fun_t * Lpk_DsdSplit( Lpk_Fun_t * p, char * pCofVars, int nCofVars, unsigned uBoundSet ) { + Lpk_Fun_t * pNew; Kit_DsdMan_t * pDsdMan; Kit_DsdNtk_t * pNtkDec, * pTemp; unsigned * pTruth = Lpk_FunTruth( p, 0 ); unsigned * pTruth0 = Lpk_FunTruth( p, 1 ); unsigned * pTruth1 = Lpk_FunTruth( p, 2 ); - Lpk_Fun_t * pNew; unsigned * ppTruths[5][16]; char pBSVars[5]; - int i, k, nVars, nCofs; + int i, k, nVars, iVacVar, nCofs; // get the bound set variables nVars = Lpk_SuppToVars( uBoundSet, pBSVars ); + // get the vacuous variable + iVacVar = pBSVars[0]; // compute the cofactors - Lpk_FunAllocTruthTables( p, nCofVars, ppTruths ); + Lpk_FunAllocTruthTables( p, nCofVars + 1, ppTruths ); for ( i = 0; i < nCofVars; i++ ) for ( k = 0; k < (1<<i); k++ ) { @@ -353,38 +419,37 @@ Lpk_Fun_t * Lpk_DsdSplit( Lpk_Fun_t * p, char * pCofVars, int nCofVars, unsigned } // decompose each cofactor w.r.t. the bound set nCofs = (1<<nCofVars); - pDsdMan = Kit_DsdManAlloc( p->nVars, p->nVars * 4 ); + pDsdMan = Kit_DsdManAlloc( p->nVars, p->nVars * 2 ); for ( k = 0; k < nCofs; k++ ) { pNtkDec = Kit_DsdDecompose( ppTruths[nCofVars][k], p->nVars ); pNtkDec = Kit_DsdExpand( pTemp = pNtkDec ); Kit_DsdNtkFree( pTemp ); - Kit_DsdTruthPartialTwo( pDsdMan, pNtkDec, uBoundSet, pBSVars[0], ppTruths[nCofVars+1][k], ppTruths[nCofVars+1][nCofs+k] ); + Kit_DsdTruthPartialTwo( pDsdMan, pNtkDec, uBoundSet, iVacVar, ppTruths[nCofVars+1][k], ppTruths[nCofVars+1][nCofs+k] ); Kit_DsdNtkFree( pNtkDec ); } Kit_DsdManFree( pDsdMan ); - // compute the composition function - for ( i = nCofVars - 1; i >= 1; i-- ) + // compute the composition/decomposition functions (they will be in pTruth0/pTruth1) + for ( i = nCofVars; i >= 1; i-- ) for ( k = 0; k < (1<<i); k++ ) - Kit_TruthMuxVar( ppTruths[i][k], ppTruths[i+1][2*k+0], ppTruths[i+1][2*k+1], nVars, pCofVars[i] ); - // now the composition/decomposition functions are in pTruth0/pTruth1 + Kit_TruthMuxVar( ppTruths[i][k], ppTruths[i+1][2*k+0], ppTruths[i+1][2*k+1], nVars, pCofVars[i-1] ); // derive the new component pNew = Lpk_FunDup( p, pTruth1 ); // update the old component Kit_TruthCopy( pTruth, pTruth0, p->nVars ); p->uSupp = Kit_TruthSupport( pTruth0, p->nVars ); - p->pFanins[pBSVars[0]] = pNew->Id; - p->pDelays[pBSVars[0]] = Lpk_SuppDelay( pNew->uSupp, pNew->pDelays ); + p->pFanins[iVacVar] = pNew->Id; + p->pDelays[iVacVar] = Lpk_SuppDelay( pNew->uSupp, pNew->pDelays ); // support minimize both Lpk_FunSuppMinimize( p ); Lpk_FunSuppMinimize( pNew ); // update delay and area requirements - pNew->nDelayLim = p->nDelayLim - 1; + pNew->nDelayLim = p->pDelays[iVacVar]; pNew->nAreaLim = 1; p->nAreaLim = p->nAreaLim - 1; // free cofactor storage - Lpk_FunFreeTruthTables( p, nCofVars, ppTruths ); + Lpk_FunFreeTruthTables( p, nCofVars + 1, ppTruths ); return pNew; } diff --git a/src/opt/lpk/lpkAbcMux.c b/src/opt/lpk/lpkAbcMux.c index 6549e175..159cae96 100644 --- a/src/opt/lpk/lpkAbcMux.c +++ b/src/opt/lpk/lpkAbcMux.c @@ -48,7 +48,6 @@ void Lpk_FunComputeCofs( Lpk_Fun_t * p, int iVar ) Kit_TruthCofactor1New( pTruth1, pTruth, p->nVars, iVar ); } - /**Function************************************************************* Synopsis [Computes cofactors w.r.t. each variable.] @@ -85,18 +84,18 @@ void Lpk_FunComputeCofSupps( Lpk_Fun_t * p, unsigned * puSupps ) SeeAlso [] ***********************************************************************/ -int Lpk_MuxAnalize( Lpk_Fun_t * p ) +Lpk_Res_t * Lpk_MuxAnalize( Lpk_Fun_t * p ) { - unsigned puSupps[32] = {0}; - int nSuppSize0, nSuppSize1, Delay, Delay0, Delay1, DelayA, DelayB; - int Var, Area, Polarity, VarBest, AreaBest, PolarityBest, nSuppSizeBest; - - if ( p->nVars > p->nAreaLim * (p->nLutK - 1) + 1 ) - return -1; + static Lpk_Res_t Res, * pRes = &Res; + unsigned puSupps[32]; + int nSuppSize0, nSuppSize1, nSuppSizeBest; + int Var, Area, Polarity, Delay, Delay0, Delay1, DelayA, DelayB; + memset( pRes, 0, sizeof(Lpk_Res_t) ); + assert( p->uSupp == Kit_BitMask(p->nVars) ); // get cofactor supports for each variable Lpk_FunComputeCofSupps( p, puSupps ); - // derive the delay and area of each MUX-decomposition - VarBest = -1; + // derive the delay and area after MUX-decomp with each var - and find the best var + pRes->Variable = -1; Lpk_SuppForEachVar( p->uSupp, Var ) { nSuppSize0 = Kit_WordCountOnes(puSupps[2*Var+0]); @@ -124,20 +123,20 @@ int Lpk_MuxAnalize( Lpk_Fun_t * p ) Area = 1 + Lpk_LutNumLuts( nSuppSize1, p->nLutK ); Polarity = 0; } - else if ( nSuppSize0 <= (int)p->nLutK ) + else if ( nSuppSize1 <= (int)p->nLutK - 2 ) { DelayA = Lpk_SuppDelay( puSupps[2*Var+1] | (1<<Var), p->pDelays ); DelayB = Lpk_SuppDelay( puSupps[2*Var+0] , p->pDelays ); Delay = ABC_MAX( DelayA, DelayB + 1 ); - Area = 1 + Lpk_LutNumLuts( nSuppSize1+2, p->nLutK ); + Area = 1 + Lpk_LutNumLuts( nSuppSize0, p->nLutK ); Polarity = 1; } - else if ( nSuppSize1 <= (int)p->nLutK - 2 ) + else if ( nSuppSize0 <= (int)p->nLutK ) { DelayA = Lpk_SuppDelay( puSupps[2*Var+1] | (1<<Var), p->pDelays ); DelayB = Lpk_SuppDelay( puSupps[2*Var+0] , p->pDelays ); Delay = ABC_MAX( DelayA, DelayB + 1 ); - Area = 1 + Lpk_LutNumLuts( nSuppSize0, p->nLutK ); + Area = 1 + Lpk_LutNumLuts( nSuppSize1+2, p->nLutK ); Polarity = 1; } else if ( nSuppSize1 <= (int)p->nLutK ) @@ -171,15 +170,16 @@ int Lpk_MuxAnalize( Lpk_Fun_t * p ) continue; if ( Area > (int)p->nAreaLim ) continue; - if ( VarBest == -1 || AreaBest > Area || (AreaBest == Area && nSuppSizeBest > nSuppSize0+nSuppSize1) ) + if ( pRes->Variable == -1 || pRes->AreaEst > Area || (pRes->AreaEst == Area && nSuppSizeBest > nSuppSize0+nSuppSize1) ) { - VarBest = Var; - AreaBest = Area; - PolarityBest = Polarity; - nSuppSizeBest = nSuppSize0+nSuppSize1; + pRes->Variable = Var; + pRes->Polarity = Polarity; + pRes->AreaEst = Area; + pRes->DelayEst = Delay; + nSuppSizeBest = nSuppSize0+nSuppSize1; } } - return (VarBest == -1)? -1 : (2*VarBest + Polarity); + return pRes->Variable == -1 ? NULL : pRes; } /**Function************************************************************* @@ -193,60 +193,61 @@ int Lpk_MuxAnalize( Lpk_Fun_t * p ) SeeAlso [] ***********************************************************************/ -Lpk_Fun_t * Lpk_MuxSplit( Lpk_Fun_t * p, int VarPol ) +Lpk_Fun_t * Lpk_MuxSplit( Lpk_Fun_t * p, int Var, int Pol ) { Lpk_Fun_t * pNew; unsigned * pTruth = Lpk_FunTruth( p, 0 ); unsigned * pTruth0 = Lpk_FunTruth( p, 1 ); unsigned * pTruth1 = Lpk_FunTruth( p, 2 ); - int Var = VarPol / 2; - int Pol = VarPol % 2; int iVarVac; - assert( VarPol >= 0 && VarPol < 2 * (int)p->nVars ); + assert( Var >= 0 && Var < (int)p->nVars ); assert( p->nAreaLim >= 2 ); Lpk_FunComputeCofs( p, Var ); - if ( Pol == 0 ) + // derive the new component + pNew = Lpk_FunDup( p, Pol ? pTruth0 : pTruth1 ); + // update the support of the old component + p->uSupp = Kit_TruthSupport( Pol ? pTruth1 : pTruth0, p->nVars ); + p->uSupp |= (1 << Var); + // update the truth table of the old component + iVarVac = Kit_WordFindFirstBit( ~p->uSupp ); + assert( iVarVac < (int)p->nVars ); + Kit_TruthIthVar( pTruth, p->nVars, Var ); + if ( Pol ) + Kit_TruthMuxVar( pTruth, pTruth, pTruth1, p->nVars, iVarVac ); + else + Kit_TruthMuxVar( pTruth, pTruth0, pTruth, p->nVars, iVarVac ); + // set the decomposed variable + p->pFanins[iVarVac] = pNew->Id; + p->pDelays[iVarVac] = p->nDelayLim - 1; + // support minimize both + Lpk_FunSuppMinimize( p ); + Lpk_FunSuppMinimize( pNew ); + // update delay and area requirements + pNew->nDelayLim = p->nDelayLim - 1; + if ( p->nVars <= p->nLutK ) { - // derive the new component - pNew = Lpk_FunDup( p, pTruth1 ); - // update the old component - p->uSupp = Kit_TruthSupport( pTruth0, p->nVars ); - iVarVac = Kit_WordFindFirstBit( ~(p->uSupp | (1 << Var)) ); - assert( iVarVac < (int)p->nVars ); - Kit_TruthIthVar( pTruth, p->nVars, iVarVac ); - // update the truth table - Kit_TruthMux( pTruth, pTruth0, pTruth1, pTruth, p->nVars ); - p->pFanins[iVarVac] = pNew->Id; - p->pDelays[iVarVac] = Lpk_SuppDelay( pNew->uSupp, pNew->pDelays ); - // support minimize both - Lpk_FunSuppMinimize( p ); - Lpk_FunSuppMinimize( pNew ); - // update delay and area requirements - pNew->nDelayLim = p->nDelayLim - 1; - if ( p->nVars <= p->nLutK ) - { - pNew->nAreaLim = p->nAreaLim - 1; - p->nAreaLim = 1; - } - else if ( pNew->nVars <= pNew->nLutK ) - { - pNew->nAreaLim = 1; - p->nAreaLim = p->nAreaLim - 1; - } - else if ( p->nVars < pNew->nVars ) - { - pNew->nAreaLim = p->nAreaLim / 2 + p->nAreaLim % 2; - p->nAreaLim = p->nAreaLim / 2 - p->nAreaLim % 2; - } - else // if ( pNew->nVars < p->nVars ) - { - pNew->nAreaLim = p->nAreaLim / 2 - p->nAreaLim % 2; - p->nAreaLim = p->nAreaLim / 2 + p->nAreaLim % 2; - } + pNew->nAreaLim = p->nAreaLim - 1; + p->nAreaLim = 1; + } + else if ( pNew->nVars <= pNew->nLutK ) + { + pNew->nAreaLim = 1; + p->nAreaLim = p->nAreaLim - 1; + } + else if ( p->nVars < pNew->nVars ) + { + pNew->nAreaLim = p->nAreaLim / 2 + p->nAreaLim % 2; + p->nAreaLim = p->nAreaLim / 2 - p->nAreaLim % 2; + } + else // if ( pNew->nVars < p->nVars ) + { + pNew->nAreaLim = p->nAreaLim / 2 - p->nAreaLim % 2; + p->nAreaLim = p->nAreaLim / 2 + p->nAreaLim % 2; } return p; } + //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// diff --git a/src/opt/lpk/lpkAbcUtil.c b/src/opt/lpk/lpkAbcUtil.c index 960ebded..681ec092 100644 --- a/src/opt/lpk/lpkAbcUtil.c +++ b/src/opt/lpk/lpkAbcUtil.c @@ -139,20 +139,20 @@ Lpk_Fun_t * Lpk_FunDup( Lpk_Fun_t * p, unsigned * pTruth ) ***********************************************************************/ void Lpk_FunSuppMinimize( Lpk_Fun_t * p ) { - int j, k, nVarsNew; + int i, k, nVarsNew; // compress the truth table if ( p->uSupp == Kit_BitMask(p->nVars) ) return; // minimize support nVarsNew = Kit_WordCountOnes(p->uSupp); Kit_TruthShrink( Lpk_FunTruth(p, 1), Lpk_FunTruth(p, 0), nVarsNew, p->nVars, p->uSupp, 1 ); - for ( j = k = 0; j < (int)p->nVars; j++ ) - if ( p->uSupp & (1 << j) ) - { - p->pFanins[k] = p->pFanins[j]; - p->pDelays[k] = p->pDelays[j]; - k++; - } + k = 0; + Lpk_SuppForEachVar( p->uSupp, i ) + { + p->pFanins[k] = p->pFanins[i]; + p->pDelays[k] = p->pDelays[i]; + k++; + } assert( k == nVarsNew ); p->nVars = k; p->uSupp = Kit_BitMask(p->nVars); diff --git a/src/opt/lpk/lpkCore.c b/src/opt/lpk/lpkCore.c index fda5423e..37bfd956 100644 --- a/src/opt/lpk/lpkCore.c +++ b/src/opt/lpk/lpkCore.c @@ -361,17 +361,10 @@ p->timeTruth += clock() - clk; if ( p->pPars->fVeryVerbose ) { // char * pFileName; - int nSuppSize; - Kit_DsdNtk_t * pDsdNtk; - nSuppSize = Extra_TruthSupportSize(pTruth, pCut->nLeaves); + int nSuppSize = Extra_TruthSupportSize( pTruth, pCut->nLeaves ); printf( " C%02d: L= %2d/%2d V= %2d/%d N= %d W= %4.2f ", i, pCut->nLeaves, nSuppSize, pCut->nNodes, pCut->nNodesDup, pCut->nLuts, pCut->Weight ); - - pDsdNtk = Kit_DsdDecompose( pTruth, pCut->nLeaves ); -// Kit_DsdVerify( pDsdNtk, pTruth, pCut->nLeaves ); - Kit_DsdPrint( stdout, pDsdNtk ); - Kit_DsdNtkFree( pDsdNtk ); -// Kit_DsdPrintFromTruth( pTruth, pCut->nLeaves ); + Kit_DsdPrintFromTruth( pTruth, pCut->nLeaves ); // pFileName = Kit_TruthDumpToFile( pTruth, pCut->nLeaves, Count++ ); // printf( "Saved truth table in file \"%s\".\n", pFileName ); } diff --git a/src/opt/lpk/lpkCut.c b/src/opt/lpk/lpkCut.c index d0908a6a..f5c0c66c 100644 --- a/src/opt/lpk/lpkCut.c +++ b/src/opt/lpk/lpkCut.c @@ -30,7 +30,7 @@ /**Function************************************************************* - Synopsis [Computes the truth able of one cut.] + Synopsis [Computes the truth table of one cut.] Description [] @@ -445,10 +445,17 @@ void Lpk_NodeCutsOne( Lpk_Man_t * p, Lpk_Cut_t * pCut, int Node ) memcpy( pCutNew->pNodes, pCut->pNodes, pCut->nNodes * sizeof(int) ); pCutNew->nNodes = pCut->nNodes; pCutNew->nNodesDup = pCut->nNodesDup; + // check if the node is already there + // if so, move the node to be the last for ( i = 0; i < (int)pCutNew->nNodes; i++ ) if ( pCutNew->pNodes[i] == Node ) + { + for ( k = i; k < (int)pCutNew->nNodes - 1; k++ ) + pCutNew->pNodes[k] = pCutNew->pNodes[k+1]; + pCutNew->pNodes[k] = Node; break; + } if ( i == (int)pCutNew->nNodes ) // new node { pCutNew->pNodes[ pCutNew->nNodes++ ] = Node; diff --git a/src/opt/lpk/lpkInt.h b/src/opt/lpk/lpkInt.h index 7022cc4a..32fb05b3 100644 --- a/src/opt/lpk/lpkInt.h +++ b/src/opt/lpk/lpkInt.h @@ -122,14 +122,14 @@ struct Lpk_Man_t_ typedef struct Lpk_Fun_t_ Lpk_Fun_t; struct Lpk_Fun_t_ { - Vec_Ptr_t * vNodes; // the array of all functions - unsigned int Id : 5; // the ID of this node + Vec_Ptr_t * vNodes; // the array of leaves and decomposition nodes + unsigned int Id : 8; // the ID of this node unsigned int nVars : 5; // the number of variables unsigned int nLutK : 4; // the number of LUT inputs - unsigned int nAreaLim : 8; // the area limit (the largest allowed) + unsigned int nAreaLim : 5; // the area limit (the largest allowed) unsigned int nDelayLim : 10; // the delay limit (the largest allowed) - char pFanins[16]; // the fanins of this function char pDelays[16]; // the delays of the inputs + char pFanins[16]; // the fanins of this function unsigned uSupp; // the support of this component unsigned pTruth[0]; // the truth table (contains room for three truth tables) }; @@ -146,6 +146,8 @@ struct Lpk_Res_t_ int nSuppSizeL; // support size of the larger (composition) function int DelayEst; // estimated delay of the decomposition int AreaEst; // estimated area of the decomposition + int Variable; // variable in MUX decomposition + int Polarity; // polarity in MUX decomposition }; static inline int Lpk_LutNumVars( int nLutsLim, int nLutK ) { return nLutsLim * (nLutK - 1) + 1; } @@ -177,11 +179,11 @@ static inline unsigned * Lpk_FunTruth( Lpk_Fun_t * p, int Num ) { assert( Num /*=== lpkAbcDec.c ============================================================*/ extern Abc_Obj_t * Lpk_Decompose( Abc_Ntk_t * pNtk, Vec_Ptr_t * vLeaves, unsigned * pTruth, int nLutK, int AreaLim, int DelayLim ); /*=== lpkAbcDsd.c ============================================================*/ -extern Lpk_Res_t * Lpk_DsdAnalize( Lpk_Fun_t * p, int nCofDepth ); +extern Lpk_Res_t * Lpk_DsdAnalize( Lpk_Fun_t * p ); extern Lpk_Fun_t * Lpk_DsdSplit( Lpk_Fun_t * p, char * pCofVars, int nCofVars, unsigned uBoundSet ); /*=== lpkAbcMux.c ============================================================*/ -extern int Lpk_MuxAnalize( Lpk_Fun_t * p ); -extern Lpk_Fun_t * Lpk_MuxSplit( Lpk_Fun_t * p, int VarPol ); +extern Lpk_Res_t * Lpk_MuxAnalize( Lpk_Fun_t * p ); +extern Lpk_Fun_t * Lpk_MuxSplit( Lpk_Fun_t * p, int Var, int Pol ); /*=== lpkAbcUtil.c ============================================================*/ extern Lpk_Fun_t * Lpk_FunAlloc( int nVars ); extern void Lpk_FunFree( Lpk_Fun_t * p ); diff --git a/src/opt/lpk/lpkMux.c b/src/opt/lpk/lpkMux.c index 7928f77e..ed046ad7 100644 --- a/src/opt/lpk/lpkMux.c +++ b/src/opt/lpk/lpkMux.c @@ -167,6 +167,8 @@ If_Obj_t * Lpk_MapSuppRedDec_rec( Lpk_Man_t * p, unsigned * pTruth, int nVars, I ppNtks[1] = Kit_DsdExpand( pTemp = ppNtks[1] ); Kit_DsdNtkFree( pTemp ); Kit_DsdTruthPartial( p->pDsdMan, ppNtks[0], pDec0, uSubset0 ); Kit_DsdTruthPartial( p->pDsdMan, ppNtks[1], pDec1, uSubset1 ); +// Kit_DsdTruthPartialTwo( p->pDsdMan, ppNtks[0], uSubset0, iVarReused, pCo0, pDec0 ); +// Kit_DsdTruthPartialTwo( p->pDsdMan, ppNtks[1], uSubset1, iVarReused, pCo1, pDec1 ); Kit_DsdNtkFree( ppNtks[0] ); Kit_DsdNtkFree( ppNtks[1] ); //Kit_DsdPrintFromTruth( pDec0, nVars ); @@ -218,6 +220,7 @@ If_Obj_t * Lpk_MapSuppRedDec_rec( Lpk_Man_t * p, unsigned * pTruth, int nVars, I Kit_TruthMuxVar( pCo1, pCo10, pCo11, nVars, iVarReused ); //Kit_DsdPrintFromTruth( pCo0, nVars ); //Kit_DsdPrintFromTruth( pCo1, nVars ); + // derive the composition function Kit_TruthMuxVar( pCo , pCo0 , pCo1 , nVars, iVar ); |