fxucreate.c

主要进行大规模的电路综合

/**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.8 2003/05/27 23:15:43 alanmi Exp $]

***********************************************************************/

#include "fxuInt.h"
#include "mvc.h"
#include "fxu.h"

////////////////////////////////////////////////////////////////////////
///                        DECLARATIONS                              ///
////////////////////////////////////////////////////////////////////////

extern int        Fxu_PreprocessCubePairs( Fxu_Matrix * p, Mvc_Cover_t * ppCovers[], int nCovers, int nPairsTotal, int nPairsMax );

static Fxu_Cube * Fxu_CreateMatrixAddCube( Fxu_Matrix * p, Fxu_Var * pVarNew, Mvc_Cover_t * pMvcCover, Mvc_Cube_t * pMvcCube, int iMvcCube, 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        Fxu_CreateCoversVarCompare( Fxu_Var ** ppV1, Fxu_Var ** ppV2 );

static int * s_pLits;

static int Fxu_CreateSCDs( Fxu_Matrix * p, Fxu_Data_t * pData );

////////////////////////////////////////////////////////////////////////
///                     FUNCTION DEFITIONS                           ///
////////////////////////////////////////////////////////////////////////

/**Function*************************************************************

  Synopsis    [Creates the sparse matrix from the array of Mvc 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;
    Mvc_Cover_t * pMvcCover;
    Mvc_Cube_t * pMvcCube;
    int * pOrder, nBitsMax;
    int i, v, iMvcCube;
    int nCubesTotal;
    int nPairsTotal;
    int nPairsStore;
    int nCubes;
    int nCubesMax;
    int iCube, iPair;

    // start the matrix
	p = Fxu_MatrixAllocate();
    p->pValue2Node = pData->pValue2Node;
    p->fMvNetwork  = pData->fMvNetwork;

    // collect all sorts of statistics
    nCubesTotal = 0;
    nPairsTotal = 0;
    nPairsStore = 0;
    nBitsMax    = -1;
    nCubesMax   = -1;
    for ( i = 0; i < pData->nValuesOld; i++ )
        if ( pMvcCover = pData->ppCovers[i] )
        {
            nCubes       = Mvc_CoverReadCubeNum( pMvcCover );
            nCubesTotal += nCubes;
            nPairsTotal += nCubes * (nCubes - 1) / 2;
            nPairsStore += nCubes * nCubes;
            if ( nBitsMax < pMvcCover->nBits )
                nBitsMax = pMvcCover->nBits;
            if ( nCubesMax < nCubes )
                nCubesMax = nCubes;
        }
    assert( nBitsMax > 0 );

    // create the column labels 
    p->ppVars = ALLOC( Fxu_Var *, pData->nValuesAlloc );
    for ( i = 0; i < pData->nValuesOld; 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->nValuesOld; i++ )
        if ( pMvcCover = pData->ppCovers[i] )
        {
            // get the number of cubes
            nCubes = Mvc_CoverReadCubeNum( pMvcCover );
            // get the new var in the matrix
            pVar = p->ppVars[i];
            // 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->nValuesOld; i++ )
    {
        // get the corresponding cover
        pMvcCover = pData->ppCovers[i];
        // skip if the cover is not given
        if ( pMvcCover == NULL )
            continue;
        // skip if the cover is empty
        if ( Mvc_CoverReadCubeNum(pMvcCover) == 0 )
            continue;
        assert( pMvcCover->nBits != 0 );

        // get the new var in the matrix
        pVar = p->ppVars[i];

        // 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
        s_pLits = pMvcCover->pLits;
        for ( v = 0; v < pMvcCover->nBits; v++ )
            pOrder[v] = v;
        qsort( (void *)pOrder, pMvcCover->nBits,
            sizeof(int),(int (*)(const void *, const void *))Fxu_CreateMatrixLitCompare);
        assert( s_pLits[ pOrder[0] ] < s_pLits[ pOrder[pMvcCover->nBits-1] ] );

        // create the corresponding cubes in the matrix
        pCubeFirst = NULL;
        Mvc_CoverForEachCubeWithIndex( pMvcCover, pMvcCube, iMvcCube )
        {
            pCubeNew = Fxu_CreateMatrixAddCube( p, pVar, 
                pMvcCover, pMvcCube, iMvcCube, pOrder );
            if ( pCubeFirst == NULL )
                pCubeFirst = pCubeNew;
            pCubeNew->pFirst = pCubeFirst;
            pCubeNew->iCube  = iMvcCube;
        }
        // set the first cube of this var
        pVar->pFirst = pCubeFirst;
        // create the place to store the cube pairs
//        Fxu_PairAllocStorage( pVar, iMvcCube );

        // 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->ppCovers, pData->nValuesOld, 
               nPairsTotal, pData->nPairsMax );
    }

    // add the var pairs to the heap
    Fxu_MatrixComputeSingles( p );

//    Fxu_HeapSinglePrint( stdout, p->pHeapSingle );
//    Fxu_CreateSCDs( p, pData );
//    Fxu_MatrixPrintDivisorProfile( stdout, p );

    // allocate temporary storage for variables
  	p->pVarsTemp  = ALLOC( Fxu_Var *, pData->nValuesAlloc );
    // allocate temporary storage for pairs
//    assert( p->nPairsMax > 0 );
    p->pPairsTemp = ALLOC( Fxu_Pair *, p->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" );
    }
    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 Mvc cover.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Fxu_Cube * Fxu_CreateMatrixAddCube( Fxu_Matrix * p, Fxu_Var * pVarNew, 
    Mvc_Cover_t * pMvcCover, Mvc_Cube_t * pMvcCube, int iMvcCube, int * pOrder )
{
	Fxu_Cube * pCube;
	Fxu_Var * pVar;
	int i;

	// create the cube
	pCube = Fxu_MatrixAddCube( p, pVarNew, iMvcCube );
    // add literals to the matrix
    for ( i = 0; i < pMvcCover->nBits; i++ )
    {
        // co-singleton transform is done here!
        if ( !Mvc_CubeBitValue( pMvcCube, pOrder[i] ) )
        {
            pVar = p->ppVars[ pMvcCover->pLits[pOrder[i]] ];
		    Fxu_MatrixAddLiteral( p, pCube, pVar );
        }
    }
	return pCube;
}


/**Function*************************************************************

  Synopsis    [Creates the new array of Mvc 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, iValue, iValueFirst, nValues;
    int n, v;

    // add the node/value data for the new columns and rows
    for ( n = 0; n < pData->nNodesNew; n++ )
    {
        // get the number of this new node in the node lits
        iNode  = pData->nNodesOld + n;
        // get the first value in the value list
        iValue = pData->pNode2Value[iNode];
        // set the value to node for the values of the new node
        pData->pValue2Node[iValue  ] = iNode;
        pData->pValue2Node[iValue+1] = iNode;
        // set the node to value for the next node
        pData->pNode2Value[iNode+1]  = iValue + 2;
    }

    // write NULL for all CI values
    for ( v = 0; v < pData->nValuesCi; v++ )
        pData->ppCoversNew[v] = NULL;

    // get the first cube of the first internal node 
    pCubeFirst = Fxu_CreateCoversFirstCube( p, pData, pData->nNodesCi );

    // go through the internal nodes
    for ( n = 0; n < pData->nNodesInt; n++ )
    {
        // get the number of this node
        iNode = pData->nNodesCi + 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 >= pData->nValuesOld )
                break;
        if ( pCube == pCubeNext )
        {  // there is no change in this node
            iValueFirst = pData->pNode2Value[iNode];
            nValues     = pData->pNode2Value[iNode + 1] - pData->pNode2Value[iNode];
            for ( v = 0; v < nValues; v++ )
                pData->ppCoversNew[iValueFirst + v] = NULL;
        }
        else
        {   // the node has changed
            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
        if ( n == pData->nNodesNew - 1 )
            pCubeNext = NULL;
        else
            pCubeNext = Fxu_CreateCoversFirstCube(  p, pData, iNode + 1 );