From 12c776ed6e5a17a491fdb986ccce99649a06850e Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Thu, 23 Aug 2012 22:20:27 -0700 Subject: Added new algorithm for NPN semi-canonical form computation. --- src/base/abci/abc.c | 3 +- src/base/abci/abcNpn.c | 23 ++++++++++- src/bool/kit/kitTruth.c | 4 +- src/misc/extra/extra.h | 3 +- src/misc/extra/extraUtilMisc.c | 87 ++++++++++++++++++++++++++++++++++++++++-- 5 files changed, 111 insertions(+), 9 deletions(-) (limited to 'src') diff --git a/src/base/abci/abc.c b/src/base/abci/abc.c index dede6c51..3eabc252 100644 --- a/src/base/abci/abc.c +++ b/src/base/abci/abc.c @@ -4928,7 +4928,8 @@ usage: Abc_Print( -2, "\t 0: none (reading and writing the file)\n" ); Abc_Print( -2, "\t 1: semi-canonical form by counting 1s in cofactors\n" ); Abc_Print( -2, "\t 2: semi-canonical form by minimizing truth table value\n" ); - Abc_Print( -2, "\t 3: exact canonical form (slow for more than 6 variables)\n" ); + Abc_Print( -2, "\t 3: exact canonical form (work only for 6 variables)\n" ); + Abc_Print( -2, "\t 4: heuristic canonical form (work only for 6 variables)\n" ); Abc_Print( -2, "\t-v : toggle verbose printout [default = %s]\n", fVerbose? "yes": "no" ); Abc_Print( -2, "\t-h : print the command usage\n"); return 1; diff --git a/src/base/abci/abcNpn.c b/src/base/abci/abcNpn.c index 5c21d98e..70c08da7 100644 --- a/src/base/abci/abcNpn.c +++ b/src/base/abci/abcNpn.c @@ -110,6 +110,8 @@ void Abc_TruthNpnPerform( Abc_TtStore_t * p, int NpnType, int fVerbose ) pAlgoName = "minimizing TT"; else if ( NpnType == 3 ) pAlgoName = "exact NPN "; + else if ( NpnType == 4 ) + pAlgoName = "heuristic NPN"; assert( p->nVars <= 16 ); if ( pAlgoName ) @@ -150,7 +152,7 @@ void Abc_TruthNpnPerform( Abc_TtStore_t * p, int NpnType, int fVerbose ) { if ( fVerbose ) printf( "%7d : ", i ); - *((word *)p->pFuncs[i]) = Extra_Truth6Minimum( *((word *)p->pFuncs[i]), pComp, pPerm ); + *((word *)p->pFuncs[i]) = Extra_Truth6MinimumExact( *((word *)p->pFuncs[i]), pComp, pPerm ); if ( fVerbose ) Extra_PrintHex( stdout, (unsigned *)p->pFuncs[i], p->nVars ), printf( "\n" ); } @@ -160,6 +162,23 @@ void Abc_TruthNpnPerform( Abc_TtStore_t * p, int NpnType, int fVerbose ) ABC_FREE( pComp ); ABC_FREE( pPerm ); } + else if ( NpnType == 4 ) + { + if ( p->nVars == 6 ) + { + for ( i = 0; i < p->nFuncs; i++ ) + { + if ( fVerbose ) + printf( "%7d : ", i ); + Kit_TruthSemiCanonicize( (unsigned *)p->pFuncs[i], pAux, p->nVars, pCanonPerm, pStore ); + *((word *)p->pFuncs[i]) = Extra_Truth6MinimumHeuristic( *((word *)p->pFuncs[i]) ); + if ( fVerbose ) + Extra_PrintHex( stdout, (unsigned *)p->pFuncs[i], p->nVars ), printf( "\n" ); + } + } + else + printf( "This feature only works for 6-variable functions.\n" ); + } else assert( 0 ); clk = clock() - clk; @@ -213,7 +232,7 @@ int Abc_NpnTest( char * pFileName, int NpnType, int fVerbose ) printf( "Using truth tables from file \"%s\"...\n", pFileName ); if ( NpnType == 0 ) Abc_TtStoreTest( pFileName ); - else if ( NpnType >= 1 && NpnType <= 3 ) + else if ( NpnType >= 1 && NpnType <= 4 ) Abc_TruthNpnTest( pFileName, NpnType, fVerbose ); else printf( "Unknown canonical form value (%d).\n", NpnType ); diff --git a/src/bool/kit/kitTruth.c b/src/bool/kit/kitTruth.c index bd8bbb1c..258207c2 100644 --- a/src/bool/kit/kitTruth.c +++ b/src/bool/kit/kitTruth.c @@ -1685,7 +1685,7 @@ unsigned Kit_TruthSemiCanonicize( unsigned * pInOut, unsigned * pAux, int nVars, // canonicize phase for ( i = 0; i < nVars; i++ ) { - if ( pStore[2*i+0] <= pStore[2*i+1] ) + if ( pStore[2*i+0] >= pStore[2*i+1] ) continue; uCanonPhase |= (1 << i); Temp = pStore[2*i+0]; @@ -1703,7 +1703,7 @@ unsigned Kit_TruthSemiCanonicize( unsigned * pInOut, unsigned * pAux, int nVars, fChange = 0; for ( i = 0; i < nVars-1; i++ ) { - if ( pStore[2*i] <= pStore[2*(i+1)] ) + if ( pStore[2*i] >= pStore[2*(i+1)] ) continue; Counter++; fChange = 1; diff --git a/src/misc/extra/extra.h b/src/misc/extra/extra.h index f198c183..8d3ba254 100644 --- a/src/misc/extra/extra.h +++ b/src/misc/extra/extra.h @@ -203,7 +203,8 @@ extern void Extra_BubbleSort( int Order[], int Costs[], int nSize, int fI /* complementation/permutation generation */ extern int * Extra_GreyCodeSchedule( int n ); extern int * Extra_PermSchedule( int n ); -extern word Extra_Truth6Minimum( word t, int * pComp, int * pPerm ); +extern word Extra_Truth6MinimumExact( word t, int * pComp, int * pPerm ); +extern word Extra_Truth6MinimumHeuristic( word t ); /*=== extraUtilCanon.c ========================================================*/ diff --git a/src/misc/extra/extraUtilMisc.c b/src/misc/extra/extraUtilMisc.c index e484bcb2..c765917c 100644 --- a/src/misc/extra/extraUtilMisc.c +++ b/src/misc/extra/extraUtilMisc.c @@ -2283,7 +2283,7 @@ static inline word Extra_Truth6ChangePhase( word t, int v ) assert( v < 6 ); return ((t & ~Truth6[v]) << (1 << v)) | ((t & Truth6[v]) >> (1 << v)); } -word Extra_Truth6Minimum( word t, int * pComp, int * pPerm ) +word Extra_Truth6MinimumExact( word t, int * pComp, int * pPerm ) { word tMin = ~(word)0; word tCur, tTemp1, tTemp2; @@ -2310,6 +2310,87 @@ word Extra_Truth6Minimum( word t, int * pComp, int * pPerm ) return tMin; } +/**Function************************************************************* + + Synopsis [Perform heuristic TT minimization.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline int Extra_Truth6Ones( word t ) +{ + t = (t & 0x5555555555555555) + ((t>> 1) & 0x5555555555555555); + t = (t & 0x3333333333333333) + ((t>> 2) & 0x3333333333333333); + t = (t & 0x0F0F0F0F0F0F0F0F) + ((t>> 4) & 0x0F0F0F0F0F0F0F0F); + t = (t & 0x00FF00FF00FF00FF) + ((t>> 8) & 0x00FF00FF00FF00FF); + t = (t & 0x0000FFFF0000FFFF) + ((t>>16) & 0x0000FFFF0000FFFF); + return (t & 0x00000000FFFFFFFF) + (t>>32); +} +static inline word Extra_Truth6MinimumRoundOne( word t, int v ) +{ + word tCur, tMin = t; // ab + assert( v >= 0 && v < 5 ); + + tCur = Extra_Truth6ChangePhase( t, v ); // !ab + tMin = Abc_MinWord( tMin, tCur ); + tCur = Extra_Truth6ChangePhase( t, v+1 ); // a!b + tMin = Abc_MinWord( tMin, tCur ); + tCur = Extra_Truth6ChangePhase( tCur, v ); // !a!b + tMin = Abc_MinWord( tMin, tCur ); + + t = Extra_Truth6SwapAdjacent( t, v ); // ba + tMin = Abc_MinWord( tMin, t ); + + tCur = Extra_Truth6ChangePhase( t, v ); // !ba + tMin = Abc_MinWord( tMin, tCur ); + tCur = Extra_Truth6ChangePhase( t, v+1 ); // b!a + tMin = Abc_MinWord( tMin, tCur ); + tCur = Extra_Truth6ChangePhase( tCur, v ); // !b!a + tMin = Abc_MinWord( tMin, tCur ); + + return tMin; +} +static inline word Extra_Truth6MinimumRoundMany( word t ) +{ + int i, k, Limit = 10; + word tCur, tMin = t; + for ( i = 0; i < Limit; i++ ) + { + word tMin0 = tMin; + for ( k = 4; k >= 0; k-- ) + { + tCur = Extra_Truth6MinimumRoundOne( tMin, k ); + tMin = Abc_MinWord( tMin, tCur ); + } + if ( tMin0 == tMin ) + break; + } + return tMin; +} +word Extra_Truth6MinimumHeuristic( word t ) +{ + word tMin1, tMin2; + int nOnes = Extra_Truth6Ones( t ); + if ( nOnes < 32 ) + return Extra_Truth6MinimumRoundMany( t ); + if ( nOnes > 32 ) + return Extra_Truth6MinimumRoundMany( ~t ); + tMin1 = Extra_Truth6MinimumRoundMany( t ); + tMin2 = Extra_Truth6MinimumRoundMany( ~t ); + return Abc_MinWord( tMin1, tMin2 ); +} +void Extra_Truth6MinimumHeuristicTest() +{ + word t = 0x5555555555555555 & ~(0x3333333333333333 & 0x0F0F0F0F0F0F0F0F); + Extra_Truth6MinimumRoundMany( t ); + t = 0; +} + + /**Function************************************************************* Synopsis [Reads functions from file.] @@ -2387,7 +2468,7 @@ void Extra_NpnTest2() word tMin, t = 0xa2222aaa08888000; pComp = Extra_GreyCodeSchedule( 6 ); pPerm = Extra_PermSchedule( 6 ); - tMin = Extra_Truth6Minimum( t, pComp, pPerm ); + tMin = Extra_Truth6MinimumExact( t, pComp, pPerm ); ABC_FREE( pPerm ); ABC_FREE( pComp ); @@ -2424,7 +2505,7 @@ void Extra_NpnTest() // compute minimum forms for ( i = 0; i < nFuncs; i++ ) { - pFuncs[i] = Extra_Truth6Minimum( pFuncs[i], pComp, pPerm ); + pFuncs[i] = Extra_Truth6MinimumExact( pFuncs[i], pComp, pPerm ); if ( i % 10000 == 0 ) printf( "%d\n", i ); } -- cgit v1.2.3