fmsflex.c

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

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

  FileName    [fmsFlex.c]

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

  Synopsis    [Complete flexibility computation without windowing.]

  Author      [MVSIS Group]
  
  Affiliation [UC Berkeley]

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

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

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

#include "fmInt.h"
 
////////////////////////////////////////////////////////////////////////
///                        DECLARATIONS                              ///
////////////////////////////////////////////////////////////////////////

static bool fmsFlexPrepareGlobalBdds( Fms_Manager_t * pMan, DdManager * dd, Sh_Network_t * pNet );

static Mvr_Relation_t * fmsFlexReturnTrivial( Sh_Network_t * pNet, Mvr_Relation_t * pMvr );
static bool             fmsFlexComputeGlobalBdds( Fms_Manager_t * pMan, DdManager * dd, Sh_Network_t * pNet );
static DdNode *         fmsFlexComputeGlobal( Fms_Manager_t * pMan, Sh_Network_t * pNet );
static Mvr_Relation_t * fmsFlexComputeLocal( Fms_Manager_t * pMan, DdNode * bFlexGlo, Sh_Network_t * pNet, Mvr_Relation_t * pMvr );
static DdNode *         fmsFlexDeriveGlobalRelation( Fms_Manager_t * pMan, Sh_Network_t * pNet );
static DdNode *         fmsFlexComposeSpecials( Fms_Manager_t * pMan, DdNode * bFlex, Vmx_VarMap_t * pVmx, Sh_Network_t * pNet );
static int *            fmsFlexCreatePermMap( Fms_Manager_t * pMan );
static DdNode *         fmsFlexRemap( DdManager * dd, DdNode * bFlex, DdNode * pbFuncs[], DdNode * pbCodes[], int nValues, DdNode * bCubeChar );
static DdNode *         fmsFlexConvolve( DdManager * dd, DdNode * pbFuncs[], DdNode * pbCodes[], int nValues );
static DdNode *         fmsFlexTransferFromSetOutputs( Fms_Manager_t * pMan, DdNode * bFlexGlo );
static int              fmsFlexGetGlobalBddSize( Sh_Network_t * pNet );

extern int timeGlobal;
extern int timeContain;
extern int timeImage;
extern int timeImagePrep;
extern int timeResub;

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

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
bool Fms_FlexibilityPrepare( Fms_Manager_t * pMan, Sh_Network_t * pNet )
{
    DdManager * dd;
    int i;

    // create the internal list of nodes in the interleaved DFS order
    Sh_NetworkInterleaveNodes( pNet );
    // create the encoded global variable map for the leaves only
    pMan->pVmxGloL = Vmx_VarMapLookup( pMan->pManVmx, pNet->pVmL, -1, NULL );
    // improve the var map by interleaving variables
    pMan->pVmxGloL = Fm_UtilsCreateVarOrdering( pMan->pVmxGloL, pNet );

    // allocate the manager large enough to store this size
    pMan->nVars0 = Vmx_VarMapReadBitsNum( pMan->pVmxGloL );
    pMan->dd = dd = Cudd_Init( pMan->nVars0, 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0 );
    // set the leaves
    Fm_UtilsAssignLeaves( dd, dd->vars, pNet, pMan->pVmxGloL, 0 );

    // compute the global BDDs
    if ( !fmsFlexPrepareGlobalBdds( pMan, dd, pNet ) )
    {
        Cudd_Quit( pMan->dd );
        pMan->dd = NULL;
        return 0;
    }
    assert( dd->size == pMan->nVars0 );

    // set the global vars
    pMan->nVars0  = dd->size + 50;
    pMan->pbVars0 = ALLOC( DdNode *, dd->size + 50 );
    for ( i = 0; i < 50; i++ )
        Cudd_bddNewVar( dd );
    memcpy( pMan->pbVars0, dd->vars, sizeof(DdNode *) * pMan->nVars0 );


    // save the global BDD
    pMan->nGlos = pNet->nOutputs;
    pMan->pbGlos = ALLOC( DdNode *, pNet->nOutputs );
    for ( i = 0; i < pNet->nOutputs; i++ )
        pMan->pbGlos[i] = Fm_DataGetNodeGlo( pNet->ppOutputs[i] );

if ( pMan->fVerbose )
printf( "Global BDD size = %d.\n", Cudd_SharingSize( pMan->pbGlos, pMan->nGlos ) );
    return 1;
}

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

  Synopsis    [Computes the global BDDs for the first time.]

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

  SeeAlso     []

***********************************************************************/
bool fmsFlexPrepareGlobalBdds( Fms_Manager_t * pMan, DdManager * dd, Sh_Network_t * pNet )
{
    ProgressBar * pProgress;
    Sh_Node_t * pNode;
    DdNode * bFunc1, * bFunc2, * bFunc;
    int TimeLimit = 0;
    int nNodes, iNode;


    // If we cannot build the global BDDs in 10 seconds, 
    // then "mfs" with windowing should be used
	TimeLimit = (int)(10000 /* in miliseconds*/ * (float)(CLOCKS_PER_SEC) / 1000 ) + clock();

    // enable reordering for the first BDD construction
    Cudd_AutodynEnable( pMan->dd, CUDD_REORDER_SYMM_SIFT );

    // go through the internal nodes in the DFS order
    nNodes = Sh_NetworkDfs( pNet );
    // start the progress var
    if ( !pMan->fVerbose )
        pProgress = Extra_ProgressBarStart( stdout, nNodes );
    iNode = 0;
    Sh_NetworkForEachNodeSpecial( pNet, pNode )
    {
        if ( ++iNode % 50 == 0 && !pMan->fVerbose )
            Extra_ProgressBarUpdate( pProgress, iNode );
        assert( pNode->pData2 == 0 );

        if ( TimeLimit && clock() > TimeLimit )
        {
            if ( !pMan->fVerbose )
                Extra_ProgressBarStop( pProgress );
            return 0;
        }

//        if ( Sh_NodeIsVar(pNode) )
        if ( pNode->pOne == NULL )
        {   // make sure the elementary BDD is set
            assert( pNode->pData );
            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 ( !pMan->fVerbose )
        Extra_ProgressBarStop( pProgress );

    // reorder one last time
	Cudd_ReduceHeap( pMan->dd, CUDD_REORDER_SYMM_SIFT, 1 );
    Cudd_AutodynDisable( pMan->dd );
    return 1;
}


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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Mvr_Relation_t * Fms_FlexibilityCompute( Fms_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;
    int clk;


    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 = fmsFlexReturnTrivial( 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 );
    // expand the variable map by including additional variables
    pMan->pVmxGlo = Vmx_VarMapCreateAppended( pMan->pVmxGloL, pVm );
 
    // 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 );
        // expand the variable map by including additional variables
        pMan->pVmxGloS = Vmx_VarMapCreateAppended( pMan->pVmxGloL, pVm );
    }

    // resize the manager
    Fms_ManagerResize( pMan, Vmx_VarMapReadBitsNum(pMan->pVmxLoc) );
    // we may also need to resize after introducing the set inputs
//    if ( pMan->pVmxGloS )
//        Fms_ManagerResize( pMan, pNet->nOutputs );

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


    // compute the global BDDs
clk = clock();
    if ( !fmsFlexComputeGlobalBdds( pMan, dd, pNet ) )
    {
timeGlobal += clock() - clk;
//        Fm_UtilsDerefNetwork( dd, pNet );
        return NULL;
    }
timeGlobal += clock() - clk;

//printf( "Global BDD size = %d\n", fmsFlexGetGlobalBddSize(pNet) );

    // derive the containment condition from both pairs
clk = clock();
    bFlexGlo = fmsFlexComputeGlobal( pMan, pNet );  
timeContain += clock() - clk;

    if ( bFlexGlo == NULL )
    {
//        Fm_UtilsDerefNetwork( dd, pNet );
        return NULL;
    }
    else
    {
       Cudd_Ref( bFlexGlo );
       if ( pMan->fSetOutputs )
       {
           bFlexGlo = fmsFlexTransferFromSetOutputs( pMan, bTemp = bFlexGlo ); Cudd_Ref( bFlexGlo );
           Cudd_RecursiveDeref( dd, bTemp );
       }
    }

    // derive the flexibility local
    pMvrLoc = fmsFlexComputeLocal( 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    [Computes the global BDDs for the first time.]

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

  SeeAlso     []

***********************************************************************/
bool fmsFlexComputeGlobalBdds( Fms_Manager_t * pMan, DdManager * dd, Sh_Network_t * pNet )
{
    Sh_Node_t * pNode;
    DdNode * bFunc1, * bFunc2, * bFunc;
    int TimeLimit = 0;

    // If we cannot build the global BDDs in 1 second, 
    // it is worth stopping and trying another node
	TimeLimit = (int)(100 /* in miliseconds*/ * (float)(CLOCKS_PER_SEC) / 1000 ) + clock();

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

//        if ( Sh_NodeIsVar(pNode) )
        if ( pNode->pOne == NULL )
        {   // make sure the elementary BDD is set
            assert( pNode->pData );
            continue;
        }
        if ( shNodeIsConst(pNode) )
        {
            if ( pNode->pData )
                continue;
            Fm_DataSetNodeGlo( pNode, dd->one );  Cudd_Ref( dd->one );
            continue;
        }
        // this is the internal node
        // make sure the BDD is not computed
//        assert( pNode->Num < 0 || pNode->pData == 0 );
        // if the BDD is computed, this is fine
        if ( pNode->pData )
            continue;

        // 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
    }
    return 1;
}


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

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

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Mvr_Relation_t * fmsFlexReturnTrivial( 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 );