From 0f9dacb7bec32bc19afb068b4bcf53a781ab2a0e Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Sun, 2 Oct 2011 16:39:51 +0700 Subject: Changes to the matching procedure. --- src/map/if/if.h | 17 +++++++---- src/map/if/ifDec07.c | 2 +- src/map/if/ifDec08.c | 2 +- src/map/if/ifDec10.c | 2 +- src/map/if/ifDec16.c | 81 +++++++++++++++++++++++++++++++++++++++++++--------- src/map/if/ifMan.c | 6 ++++ src/map/if/ifMap.c | 2 +- 7 files changed, 90 insertions(+), 22 deletions(-) (limited to 'src/map') diff --git a/src/map/if/if.h b/src/map/if/if.h index 295491c5..a42c1d79 100644 --- a/src/map/if/if.h +++ b/src/map/if/if.h @@ -121,7 +121,7 @@ struct If_Par_t_ float * pTimesReq; // required times int (* pFuncCost) (If_Cut_t *); // procedure to compute the user's cost of a cut int (* pFuncUser) (If_Man_t *, If_Obj_t *, If_Cut_t *); // procedure called for each cut when cut computation is finished - int (* pFuncCell) (unsigned *, int, int, char *); // procedure called for cut functions + int (* pFuncCell) (If_Man_t *, unsigned *, int, int, char *); // procedure called for cut functions void * pReoMan; // reordering manager }; @@ -191,6 +191,13 @@ struct If_Man_t_ // timing manager Tim_Man_t * pManTim; Vec_Int_t * vCoAttrs; // CO attributes 0=optimize; 1=keep; 2=relax + // hash table for functions + int nTableSize; // hash table size + int nTableEntries; // hash table entries + void ** pHashTable; // hash table bins + Mem_Fixed_t * pMemEntries; // memory manager for hash table entries + + // statistics // int timeTruth; }; @@ -416,10 +423,10 @@ extern float If_CutPowerRef( If_Man_t * p, If_Cut_t * pCut, If_Obj_t * extern float If_CutPowerDerefed( If_Man_t * p, If_Cut_t * pCut, If_Obj_t * pRoot ); extern float If_CutPowerRefed( If_Man_t * p, If_Cut_t * pCut, If_Obj_t * pRoot ); /*=== ifDec.c =============================================================*/ -extern int If_CutPerformCheck07( unsigned * pTruth, int nVars, int nLeaves, char * pStr ); -extern int If_CutPerformCheck08( unsigned * pTruth, int nVars, int nLeaves, char * pStr ); -extern int If_CutPerformCheck10( unsigned * pTruth, int nVars, int nLeaves, char * pStr ); -extern int If_CutPerformCheck16( unsigned * pTruth, int nVars, int nLeaves, char * pStr ); +extern int If_CutPerformCheck07( If_Man_t * p, unsigned * pTruth, int nVars, int nLeaves, char * pStr ); +extern int If_CutPerformCheck08( If_Man_t * p, unsigned * pTruth, int nVars, int nLeaves, char * pStr ); +extern int If_CutPerformCheck10( If_Man_t * p, unsigned * pTruth, int nVars, int nLeaves, char * pStr ); +extern int If_CutPerformCheck16( If_Man_t * p, unsigned * pTruth, int nVars, int nLeaves, char * pStr ); extern float If_CutDelayLutStruct( If_Man_t * p, If_Cut_t * pCut, char * pStr, float WireDelay ); /*=== ifLib.c =============================================================*/ extern If_Lib_t * If_LutLibRead( char * FileName ); diff --git a/src/map/if/ifDec07.c b/src/map/if/ifDec07.c index b10ddeb8..41949a2f 100644 --- a/src/map/if/ifDec07.c +++ b/src/map/if/ifDec07.c @@ -673,7 +673,7 @@ int If_Dec7PickBestMux( word t[2], word c0r[2], word c1r[2] ) SeeAlso [] ***********************************************************************/ -int If_CutPerformCheck07( unsigned * pTruth, int nVars, int nLeaves, char * pStr ) +int If_CutPerformCheck07( If_Man_t * p, unsigned * pTruth, int nVars, int nLeaves, char * pStr ) { int fDerive = 0; if ( nLeaves < 6 ) diff --git a/src/map/if/ifDec08.c b/src/map/if/ifDec08.c index 53aa9ff1..06081414 100644 --- a/src/map/if/ifDec08.c +++ b/src/map/if/ifDec08.c @@ -478,7 +478,7 @@ printf( "\n" ); SeeAlso [] ***********************************************************************/ -int If_CutPerformCheck08( unsigned * pTruth, int nVars, int nLeaves, char * pStr ) +int If_CutPerformCheck08( If_Man_t * p, unsigned * pTruth, int nVars, int nLeaves, char * pStr ) { int nSupp, fDerive = 0; word z[2] = {0}, pF[16]; diff --git a/src/map/if/ifDec10.c b/src/map/if/ifDec10.c index 37846140..9280e193 100644 --- a/src/map/if/ifDec10.c +++ b/src/map/if/ifDec10.c @@ -477,7 +477,7 @@ printf( "\n" ); SeeAlso [] ***********************************************************************/ -int If_CutPerformCheck10( unsigned * pTruth, int nVars, int nLeaves, char * pStr ) +int If_CutPerformCheck10( If_Man_t * p, unsigned * pTruth, int nVars, int nLeaves, char * pStr ) { int nSupp, fDerive = 0; word z[2] = {0}, pF[16]; diff --git a/src/map/if/ifDec16.c b/src/map/if/ifDec16.c index 3902f053..a6d0edee 100644 --- a/src/map/if/ifDec16.c +++ b/src/map/if/ifDec16.c @@ -29,14 +29,24 @@ ABC_NAMESPACE_IMPL_START #define CLU_VAR_MAX 16 #define CLU_WRD_MAX (1 << ((CLU_VAR_MAX)-6)) +#define CLU_UNUSED 99 // decomposition typedef struct If_Grp_t_ If_Grp_t; struct If_Grp_t_ { - char nVars; - char nMyu; - char pVars[CLU_VAR_MAX]; + char nVars; + char nMyu; + char pVars[CLU_VAR_MAX]; +}; + +// hash table entry +typedef struct If_Hte_t_ If_Hte_t; +struct If_Hte_t_ +{ + If_Hte_t * pNext; + If_Grp_t Group; + word pTruth[1]; }; // the bit count for the first 256 integer numbers @@ -77,11 +87,51 @@ extern void Extra_PrintBinary( FILE * pFile, unsigned Sign[], int nBits ); /// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// -// variable permutation for large functions +// hash table static inline int If_CluWordNum( int nVars ) { return nVars <= 6 ? 1 : 1 << (nVars-6); } +int If_CluHashKey( word * pTruth, int nWords, int Size ) +{ + static unsigned BigPrimes[8] = {12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741}; + unsigned char * s = (unsigned char *)pTruth; + unsigned Value = 0; + int i; + for ( i = 0; i < 8 * nWords; i++ ) + Value ^= BigPrimes[i % 7] * s[i]; + return Value % Size; +} +If_Grp_t * If_CluHashLookup( If_Man_t * p, word * pTruth ) +{ + If_Hte_t * pEntry; + int nWords, HashKey; + if ( p == NULL ) + return NULL; + nWords = If_CluWordNum(p->pPars->nLutSize); + if ( p->pMemEntries == NULL ) + { + p->pMemEntries = Mem_FixedStart( sizeof(If_Hte_t) + sizeof(word) * (If_CluWordNum(p->pPars->nLutSize) - 1) ); + p->nTableSize = Vec_PtrSize(p->vObjs) * p->pPars->nCutsMax; + p->pHashTable = ABC_CALLOC( void *, p->nTableSize ); + } + // check if this entry exists + HashKey = If_CluHashKey( pTruth, nWords, p->nTableSize ); + for ( pEntry = ((If_Hte_t **)p->pHashTable)[HashKey]; pEntry; pEntry = pEntry->pNext ) + if ( memcmp(pEntry->pTruth, pTruth, sizeof(word) * nWords) == 0 ) + return &pEntry->Group; + // create entry + p->nTableEntries++; + pEntry = (If_Hte_t *)Mem_FixedEntryFetch( p->pMemEntries ); + memcpy( pEntry->pTruth, pTruth, sizeof(word) * nWords ); + memset( &pEntry->Group, 0, sizeof(If_Grp_t) ); + pEntry->Group.nVars = CLU_UNUSED; + pEntry->pNext = ((If_Hte_t **)p->pHashTable)[HashKey]; + ((If_Hte_t **)p->pHashTable)[HashKey] = pEntry; + return &pEntry->Group; +} + +// variable permutation for large functions static inline void If_CluClear( word * pIn, int nVars ) { int w, nWords = If_CluWordNum( nVars ); @@ -848,9 +898,9 @@ static inline int If_CluSupport( word * t, int nVars ) } // returns the best group found -If_Grp_t If_CluCheck( word * pTruth, int nVars, int nLutLeaf, int nLutRoot ) +If_Grp_t If_CluCheck( If_Man_t * p, word * pTruth, int nVars, int nLutLeaf, int nLutRoot ) { - If_Grp_t G1 = {0}, R = {0}; + If_Grp_t G1 = {0}, R = {0}, * pHashed = NULL; word Truth, pF[CLU_WRD_MAX];//, pG[CLU_WRD_MAX]; int V2P[CLU_VAR_MAX+2], P2V[CLU_VAR_MAX+2]; int i, nSupp; @@ -879,6 +929,11 @@ If_Grp_t If_CluCheck( word * pTruth, int nVars, int nLutLeaf, int nLutRoot ) if ( !nSupp || !If_CluSuppIsMinBase(nSupp) ) return G1; + // check hash table + pHashed = If_CluHashLookup( p, pTruth ); + if ( pHashed && pHashed->nVars != CLU_UNUSED ) + return *pHashed; + // detect easy cofs G1 = If_CluDecUsingCofs( pTruth, nVars, nLutLeaf ); if ( G1.nVars == 0 ) @@ -914,7 +969,7 @@ If_Grp_t If_CluCheck( word * pTruth, int nVars, int nLutLeaf, int nLutRoot ) printf( "no\n" ); } */ - return G1; + return pHashed ? (*pHashed = G1) : G1; } } } @@ -936,7 +991,7 @@ If_Grp_t If_CluCheck( word * pTruth, int nVars, int nLutLeaf, int nLutRoot ) If_CluVerify( pTruth, nVars, &G1, &R, Truth, pF ); } } - return G1; + return pHashed ? (*pHashed = G1) : G1; } @@ -1003,7 +1058,7 @@ float If_CutDelayLutStruct( If_Man_t * p, If_Cut_t * pCut, char * pStr, float Wi } // derive the first group - G1 = If_CluCheck( (word *)If_CutTruth(pCut), nLeaves, nLutLeaf, nLutRoot ); + G1 = If_CluCheck( p, (word *)If_CutTruth(pCut), nLeaves, nLutLeaf, nLutRoot ); if ( G1.nVars == 0 ) return ABC_INFINITY; @@ -1053,7 +1108,7 @@ float If_CutDelayLutStruct( If_Man_t * p, If_Cut_t * pCut, char * pStr, float Wi SeeAlso [] ***********************************************************************/ -int If_CutPerformCheck16( unsigned * pTruth, int nVars, int nLeaves, char * pStr ) +int If_CutPerformCheck16( If_Man_t * p, unsigned * pTruth, int nVars, int nLeaves, char * pStr ) { If_Grp_t G1 = {0}, G2 = {0}, G3 = {0}; int nLutLeaf, nLutRoot; @@ -1086,7 +1141,7 @@ int If_CutPerformCheck16( unsigned * pTruth, int nVars, int nLeaves, char * pStr return 1; // derive the first group - G1 = If_CluCheck( (word *)pTruth, nLeaves, nLutLeaf, nLutRoot ); + G1 = If_CluCheck( p, (word *)pTruth, nLeaves, nLutLeaf, nLutRoot ); if ( G1.nVars == 0 ) { // printf( "-%d ", nLeaves ); @@ -1116,12 +1171,12 @@ void If_CluTest() return; - If_CutPerformCheck07( (unsigned *)&t, 6, 6, NULL ); + If_CutPerformCheck07( NULL, (unsigned *)&t, 6, 6, NULL ); // return; Kit_DsdPrintFromTruth( (unsigned*)&t, nVars ); printf( "\n" ); - G = If_CluCheck( &t, nVars, nLutLeaf, nLutRoot ); + G = If_CluCheck( NULL, &t, nVars, nLutLeaf, nLutRoot ); If_CluPrintGroup( &G ); } diff --git a/src/map/if/ifMan.c b/src/map/if/ifMan.c index ba8f4e0c..8ea579c4 100644 --- a/src/map/if/ifMan.c +++ b/src/map/if/ifMan.c @@ -160,6 +160,12 @@ void If_ManStop( If_Man_t * p ) Tim_ManStop( p->pManTim ); if ( p->vSwitching ) Vec_IntFree( p->vSwitching ); + // hash table +// if ( p->nTableEntries ) +// printf( "Entries = %d. Size = %d.\n", p->nTableEntries, p->nTableSize ); + ABC_FREE( p->pHashTable ); + if ( p->pMemEntries ) + Mem_FixedStop( p->pMemEntries, 0 ); ABC_FREE( p ); } diff --git a/src/map/if/ifMap.c b/src/map/if/ifMap.c index eb7f69b9..55d93884 100644 --- a/src/map/if/ifMap.c +++ b/src/map/if/ifMap.c @@ -207,7 +207,7 @@ void If_ObjPerformMappingAnd( If_Man_t * p, If_Obj_t * pObj, int Mode, int fPrep if ( p->pPars->pFuncCell && RetValue < 2 ) { assert( pCut->nLimit >= 4 && pCut->nLimit <= 16 ); - pCut->fUseless = !p->pPars->pFuncCell( If_CutTruth(pCut), pCut->nLimit, pCut->nLeaves, p->pPars->pLutStruct ); + pCut->fUseless = !p->pPars->pFuncCell( p, If_CutTruth(pCut), pCut->nLimit, pCut->nLeaves, p->pPars->pLutStruct ); p->nCutsUselessAll += pCut->fUseless; p->nCutsUseless[pCut->nLeaves] += pCut->fUseless; p->nCutsCountAll++; -- cgit v1.2.3