| /**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 "fxuInt.h" | |
| #include "fxu.h" | |
| ABC_NAMESPACE_IMPL_START | |
| //////////////////////////////////////////////////////////////////////// | |
| /// DECLARATIONS /// | |
| //////////////////////////////////////////////////////////////////////// | |
| static void Fxu_CreateMatrixAddCube( Fxu_Matrix * p, Fxu_Cube * pCube, char * pSopCube, Vec_Int_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 int * s_pLits; | |
| extern int Fxu_PreprocessCubePairs( Fxu_Matrix * p, Vec_Ptr_t * vCovers, int nPairsTotal, int nPairsMax ); | |
| //////////////////////////////////////////////////////////////////////// | |
| /// FUNCTION DEFINITIONS /// | |
| //////////////////////////////////////////////////////////////////////// | |
| /**Function************************************************************* | |
| Synopsis [Creates the sparse matrix from the array of SOPs.] | |
| 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; | |
| Vec_Int_t * vFanins; | |
| char * pSopCover; | |
| char * pSopCube; | |
| int * pOrder, nBitsMax; | |
| int i, v, c; | |
| int nCubesTotal; | |
| int nPairsTotal; | |
| int nPairsStore; | |
| int nCubes; | |
| int iCube, iPair; | |
| int nFanins; | |
| // collect all sorts of statistics | |
| nCubesTotal = 0; | |
| nPairsTotal = 0; | |
| nPairsStore = 0; | |
| nBitsMax = -1; | |
| for ( i = 0; i < pData->nNodesOld; i++ ) | |
| if ( (pSopCover = (char *)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 > 50000000 ) | |
| { | |
| 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 = ABC_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 = ABC_ALLOC( Fxu_Pair **, nCubesTotal + 100 ); | |
| p->ppPairs = ABC_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 = (char *)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 = ABC_ALLOC( int, nBitsMax ); | |
| // create the rows | |
| for ( i = 0; i < pData->nNodesOld; i++ ) | |
| if ( (pSopCover = (char *)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 = (Vec_Int_t *)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] ] < s_pLits[ pOrder[nFanins-1] ] ); | |
| // 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; | |
| } | |
| // 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 ); | |
| } | |
| } | |
| ABC_FREE( pOrder ); | |
| // consider the case when cube pairs should be preprocessed | |
| // before adding them to the set of divisors | |
| // if ( pData->fVerbose ) | |
| // printf( "The total number of cube pairs is %d.\n", nPairsTotal ); | |
| if ( nPairsTotal > 10000000 ) | |
| { | |
| printf( "The total number of cube pairs of the network is more than 10,000,000.\n" ); | |
| printf( "Command \"fx\" takes a long time to run in such cases. It is suggested\n" ); | |
| printf( "that the user changes the network by reducing the size of logic node and\n" ); | |
| printf( "consequently the number of cube pairs to be processed by this command.\n" ); | |
| printf( "It can be achieved as follows: \"st; if -K <num>\" or \"st; renode -s -K <num>\"\n" ); | |
| printf( "as a proprocessing step, while selecting <num> as approapriate.\n" ); | |
| return NULL; | |
| } | |
| if ( nPairsTotal > pData->nPairsMax ) | |
| if ( !Fxu_PreprocessCubePairs( p, pData->vSops, nPairsTotal, pData->nPairsMax ) ) | |
| return NULL; | |
| // if ( pData->fVerbose ) | |
| // printf( "Only %d best cube pairs will be used by the fast extract command.\n", pData->nPairsMax ); | |
| if ( p->lVars.nItems > 1000000 ) | |
| { | |
| printf( "The total number of variables is more than 1,000,000.\n" ); | |
| printf( "Command \"fx\" takes a long time to run in such cases. It is suggested\n" ); | |
| printf( "that the user changes the network by reducing the size of logic node and\n" ); | |
| printf( "consequently the number of cube pairs to be processed by this command.\n" ); | |
| printf( "It can be achieved as follows: \"st; if -K <num>\" or \"st; renode -s -K <num>\"\n" ); | |
| printf( "as a proprocessing step, while selecting <num> as approapriate.\n" ); | |
| return NULL; | |
| } | |
| // add the var pairs to the heap | |
| Fxu_MatrixComputeSingles( p, pData->fUse0, pData->nSingleMax ); | |
| // print stats | |
| 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 divs = %6d. (Total = %6d) ", p->lSingles.nItems, p->nSingleTotal ); | |
| fprintf( stdout, "2-cube divs = %6d. (Total = %6d)", p->nDivsTotal, 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_Int_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]] + 1 ]; // CST | |
| Fxu_MatrixAddLiteral( p, pCube, pVar ); | |
| } | |
| else if ( Value == '1' ) | |
| { | |
| pVar = p->ppVars[ 2 * vFanins->pArray[pOrder[i]] ]; // 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; | |
| char * pSopCover; | |
| int iNode, n; | |
| // 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 = (char *)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, * pSopCube; | |
| Fxu_Var * pVar; | |
| Fxu_Cube * pCube; | |
| Fxu_Lit * pLit; | |
| int iNum, nCubes, v; | |
| // 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( (char *)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 | |
| 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 | |
| } | |
| // count the cube | |
| nCubes++; | |
| } | |
| assert( nCubes == Abc_SopGetCubeNum(pSopCover) ); | |
| // set the new cover and the array of fanins | |
| 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] - s_pLits[*ptrY]; | |
| } | |
| //////////////////////////////////////////////////////////////////////// | |
| /// END OF FILE /// | |
| //////////////////////////////////////////////////////////////////////// | |
| ABC_NAMESPACE_IMPL_END | |