diff options
Diffstat (limited to 'src')
-rw-r--r-- | src/aig/gia/gia.h | 1 | ||||
-rw-r--r-- | src/aig/gia/giaKf.c | 225 | ||||
-rw-r--r-- | src/base/abci/abc.c | 8 |
3 files changed, 219 insertions, 15 deletions
diff --git a/src/aig/gia/gia.h b/src/aig/gia/gia.h index 0fb41153..5894c494 100644 --- a/src/aig/gia/gia.h +++ b/src/aig/gia/gia.h @@ -260,6 +260,7 @@ struct Jf_Par_t_ int fAddOrCla; int fPureAig; int fCutHashing; + int fCutSimple; int fVerbose; int fVeryVerbose; int nLutSizeMax; diff --git a/src/aig/gia/giaKf.c b/src/aig/gia/giaKf.c index 83480272..ad3aca53 100644 --- a/src/aig/gia/giaKf.c +++ b/src/aig/gia/giaKf.c @@ -301,6 +301,60 @@ static inline void Kf_SetSelectBest( Kf_Set_t * p, int fArea, int fSort ) /**Function************************************************************* + Synopsis [Check correctness of cuts.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline int Kf_CheckCut( Kf_Cut_t * pBase, Kf_Cut_t * pCut ) // check if pCut is contained in pBase +{ + int nSizeB = pBase->nLeaves; + int nSizeC = pCut->nLeaves; + int * pB = pBase->pLeaves; + int * pC = pCut->pLeaves; + int i, k; + for ( i = 0; i < nSizeC; i++ ) + { + for ( k = 0; k < nSizeB; k++ ) + if ( pC[i] == pB[k] ) + break; + if ( k == nSizeB ) + return 0; + } + return 1; +} +static inline int Kf_CheckCuts( Kf_Set_t * p ) +{ + Kf_Cut_t * pCut0, * pCut1; + int i, k, m, n, Value; + assert( p->nCuts > 0 ); + for ( i = 0; i <= p->nLutSize; i++ ) + Kf_ListForEachCut( p, i, pCut0 ) + { + // check duplicates + for ( m = 0; m < pCut0->nLeaves; m++ ) + for ( n = m+1; n < pCut0->nLeaves; n++ ) + assert( pCut0->pLeaves[m] != pCut0->pLeaves[n] ); + // check pairs + for ( k = 0; k <= p->nLutSize; k++ ) + Kf_ListForEachCut( p, k, pCut1 ) + { + if ( pCut0 == pCut1 ) + continue; + // check containments + Value = Kf_CheckCut( pCut0, pCut1 ); + assert( Value == 0 ); + } + } + return 1; +} + +/**Function************************************************************* + Synopsis [Hash table.] Description [] @@ -402,7 +456,7 @@ static inline void Kf_SetFilter( Kf_Set_t * p ) for ( k = 0; k < pCut0->nLeaves; k++ ) Kf_ListForEachCut( p, k, pCut1 ) if ( (pCut0->Sign & pCut1->Sign) == pCut1->Sign && Kf_SetCutDominatedByThis(p, pCut1) ) - { k = pCut0->nLeaves + 1; p->nCuts--; break; } + { k = pCut0->nLeaves; p->nCuts--; break; } if ( k == pCut0->nLeaves + 1 ) // remove pCut0 *pPlace = pCut0->iNext; else @@ -457,6 +511,147 @@ static inline void Kf_SetMerge( Kf_Set_t * p, int * pCuts0, int * pCuts1, int fA } p->CutCount[2] += p->nCuts; Kf_SetFilter( p ); +// Kf_CheckCuts( p ); + p->CutCount[3] += Abc_MinInt( p->nCuts, p->nCutNum-1 ); + Kf_SetSelectBest( p, fArea, 1 ); +} + +/**Function************************************************************* + + Synopsis [Cut merging with fixed order.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline int Kf_SetCutIsContainedSimple( Kf_Cut_t * pBase, Kf_Cut_t * pCut ) // check if pCut is contained in pBase +{ + int nSizeB = pBase->nLeaves; + int nSizeC = pCut->nLeaves; + int * pB = pBase->pLeaves; + int * pC = pCut->pLeaves; + int i, k; + if ( nSizeB == nSizeC ) + { + for ( i = 0; i < nSizeB; i++ ) + if ( pBase->pLeaves[i] != pCut->pLeaves[i] ) + return 0; + return 1; + } + assert( nSizeB > nSizeC ); + for ( i = 0; i < nSizeC; i++ ) + { + for ( k = 0; k < nSizeB; k++ ) + if ( pC[i] == pB[k] ) + break; + if ( k == nSizeB ) + return 0; + } + return 1; +} +static inline int Kf_SetMergeSimpleOne( Kf_Cut_t * pCut0, Kf_Cut_t * pCut1, Kf_Cut_t * pCut, int nLutSize ) +{ + int nSize0 = pCut0->nLeaves; + int nSize1 = pCut1->nLeaves; + int * pC0 = pCut0->pLeaves; + int * pC1 = pCut1->pLeaves; + int * pC = pCut->pLeaves; + int i, k, c; + // the case of the largest cut sizes + if ( nSize0 == nLutSize && nSize1 == nLutSize ) + { + for ( i = 0; i < nSize0; i++ ) + { + if ( pC0[i] != pC1[i] ) return 0; + pC[i] = pC0[i]; + } + pCut->nLeaves = nLutSize; + return 1; + } + // compare two cuts with different numbers + c = nSize0; + for ( i = 0; i < nSize1; i++ ) + { + for ( k = 0; k < nSize0; k++ ) + if ( pC1[i] == pC0[k] ) + break; + if ( k < nSize0 ) + continue; + if ( c == nLutSize ) + return 0; + pC[c++] = pC1[i]; + } + for ( i = 0; i < nSize0; i++ ) + pC[i] = pC0[i]; + pCut->nLeaves = c; + return 1; +} +static inline int Kf_SetRemoveDuplicatesSimple( Kf_Set_t * p, Kf_Cut_t * pCutNew ) +{ + Kf_Cut_t * pCut; + Kf_ListForEachCut( p, pCutNew->nLeaves, pCut ) + if ( pCut->Sign == pCutNew->Sign && Kf_SetCutIsContainedSimple(pCut, pCutNew) ) + return 1; + return 0; +} +static inline void Kf_SetFilterSimple( Kf_Set_t * p ) +{ + Kf_Cut_t * pCut0, * pCut1; + int i, k, * pPlace; + assert( p->nCuts > 0 ); + for ( i = 0; i <= p->nLutSize; i++ ) + Kf_ListForEachCutP( p, i, pCut0, pPlace ) + { + for ( k = 0; k < pCut0->nLeaves; k++ ) + Kf_ListForEachCut( p, k, pCut1 ) + if ( (pCut0->Sign & pCut1->Sign) == pCut1->Sign && Kf_SetCutIsContainedSimple(pCut0, pCut1) ) + { k = pCut0->nLeaves; p->nCuts--; break; } + if ( k == pCut0->nLeaves + 1 ) // remove pCut0 + *pPlace = pCut0->iNext; + else + pPlace = &pCut0->iNext; + } + assert( p->nCuts > 0 ); +} +static inline void Kf_SetMergeSimple( Kf_Set_t * p, int * pCuts0, int * pCuts1, int fArea, int fCutMin ) +{ + Kf_Cut_t * pCut0, * pCut1, * pCutR; + Kf_SetPrepare( p, pCuts0, pCuts1 ); + p->CutCount[0] += p->nCuts0 * p->nCuts1; + for ( pCut0 = p->pCuts0; pCut0 < p->pCuts0 + p->nCuts0; pCut0++ ) + for ( pCut1 = p->pCuts1; pCut1 < p->pCuts1 + p->nCuts1; pCut1++ ) + { + if ( pCut0->nLeaves + pCut1->nLeaves > p->nLutSize && Kf_SetCountBits(pCut0->Sign | pCut1->Sign) > p->nLutSize ) + continue; + p->CutCount[1]++; + pCutR = p->pCutsR + p->nCuts; + if ( !Kf_SetMergeSimpleOne(pCut0, pCut1, pCutR, p->nLutSize) ) + continue; + p->CutCount[2]++; + pCutR->Sign = pCut0->Sign | pCut1->Sign; + if ( Kf_SetRemoveDuplicatesSimple(p, pCutR) ) + continue; + p->nCuts++; + if ( fCutMin ) + { + int nOldSupp = pCutR->nLeaves; +// pCutR->iFunc = Kf_SetComputeTruth( p, pCut0->iFunc, pCut1->iFunc, pCut0, pCut1, pCutR ); + assert( pCutR->nLeaves <= nOldSupp ); + if ( pCutR->nLeaves < nOldSupp ) + pCutR->Sign = Kf_SetCutGetSign( pCutR ); + // delay and area are inaccurate + } + assert( pCutR->nLeaves > 1 ); + pCutR->Delay = Abc_MaxInt(pCut0->Delay, pCut1->Delay); + pCutR->Area = pCut0->Area + pCut1->Area; + // add new cut + Kf_SetAddToList( p, pCutR, 0 ); + } + Kf_SetFilterSimple( p ); +// Kf_CheckCuts( p ); p->CutCount[3] += Abc_MinInt( p->nCuts, p->nCutNum-1 ); Kf_SetSelectBest( p, fArea, 1 ); } @@ -491,13 +686,13 @@ static inline int Kf_SetCutIsContainedOrder( Kf_Cut_t * pBase, Kf_Cut_t * pCut ) return 0; if ( pBase->pLeaves[i] == pCut->pLeaves[k] ) { - if ( k++ == nSizeC ) + if ( ++k == nSizeC ) return 1; } } return 0; } -static inline int Kf_SetMergeOrder( Kf_Cut_t * pCut0, Kf_Cut_t * pCut1, Kf_Cut_t * pCut, int nLutSize ) +static inline int Kf_SetMergeOrderOne( Kf_Cut_t * pCut0, Kf_Cut_t * pCut1, Kf_Cut_t * pCut, int nLutSize ) { int nSize0 = pCut0->nLeaves; int nSize1 = pCut1->nLeaves; @@ -553,7 +748,7 @@ FlushCut1: pCut->nLeaves = c; return 1; } -static inline int Kf_SetRemoveDuplicates2( Kf_Set_t * p, Kf_Cut_t * pCutNew ) +static inline int Kf_SetRemoveDuplicatesOrder( Kf_Set_t * p, Kf_Cut_t * pCutNew ) { Kf_Cut_t * pCut; Kf_ListForEachCut( p, pCutNew->nLeaves, pCut ) @@ -561,7 +756,7 @@ static inline int Kf_SetRemoveDuplicates2( Kf_Set_t * p, Kf_Cut_t * pCutNew ) return 1; return 0; } -static inline void Kf_SetFilter2( Kf_Set_t * p ) +static inline void Kf_SetFilterOrder( Kf_Set_t * p ) { Kf_Cut_t * pCut0, * pCut1; int i, k, * pPlace; @@ -572,7 +767,7 @@ static inline void Kf_SetFilter2( Kf_Set_t * p ) for ( k = 0; k < pCut0->nLeaves; k++ ) Kf_ListForEachCut( p, k, pCut1 ) if ( (pCut0->Sign & pCut1->Sign) == pCut1->Sign && Kf_SetCutIsContainedOrder(pCut0, pCut1) ) - { k = pCut0->nLeaves + 1; p->nCuts--; break; } + { k = pCut0->nLeaves; p->nCuts--; break; } if ( k == pCut0->nLeaves + 1 ) // remove pCut0 *pPlace = pCut0->iNext; else @@ -601,7 +796,7 @@ int Kf_SetComputeTruth( Kf_Man_t * p, int iFuncLit0, int iFuncLit1, int * pCut0, return Abc_Var2Lit( truthId, fCompl ); } */ -static inline void Kf_SetMerge2( Kf_Set_t * p, int * pCuts0, int * pCuts1, int fArea, int fCutMin ) +static inline void Kf_SetMergeOrder( Kf_Set_t * p, int * pCuts0, int * pCuts1, int fArea, int fCutMin ) { Kf_Cut_t * pCut0, * pCut1, * pCutR; Kf_SetPrepare( p, pCuts0, pCuts1 ); @@ -613,11 +808,11 @@ static inline void Kf_SetMerge2( Kf_Set_t * p, int * pCuts0, int * pCuts1, int f continue; p->CutCount[1]++; pCutR = p->pCutsR + p->nCuts; - if ( !Kf_SetMergeOrder(pCut0, pCut1, pCutR, p->nLutSize) ) + if ( !Kf_SetMergeOrderOne(pCut0, pCut1, pCutR, p->nLutSize) ) continue; p->CutCount[2]++; pCutR->Sign = pCut0->Sign | pCut1->Sign; - if ( Kf_SetRemoveDuplicates2(p, pCutR) ) + if ( Kf_SetRemoveDuplicatesOrder(p, pCutR) ) continue; p->nCuts++; if ( fCutMin ) @@ -635,7 +830,8 @@ static inline void Kf_SetMerge2( Kf_Set_t * p, int * pCuts0, int * pCuts1, int f // add new cut Kf_SetAddToList( p, pCutR, 0 ); } - Kf_SetFilter2( p ); + Kf_SetFilterOrder( p ); +// Kf_CheckCuts( p ); p->CutCount[3] += Abc_MinInt( p->nCuts, p->nCutNum-1 ); Kf_SetSelectBest( p, fArea, 1 ); } @@ -794,7 +990,7 @@ void * Kf_WorkerThread( void * pArg ) } assert( pThData->Id >= 0 ); clk = Abc_Clock(); - Kf_SetMerge2( pThData->pSett, Kf_ObjCuts0(pMan, pThData->Id), Kf_ObjCuts1(pMan, pThData->Id), fAreaOnly, fCutMin ); + Kf_SetMergeOrder( pThData->pSett, Kf_ObjCuts0(pMan, pThData->Id), Kf_ObjCuts1(pMan, pThData->Id), fAreaOnly, fCutMin ); pThData->clkUsed += Abc_Clock() - clk; pThData->Status = 0; // printf( "Finished object %d\n", pThData->Id ); @@ -972,8 +1168,10 @@ void Kf_ManComputeMapping( Kf_Man_t * p ) { if ( p->pPars->fCutHashing ) Kf_SetMerge( p->pSett, Kf_ObjCuts0(p, i), Kf_ObjCuts1(p, i), p->pPars->fAreaOnly, p->pPars->fCutMin ); - else - Kf_SetMerge2( p->pSett, Kf_ObjCuts0(p, i), Kf_ObjCuts1(p, i), p->pPars->fAreaOnly, p->pPars->fCutMin ); + else if ( p->pPars->fCutSimple ) + Kf_SetMergeSimple( p->pSett, Kf_ObjCuts0(p, i), Kf_ObjCuts1(p, i), p->pPars->fAreaOnly, p->pPars->fCutMin ); + else + Kf_SetMergeOrder( p->pSett, Kf_ObjCuts0(p, i), Kf_ObjCuts1(p, i), p->pPars->fAreaOnly, p->pPars->fCutMin ); Kf_ManSaveResults( p->pSett->ppCuts, p->pSett->nCuts, p->pSett->pCutBest, p->vTemp ); Vec_IntWriteEntry( &p->vTime, i, p->pSett->pCutBest->Delay + 1 ); Vec_FltWriteEntry( &p->vArea, i, (p->pSett->pCutBest->Area + 1)/Kf_ObjRefs(p, i) ); @@ -1126,6 +1324,7 @@ void Kf_ManSetDefaultPars( Jf_Par_t * pPars ) pPars->fGenCnf = 0; pPars->fPureAig = 0; pPars->fCutHashing = 0; + pPars->fCutSimple = 0; pPars->fVerbose = 0; pPars->fVeryVerbose = 0; pPars->nLutSizeMax = KF_LEAF_MAX; diff --git a/src/base/abci/abc.c b/src/base/abci/abc.c index a498761e..697f7e6f 100644 --- a/src/base/abci/abc.c +++ b/src/base/abci/abc.c @@ -30381,7 +30381,7 @@ int Abc_CommandAbc9Kf( Abc_Frame_t * pAbc, int argc, char ** argv ) Gia_Man_t * pNew; int c; Kf_ManSetDefaultPars( pPars ); Extra_UtilGetoptReset(); - while ( ( c = Extra_UtilGetopt( argc, argv, "KCPRDWaekmdcgtvwh" ) ) != EOF ) + while ( ( c = Extra_UtilGetopt( argc, argv, "KCPRDWaekmdcgtsvwh" ) ) != EOF ) { switch ( c ) { @@ -30481,6 +30481,9 @@ int Abc_CommandAbc9Kf( Abc_Frame_t * pAbc, int argc, char ** argv ) case 't': pPars->fCutHashing ^= 1; break; + case 's': + pPars->fCutSimple ^= 1; + break; case 'v': pPars->fVerbose ^= 1; break; @@ -30513,7 +30516,7 @@ usage: sprintf(Buffer, "best possible" ); else sprintf(Buffer, "%d", pPars->DelayTarget ); - Abc_Print( -2, "usage: &kf [-KCPRDW num] [-akmdcgtvwh]\n" ); + Abc_Print( -2, "usage: &kf [-KCPRDW num] [-akmdcgtsvwh]\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 ); @@ -30529,6 +30532,7 @@ usage: Abc_Print( -2, "\t-c : toggles mapping for CNF generation [default = %s]\n", pPars->fGenCnf? "yes": "no" ); Abc_Print( -2, "\t-g : toggles generating AIG without mapping [default = %s]\n", pPars->fPureAig? "yes": "no" ); Abc_Print( -2, "\t-t : toggles cut computation using hash table [default = %s]\n", pPars->fCutHashing? "yes": "no" ); + Abc_Print( -2, "\t-s : toggles cut computation using a simple method [default = %s]\n", pPars->fCutSimple? "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"); |