fnccvr.c

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

/**CFile****************************************************************

  FileName    [fncCvrMvr.c]

  PackageName [MVSIS 2.0: Multi-valued logic synthesis system.]

  Synopsis    [Procedures to convert among the MV relation and MV SOP.]

  Author      [MVSIS Group]
  
  Affiliation [UC Berkeley]

  Date        [Ver. 1.0. Started - February 1, 2003.]

  Revision    [$Id: fncCvr.c,v 1.9 2003/05/27 23:15:04 alanmi Exp $]

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

#include "fncInt.h"

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

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

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

  Synopsis    [Derives the MV SOP from the relation.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Cvr_Cover_t * Fnc_FunctionDeriveCvrFromMvr( Mvc_Manager_t * pManMvc, Mvr_Relation_t * pMvr, int fUseDefault )
{
    DdManager * dd = pMvr->pMan->pDdLoc;
    Cvr_Cover_t * pCvr;
    Vm_VarMap_t * pVm;
    DdNode ** pbIsets;
    DdNode ** pzIsets;
    Mvc_Cover_t ** pCovers;
    Mvc_Cover_t * pMvc;
    int nCubesMax, nCubesCur, iCoverMax, i;
    int nOutputValues;
    Mvc_Data_t * pData;

        
    // get the MV var map of this relation
    pVm = pMvr->pVmx->pVm;
    // get the number of output values
    nOutputValues = Vm_VarMapReadValuesOutput( pVm );

    // if the cover has MV vars, perform distance-1 merge
    pData = NULL;
    if ( !Vm_VarMapIsBinaryInput( pVm ) )
    {
        pMvc = Mvc_CoverAlloc( pManMvc, pVm->nValuesIn );
        pData = Mvc_CoverDataAlloc( pVm, pMvc );
    }

    // allocate room for cofactors
    pbIsets = ALLOC( DdNode *, nOutputValues );
    // get the i-sets w.r.t the last variable
    Mvr_RelationCofactorsDerive( pMvr, pbIsets, pVm->nVarsIn, nOutputValues );

    // assign the default value if needed
    if ( !fUseDefault )
    {
        // create the covers
        pCovers = ALLOC( Mvc_Cover_t *, nOutputValues );
        for ( i = 0; i < nOutputValues; i++ )
        {
            pCovers[i] = Fnc_FunctionDeriveSopFromMdd( pManMvc, pMvr, pbIsets[i], pbIsets[i], pVm->nVarsIn );
            if ( pData )
                Mvc_CoverDist1Merge( pData, pCovers[i] );
        }
        // start the Cvr object
        pCvr = Cvr_CoverCreate( pVm, pCovers );
    }
    else
    {
        // create ZDDs for each i-set
        pzIsets = ALLOC( DdNode *, nOutputValues );
        if ( nOutputValues == 2 )
        {
            pzIsets[0] = NULL;
            pzIsets[1] = Extra_zddIsopCoverAlt( dd, pbIsets[1], pbIsets[1] );  
            Cudd_Ref( pzIsets[1] );
            iCoverMax = 0;
        }
        else
            iCoverMax = Fnc_FunctionDeriveZddFromMvr( dd, pbIsets, pzIsets, nOutputValues );

        // if the default value is not assigned, do it now
        if ( iCoverMax == -1 )
        { // find the largest i-set
            nCubesMax = -1;
            for ( i = 0; i < nOutputValues; i++ )
            {
                nCubesCur = Cudd_zddCount( dd, pzIsets[i] );
                if ( nCubesMax < nCubesCur )
                {
                    nCubesMax = nCubesCur;
                    iCoverMax = i;
                }
            }
            assert( nCubesMax >= 0 );
        }

        // make sure this i-set does not overlap with other i-sets
        for ( i = 0; i < nOutputValues; i++ )
            if ( i != iCoverMax )
            {
                if ( !Cudd_bddLeq( dd, pbIsets[iCoverMax], Cudd_Not(pbIsets[i]) ) )
                { // there is overlap -> we cannot use the default value
                    // compute the missing i-set 
                    if ( iCoverMax >= 0 )
                    {
                        if ( pzIsets[iCoverMax] == NULL )
                        {
                            pzIsets[iCoverMax] = Extra_zddIsopCoverAlt( dd, pbIsets[iCoverMax], pbIsets[iCoverMax] );  
                            Cudd_Ref( pzIsets[iCoverMax] );
                        }
                    }
                    iCoverMax = -1;
                    break;
                }
            }

        // create the covers
        pCovers = ALLOC( Mvc_Cover_t *, nOutputValues );
        for ( i = 0; i < nOutputValues; i++ )
            if ( i != iCoverMax )
            {
                pCovers[i] = Fnc_FunctionDeriveSopFromZdd( pManMvc, pMvr, pzIsets[i], pVm->nVarsIn );
                if ( pData )
                    Mvc_CoverDist1Merge( pData, pCovers[i] );
            }
            else
                pCovers[i] = NULL;
        // start the Cvr object
        pCvr = Cvr_CoverCreate( pVm, pCovers );

        // deref the ZDDs
        for ( i = 0; i < nOutputValues; i++ )
            if ( pzIsets[i] )
                Cudd_RecursiveDerefZdd( dd, pzIsets[i] );
        FREE( pzIsets );
    }

    // deallocate the MV data structure
    if ( pData )
    {
        Mvc_CoverDataFree( pData, pMvc );
        Mvc_CoverFree( pMvc );
        pData = NULL;
    }


    Mvr_RelationCofactorsDeref( pMvr, pbIsets, pVm->nVarsIn, nOutputValues );
    FREE( pbIsets );
    return pCvr;
}



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

  Synopsis    [Returns the default i-set.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Fnc_FunctionDeriveZddFromMvr( DdManager * dd, DdNode * pbIsets[], DdNode * pzIsets[], int nIsets )
{
    int nBTrackLimit, nIters;
    int Default, CounterZero;
    int i;

    // set the limit on the number of backtracks
    nBTrackLimit = 100;
    nIters = 0;
    while ( 1 )
    {
        nIters++;
        CounterZero = 0;
        Default = -1;
        for ( i = 0; i < nIsets; i++ )
        {
            pzIsets[i] = Extra_zddIsopCoverAltLimited( dd, pbIsets[i], pbIsets[i], nBTrackLimit );
            if ( pzIsets[i] )
            {
                Cudd_Ref( pzIsets[i] ); 
                continue;
            }
            // set the current zero cover (the default candidate)
            Default = i;
            // increment the counter of zero covers
            CounterZero++;
        }
        if ( CounterZero <= 1 )
            break;
        // deref the results
        for ( i = 0; i < nIsets; i++ )
            if ( pzIsets[i] )
            {
                Cudd_RecursiveDerefZdd( dd, pzIsets[i] );
                pzIsets[i] = NULL;
            }
        // update the backtrack limit
        if ( nIters % 4 )
            nBTrackLimit *= 2;
    }
//    printf( "%d ", nIters );
    return Default;
}


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

  Synopsis    [Derives the MV SOP from the relation.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Cvr_Cover_t * Fnc_FunctionDeriveCvrFromMvr2( Mvc_Manager_t * pManMvc, Mvr_Relation_t * pMvr, int fUseDefault )
{
    Cvr_Cover_t * pCvr;
    Vm_VarMap_t * pVm;
    DdNode ** pbIsets;
    int * pnCubesInIsets;
    Mvc_Cover_t * * pCovers;
    int nCubesMax, iCoverMax, i;
    int nOutputValues;
    
    // get the MV var map of this relation
    pVm = pMvr->pVmx->pVm;
    // get the number of output values
    nOutputValues = Vm_VarMapReadValuesOutput( pVm );

    // allocate room for cofactors
    pbIsets = ALLOC( DdNode *, nOutputValues );
    // set the i-sets w.r.t the last variable
    Mvr_RelationCofactorsDerive( pMvr, pbIsets, pVm->nVarsIn, nOutputValues );

    // assign the default value if needed
    if ( !fUseDefault )
    {
        // create the covers
        pCovers = ALLOC( Mvc_Cover_t *, nOutputValues );
        for ( i = 0; i < nOutputValues; i++ )
            pCovers[i] = Fnc_FunctionDeriveSopFromMdd( pManMvc, pMvr, pbIsets[i], pbIsets[i], pVm->nVarsIn );
        // start the Cvr object
        pCvr = Cvr_CoverCreate( pVm, pCovers );
    }
    else
    {
        // without computing ZDDs of ISOPs for each i-set, find the number of cubes
        pnCubesInIsets = ALLOC( int, nOutputValues );
        for ( i = 0; i < nOutputValues; i++ )
            pnCubesInIsets[i] = Extra_zddIsopCubeNum( pMvr->pMan->pDdLoc, pbIsets[i], pbIsets[i] );   

        // find the largest i-set
        nCubesMax = -1;
        for ( i = 0; i < nOutputValues; i++ )
            if ( nCubesMax < pnCubesInIsets[i] )
            {
                nCubesMax = pnCubesInIsets[i];
                iCoverMax = i;
            }
        assert( nCubesMax >= 0 );

        // make sure this i-set does not overlap with other i-sets
        for ( i = 0; i < nOutputValues; i++ )
            if ( i != iCoverMax )
            {
                if ( !Cudd_bddLeq( pMvr->pMan->pDdLoc, pbIsets[iCoverMax], Cudd_Not(pbIsets[i]) ) )
                { // there is an overlap -> we cannot use the default value
                    iCoverMax = -1;