| /**CFile**************************************************************** |
| |
| FileName [fxuSelect.c] |
| |
| PackageName [MVSIS 2.0: Multi-valued logic synthesis system.] |
| |
| Synopsis [Procedures to select the best divisor/complement pair.] |
| |
| Author [MVSIS Group] |
| |
| Affiliation [UC Berkeley] |
| |
| Date [Ver. 1.0. Started - February 1, 2003.] |
| |
| Revision [$Id: fxuSelect.c,v 1.0 2003/02/01 00:00:00 alanmi Exp $] |
| |
| ***********************************************************************/ |
| |
| #include "fxuInt.h" |
| |
| ABC_NAMESPACE_IMPL_START |
| |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// DECLARATIONS /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| #define MAX_SIZE_LOOKAHEAD 20 |
| |
| static int Fxu_MatrixFindComplement( Fxu_Matrix * p, int iVar ); |
| |
| static Fxu_Double * Fxu_MatrixFindComplementSingle( Fxu_Matrix * p, Fxu_Single * pSingle ); |
| static Fxu_Single * Fxu_MatrixFindComplementDouble2( Fxu_Matrix * p, Fxu_Double * pDouble ); |
| static Fxu_Double * Fxu_MatrixFindComplementDouble4( Fxu_Matrix * p, Fxu_Double * pDouble ); |
| |
| Fxu_Double * Fxu_MatrixFindDouble( Fxu_Matrix * p, |
| int piVarsC1[], int piVarsC2[], int nVarsC1, int nVarsC2 ); |
| void Fxu_MatrixGetDoubleVars( Fxu_Matrix * p, Fxu_Double * pDouble, |
| int piVarsC1[], int piVarsC2[], int * pnVarsC1, int * pnVarsC2 ); |
| |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// FUNCTION DEFINITIONS /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| /**Function************************************************************* |
| |
| Synopsis [Selects the best pair (Single,Double) and returns their weight.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Fxu_Select( Fxu_Matrix * p, Fxu_Single ** ppSingle, Fxu_Double ** ppDouble ) |
| { |
| // the top entries |
| Fxu_Single * pSingles[MAX_SIZE_LOOKAHEAD] = {0}; |
| Fxu_Double * pDoubles[MAX_SIZE_LOOKAHEAD] = {0}; |
| // the complements |
| Fxu_Double * pSCompl[MAX_SIZE_LOOKAHEAD] = {0}; |
| Fxu_Single * pDComplS[MAX_SIZE_LOOKAHEAD] = {0}; |
| Fxu_Double * pDComplD[MAX_SIZE_LOOKAHEAD] = {0}; |
| Fxu_Pair * pPair; |
| int nSingles; |
| int nDoubles; |
| int i; |
| int WeightBest; |
| int WeightCur; |
| int iNum, fBestS; |
| |
| // collect the top entries from the queues |
| for ( nSingles = 0; nSingles < MAX_SIZE_LOOKAHEAD; nSingles++ ) |
| { |
| pSingles[nSingles] = Fxu_HeapSingleGetMax( p->pHeapSingle ); |
| if ( pSingles[nSingles] == NULL ) |
| break; |
| } |
| // put them back into the queue |
| for ( i = 0; i < nSingles; i++ ) |
| if ( pSingles[i] ) |
| Fxu_HeapSingleInsert( p->pHeapSingle, pSingles[i] ); |
| |
| // the same for doubles |
| // collect the top entries from the queues |
| for ( nDoubles = 0; nDoubles < MAX_SIZE_LOOKAHEAD; nDoubles++ ) |
| { |
| pDoubles[nDoubles] = Fxu_HeapDoubleGetMax( p->pHeapDouble ); |
| if ( pDoubles[nDoubles] == NULL ) |
| break; |
| } |
| // put them back into the queue |
| for ( i = 0; i < nDoubles; i++ ) |
| if ( pDoubles[i] ) |
| Fxu_HeapDoubleInsert( p->pHeapDouble, pDoubles[i] ); |
| |
| // for each single, find the complement double (if any) |
| for ( i = 0; i < nSingles; i++ ) |
| if ( pSingles[i] ) |
| pSCompl[i] = Fxu_MatrixFindComplementSingle( p, pSingles[i] ); |
| |
| // for each double, find the complement single or double (if any) |
| for ( i = 0; i < nDoubles; i++ ) |
| if ( pDoubles[i] ) |
| { |
| pPair = pDoubles[i]->lPairs.pHead; |
| if ( pPair->nLits1 == 1 && pPair->nLits2 == 1 ) |
| { |
| pDComplS[i] = Fxu_MatrixFindComplementDouble2( p, pDoubles[i] ); |
| pDComplD[i] = NULL; |
| } |
| // else if ( pPair->nLits1 == 2 && pPair->nLits2 == 2 ) |
| // { |
| // pDComplS[i] = NULL; |
| // pDComplD[i] = Fxu_MatrixFindComplementDouble4( p, pDoubles[i] ); |
| // } |
| else |
| { |
| pDComplS[i] = NULL; |
| pDComplD[i] = NULL; |
| } |
| } |
| |
| // select the best pair |
| WeightBest = -1; |
| for ( i = 0; i < nSingles; i++ ) |
| { |
| WeightCur = pSingles[i]->Weight; |
| if ( pSCompl[i] ) |
| { |
| // add the weight of the double |
| WeightCur += pSCompl[i]->Weight; |
| // there is no need to implement this double, so... |
| pPair = pSCompl[i]->lPairs.pHead; |
| WeightCur += pPair->nLits1 + pPair->nLits2; |
| } |
| if ( WeightBest < WeightCur ) |
| { |
| WeightBest = WeightCur; |
| *ppSingle = pSingles[i]; |
| *ppDouble = pSCompl[i]; |
| fBestS = 1; |
| iNum = i; |
| } |
| } |
| for ( i = 0; i < nDoubles; i++ ) |
| { |
| WeightCur = pDoubles[i]->Weight; |
| if ( pDComplS[i] ) |
| { |
| // add the weight of the single |
| WeightCur += pDComplS[i]->Weight; |
| // there is no need to implement this double, so... |
| pPair = pDoubles[i]->lPairs.pHead; |
| WeightCur += pPair->nLits1 + pPair->nLits2; |
| } |
| if ( WeightBest < WeightCur ) |
| { |
| WeightBest = WeightCur; |
| *ppSingle = pDComplS[i]; |
| *ppDouble = pDoubles[i]; |
| fBestS = 0; |
| iNum = i; |
| } |
| } |
| /* |
| // print the statistics |
| printf( "\n" ); |
| for ( i = 0; i < nSingles; i++ ) |
| { |
| printf( "Single #%d: Weight = %3d. ", i, pSingles[i]->Weight ); |
| printf( "Compl: " ); |
| if ( pSCompl[i] == NULL ) |
| printf( "None." ); |
| else |
| printf( "D Weight = %3d Sum = %3d", |
| pSCompl[i]->Weight, pSCompl[i]->Weight + pSingles[i]->Weight ); |
| printf( "\n" ); |
| } |
| printf( "\n" ); |
| for ( i = 0; i < nDoubles; i++ ) |
| { |
| printf( "Double #%d: Weight = %3d. ", i, pDoubles[i]->Weight ); |
| printf( "Compl: " ); |
| if ( pDComplS[i] == NULL && pDComplD[i] == NULL ) |
| printf( "None." ); |
| else if ( pDComplS[i] ) |
| printf( "S Weight = %3d Sum = %3d", |
| pDComplS[i]->Weight, pDComplS[i]->Weight + pDoubles[i]->Weight ); |
| else if ( pDComplD[i] ) |
| printf( "D Weight = %3d Sum = %3d", |
| pDComplD[i]->Weight, pDComplD[i]->Weight + pDoubles[i]->Weight ); |
| printf( "\n" ); |
| } |
| if ( WeightBest == -1 ) |
| printf( "Selected NONE\n" ); |
| else |
| { |
| printf( "Selected = %s. ", fBestS? "S": "D" ); |
| printf( "Number = %d. ", iNum ); |
| printf( "Weight = %d.\n", WeightBest ); |
| } |
| printf( "\n" ); |
| */ |
| return WeightBest; |
| } |
| |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Fxu_Double * Fxu_MatrixFindComplementSingle( Fxu_Matrix * p, Fxu_Single * pSingle ) |
| { |
| // int * pValue2Node = p->pValue2Node; |
| int iVar1, iVar2; |
| int iVar1C, iVar2C; |
| // get the variables of this single div |
| iVar1 = pSingle->pVar1->iVar; |
| iVar2 = pSingle->pVar2->iVar; |
| iVar1C = Fxu_MatrixFindComplement( p, iVar1 ); |
| iVar2C = Fxu_MatrixFindComplement( p, iVar2 ); |
| if ( iVar1C == -1 || iVar2C == -1 ) |
| return NULL; |
| assert( iVar1C < iVar2C ); |
| return Fxu_MatrixFindDouble( p, &iVar1C, &iVar2C, 1, 1 ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Fxu_Single * Fxu_MatrixFindComplementDouble2( Fxu_Matrix * p, Fxu_Double * pDouble ) |
| { |
| // int * pValue2Node = p->pValue2Node; |
| int piVarsC1[10], piVarsC2[10]; |
| int nVarsC1, nVarsC2; |
| int iVar1, iVar2, iVarTemp; |
| int iVar1C, iVar2C; |
| Fxu_Single * pSingle; |
| |
| // get the variables of this double div |
| Fxu_MatrixGetDoubleVars( p, pDouble, piVarsC1, piVarsC2, &nVarsC1, &nVarsC2 ); |
| assert( nVarsC1 == 1 ); |
| assert( nVarsC2 == 1 ); |
| iVar1 = piVarsC1[0]; |
| iVar2 = piVarsC2[0]; |
| assert( iVar1 < iVar2 ); |
| |
| iVar1C = Fxu_MatrixFindComplement( p, iVar1 ); |
| iVar2C = Fxu_MatrixFindComplement( p, iVar2 ); |
| if ( iVar1C == -1 || iVar2C == -1 ) |
| return NULL; |
| |
| // go through the queque and find this one |
| // assert( iVar1C < iVar2C ); |
| if ( iVar1C > iVar2C ) |
| { |
| iVarTemp = iVar1C; |
| iVar1C = iVar2C; |
| iVar2C = iVarTemp; |
| } |
| |
| Fxu_MatrixForEachSingle( p, pSingle ) |
| if ( pSingle->pVar1->iVar == iVar1C && pSingle->pVar2->iVar == iVar2C ) |
| return pSingle; |
| return NULL; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Fxu_Double * Fxu_MatrixFindComplementDouble4( Fxu_Matrix * p, Fxu_Double * pDouble ) |
| { |
| // int * pValue2Node = p->pValue2Node; |
| int piVarsC1[10], piVarsC2[10]; |
| int nVarsC1, nVarsC2; |
| int iVar11, iVar12, iVar21, iVar22; |
| int iVar11C, iVar12C, iVar21C, iVar22C; |
| int RetValue; |
| |
| // get the variables of this double div |
| Fxu_MatrixGetDoubleVars( p, pDouble, piVarsC1, piVarsC2, &nVarsC1, &nVarsC2 ); |
| assert( nVarsC1 == 2 && nVarsC2 == 2 ); |
| |
| iVar11 = piVarsC1[0]; |
| iVar12 = piVarsC1[1]; |
| iVar21 = piVarsC2[0]; |
| iVar22 = piVarsC2[1]; |
| assert( iVar11 < iVar21 ); |
| |
| iVar11C = Fxu_MatrixFindComplement( p, iVar11 ); |
| iVar12C = Fxu_MatrixFindComplement( p, iVar12 ); |
| iVar21C = Fxu_MatrixFindComplement( p, iVar21 ); |
| iVar22C = Fxu_MatrixFindComplement( p, iVar22 ); |
| if ( iVar11C == -1 || iVar12C == -1 || iVar21C == -1 || iVar22C == -1 ) |
| return NULL; |
| if ( iVar11C != iVar21 || iVar12C != iVar22 || |
| iVar21C != iVar11 || iVar22C != iVar12 ) |
| return NULL; |
| |
| // a'b' + ab => a'b + ab' |
| // a'b + ab' => a'b' + ab |
| // swap the second pair in each cube |
| RetValue = piVarsC1[1]; |
| piVarsC1[1] = piVarsC2[1]; |
| piVarsC2[1] = RetValue; |
| |
| return Fxu_MatrixFindDouble( p, piVarsC1, piVarsC2, 2, 2 ); |
| } |
| |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Fxu_MatrixFindComplement( Fxu_Matrix * p, int iVar ) |
| { |
| return iVar ^ 1; |
| /* |
| // int * pValue2Node = p->pValue2Node; |
| int iVarC; |
| int iNode; |
| int Beg, End; |
| |
| // get the nodes |
| iNode = pValue2Node[iVar]; |
| // get the first node with the same var |
| for ( Beg = iVar; Beg >= 0; Beg-- ) |
| if ( pValue2Node[Beg] != iNode ) |
| { |
| Beg++; |
| break; |
| } |
| // get the last node with the same var |
| for ( End = iVar; ; End++ ) |
| if ( pValue2Node[End] != iNode ) |
| { |
| End--; |
| break; |
| } |
| |
| // if one of the vars is not binary, quit |
| if ( End - Beg > 1 ) |
| return -1; |
| |
| // get the complements |
| if ( iVar == Beg ) |
| iVarC = End; |
| else if ( iVar == End ) |
| iVarC = Beg; |
| else |
| { |
| assert( 0 ); |
| } |
| return iVarC; |
| */ |
| } |
| |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Fxu_MatrixGetDoubleVars( Fxu_Matrix * p, Fxu_Double * pDouble, |
| int piVarsC1[], int piVarsC2[], int * pnVarsC1, int * pnVarsC2 ) |
| { |
| Fxu_Pair * pPair; |
| Fxu_Lit * pLit1, * pLit2; |
| int nLits1, nLits2; |
| |
| // get the first pair |
| pPair = pDouble->lPairs.pHead; |
| // init the parameters |
| nLits1 = 0; |
| nLits2 = 0; |
| pLit1 = pPair->pCube1->lLits.pHead; |
| pLit2 = pPair->pCube2->lLits.pHead; |
| while ( 1 ) |
| { |
| if ( pLit1 && pLit2 ) |
| { |
| if ( pLit1->iVar == pLit2->iVar ) |
| { // ensure cube-free |
| pLit1 = pLit1->pHNext; |
| pLit2 = pLit2->pHNext; |
| } |
| else if ( pLit1->iVar < pLit2->iVar ) |
| { |
| piVarsC1[nLits1++] = pLit1->iVar; |
| pLit1 = pLit1->pHNext; |
| } |
| else |
| { |
| piVarsC2[nLits2++] = pLit2->iVar; |
| pLit2 = pLit2->pHNext; |
| } |
| } |
| else if ( pLit1 && !pLit2 ) |
| { |
| piVarsC1[nLits1++] = pLit1->iVar; |
| pLit1 = pLit1->pHNext; |
| } |
| else if ( !pLit1 && pLit2 ) |
| { |
| piVarsC2[nLits2++] = pLit2->iVar; |
| pLit2 = pLit2->pHNext; |
| } |
| else |
| break; |
| } |
| *pnVarsC1 = nLits1; |
| *pnVarsC2 = nLits2; |
| } |
| |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Fxu_Double * Fxu_MatrixFindDouble( Fxu_Matrix * p, |
| int piVarsC1[], int piVarsC2[], int nVarsC1, int nVarsC2 ) |
| { |
| int piVarsC1_[100], piVarsC2_[100]; |
| int nVarsC1_, nVarsC2_, i; |
| Fxu_Double * pDouble; |
| Fxu_Pair * pPair; |
| unsigned Key; |
| |
| assert( nVarsC1 > 0 ); |
| assert( nVarsC2 > 0 ); |
| assert( piVarsC1[0] < piVarsC2[0] ); |
| |
| // get the hash key |
| Key = Fxu_PairHashKeyArray( p, piVarsC1, piVarsC2, nVarsC1, nVarsC2 ); |
| |
| // check if the divisor for this pair already exists |
| Key %= p->nTableSize; |
| Fxu_TableForEachDouble( p, Key, pDouble ) |
| { |
| pPair = pDouble->lPairs.pHead; |
| if ( pPair->nLits1 != nVarsC1 ) |
| continue; |
| if ( pPair->nLits2 != nVarsC2 ) |
| continue; |
| // get the cubes of this divisor |
| Fxu_MatrixGetDoubleVars( p, pDouble, piVarsC1_, piVarsC2_, &nVarsC1_, &nVarsC2_ ); |
| // compare lits of the first cube |
| for ( i = 0; i < nVarsC1; i++ ) |
| if ( piVarsC1[i] != piVarsC1_[i] ) |
| break; |
| if ( i != nVarsC1 ) |
| continue; |
| // compare lits of the second cube |
| for ( i = 0; i < nVarsC2; i++ ) |
| if ( piVarsC2[i] != piVarsC2_[i] ) |
| break; |
| if ( i != nVarsC2 ) |
| continue; |
| return pDouble; |
| } |
| return NULL; |
| } |
| |
| |
| |
| |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Fxu_SelectSCD( Fxu_Matrix * p, int WeightLimit, Fxu_Var ** ppVar1, Fxu_Var ** ppVar2 ) |
| { |
| // int * pValue2Node = p->pValue2Node; |
| Fxu_Var * pVar1; |
| Fxu_Var * pVar2, * pVarTemp; |
| Fxu_Lit * pLitV, * pLitH; |
| int Coin; |
| int CounterAll; |
| int CounterTest; |
| int WeightCur; |
| int WeightBest; |
| |
| CounterAll = 0; |
| CounterTest = 0; |
| |
| WeightBest = -10; |
| |
| // iterate through the columns in the matrix |
| Fxu_MatrixForEachVariable( p, pVar1 ) |
| { |
| // start collecting the affected vars |
| Fxu_MatrixRingVarsStart( p ); |
| |
| // go through all the literals of this variable |
| for ( pLitV = pVar1->lLits.pHead; pLitV; pLitV = pLitV->pVNext ) |
| { |
| // for this literal, go through all the horizontal literals |
| for ( pLitH = pLitV->pHNext; pLitH; pLitH = pLitH->pHNext ) |
| { |
| // get another variable |
| pVar2 = pLitH->pVar; |
| CounterAll++; |
| // skip the var if it is already used |
| if ( pVar2->pOrder ) |
| continue; |
| // skip the var if it belongs to the same node |
| // if ( pValue2Node[pVar1->iVar] == pValue2Node[pVar2->iVar] ) |
| // continue; |
| // collect the var |
| Fxu_MatrixRingVarsAdd( p, pVar2 ); |
| } |
| } |
| // stop collecting the selected vars |
| Fxu_MatrixRingVarsStop( p ); |
| |
| // iterate through the selected vars |
| Fxu_MatrixForEachVarInRing( p, pVar2 ) |
| { |
| CounterTest++; |
| |
| // count the coincidence |
| Coin = Fxu_SingleCountCoincidence( p, pVar1, pVar2 ); |
| assert( Coin > 0 ); |
| |
| // get the new weight |
| WeightCur = Coin - 2; |
| |
| // compare the weights |
| if ( WeightBest < WeightCur ) |
| { |
| WeightBest = WeightCur; |
| *ppVar1 = pVar1; |
| *ppVar2 = pVar2; |
| } |
| } |
| // unmark the vars |
| Fxu_MatrixForEachVarInRingSafe( p, pVar2, pVarTemp ) |
| pVar2->pOrder = NULL; |
| Fxu_MatrixRingVarsReset( p ); |
| } |
| |
| // if ( WeightBest == WeightLimit ) |
| // return -1; |
| return WeightBest; |
| } |
| |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// END OF FILE /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| |
| ABC_NAMESPACE_IMPL_END |
| |
