From d0e834d1a615f8e0e9d04c2ac97811f63562bd0b Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Sat, 6 Aug 2005 08:01:00 -0700 Subject: Version abc50806 --- src/opt/fxu/fxuSelect.c | 603 ++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 603 insertions(+) create mode 100644 src/opt/fxu/fxuSelect.c (limited to 'src/opt/fxu/fxuSelect.c') diff --git a/src/opt/fxu/fxuSelect.c b/src/opt/fxu/fxuSelect.c new file mode 100644 index 00000000..b56407a9 --- /dev/null +++ b/src/opt/fxu/fxuSelect.c @@ -0,0 +1,603 @@ +/**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" + +//////////////////////////////////////////////////////////////////////// +/// 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 DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**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]; + Fxu_Double * pDoubles[MAX_SIZE_LOOKAHEAD]; + // the complements + Fxu_Double * pSCompl[MAX_SIZE_LOOKAHEAD]; + Fxu_Single * pDComplS[MAX_SIZE_LOOKAHEAD]; + Fxu_Double * pDComplD[MAX_SIZE_LOOKAHEAD]; + 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 /// +//////////////////////////////////////////////////////////////////////// + + -- cgit v1.2.3