diff options
Diffstat (limited to 'src/opt/lpk/lpkMux.c')
| -rw-r--r-- | src/opt/lpk/lpkMux.c | 257 |
1 files changed, 257 insertions, 0 deletions
diff --git a/src/opt/lpk/lpkMux.c b/src/opt/lpk/lpkMux.c new file mode 100644 index 00000000..d9e013f0 --- /dev/null +++ b/src/opt/lpk/lpkMux.c @@ -0,0 +1,257 @@ +/**CFile**************************************************************** + + FileName [lpkMux.c] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [Fast Boolean matching for LUT structures.] + + Synopsis [] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - April 28, 2007.] + + Revision [$Id: lpkMux.c,v 1.00 2007/04/28 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "lpkInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Find the best cofactoring variable.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Lpk_MapTreeBestVar( Lpk_Man_t * p, unsigned * pTruth, int nVars ) +{ +// Kit_DsdNtk_t * ppNtks[2], * pTemp; + unsigned * pCof0 = Vec_PtrEntry( p->vTtNodes, 0 ); + unsigned * pCof1 = Vec_PtrEntry( p->vTtNodes, 1 ); + int i, iBestVar, nSuppSizeCur0, nSuppSizeCur1, nSuppSizeCur, nSuppSizeMin; +// int nPrimeSizeCur0, nPrimeSizeCur1, nPrimeSizeCur, nPrimeSizeMin; + + // iterate through variables + iBestVar = -1; + nSuppSizeMin = ABC_INFINITY; +// nPrimeSizeMin = ABC_INFINITY; + for ( i = 0; i < nVars; i++ ) + { + // cofactor the functiona and get support sizes + Kit_TruthCofactor0New( pCof0, pTruth, nVars, i ); + Kit_TruthCofactor1New( pCof1, pTruth, nVars, i ); + nSuppSizeCur0 = Kit_TruthSupportSize( pCof0, nVars ); + nSuppSizeCur1 = Kit_TruthSupportSize( pCof1, nVars ); + nSuppSizeCur = nSuppSizeCur0 + nSuppSizeCur1; +/* + // check the size of the largest prime components + ppNtks[0] = Kit_DsdDecompose( pCof0, nVars ); + ppNtks[1] = Kit_DsdDecompose( pCof1, nVars ); + // compute the largest non-decomp block + nPrimeSizeCur0 = Kit_DsdNonDsdSizeMax(ppNtks[0]); + nPrimeSizeCur1 = Kit_DsdNonDsdSizeMax(ppNtks[1]); + nPrimeSizeCur = KIT_MAX( nPrimeSizeCur0, nPrimeSizeCur1 ); + + printf( "Evaluating variable %c:\n", 'a'+i ); +// Kit_DsdPrintExpanded( ppNtks[0] ); +// Kit_DsdPrintExpanded( ppNtks[1] ); + + ppNtks[0] = Kit_DsdExpand( pTemp = ppNtks[0] ); + Kit_DsdNtkFree( pTemp ); + + ppNtks[1] = Kit_DsdExpand( pTemp = ppNtks[1] ); + Kit_DsdNtkFree( pTemp ); + + Kit_DsdPrint( stdout, ppNtks[0] ); + Kit_DsdPrint( stdout, ppNtks[1] ); + +// Lpk_DsdEvalSets( p, ppNtks[0], ppNtks[1] ); + + // free the networks + Kit_DsdNtkFree( ppNtks[0] ); + Kit_DsdNtkFree( ppNtks[1] ); +*/ + // compare this variable with other variables + if ( nSuppSizeMin > nSuppSizeCur ) //|| (nSuppSizeMin == nSuppSizeCur && nPrimeSizeMin > nPrimeSizeCur ) ) + { + nSuppSizeMin = nSuppSizeCur; +// nPrimeSizeMin = nPrimeSizeCur; + iBestVar = i; + } + } + printf( "\n" ); + assert( iBestVar != -1 ); + return iBestVar; +} + +/**Function************************************************************* + + Synopsis [Maps the function by the best cofactoring.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +If_Obj_t * Lpk_MapTreeMux_rec( Lpk_Man_t * p, unsigned * pTruth, int nVars, If_Obj_t ** ppLeaves ) +{ + If_Obj_t * pObj0, * pObj1; + Kit_DsdNtk_t * ppNtks[2]; + unsigned * pCof0 = Vec_PtrEntry( p->vTtNodes, 0 ); + unsigned * pCof1 = Vec_PtrEntry( p->vTtNodes, 1 ); + int iBestVar; + assert( nVars > 3 ); + p->fCalledOnce = 1; + + // cofactor w.r.t. the best variable + iBestVar = Lpk_MapTreeBestVar( p, pTruth, nVars ); + Kit_TruthCofactor0New( pCof0, pTruth, nVars, iBestVar ); + Kit_TruthCofactor1New( pCof1, pTruth, nVars, iBestVar ); + // decompose the functions + ppNtks[0] = Kit_DsdDecompose( pCof0, nVars ); + ppNtks[1] = Kit_DsdDecompose( pCof1, nVars ); + if ( p->pPars->fVeryVerbose ) + { + printf( "Cofactoring w.r.t. var %c (%d -> %d+%d supp vars):\n", + 'a'+iBestVar, nVars, Kit_TruthSupportSize(pCof0, nVars), Kit_TruthSupportSize(pCof1, nVars) ); + Kit_DsdPrintExpanded( ppNtks[0] ); + Kit_DsdPrintExpanded( ppNtks[1] ); + } + // map the DSD structures + pObj0 = Lpk_MapTree_rec( p, ppNtks[0], ppLeaves, ppNtks[0]->Root, NULL ); + pObj1 = Lpk_MapTree_rec( p, ppNtks[1], ppLeaves, ppNtks[1]->Root, NULL ); + Kit_DsdNtkFree( ppNtks[0] ); + Kit_DsdNtkFree( ppNtks[1] ); + return If_ManCreateMux( p->pIfMan, pObj0, pObj1, ppLeaves[iBestVar] ); +} + + + +/**Function************************************************************* + + Synopsis [Implements support-reducing decomposition.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +If_Obj_t * Lpk_MapSuppRedDec_rec( Lpk_Man_t * p, unsigned * pTruth, int nVars, If_Obj_t ** ppLeaves ) +{ + Kit_DsdNtk_t * pNtkDec, * pNtkComp; + If_Obj_t * pObjNew; + unsigned * pCof0 = Vec_PtrEntry( p->vTtNodes, 0 ); + unsigned * pCof1 = Vec_PtrEntry( p->vTtNodes, 1 ); + unsigned * pDec0 = Vec_PtrEntry( p->vTtNodes, 2 ); + unsigned * pDec1 = Vec_PtrEntry( p->vTtNodes, 3 ); + unsigned * pDec = Vec_PtrEntry( p->vTtNodes, 4 ); + unsigned * pCo00 = Vec_PtrEntry( p->vTtNodes, 5 ); + unsigned * pCo01 = Vec_PtrEntry( p->vTtNodes, 6 ); + unsigned * pCo10 = Vec_PtrEntry( p->vTtNodes, 7 ); + unsigned * pCo11 = Vec_PtrEntry( p->vTtNodes, 8 ); + unsigned * pCo0 = Vec_PtrEntry( p->vTtNodes, 9 ); + unsigned * pCo1 = Vec_PtrEntry( p->vTtNodes, 10 ); + unsigned * pCo = Vec_PtrEntry( p->vTtNodes, 11 ); + int TrueMint0, TrueMint1; + int uSubsets, uSubset0, uSubset1, iVar, iVarReused, i; + + // determine if supp-red decomposition exists + uSubsets = Lpk_MapSuppRedDecSelect( p, pTruth, nVars, &iVar, &iVarReused ); + if ( uSubsets == 0 ) + return NULL; + + // get the bound sets + uSubset0 = uSubsets & 0xFFFF; + uSubset1 = uSubsets >> 16; + // get the cofactors + Kit_TruthCofactor0New( pCof0, pTruth, nVars, iVar ); + Kit_TruthCofactor1New( pCof1, pTruth, nVars, iVar ); + // find any true assignments of the cofactors + TrueMint0 = Kit_TruthFindFirstBit( pCof0, nVars ); + TrueMint1 = Kit_TruthFindFirstBit( pCof1, nVars ); + assert( TrueMint0 >= 0 && TrueMint1 >= 0 ); + // cofactor the cofactors according to these minterms + Kit_TruthCopy( pDec0, pCof0, nVars ); + Kit_TruthCopy( pDec1, pCof1, nVars ); + for ( i = 0; i < nVars; i++ ) + if ( !(uSubset0 & (1 << i)) ) + { + if ( TrueMint0 & (1 << i) ) + Kit_TruthCofactor1( pDec0, nVars, i ); + else + Kit_TruthCofactor0( pDec0, nVars, i ); + } + for ( i = 0; i < nVars; i++ ) + if ( !(uSubset1 & (1 << i)) ) + { + if ( TrueMint1 & (1 << i) ) + Kit_TruthCofactor1( pDec1, nVars, i ); + else + Kit_TruthCofactor0( pDec1, nVars, i ); + } + // get the decomposed function + Kit_TruthMuxVar( pDec, pDec0, pDec1, nVars, iVar ); + + // derive the remainders + Kit_TruthAndPhase( pCo00, pCof0, pDec0, nVars, 0, 1 ); + Kit_TruthAndPhase( pCo01, pCof0, pDec0, nVars, 0, 0 ); + Kit_TruthAndPhase( pCo10, pCof1, pDec1, nVars, 0, 1 ); + Kit_TruthAndPhase( pCo11, pCof1, pDec1, nVars, 0, 0 ); + // quantify bound set variables + for ( i = 0; i < nVars; i++ ) + if ( uSubset0 & (1 << i) ) + { + Kit_TruthExist( pCo00, nVars, i ); + Kit_TruthExist( pCo01, nVars, i ); + } + for ( i = 0; i < nVars; i++ ) + if ( uSubset1 & (1 << i) ) + { + Kit_TruthExist( pCo10, nVars, i ); + Kit_TruthExist( pCo11, nVars, i ); + } + // derive the functions by composing them with the new variable (iVarReused) + Kit_TruthMuxVar( pCo0, pCo00, pCo01, nVars, iVarReused ); + Kit_TruthMuxVar( pCo1, pCo10, pCo11, nVars, iVarReused ); + // derive the composition function + Kit_TruthMuxVar( pCo , pCo0 , pCo1 , nVars, iVar ); + + // process the decomposed function + pNtkDec = Kit_DsdDecompose( pDec, nVars ); + Kit_DsdPrint( stdout, pNtkDec ); + ppLeaves[iVarReused] = Lpk_MapTree_rec( p, pNtkDec, ppLeaves, pNtkDec->Root, NULL ); + Kit_DsdNtkFree( pNtkDec ); + + // process the composition function + pNtkComp = Kit_DsdDecompose( pCo, nVars ); + Kit_DsdPrint( stdout, pNtkComp ); + pObjNew = Lpk_MapTree_rec( p, pNtkComp, ppLeaves, pNtkComp->Root, NULL ); + Kit_DsdNtkFree( pNtkComp ); + return pObjNew; +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + |