ntkiresub.c

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

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

  FileName    [ntkiResub.c]

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

  Synopsis    [Performs resubstitution for the network or for one node.]

  Author      [MVSIS Group]
  
  Affiliation [UC Berkeley]

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

  Revision    [$Id: ntkiResub.c,v 1.4 2003/05/27 23:14:34 alanmi Exp $]

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

#include "ntkiInt.h"

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

static Ntk_Node_t *     Ntk_NetworkCompareResubNode( Ntk_Node_t * pNode, Mvr_Relation_t * pMvr, int AcceptType, int nCandsMax, bool fVerbose );
static Mvr_Relation_t * Ntk_NetworkGetResubMvr( Ntk_Node_t * pNode, Mvr_Relation_t * pMvr );
static int              Ntk_NetworkGetResubCands( Ntk_Node_t * pNode, int nCandMax );
static Mvr_Relation_t * Ntk_NetworkDeriveResubMvr( Ntk_Node_t * pNode, Mvr_Relation_t * pMvr, Ntk_Node_t * ppCands[], int nCands );
static void             Ntk_NetworkSortResubCands( Ntk_Network_t * pNet, int nCands, int nCandLimit );
static int              Ntk_NetworkResubCompareNodes( Ntk_Node_t ** ppN1, Ntk_Node_t ** ppN2 );;

static int              Ntk_NetworkMfsCompareNodes( Ntk_Node_t ** ppN1, Ntk_Node_t ** ppN2 );

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

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

  Synopsis    [Performs boolean resubstitution for the network.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Ntk_NetworkResub( Ntk_Network_t * pNet, int nCandsMax, bool fVerbose )
{
    ProgressBar * pProgress;
    Ntk_Node_t * pNode;
    int nNodes, AcceptType;

    if ( nCandsMax < 1 )
    {
        fprintf( Ntk_NetworkReadMvsisOut(pNet), "Ntk_NetworkResub(): The number of candidates to consider is %d.\n", nCandsMax );
        fprintf( Ntk_NetworkReadMvsisOut(pNet), "Resubsitution is not performed.\n" );
        return;
    }
 
    // sweep the buffers/intervers
    Ntk_NetworkSweep( pNet, 1, 1, 0, 0 );

    // start the progress var
    if ( !fVerbose )
        pProgress = Extra_ProgressBarStart( stdout, Ntk_NetworkReadNodeIntNum(pNet) );

    // get the type of the current cost function
    AcceptType = Ntk_NetworkGetAcceptType( pNet );
    // go through the nodes and set the defaults
    nNodes = 0;
    Ntk_NetworkForEachNode( pNet, pNode )
    {
        if ( Ntk_NodeReadFaninNum(pNode) < 2 )
            continue;
        Ntk_NetworkResubNode( pNode, Ntk_NodeGetFuncMvr(pNode), AcceptType, nCandsMax, fVerbose );
        if ( ++nNodes % 5 == 0 && !fVerbose )
            Extra_ProgressBarUpdate( pProgress, nNodes );
    }
    if ( !fVerbose )
        Extra_ProgressBarStop( pProgress );
 
    // sweep the buffers/intervers
    Ntk_NetworkSweep( pNet, 1, 1, 0, 0 );

    if ( !Ntk_NetworkCheck( pNet ) )
        fprintf( Ntk_NetworkReadMvsisOut(pNet), "Ntk_NetworkResub(): Network check has failed.\n" );
}

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

  Synopsis    [Performs boolean resubstitution for one node.]

  Description [Derive the node after resubtitution and, if the node
  is acceptable, makes changes to the network. Returns 1 if resubstitution
  was accepted.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
bool Ntk_NetworkResubNode( Ntk_Node_t * pNode, Mvr_Relation_t * pMvr, int AcceptType, int nCandsMax, bool fVerbose )
{
    Ntk_Node_t * pNodeNew;
    if ( nCandsMax <= 0 )
        return 0;
    // derive the new resubstituted node if it exists
    pNodeNew = Ntk_NetworkCompareResubNode( pNode, pMvr, AcceptType, nCandsMax, fVerbose );
    if ( pNodeNew )
    {
        Ntk_NodeReplace( pNode, pNodeNew );
        return 1;
    }
    return 0;
}

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

  Synopsis    [Derives the node after resubstitution.]

  Description [Compares the derived node with the original node
  and return the derived one only if it gives some improvement
  in terms of the current cost function.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Ntk_Node_t * Ntk_NetworkCompareResubNode( Ntk_Node_t * pNode, Mvr_Relation_t * pMvr, int AcceptType, int nCandsMax, bool fVerbose )
{
    FILE * pOutput;
    Cvr_Cover_t * pCvr, * pCvrMin;
    Ntk_Node_t * pNodeResub;
    Mvr_Relation_t * pMvrResub;
    int nCands;

    // derive the resubstituted node
    pNodeResub = Ntk_NetworkGetResubNode( pNode, pMvr, nCandsMax );
    if ( pNodeResub == NULL )
        return NULL;

    // consider the current Cvr
    pCvr = Ntk_NodeReadFuncCvr( pNode );

    // minimize the resubstituted relation
    pMvrResub = Ntk_NodeReadFuncMvr( pNodeResub );
    pCvrMin = Fnc_FunctionMinimizeCvr( Ntk_NodeReadManMvc(pNode), pMvrResub, 0 ); // espresso
    if ( pCvrMin == NULL )
        pCvrMin = Fnc_FunctionMinimizeCvr( Ntk_NodeReadManMvc(pNode), pMvrResub, 1 ); // isop

    // print statistics about resubstitution
    if ( fVerbose )
    {
        pOutput = Ntk_NodeReadMvsisOut(pNode);
        fprintf( pOutput, "%5s : ", Ntk_NodeGetNamePrintable(pNode) );
        nCands = Ntk_NodeReadFaninNum(pNodeResub) - Ntk_NodeReadFaninNum(pNode);
        if ( pCvr )
            fprintf( pOutput, "CUR  cb= %3d lit= %3d  ", Cvr_CoverReadCubeNum(pCvr), Cvr_CoverReadLitFacNum(pCvr) );
        else
            fprintf( pOutput, "CUR  cb= %3s lit= %3s  ", "-", "-" );

        if ( pCvrMin )
            fprintf( pOutput, "RESUB cand = %5d   cb= %3d lit= %3d   ", nCands, Cvr_CoverReadCubeNum(pCvrMin), Cvr_CoverReadLitFacNum(pCvrMin) );
        else
            fprintf( pOutput, "RESUB cand = %5d   cb= %3s lit= %3s   ", nCands, "-", "-" );
//        fprintf( pOutput, "\n" );
    }

    // consider four situations depending on the presence/absence of Cvr and CvrMin
    if ( pCvr && pCvrMin )
    { // both Cvrs are available - choose the best one

        // compare the minimized relation with the original one
        if ( Ntk_NodeTestAcceptCvr( pCvr, pCvrMin, AcceptType, 0 ) )
        { // accept the minimized, resubstituted node
            if ( fVerbose )
                fprintf( pOutput, "Accept\n" );
            // finalize the resubstituted node
            // set the new Cvr - this will remove pMvrResub
            Ntk_NodeSetFuncCvr( pNodeResub, pCvrMin );
            Ntk_NodeMakeMinimumBase( pNodeResub );
            Ntk_NodeOrderFanins( pNodeResub );
            return pNodeResub;
        }
        else
        { // reject the resubstituted node
            if ( fVerbose )
                fprintf( pOutput, "\n" );
            Cvr_CoverFree( pCvrMin );
            Ntk_NodeDelete( pNodeResub );
            return NULL;
        }
    }
    else if ( pCvr )
    { // only the old Cvr is available - leave it as it is
        if ( fVerbose )
            fprintf( pOutput, "\n" );
        Ntk_NodeDelete( pNodeResub );
        return NULL;
    }
    else if ( pCvrMin )
    { // only the new Cvr is available - set it
        if ( fVerbose )
            fprintf( pOutput, "Accept\n" );
        // finalize the resubstituted node
        // set the new Cvr - this will remove pMvrResub
        Ntk_NodeSetFuncCvr( pNodeResub, pCvrMin );
        Ntk_NodeMakeMinimumBase( pNodeResub );
        Ntk_NodeOrderFanins( pNodeResub );
        return pNodeResub;
    }
    else
    {
        if ( fVerbose )
            fprintf( pOutput, "\n" );
        Ntk_NodeDelete( pNodeResub );
        return NULL;
    }
}

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

  Synopsis    [Derives the node after resubstitution.]

  Description [The derived node is not minimum base and does not have
  the fanins ordered. Returns NULL if there are no resub candidates
  for the original node.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Ntk_Node_t * Ntk_NetworkGetResubNode( Ntk_Node_t * pNode, Mvr_Relation_t * pMvr, int nCandsMax )
{
    Ntk_Node_t * pNodeNew;
    Mvr_Relation_t * pMvrNew;
    Ntk_Node_t ** ppCands;
    int nCands, RetValue, i;

    // get resubustitution candidates for this node
    nCands = Ntk_NetworkGetResubCands( pNode, nCandsMax );
    if ( nCands == 0 )
        return NULL;

    // load the candidates into the array
    ppCands = ALLOC( Ntk_Node_t *, nCands );
    RetValue = Ntk_NetworkCreateArrayFromSpecial( pNode->pNet, ppCands );

    // create the resulting relation
    pMvrNew = Ntk_NetworkDeriveResubMvr( pNode, pMvr, ppCands, nCands );

    // create the resub node
    pNodeNew = Ntk_NodeClone( pNode->pNet, pNode );
    // add the additional fanins
    for ( i = 0; i < nCands; i++ )
        Ntk_NodeAddFanin( pNodeNew, ppCands[i] );
    FREE( ppCands );

    // set the var map and the relation
    Ntk_NodeWriteFuncVm( pNodeNew, Mvr_RelationReadVm(pMvrNew) );
    Ntk_NodeWriteFuncMvr( pNodeNew, pMvrNew );
    return pNodeNew;
}


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

  Synopsis    [Selects resubustitution candidates.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Ntk_NetworkGetResubCands( Ntk_Node_t * pNode, int nCandMax )
{
    Ntk_Node_t * pFanin, * pFanout;
    Ntk_Pin_t * pPin, * pPin2;
    int nCands;

    // mark the TFO cone of the node
    Ntk_NetworkComputeNodeTfo( pNode->pNet, &pNode, 1, 10000, 0, 1 );

    // increment the traversal ID