From 280a485336963305b795efaee1d84c854fa90abc Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Wed, 2 Apr 2014 19:33:49 -0700 Subject: Improvements to technology mapping. --- src/map/if/if.h | 8 ++++---- src/map/if/ifMan.c | 49 ++++++++++++++++++++++++++++++------------------- src/map/if/ifTruth.c | 43 +++++++++++++++++++++++-------------------- 3 files changed, 57 insertions(+), 43 deletions(-) (limited to 'src') diff --git a/src/map/if/if.h b/src/map/if/if.h index feb560f7..9471d3c0 100644 --- a/src/map/if/if.h +++ b/src/map/if/if.h @@ -216,7 +216,7 @@ struct If_Man_t_ int nMaxIters; // the maximum number of iterations int Period; // the current value of the clock period (for seq mapping) // memory management - int nTruth6Words; // the size of the truth table if allocated + int nTruth6Words[IF_MAX_FUNC_LUTSIZE+1]; // the size of the truth table if allocated int nPermWords; // the size of the permutation array (in words) int nObjBytes; // the size of the object int nCutBytes; // the size of the cut @@ -234,7 +234,7 @@ struct If_Man_t_ int nCutsUselessAll; int nCuts5, nCuts5a; If_DsdMan_t * pIfDsdMan; - Vec_Mem_t * vTtMem; // truth table memory and hash table + Vec_Mem_t * vTtMem[IF_MAX_FUNC_LUTSIZE+1]; // truth table memory and hash table Vec_Int_t * vTtDsds; // mapping of truth table into DSD Vec_Str_t * vTtPerms; // mapping of truth table into permutations Hash_IntMan_t * vPairHash; // hashing pairs of truth tables @@ -406,10 +406,10 @@ static inline void If_CutSetData( If_Cut_t * pCut, void * pData ) { * static inline int If_CutDataInt( If_Cut_t * pCut ) { return *(int *)pCut; } static inline void If_CutSetDataInt( If_Cut_t * pCut, int Data ) { *(int *)pCut = Data; } -static inline word * If_CutTruthWR( If_Man_t * p, If_Cut_t * pCut ) { return p->vTtMem ? Vec_MemReadEntry(p->vTtMem, Abc_Lit2Var(pCut->iCutFunc)) : NULL; } +static inline word * If_CutTruthWR( If_Man_t * p, If_Cut_t * pCut ) { return p->vTtMem ? Vec_MemReadEntry(p->vTtMem[pCut->nLeaves], Abc_Lit2Var(pCut->iCutFunc)) : NULL; } static inline unsigned * If_CutTruthR( If_Man_t * p, If_Cut_t * pCut ) { return (unsigned *)If_CutTruthWR(p, pCut); } static inline int If_CutTruthIsCompl( If_Cut_t * pCut ) { assert( pCut->iCutFunc >= 0 ); return Abc_LitIsCompl(pCut->iCutFunc); } -static inline word * If_CutTruthW( If_Man_t * p, If_Cut_t * pCut ) { if ( p->vTtMem == NULL ) return NULL; assert( pCut->iCutFunc >= 0 ); Abc_TtCopy( p->puTempW, If_CutTruthWR(p, pCut), p->nTruth6Words, If_CutTruthIsCompl(pCut) ); return p->puTempW; } +static inline word * If_CutTruthW( If_Man_t * p, If_Cut_t * pCut ) { if ( p->vTtMem == NULL ) return NULL; assert( pCut->iCutFunc >= 0 ); Abc_TtCopy( p->puTempW, If_CutTruthWR(p, pCut), p->nTruth6Words[pCut->nLeaves], If_CutTruthIsCompl(pCut) ); return p->puTempW; } static inline unsigned * If_CutTruth( If_Man_t * p, If_Cut_t * pCut ) { return (unsigned *)If_CutTruthW(p, pCut); } static inline float If_CutLutArea( If_Man_t * p, If_Cut_t * pCut ) { return pCut->fUser? (float)pCut->Cost : (p->pPars->pLutLib? p->pPars->pLutLib->pLutAreas[pCut->nLeaves] : (float)1.0); } diff --git a/src/map/if/ifMan.c b/src/map/if/ifMan.c index f2075e9f..68c6344a 100644 --- a/src/map/if/ifMan.c +++ b/src/map/if/ifMan.c @@ -51,7 +51,7 @@ extern abctime s_TimeComp[4]; ***********************************************************************/ If_Man_t * If_ManStart( If_Par_t * pPars ) { - If_Man_t * p; + If_Man_t * p; int v; assert( !pPars->fUseDsd || !pPars->fUseTtPerm ); // start the manager p = ABC_ALLOC( If_Man_t, 1 ); @@ -65,9 +65,15 @@ If_Man_t * If_ManStart( If_Par_t * pPars ) // p->vMapped = Vec_PtrAlloc( 100 ); p->vTemp = Vec_PtrAlloc( 100 ); // prepare the memory manager - p->vTtMem = p->pPars->fTruth? Vec_MemAllocForTT( p->pPars->nLutSize ) : NULL; - p->nTruth6Words= p->pPars->fTruth? Abc_Truth6WordNum( p->pPars->nLutSize ) : 0; -// p->nTruthWords = p->pPars->fTruth? If_CutTruthWords( p->pPars->nLutSize ) : 0; + if ( p->pPars->fTruth ) + { + for ( v = 0; v <= p->pPars->nLutSize; v++ ) + p->nTruth6Words[v] = Abc_Truth6WordNum( v ); + for ( v = 6; v <= p->pPars->nLutSize; v++ ) + p->vTtMem[v] = Vec_MemAllocForTT( v ); + for ( v = 0; v < 6; v++ ) + p->vTtMem[v] = p->vTtMem[6]; + } p->nPermWords = p->pPars->fUsePerm? If_CutPermWords( p->pPars->nLutSize ) : 0; p->nObjBytes = sizeof(If_Obj_t) + sizeof(int) * (p->pPars->nLutSize + p->nPermWords/* + p->nTruthWords*/); p->nCutBytes = sizeof(If_Cut_t) + sizeof(int) * (p->pPars->nLutSize + p->nPermWords/* + p->nTruthWords*/); @@ -77,13 +83,13 @@ If_Man_t * If_ManStart( If_Par_t * pPars ) // report expected memory usage if ( p->pPars->fVerbose ) Abc_Print( 1, "K = %d. Memory (bytes): Truth = %4d. Cut = %4d. Obj = %4d. Set = %4d. CutMin = %s\n", - p->pPars->nLutSize, 8 * p->nTruth6Words, p->nCutBytes, p->nObjBytes, p->nSetBytes, p->pPars->fCutMin? "yes":"no" ); + p->pPars->nLutSize, 8 * p->nTruth6Words[p->pPars->nLutSize], p->nCutBytes, p->nObjBytes, p->nSetBytes, p->pPars->fCutMin? "yes":"no" ); // room for temporary truth tables - p->puTemp[0] = p->pPars->fTruth? ABC_ALLOC( unsigned, 8 * p->nTruth6Words ) : NULL; - p->puTemp[1] = p->puTemp[0] + p->nTruth6Words*2; - p->puTemp[2] = p->puTemp[1] + p->nTruth6Words*2; - p->puTemp[3] = p->puTemp[2] + p->nTruth6Words*2; - p->puTempW = p->pPars->fTruth? ABC_ALLOC( word, p->nTruth6Words ) : NULL; + p->puTemp[0] = p->pPars->fTruth? ABC_ALLOC( unsigned, 8 * p->nTruth6Words[p->pPars->nLutSize] ) : NULL; + p->puTemp[1] = p->puTemp[0] + p->nTruth6Words[p->pPars->nLutSize]*2; + p->puTemp[2] = p->puTemp[1] + p->nTruth6Words[p->pPars->nLutSize]*2; + p->puTemp[3] = p->puTemp[2] + p->nTruth6Words[p->pPars->nLutSize]*2; + p->puTempW = p->pPars->fTruth? ABC_ALLOC( word, p->nTruth6Words[p->pPars->nLutSize] ) : NULL; if ( pPars->fUseDsd ) { p->vTtDsds = Vec_IntAlloc( 1000 ); @@ -95,10 +101,6 @@ If_Man_t * If_ManStart( If_Par_t * pPars ) } if ( pPars->fUseTtPerm ) { - word uTruth = 0; - Vec_MemHashInsert( p->vTtMem, &uTruth ); - uTruth = ABC_CONST(0xAAAAAAAAAAAAAAAA); - Vec_MemHashInsert( p->vTtMem, &uTruth ); p->vPairHash = Hash_IntManStart( 10000 ); p->vTtPerms = Vec_StrAlloc( 10000 ); } @@ -152,13 +154,20 @@ void If_ManRestart( If_Man_t * p ) void If_ManStop( If_Man_t * p ) { extern void If_ManCacheAnalize( If_Man_t * p ); + int i; if ( p->pPars->fVerbose && p->vCutData ) If_ManCacheAnalize( p ); - 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->fVerbose && p->pPars->fTruth ) + { + int nUnique = 0, nMemTotal = 0; + for ( i = 6; i <= p->pPars->nLutSize; i++ ) + nUnique += Vec_MemEntryNum(p->vTtMem[i]); + for ( i = 6; i <= p->pPars->nLutSize; i++ ) + nMemTotal += (int)Vec_MemMemory(p->vTtMem[i]); + printf( "Unique truth tables = %d. Memory = %.2f MB\n", nUnique, 1.0 * nMemTotal / (1<<20) ); + } if ( p->pPars->fVerbose && p->nCutsUselessAll ) { - int i; for ( i = 0; i <= 16; i++ ) if ( p->nCutsUseless[i] ) Abc_Print( 1, "Useless cuts %2d = %9d (out of %9d) (%6.2f %%)\n", i, p->nCutsUseless[i], p->nCutsCount[i], 100.0*p->nCutsUseless[i]/(p->nCutsCount[i]+1) ); @@ -189,8 +198,10 @@ void If_ManStop( If_Man_t * p ) Vec_IntFreeP( &p->vCutData ); if ( p->vPairHash ) Hash_IntManStop( p->vPairHash ); - Vec_MemHashFree( p->vTtMem ); - Vec_MemFreeP( &p->vTtMem ); + for ( i = 6; i <= p->pPars->nLutSize; i++ ) + Vec_MemHashFree( p->vTtMem[i] ); + for ( i = 6; i <= p->pPars->nLutSize; i++ ) + Vec_MemFreeP( &p->vTtMem[i] ); Mem_FixedStop( p->pMemObj, 0 ); ABC_FREE( p->pMemCi ); ABC_FREE( p->pMemAnd ); diff --git a/src/map/if/ifTruth.c b/src/map/if/ifTruth.c index 8063dd5a..f9177e11 100644 --- a/src/map/if/ifTruth.c +++ b/src/map/if/ifTruth.c @@ -71,14 +71,14 @@ void If_CutRotatePins( If_Man_t * p, If_Cut_t * pCut ) assert( !p->pPars->fUseTtPerm ); If_CutForEachLeaf( p, pCut, pLeaf, i ) PinDelays[i] = If_ObjCutBest(pLeaf)->Delay; - if ( p->vTtMem == NULL ) + if ( p->vTtMem[pCut->nLeaves] == NULL ) { - If_CutTruthPermute( NULL, If_CutLeaveNum(pCut), pCut->nLimit, p->nTruth6Words, PinDelays, If_CutLeaves(pCut) ); + If_CutTruthPermute( NULL, If_CutLeaveNum(pCut), pCut->nLeaves, p->nTruth6Words[pCut->nLeaves], PinDelays, If_CutLeaves(pCut) ); return; } - Abc_TtCopy( p->puTempW, If_CutTruthWR(p, pCut), p->nTruth6Words, 0 ); - If_CutTruthPermute( p->puTempW, If_CutLeaveNum(pCut), pCut->nLimit, p->nTruth6Words, PinDelays, If_CutLeaves(pCut) ); - truthId = Vec_MemHashInsert( p->vTtMem, p->puTempW ); + Abc_TtCopy( p->puTempW, If_CutTruthWR(p, pCut), p->nTruth6Words[pCut->nLeaves], 0 ); + If_CutTruthPermute( p->puTempW, If_CutLeaveNum(pCut), pCut->nLeaves, p->nTruth6Words[pCut->nLeaves], PinDelays, If_CutLeaves(pCut) ); + truthId = Vec_MemHashInsert( p->vTtMem[pCut->nLeaves], p->puTempW ); pCut->iCutFunc = Abc_Var2Lit( truthId, If_CutTruthIsCompl(pCut) ); assert( (p->puTempW[0] & 1) == 0 ); } @@ -97,21 +97,23 @@ void If_CutRotatePins( If_Man_t * p, If_Cut_t * pCut ) int If_CutComputeTruth( If_Man_t * p, If_Cut_t * pCut, If_Cut_t * pCut0, If_Cut_t * pCut1, int fCompl0, int fCompl1 ) { int fCompl, truthId, nLeavesNew, RetValue = 0; - int nWords = Abc_TtWordNum( pCut->nLimit ); - word * pTruth0s = Vec_MemReadEntry( p->vTtMem, Abc_Lit2Var(pCut0->iCutFunc) ); - word * pTruth1s = Vec_MemReadEntry( p->vTtMem, Abc_Lit2Var(pCut1->iCutFunc) ); + int nWords = Abc_TtWordNum( pCut->nLeaves ); + word * pTruth0s = Vec_MemReadEntry( p->vTtMem[pCut0->nLeaves], Abc_Lit2Var(pCut0->iCutFunc) ); + word * pTruth1s = Vec_MemReadEntry( p->vTtMem[pCut1->nLeaves], Abc_Lit2Var(pCut1->iCutFunc) ); word * pTruth0 = (word *)p->puTemp[0]; word * pTruth1 = (word *)p->puTemp[1]; word * pTruth = (word *)p->puTemp[2]; Abc_TtCopy( pTruth0, pTruth0s, nWords, fCompl0 ^ pCut0->fCompl ^ Abc_LitIsCompl(pCut0->iCutFunc) ); Abc_TtCopy( pTruth1, pTruth1s, nWords, fCompl1 ^ pCut1->fCompl ^ Abc_LitIsCompl(pCut1->iCutFunc) ); - Abc_TtStretch( pTruth0, pCut->nLimit, pCut0->pLeaves, pCut0->nLeaves, pCut->pLeaves, pCut->nLeaves ); - Abc_TtStretch( pTruth1, pCut->nLimit, pCut1->pLeaves, pCut1->nLeaves, pCut->pLeaves, pCut->nLeaves ); + Abc_TtStretch6( pTruth0, pCut0->nLeaves, pCut->nLeaves ); + Abc_TtStretch6( pTruth1, pCut1->nLeaves, pCut->nLeaves ); + Abc_TtStretch( pTruth0, pCut->nLeaves, pCut0->pLeaves, pCut0->nLeaves, pCut->pLeaves, pCut->nLeaves ); + Abc_TtStretch( pTruth1, pCut->nLeaves, pCut1->pLeaves, pCut1->nLeaves, pCut->pLeaves, pCut->nLeaves ); fCompl = (pTruth0[0] & pTruth1[0] & 1); Abc_TtAnd( pTruth, pTruth0, pTruth1, nWords, fCompl ); if ( p->pPars->fCutMin ) { - nLeavesNew = Abc_TtMinBase( pTruth, pCut->pLeaves, pCut->nLeaves, pCut->nLimit ); + nLeavesNew = Abc_TtMinBase( pTruth, pCut->pLeaves, pCut->nLeaves, pCut->nLeaves ); if ( nLeavesNew < If_CutLeaveNum(pCut) ) { pCut->nLeaves = nLeavesNew; @@ -119,7 +121,7 @@ int If_CutComputeTruth( If_Man_t * p, If_Cut_t * pCut, If_Cut_t * pCut0, If_Cut_ RetValue = 1; } } - truthId = Vec_MemHashInsert( p->vTtMem, pTruth ); + truthId = Vec_MemHashInsert( p->vTtMem[pCut->nLeaves], pTruth ); pCut->iCutFunc = Abc_Var2Lit( truthId, fCompl ); assert( (pTruth[0] & 1) == 0 ); #ifdef IF_TRY_NEW @@ -127,7 +129,7 @@ int If_CutComputeTruth( If_Man_t * p, If_Cut_t * pCut, If_Cut_t * pCut0, If_Cut_ word pCopy[1024]; char pCanonPerm[16]; memcpy( pCopy, If_CutTruthW(pCut), sizeof(word) * nWords ); - Abc_TtCanonicize( pCopy, pCut->nLimit, pCanonPerm ); + Abc_TtCanonicize( pCopy, pCut->nLeaves, pCanonPerm ); } #endif return RetValue; @@ -150,9 +152,9 @@ int If_CutComputeTruthPerm( If_Man_t * p, If_Cut_t * pCut, If_Cut_t * pCut0, If_ int pPerm[IF_MAX_LUTSIZE]; char pCanonPerm[IF_MAX_LUTSIZE]; int v, Place, fCompl, truthId, nLeavesNew, uCanonPhase, RetValue = 0; - int nWords = Abc_TtWordNum( pCut->nLimit ); - word * pTruth0s = Vec_MemReadEntry( p->vTtMem, Abc_Lit2Var(pCut0->iCutFunc) ); - word * pTruth1s = Vec_MemReadEntry( p->vTtMem, Abc_Lit2Var(pCut1->iCutFunc) ); + int nWords = Abc_TtWordNum( pCut->nLeaves ); + word * pTruth0s = Vec_MemReadEntry( p->vTtMem[pCut0->nLeaves], Abc_Lit2Var(pCut0->iCutFunc) ); + word * pTruth1s = Vec_MemReadEntry( p->vTtMem[pCut1->nLeaves], Abc_Lit2Var(pCut1->iCutFunc) ); word * pTruth0 = (word *)p->puTemp[0]; word * pTruth1 = (word *)p->puTemp[1]; word * pTruth = (word *)p->puTemp[2]; @@ -160,7 +162,8 @@ int If_CutComputeTruthPerm( If_Man_t * p, If_Cut_t * pCut, If_Cut_t * pCut0, If_ assert( pCut1->iCutDsd >= 0 ); Abc_TtCopy( pTruth0, pTruth0s, nWords, fCompl0 ^ pCut0->fCompl ^ Abc_LitIsCompl(pCut0->iCutFunc) ); Abc_TtCopy( pTruth1, pTruth1s, nWords, fCompl1 ^ pCut1->fCompl ^ Abc_LitIsCompl(pCut1->iCutFunc) ); - + Abc_TtStretch6( pTruth0, pCut0->nLeaves, pCut->nLeaves ); + Abc_TtStretch6( pTruth1, pCut1->nLeaves, pCut->nLeaves ); if ( fVerbose ) { @@ -183,7 +186,7 @@ if ( fVerbose ) Place = p->pPerm[1][v]; if ( Place == v || Place == -1 ) continue; - Abc_TtSwapVars( pTruth1, pCut->nLimit, v, Place ); + Abc_TtSwapVars( pTruth1, pCut->nLeaves, v, Place ); p->pPerm[1][v] = p->pPerm[1][Place]; p->pPerm[1][Place] = Place; v--; @@ -200,7 +203,7 @@ if ( fVerbose ) // minimize support if ( p->pPars->fCutMin ) { - nLeavesNew = Abc_TtMinBase( pTruth, pCut->pLeaves, pCut->nLeaves, pCut->nLimit ); + nLeavesNew = Abc_TtMinBase( pTruth, pCut->pLeaves, pCut->nLeaves, pCut->nLeaves ); if ( nLeavesNew < If_CutLeaveNum(pCut) ) { pCut->nLeaves = nLeavesNew; @@ -226,7 +229,7 @@ if ( fVerbose ) // hash function fCompl = ((uCanonPhase >> pCut->nLeaves) & 1); - truthId = Vec_MemHashInsert( p->vTtMem, pTruth ); + truthId = Vec_MemHashInsert( p->vTtMem[pCut->nLeaves], pTruth ); pCut->iCutFunc = Abc_Var2Lit( truthId, fCompl ); if ( fVerbose ) -- cgit v1.2.3