fmwflex.c

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

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

  FileName    [fmwFlex.c]

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

  Synopsis    [Complete flexibility computation with windowing.]

  Author      [MVSIS Group]
  
  Affiliation [UC Berkeley]

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

  Revision    [$Id: fmwFlex.c,v 1.3 2003/05/27 23:15:36 alanmi Exp $]

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

#include "fmInt.h"

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

static Mvr_Relation_t * fmwFlexReturnTrivial( Sh_Network_t * pNet, Mvr_Relation_t * pMvr );
static bool             fmwFlexComputeGlobalBdds( Fmw_Manager_t * pMan, DdManager * dd, Sh_Network_t * pNet );
static DdNode *         fmwFlexComputeGlobal( Fmw_Manager_t * pMan, Sh_Network_t * pNet );
static Mvr_Relation_t * fmwFlexComputeLocal( Fmw_Manager_t * pMan, DdNode * bFlexGlo, Sh_Network_t * pNet, Mvr_Relation_t * pMvr );
static DdNode *         fmwFlexDeriveGlobalRelation( Fmw_Manager_t * pMan, Sh_Network_t * pNet );
static DdNode *         fmwFlexComposeSpecials( Fmw_Manager_t * pMan, DdNode * bFlex, Vmx_VarMap_t * pVmx, Sh_Network_t * pNet );
static int *            fmwFlexCreatePermMap( Fmw_Manager_t * pMan );
static DdNode *         fmwFlexRemap( DdManager * dd, DdNode * bFlex, DdNode * pbFuncs[], DdNode * pbCodes[], int nValues, DdNode * bCubeChar );
static DdNode *         fmwFlexConvolve( DdManager * dd, DdNode * pbFuncs[], DdNode * pbCodes[], int nValues );
static DdNode *         fmwFlexTransferFromSetOutputs( Fmw_Manager_t * pMan, DdNode * bFlexGlo );
static int              fmwFlexGetGlobalBddSize( Sh_Network_t * pNet );

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

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Mvr_Relation_t * Fm_FlexibilityCompute( Fmw_Manager_t * pMan, Sh_Network_t * pNet, Mvr_Relation_t * pMvr )
{
    DdManager * dd = pMan->dd;
    Mvr_Relation_t * pMvrLoc;
    Vm_VarMap_t * pVm;
    DdNode * bFlexGlo, * bTemp;

    assert( pNet->nInputsCore > 0 && pNet->nOutputsCore > 0 );

//    Sh_NodePrintArray( pNet->ppOutputsCore, pNet->nOutputsCore );

    // the computation of flexibility is not needed
    // if the structural hashing has derived constant functions for all i-sets
    // here we check this condition
    if ( pMvrLoc = fmwFlexReturnTrivial( pNet, pMvr ) )
    {
        if ( pMan->fVerbose )
            printf( "Strashing has derived a constant %d-valued node.\n", pNet->nOutputsCore );
        return pMvrLoc;
    }

    // create the internal list of nodes in the interleaved DFS order
    Sh_NetworkInterleaveNodes( pNet );;
    // clean the data fields of the nodes in the list
    Sh_NetworkCleanData( pNet );

    // create the encoded local variable map
    pVm = Vm_VarMapCreateInputOutput( pNet->pVmLC, pNet->pVmRC );
    pMan->pVmxLoc = Vmx_VarMapLookup( pMan->pManVmx, pVm, -1, NULL );
    // create the encoded global variable map
    pVm = Vm_VarMapCreateInputOutput( pNet->pVmL, pNet->pVmRC );
    pMan->pVmxGlo = Vmx_VarMapLookup( pMan->pManVmx, pVm, -1, NULL );
 
    // create the encoded local variable map with sets
    if ( pMan->fSetOutputs )
    { // create the set-output map
        pVm = Vm_VarMapCreateInputOutputSet( pNet->pVmL, pNet->pVmRC, 0, 1 );
        pMan->pVmxGloS = Vmx_VarMapLookup( pMan->pManVmx, pVm, -1, NULL );
        pMan->pVmxGloS = Fm_UtilsCreateVarOrdering( pMan->pVmxGloS, pNet );
    }
    else
    {
        pMan->pVmxGlo = Fm_UtilsCreateVarOrdering( pMan->pVmxGlo, pNet );
    }

    // resize the manager
    Fmw_ManagerResize( pMan, Vmx_VarMapReadBitsNum(pMan->pVmxLoc) );
    Fmw_ManagerResize( pMan, Vmx_VarMapReadBitsNum(pMan->pVmxGlo) );
    if ( pMan->pVmxGloS )
        Fmw_ManagerResize( pMan, Vmx_VarMapReadBitsNum(pMan->pVmxGloS) );

    // set the var encoding cubes at the nodes
    if ( !pMan->fSetOutputs )
        Fm_UtilsAssignLeaves( dd, pMan->pbVars0, pNet, pMan->pVmxGlo, 0 );
    else
        Fm_UtilsAssignLeavesSet( dd, pMan->pbVars0, pNet, pMan->pVmxGloS, 0 );

    // compute the global BDDs
    Sh_NetworkDfs( pNet );
    if ( !fmwFlexComputeGlobalBdds( pMan, dd, pNet ) )
    {
        Fm_UtilsDerefNetwork( dd, pNet );
        return NULL;
    }
//printf( "Global BDD size = %d\n", fmwFlexGetGlobalBddSize(pNet) );
    // derive the containment condition from both pairs
    bFlexGlo = fmwFlexComputeGlobal( pMan, pNet );  
    if ( bFlexGlo == NULL )
    {
        Fm_UtilsDerefNetwork( dd, pNet );
        return NULL;

        if ( pMan->fVerbose )
            printf( "Global flexbility comptutation has timed out!\n" );
        bFlexGlo = fmwFlexDeriveGlobalRelation( pMan, pNet );
        Cudd_Ref( bFlexGlo );
    }
    else
    {
       Cudd_Ref( bFlexGlo );
       if ( pMan->fSetOutputs )
       {
           bFlexGlo = fmwFlexTransferFromSetOutputs( pMan, bTemp = bFlexGlo ); Cudd_Ref( bFlexGlo );
           Cudd_RecursiveDeref( dd, bTemp );
       }
    }

    // derive the flexibility local
    pMvrLoc = fmwFlexComputeLocal( pMan, bFlexGlo, pNet, pMvr );
    Cudd_RecursiveDeref( dd, bFlexGlo );

    assert( Vm_VarMapReadVarsInNum( Mvr_RelationReadVm(pMvr) ) == 
            Vm_VarMapReadVarsInNum( Mvr_RelationReadVm(pMvrLoc) ) );

    // deref the intemediate BDDs
    Fm_UtilsDerefNetwork( dd, pNet );
    return pMvrLoc;
}


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

  Synopsis    [Returns the trivial solution if it is computed by strashing.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Mvr_Relation_t * fmwFlexReturnTrivial( Sh_Network_t * pNet, Mvr_Relation_t * pMvr )
{
    DdManager * dd;
    Mvr_Relation_t * pMvrLoc;
    Vmx_VarMap_t * pVmxLoc;
    DdNode ** pbCodes;
    DdNode * bFunc, * bTemp;
    unsigned Polarity;
    int nVarsIn, nVarsOut, i;

    Polarity = 0;
    for ( i = 0; i < pNet->nOutputsCore; i++ )
        if ( !Sh_NodeIsConst(pNet->ppOutputsCore[i]) )
            return NULL;
        else
        {
            if ( !Sh_IsComplement(pNet->ppOutputsCore[i]) )
                Polarity |= ( 1 << i );
        }

    // if we end up here, the relation is indeed a constant
    dd       = Mvr_RelationReadDd(pMvr);
    pVmxLoc  = Mvr_RelationReadVmx(pMvr);
    nVarsIn  = Vm_VarMapReadVarsInNum( Vmx_VarMapReadVm(pVmxLoc) );
    nVarsOut = Vm_VarMapReadVarsOutNum( Vmx_VarMapReadVm(pVmxLoc) );
    assert( nVarsOut == 1 );
    pbCodes  = Vmx_VarMapEncodeVar( dd, pVmxLoc, nVarsIn );

    // create the constant relation
    bFunc = b0; Cudd_Ref( bFunc );
    for ( i = 0; i < pNet->nOutputsCore; i++ )
        if ( Polarity & (1 << i) )
        {
            bFunc = Cudd_bddOr( dd, bTemp = bFunc, pbCodes[i] );  Cudd_Ref( bFunc );
            Cudd_RecursiveDeref( dd, bTemp );
        }

    // deref the codes
    Vmx_VarMapEncodeDeref( dd, pVmxLoc, pbCodes );

    // create the relation
    pMvrLoc = Mvr_RelationCreate( Mvr_RelationReadMan(pMvr), pVmxLoc, bFunc ); 
    Cudd_Deref( bFunc );
    return pMvrLoc;
}


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

  Synopsis    [Computes the global BDDs for all the node.]

  Description [Assumes the internal nodes are linked in the specialized
  linked list. Returns 0 if the timeout has occurred.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
bool fmwFlexComputeGlobalBdds( Fmw_Manager_t * pMan, DdManager * dd, Sh_Network_t * pNet )
{
    Sh_Node_t * pNode;
    DdNode * bFunc1, * bFunc2, * bFunc;
    DdNode * bFunc1Z, * bFunc2Z, * bFuncZ;
    int TimeLimit = 0;

	TimeLimit = (int)(500 /* in miliseconds*/ * (float)(CLOCKS_PER_SEC) / 1000 ) + clock();

    // go through the internal nodes in the DFS order
    Sh_NetworkForEachNodeSpecial( pNet, pNode )
    {
        if ( TimeLimit && clock() > TimeLimit )
            return 0;

//        if ( Sh_NodeIsVar(pNode) )
        if ( pNode->pOne == NULL )
        {   // make sure the elementary BDD is set
//            assert( pNode->pData );
            if ( pNode->pData )
                continue;
            if ( pNode->pData == 0 )
            {
                if ( pMan->fVerbose )
                    printf( "Visiting trivial special node...\n" );
                assert( pNode->pData2 );
                bFunc = Fm_DataGetNodeGlo( pNet->pMan->pVars[(int)pNode->pTwo] );  Cudd_Ref( bFunc );
                Fm_DataSetNodeGlo( pNode, bFunc ); // takes ref
                continue;
            }
            assert( 0 );
            continue;
        }
        if ( shNodeIsConst(pNode) )
        {
            assert( pNode->pData == 0 );
            Fm_DataSetNodeGlo( pNode, dd->one );  Cudd_Ref( dd->one );
            continue;
        }
        // this is the internal node
        // make sure the BDD is not computed
        assert( pNode->pData == 0 );

        // compute the global BDD
        bFunc1 = Fm_DataGetNodeGlo( pNode->pOne );
        bFunc2 = Fm_DataGetNodeGlo( pNode->pTwo );
        // get the result
        bFunc = Cudd_bddAnd( dd, bFunc1, bFunc2 );  Cudd_Ref( bFunc );
        // set it at the node
        Fm_DataSetNodeGlo( pNode, bFunc ); // takes ref

        // if the global BDD Z is set, do not compute it
        if ( bFuncZ = Fm_DataGetNodeGloZ(pNode) )
            continue;

        // compute the global BDD Z
        bFunc1Z = Fm_DataGetNodeGloZ( pNode->pOne );
        bFunc2Z = Fm_DataGetNodeGloZ( pNode->pTwo );
        if ( bFunc1Z || bFunc2Z )
        {
            if ( bFunc1Z == NULL )
                bFunc1Z = bFunc1;
            if ( bFunc2Z == NULL )
                bFunc2Z = bFunc2;
            // get the result
            bFuncZ = Cudd_bddAnd( dd, bFunc1Z, bFunc2Z );  Cudd_Ref( bFuncZ );
            // set it at the node
            Fm_DataSetNodeGloZ( pNode, bFuncZ ); // takes ref
        }
    }
    return 1;
}


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

  Synopsis    [Get the flexibility in the global space.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
DdNode * fmwFlexComputeGlobal( Fmw_Manager_t * pMan, Sh_Network_t * pNet )
{
    DdManager * dd = pMan->dd;
    Vm_VarMap_t * pVm;
    DdNode * bFunc, * bFuncZ;
    DdNode * bRel, * bCond, * bTemp;
    Sh_Node_t * pNode;
    int * pValues, * pValuesFirst;
    int i, v, iValue, nVarsOut;

    Extra_OperationTimeoutSet( 300 );

    // get parameters
    pVm          = pNet->pVmR;
    nVarsOut     = Vm_VarMapReadVarsInNum( pVm );
    pValues      = Vm_VarMapReadValuesArray( pVm );
    pValuesFirst = Vm_VarMapReadValuesFirstArray( pVm );

    // create the containment condition
    bRel = b1;   Cudd_Ref( bRel );
    iValue = 0;
    for ( i = 0; i < nVarsOut; i++ )
    {
        for ( v = 0; v < pValues[i]; v++ )
        {
            // get the node
            pNode = pNet->ppOutputs[pValuesFirst[i] + v];

            // get the global BDD of the cut network
            bFuncZ = Fm_DataGetNodeGloZ( pNode );
            // if this BDD is not set, this output does not depend on the cut var
            if ( bFuncZ == NULL )
                continue;

            // get the global BDD of the primary network
            bFunc = Fm_DataGetNodeGlo( pNode );

            // get the condition  (bFuncZ => bFunc)
            bCond = Cudd_bddOr( dd, Cudd_Not(bFuncZ), bFunc ); Cudd_Ref( bCond );