diff options
Diffstat (limited to 'src/opt/fxu/fxuCreate.c')
| -rw-r--r-- | src/opt/fxu/fxuCreate.c | 425 |
1 files changed, 425 insertions, 0 deletions
diff --git a/src/opt/fxu/fxuCreate.c b/src/opt/fxu/fxuCreate.c new file mode 100644 index 00000000..04b23fce --- /dev/null +++ b/src/opt/fxu/fxuCreate.c @@ -0,0 +1,425 @@ +/**CFile**************************************************************** + + FileName [fxuCreate.c] + + PackageName [MVSIS 2.0: Multi-valued logic synthesis system.] + + Synopsis [Create matrix from covers and covers from matrix.] + + Author [MVSIS Group] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - February 1, 2003.] + + Revision [$Id: fxuCreate.c,v 1.0 2003/02/01 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "abc.h" +#include "fxuInt.h" +#include "fxu.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +extern int Fxu_PreprocessCubePairs( Fxu_Matrix * p, Vec_Ptr_t * vCovers, int nPairsTotal, int nPairsMax ); + +static void Fxu_CreateMatrixAddCube( Fxu_Matrix * p, Fxu_Cube * pCube, char * pSopCube, Vec_Fan_t * vFanins, int * pOrder ); +static int Fxu_CreateMatrixLitCompare( int * ptrX, int * ptrY ); +static void Fxu_CreateCoversNode( Fxu_Matrix * p, Fxu_Data_t * pData, int iNode, Fxu_Cube * pCubeFirst, Fxu_Cube * pCubeNext ); +static Fxu_Cube * Fxu_CreateCoversFirstCube( Fxu_Matrix * p, Fxu_Data_t * pData, int iNode ); +static Abc_Fan_t * s_pLits; + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Creates the sparse matrix from the array of Sop covers.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fxu_Matrix * Fxu_CreateMatrix( Fxu_Data_t * pData ) +{ + Fxu_Matrix * p; + Fxu_Var * pVar; + Fxu_Cube * pCubeFirst, * pCubeNew; + Fxu_Cube * pCube1, * pCube2; + char * pSopCover; + char * pSopCube; + int * pOrder, nBitsMax; + int i, v, c; + int nCubesTotal; + int nPairsTotal; + int nPairsStore; + int nCubes; + int iCube, iPair; + int nFanins; + Vec_Fan_t * vFanins; + + // collect all sorts of statistics + nCubesTotal = 0; + nPairsTotal = 0; + nPairsStore = 0; + nBitsMax = -1; + for ( i = 0; i < pData->nNodesOld; i++ ) + if ( pSopCover = pData->vSops->pArray[i] ) + { + nCubes = Abc_SopGetCubeNum( pSopCover ); + nFanins = Abc_SopGetVarNum( pSopCover ); + assert( nFanins > 1 && nCubes > 0 ); + + nCubesTotal += nCubes; + nPairsTotal += nCubes * (nCubes - 1) / 2; + nPairsStore += nCubes * nCubes; + if ( nBitsMax < nFanins ) + nBitsMax = nFanins; + } + if ( nBitsMax <= 0 ) + { + printf( "The current network does not have SOPs to perform extraction.\n" ); + return NULL; + } + + if ( nPairsStore > 10000000 ) + { + printf( "The problem is too large to be solved by \"fxu\" (%d cubes and %d cube pairs)\n", nCubesTotal, nPairsStore ); + return NULL; + } + + // start the matrix + p = Fxu_MatrixAllocate(); + // create the column labels + p->ppVars = ALLOC( Fxu_Var *, 2 * (pData->nNodesOld + pData->nNodesExt) ); + for ( i = 0; i < 2 * pData->nNodesOld; i++ ) + p->ppVars[i] = Fxu_MatrixAddVar( p ); + + // allocate storage for all cube pairs at once + p->pppPairs = ALLOC( Fxu_Pair **, nCubesTotal + 100 ); + p->ppPairs = ALLOC( Fxu_Pair *, nPairsStore + 100 ); + memset( p->ppPairs, 0, sizeof(Fxu_Pair *) * nPairsStore ); + iCube = 0; + iPair = 0; + for ( i = 0; i < pData->nNodesOld; i++ ) + if ( pSopCover = pData->vSops->pArray[i] ) + { + // get the number of cubes + nCubes = Abc_SopGetCubeNum( pSopCover ); + // get the new var in the matrix + pVar = p->ppVars[2*i+1]; + // assign the pair storage + pVar->nCubes = nCubes; + if ( nCubes > 0 ) + { + pVar->ppPairs = p->pppPairs + iCube; + pVar->ppPairs[0] = p->ppPairs + iPair; + for ( v = 1; v < nCubes; v++ ) + pVar->ppPairs[v] = pVar->ppPairs[v-1] + nCubes; + } + // update + iCube += nCubes; + iPair += nCubes * nCubes; + } + assert( iCube == nCubesTotal ); + assert( iPair == nPairsStore ); + + + // allocate room for the reordered literals + pOrder = ALLOC( int, nBitsMax ); + // create the rows + for ( i = 0; i < pData->nNodesOld; i++ ) + if ( pSopCover = pData->vSops->pArray[i] ) + { + // get the new var in the matrix + pVar = p->ppVars[2*i+1]; + // here we sort the literals of the cover + // in the increasing order of the numbers of the corresponding nodes + // because literals should be added to the matrix in this order + vFanins = pData->vFanins->pArray[i]; + s_pLits = vFanins->pArray; + // start the variable order + nFanins = Abc_SopGetVarNum( pSopCover ); + for ( v = 0; v < nFanins; v++ ) + pOrder[v] = v; + // reorder the fanins + qsort( (void *)pOrder, nFanins, sizeof(int),(int (*)(const void *, const void *))Fxu_CreateMatrixLitCompare); + assert( s_pLits[ pOrder[0] ].iFan < s_pLits[ pOrder[nFanins-1] ].iFan ); + // create the corresponding cubes in the matrix + pCubeFirst = NULL; + c = 0; + Abc_SopForEachCube( pSopCover, nFanins, pSopCube ) + { + // create the cube + pCubeNew = Fxu_MatrixAddCube( p, pVar, c ); + Fxu_CreateMatrixAddCube( p, pCubeNew, pSopCube, vFanins, pOrder ); + if ( pCubeFirst == NULL ) + pCubeFirst = pCubeNew; + pCubeNew->pFirst = pCubeFirst; + c++; + } + // set the first cube of this var + pVar->pFirst = pCubeFirst; + // create the divisors without preprocessing + if ( nPairsTotal <= pData->nPairsMax ) + { + for ( pCube1 = pCubeFirst; pCube1; pCube1 = pCube1->pNext ) + for ( pCube2 = pCube1? pCube1->pNext: NULL; pCube2; pCube2 = pCube2->pNext ) + Fxu_MatrixAddDivisor( p, pCube1, pCube2 ); + } + } + FREE( pOrder ); + + // consider the case when cube pairs should be preprocessed + // before adding them to the set of divisors + if ( nPairsTotal > pData->nPairsMax ) + Fxu_PreprocessCubePairs( p, pData->vSops, nPairsTotal, pData->nPairsMax ); + + // add the var pairs to the heap + Fxu_MatrixComputeSingles( p ); + + // allocate temporary storage for pairs + if ( pData->nPairsMax < 1000 ) + pData->nPairsMax = 1000; + p->pPairsTemp = ALLOC( Fxu_Pair *, pData->nPairsMax * 10 + 100 ); + if ( pData->fVerbose ) + { + double Density; + Density = ((double)p->nEntries) / p->lVars.nItems / p->lCubes.nItems; + fprintf( stdout, "Matrix: [vars x cubes] = [%d x %d] ", + p->lVars.nItems, p->lCubes.nItems ); + fprintf( stdout, "Lits = %d Density = %.5f%%\n", + p->nEntries, Density ); + fprintf( stdout, "1-cube divisors = %6d. ", p->lSingles.nItems ); + fprintf( stdout, "2-cube divisors = %6d. ", p->nDivsTotal ); + fprintf( stdout, "Cube pairs = %6d.", nPairsTotal ); + fprintf( stdout, "\n" ); + } +// Fxu_MatrixPrint( stdout, p ); + return p; +} + +/**Function************************************************************* + + Synopsis [Adds one cube with literals to the matrix.] + + Description [Create the cube and literals in the matrix corresponding + to the given cube in the SOP cover. Co-singleton transform is performed here.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_CreateMatrixAddCube( Fxu_Matrix * p, Fxu_Cube * pCube, char * pSopCube, Vec_Fan_t * vFanins, int * pOrder ) +{ + Fxu_Var * pVar; + int Value, i; + // add literals to the matrix + Abc_CubeForEachVar( pSopCube, Value, i ) + { + Value = pSopCube[pOrder[i]]; + if ( Value == '0' ) + { + pVar = p->ppVars[ 2 * vFanins->pArray[pOrder[i]].iFan + 1 ]; // CST + Fxu_MatrixAddLiteral( p, pCube, pVar ); + } + else if ( Value == '1' ) + { + pVar = p->ppVars[ 2 * vFanins->pArray[pOrder[i]].iFan ]; // CST + Fxu_MatrixAddLiteral( p, pCube, pVar ); + } + } +} + + +/**Function************************************************************* + + Synopsis [Creates the new array of Sop covers from the sparse matrix.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_CreateCovers( Fxu_Matrix * p, Fxu_Data_t * pData ) +{ + Fxu_Cube * pCube, * pCubeFirst, * pCubeNext; + int iNode, n; + char * pSopCover; + + // get the first cube of the first internal node + pCubeFirst = Fxu_CreateCoversFirstCube( p, pData, 0 ); + + // go through the internal nodes + for ( n = 0; n < pData->nNodesOld; n++ ) + if ( pSopCover = pData->vSops->pArray[n] ) + { + // get the number of this node + iNode = n; + // get the next first cube + pCubeNext = Fxu_CreateCoversFirstCube( p, pData, iNode + 1 ); + // check if there any new variables in these cubes + for ( pCube = pCubeFirst; pCube != pCubeNext; pCube = pCube->pNext ) + if ( pCube->lLits.pTail && pCube->lLits.pTail->iVar >= 2 * pData->nNodesOld ) + break; + if ( pCube != pCubeNext ) + Fxu_CreateCoversNode( p, pData, iNode, pCubeFirst, pCubeNext ); + // update the first cube + pCubeFirst = pCubeNext; + } + + // add the covers for the extracted nodes + for ( n = 0; n < pData->nNodesNew; n++ ) + { + // get the number of this node + iNode = pData->nNodesOld + n; + // get the next first cube + pCubeNext = Fxu_CreateCoversFirstCube( p, pData, iNode + 1 ); + // the node should be added + Fxu_CreateCoversNode( p, pData, iNode, pCubeFirst, pCubeNext ); + // update the first cube + pCubeFirst = pCubeNext; + } +} + +/**Function************************************************************* + + Synopsis [Create Sop covers for one node that has changed.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_CreateCoversNode( Fxu_Matrix * p, Fxu_Data_t * pData, int iNode, Fxu_Cube * pCubeFirst, Fxu_Cube * pCubeNext ) +{ + Vec_Int_t * vInputsNew; + char * pSopCover; + char * pSopCube; + Fxu_Var * pVar; + Fxu_Cube * pCube; + Fxu_Lit * pLit; + int iNum, nCubes, v; + int fEmptyCube; + + // collect positive polarity variable in the cubes between pCubeFirst and pCubeNext + Fxu_MatrixRingVarsStart( p ); + for ( pCube = pCubeFirst; pCube != pCubeNext; pCube = pCube->pNext ) + for ( pLit = pCube->lLits.pHead; pLit; pLit = pLit->pHNext ) + { + pVar = p->ppVars[ 2 * (pLit->pVar->iVar/2) + 1 ]; + if ( pVar->pOrder == NULL ) + Fxu_MatrixRingVarsAdd( p, pVar ); + } + Fxu_MatrixRingVarsStop( p ); + + // collect the variable numbers + vInputsNew = Vec_IntAlloc( 4 ); + Fxu_MatrixForEachVarInRing( p, pVar ) + Vec_IntPush( vInputsNew, pVar->iVar / 2 ); + Fxu_MatrixRingVarsUnmark( p ); + + // sort the vars by their number + Vec_IntSort( vInputsNew, 0 ); + + // mark the vars with their numbers in the sorted array + for ( v = 0; v < vInputsNew->nSize; v++ ) + { + p->ppVars[ 2 * vInputsNew->pArray[v] + 0 ]->lLits.nItems = v; // hack - reuse lLits.nItems + p->ppVars[ 2 * vInputsNew->pArray[v] + 1 ]->lLits.nItems = v; // hack - reuse lLits.nItems + } + + // count the number of cubes + nCubes = 0; + for ( pCube = pCubeFirst; pCube != pCubeNext; pCube = pCube->pNext ) + if ( pCube->lLits.nItems ) + nCubes++; + + // allocate room for the new cover + pSopCover = Abc_SopStart( pData->pManSop, nCubes, vInputsNew->nSize ); + // set the correct polarity of the cover + if ( iNode < pData->nNodesOld && Abc_SopGetPhase( pData->vSops->pArray[iNode] ) == 0 ) + Abc_SopComplement( pSopCover ); + + // add the cubes + nCubes = 0; + for ( pCube = pCubeFirst; pCube != pCubeNext; pCube = pCube->pNext ) + { + if ( pCube->lLits.nItems == 0 ) + continue; + // get hold of the SOP cube + pSopCube = pSopCover + nCubes * (vInputsNew->nSize + 3); + // insert literals + fEmptyCube = 1; + for ( pLit = pCube->lLits.pHead; pLit; pLit = pLit->pHNext ) + { + iNum = pLit->pVar->lLits.nItems; // hack - reuse lLits.nItems + assert( iNum < vInputsNew->nSize ); + if ( pLit->pVar->iVar / 2 < pData->nNodesOld ) + pSopCube[iNum] = (pLit->pVar->iVar & 1)? '0' : '1'; // reverse CST + else + pSopCube[iNum] = (pLit->pVar->iVar & 1)? '1' : '0'; // no CST + fEmptyCube = 0; + } + assert( !fEmptyCube ); + // count the cube + nCubes++; + } + assert( nCubes == Abc_SopGetCubeNum(pSopCover) ); + + pData->vSopsNew->pArray[iNode] = pSopCover; + pData->vFaninsNew->pArray[iNode] = vInputsNew; +} + + +/**Function************************************************************* + + Synopsis [Adds the var to storage.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fxu_Cube * Fxu_CreateCoversFirstCube( Fxu_Matrix * p, Fxu_Data_t * pData, int iVar ) +{ + int v; + for ( v = iVar; v < pData->nNodesOld + pData->nNodesNew; v++ ) + if ( p->ppVars[ 2*v + 1 ]->pFirst ) + return p->ppVars[ 2*v + 1 ]->pFirst; + return NULL; +} + +/**Function************************************************************* + + Synopsis [Compares the vars by their number.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fxu_CreateMatrixLitCompare( int * ptrX, int * ptrY ) +{ + return s_pLits[*ptrX].iFan - s_pLits[*ptrY].iFan; +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// |