From 14606c473e728faa7617f7207ac7620fba050f76 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Thu, 12 Sep 2013 17:53:41 -0700 Subject: Improvements to the new technology mapper. --- src/aig/gia/gia.h | 1 + src/aig/gia/giaJf.c | 141 +++++++++++++++++++++++++++++++++------------- src/base/abci/abc.c | 8 ++- src/misc/util/utilTruth.h | 46 +++++++++++++++ 4 files changed, 156 insertions(+), 40 deletions(-) (limited to 'src') diff --git a/src/aig/gia/gia.h b/src/aig/gia/gia.h index e1fd6a63..35c6ebb5 100644 --- a/src/aig/gia/gia.h +++ b/src/aig/gia/gia.h @@ -244,6 +244,7 @@ struct Jf_Par_t_ int fAreaOnly; int fCoarsen; int fCutMin; + int fUseTts; int fVerbose; int fVeryVerbose; int nLutSizeMax; diff --git a/src/aig/gia/giaJf.c b/src/aig/gia/giaJf.c index d5fa3c7f..eb6278b2 100644 --- a/src/aig/gia/giaJf.c +++ b/src/aig/gia/giaJf.c @@ -20,8 +20,10 @@ #include "gia.h" #include "misc/vec/vecSet.h" +#include "misc/vec/vecMem.h" #include "misc/extra/extra.h" #include "bool/kit/kit.h" +#include "misc/util/utilTruth.h" ABC_NAMESPACE_IMPL_START @@ -48,6 +50,7 @@ struct Jf_Man_t_ Gia_Man_t * pGia; // user's manager Jf_Par_t * pPars; // users parameter Sdm_Man_t * pDsd; // extern DSD manager + Vec_Mem_t * vTtMem; // truth table memory and hash table Vec_Int_t vCuts; // cuts for each node Vec_Int_t vArr; // arrival time Vec_Int_t vDep; // departure time @@ -61,29 +64,32 @@ struct Jf_Man_t_ int nCoarse; // coarse nodes }; -static inline int Jf_ObjIsUnit( Gia_Obj_t * p ) { return !p->fMark0; } -static inline void Jf_ObjCleanUnit( Gia_Obj_t * p ) { assert(Jf_ObjIsUnit(p)); p->fMark0 = 1; } -static inline void Jf_ObjSetUnit( Gia_Obj_t * p ) { p->fMark0 = 0; } - -static inline int Jf_ObjCutH( Jf_Man_t * p, int i ) { return Vec_IntEntry(&p->vCuts, i); } -static inline int * Jf_ObjCuts( Jf_Man_t * p, int i ) { return (int *)Vec_SetEntry(&p->pMem, Jf_ObjCutH(p, i)); } -static inline int * Jf_ObjCutBest( Jf_Man_t * p, int i ) { return Jf_ObjCuts(p, i) + 1; } -static inline int Jf_ObjArr( Jf_Man_t * p, int i ) { return Vec_IntEntry(&p->vArr, i); } -static inline int Jf_ObjDep( Jf_Man_t * p, int i ) { return Vec_IntEntry(&p->vDep, i); } -static inline float Jf_ObjFlow( Jf_Man_t * p, int i ) { return Vec_FltEntry(&p->vFlow, i); } -static inline float Jf_ObjRefs( Jf_Man_t * p, int i ) { return Vec_FltEntry(&p->vRefs, i); } -//static inline int Jf_ObjLit( int i, int c ) { return i; } -static inline int Jf_ObjLit( int i, int c ) { return Abc_Var2Lit( i, c ); } - -static inline int Jf_CutSize( int * pCut ) { return pCut[0] & 0x1F; } -static inline int Jf_CutFunc( int * pCut ) { return (pCut[0] >> 5); } -static inline int Jf_CutFuncClass( int * pCut ) { return Abc_Lit2Var(Jf_CutFunc(pCut)); } -static inline int Jf_CutFuncCompl( int * pCut ) { return Abc_LitIsCompl(Jf_CutFunc(pCut)); } -static inline int * Jf_CutLits( int * pCut ) { return pCut + 1; } -static inline int Jf_CutLit( int * pCut, int i ) { assert(i);return pCut[i]; } -//static inline int Jf_CutVar( int * pCut, int i ) { assert(i); return pCut[i]; } -static inline int Jf_CutVar( int * pCut, int i ) { assert(i);return Abc_Lit2Var(pCut[i]); } -static inline int Jf_CutIsTriv( int * pCut, int i ) { return Jf_CutSize(pCut) == 1 && Jf_CutVar(pCut, 1) == i; } +static inline int Jf_ObjIsUnit( Gia_Obj_t * p ) { return !p->fMark0; } +static inline void Jf_ObjCleanUnit( Gia_Obj_t * p ) { assert(Jf_ObjIsUnit(p)); p->fMark0 = 1; } +static inline void Jf_ObjSetUnit( Gia_Obj_t * p ) { p->fMark0 = 0; } + +static inline int Jf_ObjCutH( Jf_Man_t * p, int i ) { return Vec_IntEntry(&p->vCuts, i); } +static inline int * Jf_ObjCuts( Jf_Man_t * p, int i ) { return (int *)Vec_SetEntry(&p->pMem, Jf_ObjCutH(p, i)); } +static inline int * Jf_ObjCutBest( Jf_Man_t * p, int i ) { return Jf_ObjCuts(p, i) + 1; } +static inline int Jf_ObjArr( Jf_Man_t * p, int i ) { return Vec_IntEntry(&p->vArr, i); } +static inline int Jf_ObjDep( Jf_Man_t * p, int i ) { return Vec_IntEntry(&p->vDep, i); } +static inline float Jf_ObjFlow( Jf_Man_t * p, int i ) { return Vec_FltEntry(&p->vFlow, i); } +static inline float Jf_ObjRefs( Jf_Man_t * p, int i ) { return Vec_FltEntry(&p->vRefs, i); } +//static inline int Jf_ObjLit( int i, int c ) { return i; } +static inline int Jf_ObjLit( int i, int c ) { return Abc_Var2Lit( i, c ); } + +static inline int Jf_CutSize( int * pCut ) { return pCut[0] & 0x1F; } +static inline int Jf_CutFunc( int * pCut ) { return (pCut[0] >> 5); } +static inline int Jf_CutFuncClass( int * pCut ) { return Abc_Lit2Var(Jf_CutFunc(pCut)); } +static inline int Jf_CutFuncCompl( int * pCut ) { return Abc_LitIsCompl(Jf_CutFunc(pCut)); } +static inline int * Jf_CutLits( int * pCut ) { return pCut + 1; } +static inline int Jf_CutLit( int * pCut, int i ) { assert(i);return pCut[i]; } +//static inline int Jf_CutVar( int * pCut, int i ) { assert(i); return pCut[i]; } +static inline int Jf_CutVar( int * pCut, int i ) { assert(i);return Abc_Lit2Var(pCut[i]); } +static inline int Jf_CutIsTriv( int * pCut, int i ) { return Jf_CutSize(pCut) == 1 && Jf_CutVar(pCut, 1) == i; } + +static inline int Jf_ObjFunc0( Gia_Obj_t * p, int * q ) { return Abc_LitNotCond(Jf_CutFunc(q), Gia_ObjFaninC0(p)); } +static inline int Jf_ObjFunc1( Gia_Obj_t * p, int * q ) { return Abc_LitNotCond(Jf_CutFunc(q), Gia_ObjFaninC1(p)); } #define Jf_ObjForEachCut( pList, pCut, i ) for ( i = 0, pCut = pList + 1; i < pList[0]; i++, pCut += Jf_CutSize(pCut) + 1 ) #define Jf_CutForEachLit( pCut, Lit, i ) for ( i = 1; i <= Jf_CutSize(pCut) && (Lit = Jf_CutLit(pCut, i)); i++ ) @@ -220,7 +226,16 @@ Jf_Man_t * Jf_ManAlloc( Gia_Man_t * pGia, Jf_Par_t * pPars ) p = ABC_CALLOC( Jf_Man_t, 1 ); p->pGia = pGia; p->pPars = pPars; - p->pDsd = pPars->fCutMin ? Sdm_ManRead() : NULL; + if ( pPars->fCutMin && !pPars->fUseTts ) + p->pDsd = Sdm_ManRead(); + else if ( pPars->fCutMin && pPars->fUseTts ) + { + word uTruth; int Value; + p->vTtMem = Vec_MemAlloc( 1, 12 ); // 32 KB/page for 6-var functions + Vec_MemHashAlloc( p->vTtMem, 10000 ); + uTruth = ABC_CONST(0x0000000000000000); Value = Vec_MemHashInsert( p->vTtMem, &uTruth ); assert( Value == 0 ); + uTruth = ABC_CONST(0xAAAAAAAAAAAAAAAA); Value = Vec_MemHashInsert( p->vTtMem, &uTruth ); assert( Value == 1 ); + } Vec_IntFill( &p->vCuts, Gia_ManObjNum(pGia), 0 ); Vec_IntFill( &p->vArr, Gia_ManObjNum(pGia), 0 ); Vec_IntFill( &p->vDep, Gia_ManObjNum(pGia), 0 ); @@ -236,6 +251,8 @@ void Jf_ManFree( Jf_Man_t * p ) { if ( p->pPars->fVerbose && p->pDsd ) Sdm_ManPrintDsdStats( p->pDsd, 0 ); + if ( p->pPars->fVerbose && p->vTtMem ) + printf( "Unique truth tables = %d. Memory = %.2f MB\n", Vec_MemEntryNum(p->vTtMem), Vec_MemMemory(p->vTtMem) / (1<<20) ); if ( p->pPars->fVeryVerbose && p->pPars->fCutMin ) Jf_ManProfileClasses( p ); if ( p->pPars->fCoarsen ) @@ -246,6 +263,11 @@ void Jf_ManFree( Jf_Man_t * p ) ABC_FREE( p->vDep.pArray ); ABC_FREE( p->vFlow.pArray ); ABC_FREE( p->vRefs.pArray ); + if ( p->pPars->fCutMin && p->pPars->fUseTts ) + { + Vec_MemHashFree( p->vTtMem ); + Vec_MemFree( p->vTtMem ); + } Vec_SetFree_( &p->pMem ); Vec_IntFreeP( &p->vTemp ); ABC_FREE( p ); @@ -851,6 +873,35 @@ static inline void Jf_ObjCheckStore( Jf_Man_t * p, Jf_Cut_t ** pSto, int c, int } } +/**Function************************************************************* + + Synopsis [Cut minimization.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Jf_TtComputeForCut( Jf_Man_t * p, int iFuncLit0, int iFuncLit1, int * pCut0, int * pCut1, int * pCutOut ) +{ + word uTruth; int fCompl, truthId; + int LutSize = p->pPars->nLutSize; + word * pTruth0 = Vec_MemReadEntry(p->vTtMem, Abc_Lit2Var(iFuncLit0)); + word * pTruth1 = Vec_MemReadEntry(p->vTtMem, Abc_Lit2Var(iFuncLit1)); + word uTruth0 = Abc_LitIsCompl(iFuncLit0) ? ~*pTruth0 : *pTruth0; + word uTruth1 = Abc_LitIsCompl(iFuncLit1) ? ~*pTruth1 : *pTruth1; + Abc_TtStretch( &uTruth0, LutSize, pCut0 + 1, Jf_CutSize(pCut0), pCutOut + 1, Jf_CutSize(pCutOut) ); + Abc_TtStretch( &uTruth1, LutSize, pCut1 + 1, Jf_CutSize(pCut1), pCutOut + 1, Jf_CutSize(pCutOut) ); + Abc_TtAnd( &uTruth, &uTruth0, &uTruth1, Abc_TtWordNum(LutSize), 0 ); + pCutOut[0] = Abc_TtMinBase( &uTruth, pCutOut + 1, pCutOut[0] ); + fCompl = (uTruth & 1); + uTruth = fCompl ? ~uTruth : uTruth; + truthId = Vec_MemHashInsert(p->vTtMem, &uTruth); + return Abc_Var2Lit( truthId, fCompl ); +} + /**Function************************************************************* Synopsis [Cut enumeration.] @@ -898,8 +949,7 @@ void Jf_ObjComputeCuts( Jf_Man_t * p, Gia_Obj_t * pObj, int fEdge ) Jf_Cut_t Sto[JF_CUT_MAX+2]; // cut storage Jf_Cut_t * pSto[JF_CUT_MAX+2]; // pointers to cut storage int * pCut0, * pCut1, * pCuts0, * pCuts1; - int iDsdLit0, iDsdLit1, nOldSupp; - int Config, i, k, c = 0; + int nOldSupp, Config, i, k, c = 0; // prepare cuts for ( i = 0; i <= CutNum+1; i++ ) pSto[i] = Sto + i, pSto[i]->iFunc = 0; @@ -919,27 +969,36 @@ void Jf_ObjComputeCuts( Jf_Man_t * p, Gia_Obj_t * pObj, int fEdge ) if ( Jf_CountBits(Sign0[i] | Sign1[k]) > LutSize ) continue; p->CutCount[1]++; - if ( p->pPars->fCutMin ) + if ( !p->pPars->fCutMin ) { - if ( !(Config = Jf_CutMerge2(pCut0, pCut1, pSto[c]->pCut, LutSize)) ) + if ( !Jf_CutMergeOrder(pCut0, pCut1, pSto[c]->pCut, LutSize) ) continue; pSto[c]->Sign = Sign0[i] | Sign1[k]; - nOldSupp = pSto[c]->pCut[0]; - iDsdLit0 = Abc_LitNotCond( Jf_CutFunc(pCut0), Gia_ObjFaninC0(pObj) ); - iDsdLit1 = Abc_LitNotCond( Jf_CutFunc(pCut1), Gia_ObjFaninC1(pObj) ); - pSto[c]->iFunc = Sdm_ManComputeFunc( p->pDsd, iDsdLit0, iDsdLit1, pSto[c]->pCut, Config, 0 ); - if ( pSto[c]->iFunc == -1 ) + } + else if ( p->pPars->fUseTts ) + { + if ( !Jf_CutMergeOrder(pCut0, pCut1, pSto[c]->pCut, LutSize) ) continue; + pSto[c]->Sign = Sign0[i] | Sign1[k]; + nOldSupp = pSto[c]->pCut[0]; + pSto[c]->iFunc = Jf_TtComputeForCut( p, Jf_ObjFunc0(pObj, pCut0), Jf_ObjFunc1(pObj, pCut1), pCut0, pCut1, pSto[c]->pCut ); assert( pSto[c]->pCut[0] <= nOldSupp ); if ( pSto[c]->pCut[0] < nOldSupp ) pSto[c]->Sign = Jf_CutGetSign( pSto[c]->pCut ); - //pSto[c]->Cost = Sdm_ManReadDsdClauseNum( p->pDsd, Abc_Lit2Var(pSto[c]->iFunc) ); } else { - if ( !Jf_CutMergeOrder(pCut0, pCut1, pSto[c]->pCut, LutSize) ) + if ( !(Config = Jf_CutMerge2(pCut0, pCut1, pSto[c]->pCut, LutSize)) ) continue; pSto[c]->Sign = Sign0[i] | Sign1[k]; + nOldSupp = pSto[c]->pCut[0]; + pSto[c]->iFunc = Sdm_ManComputeFunc( p->pDsd, Jf_ObjFunc0(pObj, pCut0), Jf_ObjFunc1(pObj, pCut1), pSto[c]->pCut, Config, 0 ); + if ( pSto[c]->iFunc == -1 ) + continue; + assert( pSto[c]->pCut[0] <= nOldSupp ); + if ( pSto[c]->pCut[0] < nOldSupp ) + pSto[c]->Sign = Jf_CutGetSign( pSto[c]->pCut ); + //pSto[c]->Cost = Sdm_ManReadDsdClauseNum( p->pDsd, Abc_Lit2Var(pSto[c]->iFunc) ); } // Jf_CutCheck( pSto[c]->pCut ); p->CutCount[2]++; @@ -954,7 +1013,7 @@ void Jf_ObjComputeCuts( Jf_Man_t * p, Gia_Obj_t * pObj, int fEdge ) if ( !Jf_ObjIsUnit(pObj) && !Jf_ObjHasCutWithSize(pSto, c, 2) ) { assert( Jf_ObjIsUnit(Gia_ObjFanin0(pObj)) && Jf_ObjIsUnit(Gia_ObjFanin1(pObj)) ); - pSto[c]->iFunc = p->pPars->fCutMin ? 4 : 0; // set function + pSto[c]->iFunc = p->pPars->fCutMin ? 4 : 0; // set function (DSD only!) pSto[c]->pCut[0] = 2; pSto[c]->pCut[1] = Jf_ObjLit(Gia_ObjFaninId0(pObj, iObj), Gia_ObjFaninC0(pObj)); pSto[c]->pCut[2] = Jf_ObjLit(Gia_ObjFaninId1(pObj, iObj), Gia_ObjFaninC1(pObj)); @@ -1188,8 +1247,12 @@ Gia_Man_t * Jf_ManDeriveMappingGia( Jf_Man_t * p ) continue; pCut = Jf_ObjCutBest( p, i ); Class = Jf_CutFuncClass( pCut ); + if ( p->pPars->fUseTts ) + uTruth = *Vec_MemReadEntry(p->vTtMem, Class); + else + uTruth = Sdm_ManReadDsdTruth(p->pDsd, Class); // printf( "Best cut of node %d: ", i ); Jf_CutPrint(pCut); - assert( Sdm_ManReadDsdVarNum( p->pDsd, Class ) == Jf_CutSize(pCut) ); +// assert( Sdm_ManReadDsdVarNum( p->pDsd, Class ) == Jf_CutSize(pCut) ); if ( Jf_CutSize(pCut) == 0 ) { assert( Class == 0 ); @@ -1209,7 +1272,6 @@ Gia_Man_t * Jf_ManDeriveMappingGia( Jf_Man_t * p ) Jf_CutForEachLit( pCut, iLit, k ) Vec_IntPush( vLeaves, Abc_Lit2LitL(Vec_IntArray(vCopies), iLit) ); // create GIA - uTruth = Sdm_ManReadDsdTruth( p->pDsd, Class ); iLit = Kit_TruthToGia( pNew, (unsigned *)&uTruth, Vec_IntSize(vLeaves), vCover, vLeaves, 0 ); iLit = Abc_LitNotCond( iLit, Jf_CutFuncCompl(pCut) ); Vec_IntWriteEntry( vCopies, i, iLit ); @@ -1291,6 +1353,7 @@ void Jf_ManSetDefaultPars( Jf_Par_t * pPars ) pPars->fAreaOnly = 1; pPars->fCoarsen = 0; pPars->fCutMin = 0; + pPars->fUseTts = 0; pPars->fVerbose = 0; pPars->fVeryVerbose = 0; pPars->nLutSizeMax = JF_LEAF_MAX; @@ -1311,6 +1374,8 @@ Gia_Man_t * Jf_ManPerformMapping( Gia_Man_t * pGia, Jf_Par_t * pPars ) { Gia_Man_t * pNew = pGia; Jf_Man_t * p; int i; + if ( pPars->fCutMin && pPars->fUseTts ) + pPars->fCoarsen = 0; p = Jf_ManAlloc( pGia, pPars ); p->pCutCmp = pPars->fAreaOnly ? Jf_CutCompareArea : Jf_CutCompareDelay; Jf_ManComputeCuts( p, 0 ); diff --git a/src/base/abci/abc.c b/src/base/abci/abc.c index bbe62920..475cbb5b 100644 --- a/src/base/abci/abc.c +++ b/src/base/abci/abc.c @@ -29847,7 +29847,7 @@ int Abc_CommandAbc9Jf( Abc_Frame_t * pAbc, int argc, char ** argv ) int c; Jf_ManSetDefaultPars( pPars ); Extra_UtilGetoptReset(); - while ( ( c = Extra_UtilGetopt( argc, argv, "KCRDacmvwh" ) ) != EOF ) + while ( ( c = Extra_UtilGetopt( argc, argv, "KCRDacmtvwh" ) ) != EOF ) { switch ( c ) { @@ -29910,6 +29910,9 @@ int Abc_CommandAbc9Jf( Abc_Frame_t * pAbc, int argc, char ** argv ) case 'm': pPars->fCutMin ^= 1; break; + case 't': + pPars->fUseTts ^= 1; + break; case 'v': pPars->fVerbose ^= 1; break; @@ -29948,7 +29951,7 @@ usage: sprintf(Buffer, "best possible" ); else sprintf(Buffer, "%d", pPars->DelayTarget ); - Abc_Print( -2, "usage: &jf [-KCRD num] [-acvwh]\n" ); + Abc_Print( -2, "usage: &jf [-KCRD num] [-acmtvwh]\n" ); Abc_Print( -2, "\t performs technology mapping of the network\n" ); Abc_Print( -2, "\t-K num : LUT size for the mapping (2 <= K <= %d) [default = %d]\n", pPars->nLutSizeMax, pPars->nLutSize ); Abc_Print( -2, "\t-C num : the max number of priority cuts (1 <= C <= %d) [default = %d]\n", pPars->nCutNumMax, pPars->nCutNum ); @@ -29957,6 +29960,7 @@ usage: Abc_Print( -2, "\t-a : toggles area-oriented mapping [default = %s]\n", pPars->fAreaOnly? "yes": "no" ); Abc_Print( -2, "\t-c : toggles coarsening the subject graph [default = %s]\n", pPars->fCoarsen? "yes": "no" ); Abc_Print( -2, "\t-m : toggles cut minimization [default = %s]\n", pPars->fCutMin? "yes": "no" ); + Abc_Print( -2, "\t-t : toggles truth tables for minimization [default = %s]\n", pPars->fUseTts? "yes": "no" ); Abc_Print( -2, "\t-v : toggles verbose output [default = %s]\n", pPars->fVerbose? "yes": "no" ); Abc_Print( -2, "\t-w : toggles very verbose output [default = %s]\n", pPars->fVeryVerbose? "yes": "no" ); Abc_Print( -2, "\t-h : prints the command usage\n"); diff --git a/src/misc/util/utilTruth.h b/src/misc/util/utilTruth.h index 245a78fc..07f36382 100644 --- a/src/misc/util/utilTruth.h +++ b/src/misc/util/utilTruth.h @@ -1109,6 +1109,52 @@ static inline int Abc_TtMinimumBase( word * t, int * pSupp, int nVarsAll, int * return 1; } +/**Function************************************************************* + + Synopsis [Cut minimization.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline int Abc_TtMinBase( word * pTruth, int * pVars, int nVars ) +{ + int i, k; + for ( i = k = 0; i < nVars; i++ ) + { + if ( !Abc_TtHasVar( pTruth, nVars, i ) ) + continue; + if ( k < i ) + { + pVars[k] = pVars[i]; + Abc_TtSwapVars( pTruth, nVars, k, i ); + } + k++; + } + if ( k == nVars ) + return k; + assert( k < nVars ); +// assert( k == Abc_TtSupportSize(pTruth, nVars) ); + return k; +} +static inline void Abc_TtStretch( word * pTruth0, int nVars, int * pCut0, int nCutSize0, int * pCut, int nCutSize ) +{ + int i, k; + for ( i = nCutSize - 1, k = nCutSize0 - 1; i >= 0 && k >= 0; i-- ) + { + if ( pCut[i] > pCut0[k] ) + continue; + assert( pCut[i] == pCut0[k] ); + if ( k < i ) + Abc_TtSwapVars( pTruth0, nVars, k, i ); + k--; + } + assert( k == -1 ); +} + /**Function************************************************************* Synopsis [Implemeting given NPN config.] -- cgit v1.2.3