fncsopmin.c

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

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

  FileName    [fncSopMin.c]

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

  Synopsis    [Heuristic MV SOP minimization.]

  Author      [MVSIS Group]
  
  Affiliation [UC Berkeley]

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

  Revision    [$Id: fncSopMin.c,v 1.8 2003/05/27 23:15:06 alanmi Exp $]

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

#include "fncInt.h"
#include "cvrInt.h"

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

static DdNode * Fnc_FunctionDomainEssen( Mvr_Relation_t * pMvr, DdNode * bValueCube, DdNode * bCharCube );
static DdNode * Fnc_FunctionDomainTotal( Mvr_Relation_t * pMvr, DdNode * bValueCube, DdNode * bCharCube );

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

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

  Synopsis    [Heuristic minimization of ND MV SOP using ND MV relation.]

  Description [Returns (possibly ND) MV-SOP derived from the MV relation
  using the simple strategy: first compute the essential cubes that can be 
  covered with one i-set only; next greedily cover the remaining domains
  on-set    of the i-set:   ON(i)    = Univ  v [ R(a,v) == Vi(v) ]
  on/dc-set of the i-set:   ON/DC(i) = Exist v [ R(a,v) &  Vi(v) ]
  when all the i-sets are ready, the largest one becomes the default.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Cvr_Cover_t * Fnc_FunctionMinimizeCvr( Mvc_Manager_t * pManMvc, Mvr_Relation_t * pMvr, bool fUseIsop )
{
    DdManager * dd = pMvr->pMan->pDdLoc;
    Vm_VarMap_t * pVm = pMvr->pVmx->pVm;
    Mvc_Cover_t ** pbIsets;
    DdNode * bOn, * bOnDc, * bCharCube;
    DdNode * bFunc, * bAreaRem, * bTemp;
    DdNode ** pbCodes, ** pbCodesOut;
    int v, nOutputValues;
    int DefValue;
    int nCubesMax, nCubes;
    int MaxCoverCubeCount = -1;
    int MaxCoverValue;
    int fOneTimeout = 0;  // 1 if ISOP times out for one of the essential covers

    // reorder the relation
    Mvr_RelationReorder( pMvr );

    // the relation cannot be zero
    assert( pMvr->bRel != b0 );
    // get the number of values
    nOutputValues = Vm_VarMapReadValuesOutNum(pVm);
    
    // get the MV-PLA covers
    pbIsets = ALLOC( Mvc_Cover_t *, nOutputValues );
    memset( pbIsets, 0, sizeof(Mvc_Cover_t *) * nOutputValues );

    // the relation can be one
    // meaning that the output of this node is a don't-care
    if ( pMvr->bRel == b1 )
    { // set the node to a constant ND, it will be eliminated during sweep
        // (if this node remains in the network, make sure it is never resubstituted!!!)
        for ( v = 0; v < nOutputValues; v++ )
        {
            pbIsets[v] = Mvc_CoverAlloc( pManMvc, pVm->nValuesIn );
            Mvc_CoverMakeTautology( pbIsets[v] );
        }
        return Cvr_CoverCreate( pVm, pbIsets );
    }

    // derive the encoding cubes
    pbCodes = Vmx_VarMapEncodeMap( dd, pMvr->pVmx );
    // set the pointer to the output encoding cubes
    pbCodesOut = pbCodes + pVm->nValuesIn;
    // get the char cube w.r.t. the output value
    bCharCube = Vmx_VarMapCharCube( dd, pMvr->pVmx, pVm->nVarsIn );  Cudd_Ref( bCharCube );


    // remove the inessential values
    for ( v = 0; v < nOutputValues; v++ )
    {
        bOn = Fnc_FunctionDomainEssen( pMvr, pbCodesOut[v], bCharCube );  Cudd_Ref( bOn );
        if ( bOn == b0 )
        {
            // this value can be removed
            pMvr->bRel = Cudd_bddAnd( dd, bTemp = pMvr->bRel, Cudd_Not(pbCodesOut[v]) );  
            Cudd_Ref( pMvr->bRel );
            Cudd_RecursiveDeref( dd, bTemp );
        }
        Cudd_RecursiveDeref( dd, bOn );
    }
    assert( Mvr_RelationIsWellDefined(pMvr) );


    // prepare the Espresso computation
    if ( !fUseIsop )
       Cvr_CoverEspressoSetup(pVm);

    // start the remaining area
    bAreaRem = b1;   Cudd_Ref( bAreaRem );

    // find the cover that covers the essential part of each i-set
    for ( v = 0; v < nOutputValues; v++ )
    {
        // extract the on-set and the on/dc-set of this value
        bOn   = Fnc_FunctionDomainEssen( pMvr, pbCodesOut[v], bCharCube );  Cudd_Ref( bOn );
        bOnDc = Fnc_FunctionDomainTotal( pMvr, pbCodesOut[v], bCharCube );  Cudd_Ref( bOnDc );

#ifndef NDEBUG
        // verify the containment
        if ( !Cudd_bddLeq( dd, bOn, bOnDc ) )
            fprintf( stdout, "Fnc_FunctionMinimizeCvr(): ON-set is not contained in ON/DC-set\n" );
#endif

        // minimize the cover
        if ( fUseIsop )
            pbIsets[v] = Fnc_FunctionDeriveSopFromMddLimited( pManMvc, pMvr, bOn, bOnDc, pVm->nVarsIn );
        else
            pbIsets[v] = Fnc_FunctionDeriveSopFromMddEspresso( pManMvc, pMvr, bOn, bOnDc, pVm->nVarsIn );

        // check if timeout/cubeout has occurred
        if ( pbIsets[v] == NULL )
        {
            if ( !fOneTimeout )
            {
                fOneTimeout = 1;
                // reset the timeout for the ISOP computation to continue
//              mvfsIsopTimeoutSet( enviNode->enviNet->timeoutNode );

                // set the current value as a default value
                MaxCoverCubeCount = 1000000;
                MaxCoverValue     = v;

                // subtract from the remaning area
                bAreaRem = Cudd_bddAnd( dd, bTemp = bAreaRem, Cudd_Not(bOnDc) );  Cudd_Ref( bAreaRem );
                Cudd_RecursiveDeref( dd, bOn );
                Cudd_RecursiveDeref( dd, bOnDc );
                Cudd_RecursiveDeref( dd, bTemp );
                continue;
            }
            else
            {
                // deref the temporary BDDs
                Cudd_RecursiveDeref( dd, bOn );
                Cudd_RecursiveDeref( dd, bOnDc );
                Cudd_RecursiveDeref( dd, bAreaRem );
                Vmx_VarMapEncodeDeref( dd, pMvr->pVmx, pbCodes );
                Cudd_RecursiveDeref( dd, bCharCube );
                // undo Espresso cube
                if ( !fUseIsop )
                    Cvr_CoverEspressoSetdown(pVm);
                // free the computed covers
                for ( v = 0; v < nOutputValues; v++ )
                    if ( pbIsets[v] )
                        Mvc_CoverFree( pbIsets[v] );
                FREE( pbIsets );
                // return NULL, meaning we cannot minimize the cover with these limits
                return NULL;
            }
        }

        // find the covered part of the area
        bFunc = Fnc_FunctionDeriveMddFromSop( dd, pVm, pbIsets[v], pbCodes );  Cudd_Ref( bFunc );

#ifndef NDEBUG
        // verification
        if ( !Cudd_bddLeq( dd, bOn, bFunc ) )
            fprintf( stdout, "Fnc_FunctionMinimizeCvr(): The on-set is not contained in the solution\n" );
        if ( !Cudd_bddLeq( dd, bFunc, bOnDc ) )
            fprintf( stdout, "Fnc_FunctionMinimizeCvr(): The solution is not contained in the on-set plus dc-set\n" );
#endif

        Cudd_RecursiveDeref( dd, bOn );
        Cudd_RecursiveDeref( dd, bOnDc );

        // subtract from the remaning area
        bAreaRem = Cudd_bddAnd( dd, bTemp = bAreaRem, Cudd_Not(bFunc) );  Cudd_Ref( bAreaRem );
        Cudd_RecursiveDeref( dd, bTemp );
        Cudd_RecursiveDeref( dd, bFunc );

        // get the value with the largest number of cubes
        nCubes = Mvc_CoverReadCubeNum(pbIsets[v]);
        if ( MaxCoverCubeCount < nCubes )
        {
             MaxCoverCubeCount = nCubes;
             MaxCoverValue     = v;
        }
    }

    // check the remaning area
    if ( bAreaRem != b0 )
    {   // the remaining area is not zero; there remains something to be covered
        DdNode * bCoveringValues, * bInputVarCube;

        // get the input variable cube
        bInputVarCube = Vmx_VarMapCharCubeInput( dd, pMvr->pVmx );