diff options
author | Alan Mishchenko <alanmi@berkeley.edu> | 2007-10-01 08:01:00 -0700 |
---|---|---|
committer | Alan Mishchenko <alanmi@berkeley.edu> | 2007-10-01 08:01:00 -0700 |
commit | 4812c90424dfc40d26725244723887a2d16ddfd9 (patch) | |
tree | b32ace96e7e2d84d586e09ba605463b6f49c3271 /src/opt/lpk/lpkAbcDec.c | |
parent | e54d9691616b9a0326e2fdb3156bb4eeb8abfcd7 (diff) | |
download | abc-4812c90424dfc40d26725244723887a2d16ddfd9.tar.gz abc-4812c90424dfc40d26725244723887a2d16ddfd9.tar.bz2 abc-4812c90424dfc40d26725244723887a2d16ddfd9.zip |
Version abc71001
Diffstat (limited to 'src/opt/lpk/lpkAbcDec.c')
-rw-r--r-- | src/opt/lpk/lpkAbcDec.c | 290 |
1 files changed, 290 insertions, 0 deletions
diff --git a/src/opt/lpk/lpkAbcDec.c b/src/opt/lpk/lpkAbcDec.c new file mode 100644 index 00000000..aa2d4bc0 --- /dev/null +++ b/src/opt/lpk/lpkAbcDec.c @@ -0,0 +1,290 @@ +/**CFile**************************************************************** + + FileName [lpkAbcDec.c] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [Fast Boolean matching for LUT structures.] + + Synopsis [The new core procedure.] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - April 28, 2007.] + + Revision [$Id: lpkAbcDec.c,v 1.00 2007/04/28 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "lpkInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Implements the function.] + + Description [Returns the node implementing this function.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Abc_Obj_t * Lpk_ImplementFun( Lpk_Man_t * pMan, 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; + if ( p->fMark ) + pMan->nMuxes++; + else + pMan->nDsds++; + // create the new node + pObjNew = Abc_NtkCreateNode( pNtk ); + for ( i = 0; i < (int)p->nVars; i++ ) + Abc_ObjAddFanin( pObjNew, Abc_ObjRegular(Vec_PtrEntry(vLeaves, p->pFanins[i])) ); + Abc_ObjSetLevel( pObjNew, Abc_ObjLevelNew(pObjNew) ); + // assign the node's function + pTruth = Lpk_FunTruth(p, 0); + if ( p->nVars == 0 ) + { + 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; +} + +/**Function************************************************************* + + Synopsis [Implements the function.] + + Description [Returns the node implementing this function.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Abc_Obj_t * Lpk_Implement_rec( Lpk_Man_t * pMan, Abc_Ntk_t * pNtk, Vec_Ptr_t * vLeaves, Lpk_Fun_t * pFun ) +{ + Abc_Obj_t * pFanin, * pRes; + int i; + // prepare the leaves of the function + for ( i = 0; i < (int)pFun->nVars; i++ ) + { + pFanin = Vec_PtrEntry( vLeaves, pFun->pFanins[i] ); + if ( !Abc_ObjIsComplement(pFanin) ) + Lpk_Implement_rec( pMan, pNtk, vLeaves, (Lpk_Fun_t *)pFanin ); + pFanin = Vec_PtrEntry( vLeaves, pFun->pFanins[i] ); + assert( Abc_ObjIsComplement(pFanin) ); + } + // construct the function + pRes = Lpk_ImplementFun( pMan, pNtk, vLeaves, pFun ); + // replace the function + Vec_PtrWriteEntry( vLeaves, pFun->Id, Abc_ObjNot(pRes) ); + Lpk_FunFree( pFun ); + return pRes; +} + +/**Function************************************************************* + + Synopsis [Implements the function.] + + Description [Returns the node implementing this function.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Abc_Obj_t * Lpk_Implement( Lpk_Man_t * pMan, Abc_Ntk_t * pNtk, Vec_Ptr_t * vLeaves, int nLeavesOld ) +{ + Abc_Obj_t * pFanin, * pRes; + int i; + assert( nLeavesOld < Vec_PtrSize(vLeaves) ); + // mark implemented nodes + Vec_PtrForEachEntryStop( vLeaves, pFanin, i, nLeavesOld ) + Vec_PtrWriteEntry( vLeaves, i, Abc_ObjNot(pFanin) ); + // recursively construct starting from the first entry + pRes = Lpk_Implement_rec( pMan, pNtk, vLeaves, Vec_PtrEntry( vLeaves, nLeavesOld ) ); + Vec_PtrShrink( vLeaves, nLeavesOld ); + return pRes; +} + +/**Function************************************************************* + + Synopsis [Decomposes the function using recursive MUX decomposition.] + + 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 [] + + SeeAlso [] + +***********************************************************************/ +int Lpk_Decompose_rec( Lpk_Man_t * pMan, Lpk_Fun_t * p ) +{ + static Lpk_Res_t Res0, * pRes0 = &Res0; + Lpk_Res_t * pResMux, * pResDsd; + Lpk_Fun_t * p2; + int clk; + + // 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; + // skip if delay bound is exceeded + if ( Lpk_SuppDelay(p->uSupp, p->pDelays) > (int)p->nDelayLim ) + return 0; + + // compute supports if needed + if ( !p->fSupports ) + Lpk_FunComputeCofSupps( p ); + + // check DSD decomposition +clk = clock(); + pResDsd = Lpk_DsdAnalize( pMan, p, pMan->pPars->nVarsShared ); +pMan->timeEvalDsdAn += clock() - clk; + if ( pResDsd && (pResDsd->nBSVars == (int)p->nLutK || pResDsd->nBSVars == (int)p->nLutK - 1) && + pResDsd->AreaEst <= (int)p->nAreaLim && pResDsd->DelayEst <= (int)p->nDelayLim ) + { +clk = clock(); + p2 = Lpk_DsdSplit( pMan, p, pResDsd->pCofVars, pResDsd->nCofVars, pResDsd->BSVars ); +pMan->timeEvalDsdSp += clock() - clk; + assert( p2->nVars <= (int)p->nLutK ); + if ( p->nVars > p->nLutK && !Lpk_Decompose_rec( pMan, p ) ) + return 0; + return 1; + } + + // check MUX decomposition +clk = clock(); + pResMux = Lpk_MuxAnalize( pMan, p ); +pMan->timeEvalMuxAn += clock() - clk; +// pResMux = NULL; + 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 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 ) + { +clk = clock(); + p2 = Lpk_MuxSplit( pMan, p, pResMux->Variable, pResMux->Polarity ); +pMan->timeEvalMuxSp += clock() - clk; + if ( p2->nVars > p->nLutK && !Lpk_Decompose_rec( pMan, p2 ) ) + return 0; + if ( p->nVars > p->nLutK && !Lpk_Decompose_rec( pMan, p ) ) + return 0; + return 1; + } + if ( pResDsd ) + { +clk = clock(); + p2 = Lpk_DsdSplit( pMan, p, pResDsd->pCofVars, pResDsd->nCofVars, pResDsd->BSVars ); +pMan->timeEvalDsdSp += clock() - clk; + assert( p2->nVars <= (int)p->nLutK ); + if ( p->nVars > p->nLutK && !Lpk_Decompose_rec( pMan, 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************************************************************* + + Synopsis [Decomposes the function using recursive MUX decomposition.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Abc_Obj_t * Lpk_Decompose( Lpk_Man_t * p, Abc_Ntk_t * pNtk, Vec_Ptr_t * vLeaves, unsigned * pTruth, unsigned * puSupps, int nLutK, int AreaLim, int DelayLim ) +{ + Lpk_Fun_t * pFun; + Abc_Obj_t * pObjNew = NULL; + int nLeaves = Vec_PtrSize( vLeaves ); + pFun = Lpk_FunCreate( pNtk, vLeaves, pTruth, nLutK, AreaLim, DelayLim ); + if ( puSupps[0] || puSupps[1] ) + { +/* + int i; + Lpk_FunComputeCofSupps( pFun ); + for ( i = 0; i < nLeaves; i++ ) + { + assert( pFun->puSupps[2*i+0] == puSupps[2*i+0] ); + assert( pFun->puSupps[2*i+1] == puSupps[2*i+1] ); + } +*/ + memcpy( pFun->puSupps, puSupps, sizeof(unsigned) * 2 * nLeaves ); + pFun->fSupports = 1; + } + Lpk_FunSuppMinimize( pFun ); + if ( pFun->nVars <= pFun->nLutK ) + pObjNew = Lpk_ImplementFun( p, pNtk, vLeaves, pFun ); + else if ( Lpk_Decompose_rec(p, pFun) ) + pObjNew = Lpk_Implement( p, pNtk, vLeaves, nLeaves ); + Lpk_DecomposeClean( vLeaves, nLeaves ); + return pObjNew; +} + + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + |