simpfull.c

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

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

  FileName    [simpCodc.c]

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

  Synopsis    [MV network simplification using CODC's]

  Author      [MVSIS Group]
  
  Affiliation [UC Berkeley]

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

  Revision    [$Id: simpFull.c,v 1.31 2003/05/27 23:16:14 alanmi Exp $]

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

#include "simpInt.h"
#include <time.h>


/*---------------------------------------------------------------------------*/
/* Constant declarations                                                     */
/*---------------------------------------------------------------------------*/


/**AutomaticStart*************************************************************/

/*---------------------------------------------------------------------------*/
/* Static function prototypes                                                */
/*---------------------------------------------------------------------------*/

static Simp_Node_t *SimpNodeInit(Ntk_Network_t *net,Ntk_Node_t *node);
static void         SimpNodeEnd (Simp_Info_t *pInfo,Ntk_Node_t *node);
static st_table *   SimpNodeSupportCi(Ntk_Network_t *net,Ntk_Node_t *node);
static int          SimpNodeSupportNum(Ntk_Node_t *node);
static int          SimpNodeSupportCompare(char **pn1, char **pn2);
static void         SimpNodeUpdate(Ntk_Node_t *node, Simp_Info_t *pInfo);
static void         SimpNodeFreeGlo ( Ntk_Node_t *pNode, Simp_Info_t *pInfo );
static bool         SimpNodeIsOrphan( Ntk_Node_t *pNode, Simp_Node_t *pSimp );

static void         SimpProcessOrphanRecur(Ntk_Node_t *tnode);
static void         SimpBfsOrderRecur(Simp_Info_t *pInfo, sarray_t *aLevelThis,
                           sarray_t *aLevelAll,st_table *stFoutCount,int iLevels);

static bool         SimpComputeMddGlobal(Ntk_Network_t *n, Simp_Info_t *pInfo);
static bool         SimpSimplifyWithCodc(Ntk_Node_t *n,  Simp_Info_t *pInfo);


/**AutomaticEnd***************************************************************/


/*---------------------------------------------------------------------------*/
/* Definition of exported functions                                          */
/*---------------------------------------------------------------------------*/

/**Function********************************************************************
  Synopsis    [Simplify the network using MV-CODC's.]
  Description [Simplify the network using MV-CODC's. Return TRUE if a timeout
  has occured. The CODC computation is programmed to be as modular as
  possible. A separate package can also use the CODC set by simply following
  the following calls:
      pInfo = Simp_InfoInit(network);
      Simp_FullsimpInit(network, pInfo);
      ...compute CODC/SDC/MODC and do you own stuff...
      Simp_FullsimpEnd(network, pInfo);
  ]
  SideEffects []
  SeeAlso     []
******************************************************************************/
bool
Simp_NetworkFullSimplify(
    Ntk_Network_t *pNet,
    Simp_Info_t   *pInfo)
{
    int          i, num_timeouts;
    bool         timeout_occur;
    sarray_t    *listBfs;
    Ntk_Node_t  *pNode;
    ProgressBar * pProgress;
    long         clk, start_time, simplify_time, time_left;
    
    start_time = clock();
    timeout_occur = FALSE;
    
    /* assume sweep has been done */
    
    Simp_FullsimpInit(pNet, pInfo);
    pInfo->time_glob += clock() - start_time;
    
    /* order nodes according to size of their supports */
    listBfs = SimpComputeBfsOrder( pNet, pInfo);
    
    /* start the progress bar */
    pProgress = Extra_ProgressBarStart( stdout, listBfs->num );
    
    simplify_time = clock();
    num_timeouts  = 0;
    time_left     = pInfo->timeout_net;
    
    sarrayForEachItem ( Ntk_Node_t *, listBfs, i, pNode ) {
        
        if ( Ntk_NodeIsCo( pNode ) ) continue;
        clk = clock();
        
        if (SimpSimplifyWithCodc( pNode, pInfo )) {
            printf("Node timeout (%d sec) at [%s]\n",
                   (int)(pInfo->timeout_node/CLOCKS_PER_SEC),
                   Ntk_NodeGetNamePrintable(pNode));
            num_timeouts++;
        }
        
        time_left -= clock() - clk;
        if (time_left <= 0) { 
            timeout_occur = 1;
            printf("Total timeout (%d sec) occured at node [%s]\n",
                   (int)(pInfo->timeout_net/CLOCKS_PER_SEC),
                   Ntk_NodeGetNamePrintable(pNode));
            break;
        }
        
        if ( i % 10 == 0 ) {
            Extra_ProgressBarUpdate( pProgress, i );
        }
    }
    sarray_free(listBfs);
    Extra_ProgressBarStop( pProgress );
    
    /* print total number of timed out nodes */
    if (!timeout_occur && num_timeouts > 0) {
        printf("Iter %d: timeout at %d node(s)\n",
                pInfo->nIter, num_timeouts);
    }
    
    /* print performance statistics */
    if (pInfo->verbose) {
        printf("\nPerformance summary:\n");
        printf("MINI:\t%s\n", print_time(pInfo->time_mini));
        printf("IMAG:\t%s\n", print_time(pInfo->time_imag));
        printf("CSPF:\t%s\n", print_time(pInfo->time_cspf));
        printf("GLOB:\t%s\n", print_time(pInfo->time_glob));
        printf("TOTL:\t%s\n", print_time(clock()-start_time));
    }
    
    Simp_FullsimpEnd(pNet, pInfo);
    
    return timeout_occur;
}


/**Function********************************************************************
  Synopsis    [Initialize the data structure needed for CODC computation.]
  Description [Return 1 if failed.]
  SideEffects []
  SeeAlso     []
******************************************************************************/
bool
Simp_FullsimpInit(
    Ntk_Network_t *pNet,
    Simp_Info_t   *pInfo) 
{
    int          iSeq;
    DdNode     **pbFuncs;
    Ntk_Node_t  *pNode, *pFanin;
    Simp_Node_t *pSimp;
    
    /* allocate aux_field for mv_simp_type_t */
    Ntk_NetworkForEachCo( pNet, pNode ) {
        Simp_DaemonSetNodeData(pNode, NULL);
    }
    Ntk_NetworkForEachCi( pNet, pNode ) {
        Simp_DaemonSetNodeData(pNode, NULL);
    }
    
    Ntk_NetworkForEachNode( pNet, pNode ) {
        pSimp = SimpNodeInit(pNet, pNode);
        Simp_DaemonSetNodeData(pNode, pSimp);
    }
    
    /* initiate a new Cudd manager for global MDD's */
    pInfo->ddmg = Cudd_Init( 0, 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0 );
    Cudd_AutodynEnable( pInfo->ddmg, CUDD_REORDER_SYMM_SIFT );
    
    /* allocate space for MVF; compute local and global MDD */
    if (SimpComputeMddGlobal(pNet, pInfo)) {
        return 1;
    }
    Cudd_AutodynDisable( pInfo->ddmg );
    
    /* store information for complete flexibility computation */
    if ( pInfo->dc_type == 3 ) {
        int nValues;
        
        pInfo->ppbCoGlo = ALLOC( Mva_Func_t *, Ntk_NetworkReadCoNum(pNet) );
        iSeq = 0;
        Ntk_NetworkForEachCo( pNet, pNode ) {
            
            pFanin  = Ntk_NodeReadFaninNode( pNode, 0 );
            pbFuncs = Ntk_NodeReadFuncGlo( pFanin );
            nValues = Ntk_NodeReadValueNum(pFanin);
            pInfo->ppbCoGlo[iSeq++] = Mva_FuncCreate( pInfo->ddmg,
                                         nValues, pbFuncs );
        }
    }
    return 0;
}


/**Function********************************************************************
  Synopsis    [Clean up the data structure needed for CODC computation.]
  Description [Assume that Simp_FullsimpInit() has been called. Return 1 if failed.]
  SideEffects []
  SeeAlso     [Simp_FullsimpInit]
******************************************************************************/
bool
Simp_FullsimpEnd(
    Ntk_Network_t *network,
    Simp_Info_t   *pInfo) 
{
    int         nValues, i;
    Ntk_Node_t *pNode;
    DdNode    **pbFuncs;
    
    Ntk_NetworkForEachNode( network, pNode ) {
        SimpNodeEnd( pInfo, pNode );
        
        pbFuncs = Ntk_NodeReadFuncGlo( pNode );
        nValues = Ntk_NodeReadValueNum( pNode );
        if ( pbFuncs ) {
            Ntk_NodeWriteFuncGlo( pNode, NULL );
            for ( i = 0; i < nValues; i++ )
                Cudd_RecursiveDeref( pInfo->ddmg, pbFuncs[i] );
            FREE( pbFuncs );
        }
    }
    Ntk_NetworkForEachCi( network, pNode ) {
        pbFuncs = Ntk_NodeReadFuncGlo( pNode );
        nValues = Ntk_NodeReadValueNum( pNode );
        if ( pbFuncs ) {
            Ntk_NodeWriteFuncGlo( pNode, NULL );
            for ( i = 0; i < nValues; i++ )
                Cudd_RecursiveDeref( pInfo->ddmg, pbFuncs[i] );
            FREE( pbFuncs );
        }
    }
    
    if ( pInfo->ppNodes ) {
        FREE( pInfo->ppNodes );
    }
    if ( pInfo->ppbCoGlo ) {
        int nCo = Ntk_NetworkReadCoNum( pInfo->network );
        for ( i=0; i<nCo; ++i ) {
            if ( pInfo->ppbCoGlo[i] != NULL )
                Mva_FuncFree( pInfo->ppbCoGlo[i] );
        }
        FREE( pInfo->ppbCoGlo );
    }
    
    Extra_StopManager( pInfo->ddmg );
    //Cudd_Quit( pInfo->ddmg );
    return 0;
}


/*---------------------------------------------------------------------------*/
/* Definition of internal functions                                          */
/*---------------------------------------------------------------------------*/

/**Function********************************************************************
  Synopsis    [Compute a reverse topological order]
  Description [Compute a reverse topological order of all nodes in the
  network. A node always appear BEFORE its fanin nodes. Given the same
  topological level, the nodes with large PI support set is ordered first. A
  new array is returned, which should be freed by the user. (could reimplement
  more efficiently with Ntk_NetworkLevelize() TODO).]
  SideEffects []
  SeeAlso     []
******************************************************************************/
sarray_t *
SimpComputeBfsOrder(
    Ntk_Network_t *network,
    Simp_Info_t   *pInfo)
{
    int i,j, nCo, iSeq;
    Ntk_Node_t *pNode;
    sarray_t    *aLevelThis, *aLevelAll, *aTemp1, *aListFinal;
    st_table   *stFoutCount;
    
    iSeq = 0;
    nCo  = Ntk_NetworkReadCoNum( network );
    stFoutCount  = st_init_table(st_ptrcmp, st_ptrhash);
    aLevelThis   = sarray_alloc( Ntk_Node_t *, nCo );
    aLevelAll    = sarray_alloc( Ntk_Node_t *, nCo );
    aListFinal   = sarray_alloc( Ntk_Node_t *, Ntk_NetworkReadNodeTotalNum( network ) );
    
    /* compute combinational outputs */
    Ntk_NetworkForEachCo( network, pNode ) {
        sarray_insert( Ntk_Node_t *, aLevelThis, iSeq++, pNode );
    }
    aLevelThis->num = nCo;
    
    /* recursively compute the BFS order */
    SimpBfsOrderRecur(pInfo, aLevelThis, aLevelAll, stFoutCount, 0);
    st_free_table(stFoutCount);
    
    /* process aLevelAll */
    for (i=0; i < aLevelAll->num; ++i) {