abcSpeedup.c File Reference

#include "base/abc/abc.h"
#include "base/main/main.h"
#include "map/if/if.h"
#include "aig/aig/aig.h"

Go to the source code of this file.

Functions
static ABC_NAMESPACE_IMPL_START float	Abc_ObjArrival (Abc_Obj_t *pNode)
	DECLARATIONS ///. More...
static float	Abc_ObjRequired (Abc_Obj_t *pNode)
static float	Abc_ObjSlack (Abc_Obj_t *pNode)
static void	Abc_ObjSetArrival (Abc_Obj_t *pNode, float Time)
static void	Abc_ObjSetRequired (Abc_Obj_t *pNode, float Time)
static void	Abc_ObjSetSlack (Abc_Obj_t *pNode, float Time)
void	Abc_NtkDelayTraceSortPins (Abc_Obj_t *pNode, int *pPinPerm, float *pPinDelays)
	FUNCTION DEFINITIONS ///. More...
float	Abc_NtkDelayTraceLut (Abc_Ntk_t *pNtk, int fUseLutLib)
void	Abc_NtkDelayTracePrint (Abc_Ntk_t *pNtk, int fUseLutLib, int fVerbose)
int	Abc_AigCheckTfi_rec (Abc_Obj_t *pNode, Abc_Obj_t *pOld)
int	Abc_AigCheckTfi (Abc_Obj_t *pNew, Abc_Obj_t *pOld)
int	Abc_NtkSpeedupNode_rec (Abc_Obj_t *pNode, Vec_Ptr_t *vNodes)
void	Abc_NtkSpeedupNode (Abc_Ntk_t *pNtk, Abc_Ntk_t *pAig, Abc_Obj_t *pNode, Vec_Ptr_t *vLeaves, Vec_Ptr_t *vTimes)
unsigned	Abc_NtkDelayTraceTCEdges (Abc_Ntk_t *pNtk, Abc_Obj_t *pNode, float tDelta, int fUseLutLib)
Abc_Ntk_t *	Abc_NtkSpeedup (Abc_Ntk_t *pNtk, int fUseLutLib, int Percentage, int Degree, int fVerbose, int fVeryVerbose)
Vec_Int_t *	Abc_NtkPowerEstimate (Abc_Ntk_t *pNtk, int fProbOne)
void	Abc_NtkPowerPrint (Abc_Ntk_t *pNtk, Vec_Int_t *vProbs)
unsigned	Abc_NtkPowerCriticalEdges (Abc_Ntk_t *pNtk, Abc_Obj_t *pNode, float Limit, Vec_Int_t *vProbs)
Abc_Ntk_t *	Abc_NtkPowerdown (Abc_Ntk_t *pNtk, int fUseLutLib, int Percentage, int Degree, int fVerbose, int fVeryVerbose)

Function Documentation

int Abc_AigCheckTfi	(	Abc_Obj_t *	pNew,
		Abc_Obj_t *	pOld
	)

Function*************************************************************

Synopsis [Returns 1 if pOld is in the TFI of pNew.]

Description []

SideEffects []

SeeAlso []

Definition at line 330 of file abcSpeedup.c.

{
    assert( !Abc_ObjIsComplement(pNew) );
    assert( !Abc_ObjIsComplement(pOld) );
    Abc_NtkIncrementTravId( pNew->pNtk );
    return Abc_AigCheckTfi_rec( pNew, pOld );
}

int Abc_AigCheckTfi_rec	(	Abc_Obj_t *	pNode,
		Abc_Obj_t *	pOld
	)

Function*************************************************************

Synopsis [Returns 1 if pOld is in the TFI of pNew.]

Description []

SideEffects []

SeeAlso []

Definition at line 297 of file abcSpeedup.c.

{
    // check the trivial cases
    if ( pNode == NULL )
        return 0;
    if ( Abc_ObjIsCi(pNode) )
        return 0;
    if ( pNode == pOld )
        return 1;
    // skip the visited node
    if ( Abc_NodeIsTravIdCurrent( pNode ) )
        return 0;
    Abc_NodeSetTravIdCurrent( pNode );
    // check the children
    if ( Abc_AigCheckTfi_rec( Abc_ObjFanin0(pNode), pOld ) )
        return 1;
    if ( Abc_AigCheckTfi_rec( Abc_ObjFanin1(pNode), pOld ) )
        return 1;
    // check equivalent nodes
    return Abc_AigCheckTfi_rec( (Abc_Obj_t *)pNode->pData, pOld );
}

float Abc_NtkDelayTraceLut	(	Abc_Ntk_t *	pNtk,
		int	fUseLutLib
	)

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 100 of file abcSpeedup.c.

{
    int fUseSorting = 1;
    int pPinPerm[32];
    float pPinDelays[32];
    If_LibLut_t * pLutLib;
    Abc_Obj_t * pNode, * pFanin;
    Vec_Ptr_t * vNodes;
    float tArrival, tRequired, tSlack, * pDelays;
    int i, k;

    assert( Abc_NtkIsLogic(pNtk) );
    // get the library
    pLutLib = fUseLutLib?  (If_LibLut_t *)Abc_FrameReadLibLut() : NULL;
    if ( pLutLib && pLutLib->LutMax < Abc_NtkGetFaninMax(pNtk) )
    {
        printf( "The max LUT size (%d) is less than the max fanin count (%d).\n", 
            pLutLib->LutMax, Abc_NtkGetFaninMax(pNtk) );
        return -ABC_INFINITY;
    }

    // initialize the arrival times
    ABC_FREE( pNtk->pLutTimes );
    pNtk->pLutTimes = ABC_ALLOC( float, 3 * Abc_NtkObjNumMax(pNtk) );
    for ( i = 0; i < Abc_NtkObjNumMax(pNtk); i++ )
    {
        pNtk->pLutTimes[3*i+0] = pNtk->pLutTimes[3*i+2] = 0;
        pNtk->pLutTimes[3*i+1] = ABC_INFINITY;
    }

    // propagate arrival times
    vNodes = Abc_NtkDfs( pNtk, 1 );
    Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pNode, i )
    {
        tArrival = -ABC_INFINITY;
        if ( pLutLib == NULL )
        {
            Abc_ObjForEachFanin( pNode, pFanin, k )
                if ( tArrival < Abc_ObjArrival(pFanin) + 1.0 )
                    tArrival = Abc_ObjArrival(pFanin) + 1.0;
        }
        else if ( !pLutLib->fVarPinDelays )
        {
            pDelays = pLutLib->pLutDelays[Abc_ObjFaninNum(pNode)];
            Abc_ObjForEachFanin( pNode, pFanin, k )
                if ( tArrival < Abc_ObjArrival(pFanin) + pDelays[0] )
                    tArrival = Abc_ObjArrival(pFanin) + pDelays[0];
        }
        else
        {
            pDelays = pLutLib->pLutDelays[Abc_ObjFaninNum(pNode)];
            if ( fUseSorting )
            {
                Abc_NtkDelayTraceSortPins( pNode, pPinPerm, pPinDelays );
                Abc_ObjForEachFanin( pNode, pFanin, k ) 
                    if ( tArrival < Abc_ObjArrival(Abc_ObjFanin(pNode,pPinPerm[k])) + pDelays[k] )
                        tArrival = Abc_ObjArrival(Abc_ObjFanin(pNode,pPinPerm[k])) + pDelays[k];
            }
            else
            {
                Abc_ObjForEachFanin( pNode, pFanin, k )
                    if ( tArrival < Abc_ObjArrival(pFanin) + pDelays[k] )
                        tArrival = Abc_ObjArrival(pFanin) + pDelays[k];
            }
        }
        if ( Abc_ObjFaninNum(pNode) == 0 )
            tArrival = 0.0;
        Abc_ObjSetArrival( pNode, tArrival );
    }
    Vec_PtrFree( vNodes );

    // get the latest arrival times
    tArrival = -ABC_INFINITY;
    Abc_NtkForEachCo( pNtk, pNode, i )
        if ( tArrival < Abc_ObjArrival(Abc_ObjFanin0(pNode)) )
            tArrival = Abc_ObjArrival(Abc_ObjFanin0(pNode));

    // initialize the required times
    Abc_NtkForEachCo( pNtk, pNode, i )
        if ( Abc_ObjRequired(Abc_ObjFanin0(pNode)) > tArrival )
            Abc_ObjSetRequired( Abc_ObjFanin0(pNode), tArrival );

    // propagate the required times
    vNodes = Abc_NtkDfsReverse( pNtk );
    Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pNode, i )
    {
        if ( pLutLib == NULL )
        {
            tRequired = Abc_ObjRequired(pNode) - (float)1.0;
            Abc_ObjForEachFanin( pNode, pFanin, k )
                if ( Abc_ObjRequired(pFanin) > tRequired )
                    Abc_ObjSetRequired( pFanin, tRequired );
        }
        else if ( !pLutLib->fVarPinDelays )
        {
            pDelays = pLutLib->pLutDelays[Abc_ObjFaninNum(pNode)];
            tRequired = Abc_ObjRequired(pNode) - pDelays[0];
            Abc_ObjForEachFanin( pNode, pFanin, k )
                if ( Abc_ObjRequired(pFanin) > tRequired )
                    Abc_ObjSetRequired( pFanin, tRequired );
        }
        else 
        {
            pDelays = pLutLib->pLutDelays[Abc_ObjFaninNum(pNode)];
            if ( fUseSorting )
            {
                Abc_NtkDelayTraceSortPins( pNode, pPinPerm, pPinDelays );
                Abc_ObjForEachFanin( pNode, pFanin, k )
                {
                    tRequired = Abc_ObjRequired(pNode) - pDelays[k];
                    if ( Abc_ObjRequired(Abc_ObjFanin(pNode,pPinPerm[k])) > tRequired )
                        Abc_ObjSetRequired( Abc_ObjFanin(pNode,pPinPerm[k]), tRequired );
                }
            }
            else
            {
                Abc_ObjForEachFanin( pNode, pFanin, k )
                {
                    tRequired = Abc_ObjRequired(pNode) - pDelays[k];
                    if ( Abc_ObjRequired(pFanin) > tRequired )
                        Abc_ObjSetRequired( pFanin, tRequired );
                }
            }
        }
        // set slack for this object
        tSlack = Abc_ObjRequired(pNode) - Abc_ObjArrival(pNode);
        assert( tSlack + 0.001 > 0.0 );
        Abc_ObjSetSlack( pNode, tSlack < 0.0 ? 0.0 : tSlack );
    }
    Vec_PtrFree( vNodes );
    return tArrival;
}

void Abc_NtkDelayTracePrint	(	Abc_Ntk_t *	pNtk,
		int	fUseLutLib,
		int	fVerbose
	)

Function*************************************************************

Synopsis [Delay tracing of the LUT mapped network.]

Description []

SideEffects []

SeeAlso []

Definition at line 244 of file abcSpeedup.c.

{
    Abc_Obj_t * pNode;
    If_LibLut_t * pLutLib;
    int i, Nodes, * pCounters;
    float tArrival, tDelta, nSteps, Num;
    // get the library
    pLutLib = fUseLutLib?  (If_LibLut_t *)Abc_FrameReadLibLut() : NULL;
    if ( pLutLib && pLutLib->LutMax < Abc_NtkGetFaninMax(pNtk) )
    {
        printf( "The max LUT size (%d) is less than the max fanin count (%d).\n", 
            pLutLib->LutMax, Abc_NtkGetFaninMax(pNtk) );
        return;
    }
    // decide how many steps
    nSteps = fUseLutLib ? 20 : Abc_NtkLevel(pNtk);
    pCounters = ABC_ALLOC( int, nSteps + 1 );
    memset( pCounters, 0, sizeof(int)*(nSteps + 1) );
    // perform delay trace
    tArrival = Abc_NtkDelayTraceLut( pNtk, fUseLutLib );
    tDelta = tArrival / nSteps;
    // count how many nodes have slack in the corresponding intervals
    Abc_NtkForEachNode( pNtk, pNode, i )
    {
        if ( Abc_ObjFaninNum(pNode) == 0 )
            continue;
        Num = Abc_ObjSlack(pNode) / tDelta;
        assert( Num >=0 && Num <= nSteps );
        pCounters[(int)Num]++;
    }
    // print the results
    printf( "Max delay = %6.2f. Delay trace using %s model:\n", tArrival, fUseLutLib? "LUT library" : "unit-delay" );
    Nodes = 0;
    for ( i = 0; i < nSteps; i++ )
    {
        Nodes += pCounters[i];
        printf( "%3d %s : %5d  (%6.2f %%)\n", fUseLutLib? 5*(i+1) : i+1, 
            fUseLutLib? "%":"lev", Nodes, 100.0*Nodes/Abc_NtkNodeNum(pNtk) );
    }
    ABC_FREE( pCounters );
}

void Abc_NtkDelayTraceSortPins	(	Abc_Obj_t *	pNode,
		int *	pPinPerm,
		float *	pPinDelays
	)

FUNCTION DEFINITIONS ///.

Function*************************************************************

Synopsis [Sorts the pins in the decreasing order of delays.]

Description []

SideEffects []

SeeAlso []

Definition at line 56 of file abcSpeedup.c.

{
    Abc_Obj_t * pFanin;
    int i, j, best_i, temp;
    // start the trivial permutation and collect pin delays
    Abc_ObjForEachFanin( pNode, pFanin, i )
    {
        pPinPerm[i] = i;
        pPinDelays[i] = Abc_ObjArrival(pFanin);
    }
    // selection sort the pins in the decreasible order of delays
    // this order will match the increasing order of LUT input pins
    for ( i = 0; i < Abc_ObjFaninNum(pNode)-1; i++ )
    {
        best_i = i;
        for ( j = i+1; j < Abc_ObjFaninNum(pNode); j++ )
            if ( pPinDelays[pPinPerm[j]] > pPinDelays[pPinPerm[best_i]] )
                best_i = j;
        if ( best_i == i )
            continue;
        temp = pPinPerm[i]; 
        pPinPerm[i] = pPinPerm[best_i]; 
        pPinPerm[best_i] = temp;
    }
    // verify
    assert( Abc_ObjFaninNum(pNode) == 0 || pPinPerm[0] < Abc_ObjFaninNum(pNode) );
    for ( i = 1; i < Abc_ObjFaninNum(pNode); i++ )
    {
        assert( pPinPerm[i] < Abc_ObjFaninNum(pNode) );
        assert( pPinDelays[pPinPerm[i-1]] >= pPinDelays[pPinPerm[i]] );
    }
}

unsigned Abc_NtkDelayTraceTCEdges	(	Abc_Ntk_t *	pNtk,
		Abc_Obj_t *	pNode,
		float	tDelta,
		int	fUseLutLib
	)

Function*************************************************************

Synopsis [Determines timing-critical edges of the node.]

Description []

SideEffects []

SeeAlso []

Definition at line 466 of file abcSpeedup.c.

{
    int pPinPerm[32];
    float pPinDelays[32];
    If_LibLut_t * pLutLib;
    Abc_Obj_t * pFanin;
    unsigned uResult = 0;
    float tRequired, * pDelays;
    int k;
    pLutLib = fUseLutLib?  (If_LibLut_t *)Abc_FrameReadLibLut() : NULL;
    tRequired = Abc_ObjRequired(pNode);
    if ( pLutLib == NULL )
    {
        Abc_ObjForEachFanin( pNode, pFanin, k )
            if ( tRequired < Abc_ObjArrival(pFanin) + 1.0 + tDelta )
                uResult |= (1 << k);
    }
    else if ( !pLutLib->fVarPinDelays )
    {
        pDelays = pLutLib->pLutDelays[Abc_ObjFaninNum(pNode)];
        Abc_ObjForEachFanin( pNode, pFanin, k )
            if ( tRequired < Abc_ObjArrival(pFanin) + pDelays[0] + tDelta )
                uResult |= (1 << k);
    }
    else
    {
        pDelays = pLutLib->pLutDelays[Abc_ObjFaninNum(pNode)];
        Abc_NtkDelayTraceSortPins( pNode, pPinPerm, pPinDelays );
        Abc_ObjForEachFanin( pNode, pFanin, k )
            if ( tRequired < Abc_ObjArrival(Abc_ObjFanin(pNode,pPinPerm[k])) + pDelays[k] + tDelta )
                uResult |= (1 << pPinPerm[k]);
    }
    return uResult;
}

unsigned Abc_NtkPowerCriticalEdges	(	Abc_Ntk_t *	pNtk,
		Abc_Obj_t *	pNode,
		float	Limit,
		Vec_Int_t *	vProbs
	)

Function*************************************************************

Synopsis [Determines timing-critical edges of the node.]

Description []

SideEffects []

SeeAlso []

Definition at line 788 of file abcSpeedup.c.

{
    Abc_Obj_t * pFanin;
    float * pProb = (float *)vProbs->pArray;
    unsigned uResult = 0;
    int k;
    Abc_ObjForEachFanin( pNode, pFanin, k )
        if ( pProb[pFanin->Id] >= Limit )
            uResult |= (1 << k);
    return uResult;
}

Abc_Ntk_t* Abc_NtkPowerdown	(	Abc_Ntk_t *	pNtk,
		int	fUseLutLib,
		int	Percentage,
		int	Degree,
		int	fVerbose,
		int	fVeryVerbose
	)

Function*************************************************************

Synopsis [Adds choices to speed up the network by the given percentage.]

Description []

SideEffects []

SeeAlso []

Definition at line 811 of file abcSpeedup.c.

{
    Abc_Ntk_t * pNtkNew;
    Vec_Int_t * vProbs;
    Vec_Ptr_t * vTimeCries, * vTimeFanins;
    Abc_Obj_t * pNode, * pFanin, * pFanin2;
    float * pProb, Limit;
    int i, k, k2, Counter, CounterRes, nTimeCris;
    unsigned * puPCEdges;
    // compute the limit
    Limit = 0.5 - (1.0 * Percentage / 100);
    // perform computation of switching probability
    vProbs = Abc_NtkPowerEstimate( pNtk, 0 );
    pProb = (float *)vProbs->pArray;
    // compute percentage of wires of each type
    if ( fVerbose )
        Abc_NtkPowerPrint( pNtk, vProbs );
    // mark the power critical nodes and edges
    puPCEdges = ABC_ALLOC( unsigned, Abc_NtkObjNumMax(pNtk) );
    memset( puPCEdges, 0, sizeof(unsigned) * Abc_NtkObjNumMax(pNtk) );
    Abc_NtkForEachNode( pNtk, pNode, i )
    {
        if ( pProb[pNode->Id] < Limit )
            continue;
        puPCEdges[pNode->Id] = Abc_NtkPowerCriticalEdges( pNtk, pNode, Limit, vProbs );
    }
/*
    if ( fVerbose )
    {
        Counter = CounterRes = 0;
        Abc_NtkForEachNode( pNtk, pNode, i )
        {
            Counter += Abc_ObjFaninNum(pNode);
            CounterRes += Extra_WordCountOnes( puPCEdges[pNode->Id] );
        }
        printf( "Edges: Total = %7d. Critical = %7d. Ratio = %4.2f\n", 
            Counter, CounterRes, 1.0*CounterRes/Counter );
    }
*/
    // start the resulting network
    pNtkNew = Abc_NtkStrash( pNtk, 0, 1, 0 );

    // collect nodes to be used for resynthesis
    Counter = CounterRes = 0;
    vTimeCries = Vec_PtrAlloc( 16 );
    vTimeFanins = Vec_PtrAlloc( 16 );
    Abc_NtkForEachNode( pNtk, pNode, i )
    {
//        if ( pProb[pNode->Id] < Limit )
//            continue;
        // count the number of non-PI power-critical nodes
        nTimeCris = 0;
        Abc_ObjForEachFanin( pNode, pFanin, k )
            if ( !Abc_ObjIsCi(pFanin) && (puPCEdges[pNode->Id] & (1<<k)) )
                nTimeCris++;
        if ( !fVeryVerbose && nTimeCris == 0 )
            continue;
        Counter++;
        // count the total number of power-critical second-generation nodes
        Vec_PtrClear( vTimeCries );
        if ( nTimeCris )
        {
            Abc_ObjForEachFanin( pNode, pFanin, k )
                if ( !Abc_ObjIsCi(pFanin) && (puPCEdges[pNode->Id] & (1<<k)) )
                    Abc_ObjForEachFanin( pFanin, pFanin2, k2 )
                        if ( puPCEdges[pFanin->Id] & (1<<k2) )
                            Vec_PtrPushUnique( vTimeCries, pFanin2 );
        }
//        if ( !fVeryVerbose && (Vec_PtrSize(vTimeCries) == 0 || Vec_PtrSize(vTimeCries) > Degree) )
        if ( (Vec_PtrSize(vTimeCries) == 0 || Vec_PtrSize(vTimeCries) > Degree) )
            continue;
        CounterRes++;
        // collect second generation nodes
        Vec_PtrClear( vTimeFanins );
        Abc_ObjForEachFanin( pNode, pFanin, k )
        {
            if ( Abc_ObjIsCi(pFanin) )
                Vec_PtrPushUnique( vTimeFanins, pFanin );
            else
                Abc_ObjForEachFanin( pFanin, pFanin2, k2 )
                    Vec_PtrPushUnique( vTimeFanins, pFanin2 );                    
        }
        // print the results
        if ( fVeryVerbose )
        {
        printf( "%5d Node %5d : %d %2d %2d  ", Counter, pNode->Id, 
            nTimeCris, Vec_PtrSize(vTimeCries), Vec_PtrSize(vTimeFanins) );
        Abc_ObjForEachFanin( pNode, pFanin, k )
            printf( "%d(%.2f)%s ", pFanin->Id, pProb[pFanin->Id], (puPCEdges[pNode->Id] & (1<<k))? "*":"" );
        printf( "\n" );
        }
        // add the node to choices
        if ( Vec_PtrSize(vTimeCries) == 0 || Vec_PtrSize(vTimeCries) > Degree )
            continue;
        // order the fanins in the increasing order of criticalily
        if ( Vec_PtrSize(vTimeCries) > 1 )
        {
            pFanin = (Abc_Obj_t *)Vec_PtrEntry( vTimeCries, 0 );
            pFanin2 = (Abc_Obj_t *)Vec_PtrEntry( vTimeCries, 1 );
//            if ( Abc_ObjSlack(pFanin) < Abc_ObjSlack(pFanin2) )
            if ( pProb[pFanin->Id] > pProb[pFanin2->Id] )
            {
                Vec_PtrWriteEntry( vTimeCries, 0, pFanin2 );
                Vec_PtrWriteEntry( vTimeCries, 1, pFanin );
            }
        }
        if ( Vec_PtrSize(vTimeCries) > 2 )
        {
            pFanin = (Abc_Obj_t *)Vec_PtrEntry( vTimeCries, 1 );
            pFanin2 = (Abc_Obj_t *)Vec_PtrEntry( vTimeCries, 2 );
//            if ( Abc_ObjSlack(pFanin) < Abc_ObjSlack(pFanin2) )
            if ( pProb[pFanin->Id] > pProb[pFanin2->Id] )
            {
                Vec_PtrWriteEntry( vTimeCries, 1, pFanin2 );
                Vec_PtrWriteEntry( vTimeCries, 2, pFanin );
            }
            pFanin = (Abc_Obj_t *)Vec_PtrEntry( vTimeCries, 0 );
            pFanin2 = (Abc_Obj_t *)Vec_PtrEntry( vTimeCries, 1 );
//            if ( Abc_ObjSlack(pFanin) < Abc_ObjSlack(pFanin2) )
            if ( pProb[pFanin->Id] > pProb[pFanin2->Id] )
            {
                Vec_PtrWriteEntry( vTimeCries, 0, pFanin2 );
                Vec_PtrWriteEntry( vTimeCries, 1, pFanin );
            }
        }
        // add choice
        Abc_NtkSpeedupNode( pNtk, pNtkNew, pNode, vTimeFanins, vTimeCries );
    }
    Vec_PtrFree( vTimeCries );
    Vec_PtrFree( vTimeFanins );
    ABC_FREE( puPCEdges );
    if ( fVerbose )
        printf( "Nodes: Total = %7d. Power-critical = %7d. Workable = %7d. Ratio = %4.2f\n", 
            Abc_NtkNodeNum(pNtk), Counter, CounterRes, 1.0*CounterRes/Counter ); 

    // remove invalid choice nodes
    Abc_AigForEachAnd( pNtkNew, pNode, i )
        if ( pNode->pData )
        {
            if ( Abc_ObjFanoutNum((Abc_Obj_t *)pNode->pData) > 0 )
                pNode->pData = NULL;
        }

    // return the result
    Vec_IntFree( vProbs );
    return pNtkNew;
}

Vec_Int_t* Abc_NtkPowerEstimate	(	Abc_Ntk_t *	pNtk,
		int	fProbOne
	)

Function*************************************************************

Synopsis [Marks nodes for power-optimization.]

Description []

SideEffects []

SeeAlso []

Definition at line 669 of file abcSpeedup.c.

{
    extern Aig_Man_t * Abc_NtkToDar( Abc_Ntk_t * pNtk, int fExors, int fRegisters );
    extern Vec_Int_t * Saig_ManComputeSwitchProbs( Aig_Man_t * p, int nFrames, int nPref, int fProbOne );
    Vec_Int_t * vProbs;
    Vec_Int_t * vSwitching;
    float * pProbability;
    float * pSwitching;
    Abc_Ntk_t * pNtkStr;
    Aig_Man_t * pAig;
    Aig_Obj_t * pObjAig;
    Abc_Obj_t * pObjAbc, * pObjAbc2;
    int i;
    // start the resulting array
    vProbs = Vec_IntStart( Abc_NtkObjNumMax(pNtk) );
    pProbability = (float *)vProbs->pArray;
    // strash the network
    pNtkStr = Abc_NtkStrash( pNtk, 0, 1, 0 );
    Abc_NtkForEachObj( pNtk, pObjAbc, i )
        if ( Abc_ObjRegular((Abc_Obj_t *)pObjAbc->pTemp)->Type == ABC_FUNC_NONE )
            pObjAbc->pTemp = NULL;
    // map network into an AIG
    pAig = Abc_NtkToDar( pNtkStr, 0, (int)(Abc_NtkLatchNum(pNtk) > 0) );
    vSwitching = Saig_ManComputeSwitchProbs( pAig, 48, 16, fProbOne );
    pSwitching = (float *)vSwitching->pArray;
    Abc_NtkForEachObj( pNtk, pObjAbc, i )
    {
        if ( (pObjAbc2 = Abc_ObjRegular((Abc_Obj_t *)pObjAbc->pTemp)) && (pObjAig = Aig_Regular((Aig_Obj_t *)pObjAbc2->pTemp)) )
            pProbability[pObjAbc->Id] = pSwitching[pObjAig->Id];
    }
    Vec_IntFree( vSwitching );
    Aig_ManStop( pAig );
    Abc_NtkDelete( pNtkStr );
    return vProbs;
}

void Abc_NtkPowerPrint	(	Abc_Ntk_t *	pNtk,
		Vec_Int_t *	vProbs
	)

Function*************************************************************

Synopsis [Marks nodes for power-optimization.]

Description []

SideEffects []

SeeAlso []

Definition at line 716 of file abcSpeedup.c.

{
    Abc_Obj_t * pObj;
    float * pProb, TotalProb = 0.0, ProbThis, Probs[6] = {0.0};
    int i, nNodes = 0, nEdges = 0, Counter[6] = {0};
    pProb = (float *)vProbs->pArray;
    assert( Vec_IntSize(vProbs) >= Abc_NtkObjNumMax(pNtk) );
    Abc_NtkForEachObj( pNtk, pObj, i )
    {
        if ( !Abc_ObjIsNode(pObj) && !Abc_ObjIsPi(pObj) )
            continue;
        nNodes++;
        nEdges += Abc_ObjFanoutNum(pObj);
        ProbThis = pProb[i] * Abc_ObjFanoutNum(pObj);
        TotalProb += ProbThis;
        assert( pProb[i] >= 0.0 && pProb[i] <= 1.0 );
        if ( pProb[i] >= 0.5 )
        {
            Counter[5]++;
            Probs[5] += ProbThis;
        }
        else if ( pProb[i] >= 0.4 )
        {
            Counter[4]++;
            Probs[4] += ProbThis;
        }
        else if ( pProb[i] >= 0.3 )
        {
            Counter[3]++;
            Probs[3] += ProbThis;
        }
        else if ( pProb[i] >= 0.2 )
        {
            Counter[2]++;
            Probs[2] += ProbThis;
        }
        else if ( pProb[i] >= 0.1 )
        {
            Counter[1]++;
            Probs[1] += ProbThis;
        }
        else 
        {
            Counter[0]++;
            Probs[0] += ProbThis;
        }
    }
    printf( "Node  distribution: " );
    for ( i = 0; i < 6; i++ )
        printf( "n%d%d = %6.2f%%  ", i, i+1, 100.0 * Counter[i]/nNodes );
    printf( "\n" );
    printf( "Power distribution: " );
    for ( i = 0; i < 6; i++ )
        printf( "p%d%d = %6.2f%%  ", i, i+1, 100.0 * Probs[i]/TotalProb );
    printf( "\n" );
    printf( "Total probs = %7.2f. ", TotalProb );
    printf( "Total edges = %d. ", nEdges );
    printf( "Average = %7.2f. ", TotalProb / nEdges );
    printf( "\n" );
}

Abc_Ntk_t* Abc_NtkSpeedup	(	Abc_Ntk_t *	pNtk,
		int	fUseLutLib,
		int	Percentage,
		int	Degree,
		int	fVerbose,
		int	fVeryVerbose
	)

Function*************************************************************

Synopsis [Adds choices to speed up the network by the given percentage.]

Description []

SideEffects []

SeeAlso []

Definition at line 512 of file abcSpeedup.c.

{
    Abc_Ntk_t * pNtkNew;
    Vec_Ptr_t * vTimeCries, * vTimeFanins;
    Abc_Obj_t * pNode, * pFanin, * pFanin2;
    float tDelta, tArrival;
    int i, k, k2, Counter, CounterRes, nTimeCris;
    unsigned * puTCEdges;
    // perform delay trace
    tArrival = Abc_NtkDelayTraceLut( pNtk, fUseLutLib );
    tDelta = fUseLutLib ? tArrival*Percentage/100.0 : 1.0;
    if ( fVerbose )
    {
        printf( "Max delay = %.2f. Delta = %.2f. ", tArrival, tDelta );
        printf( "Using %s model. ", fUseLutLib? "LUT library" : "unit-delay" );
        if ( fUseLutLib )
            printf( "Percentage = %d. ", Percentage );
        printf( "\n" );
    }
    // mark the timing critical nodes and edges
    puTCEdges = ABC_ALLOC( unsigned, Abc_NtkObjNumMax(pNtk) );
    memset( puTCEdges, 0, sizeof(unsigned) * Abc_NtkObjNumMax(pNtk) );
    Abc_NtkForEachNode( pNtk, pNode, i )
    {
        if ( Abc_ObjSlack(pNode) >= tDelta )
            continue;
        puTCEdges[pNode->Id] = Abc_NtkDelayTraceTCEdges( pNtk, pNode, tDelta, fUseLutLib );
    }
    if ( fVerbose )
    {
        Counter = CounterRes = 0;
        Abc_NtkForEachNode( pNtk, pNode, i )
        {
            Abc_ObjForEachFanin( pNode, pFanin, k )
                if ( !Abc_ObjIsCi(pFanin) && Abc_ObjSlack(pFanin) < tDelta )
                    Counter++;
            CounterRes += Extra_WordCountOnes( puTCEdges[pNode->Id] );
        }
        printf( "Edges: Total = %7d. 0-slack = %7d. Critical = %7d. Ratio = %4.2f\n", 
            Abc_NtkGetTotalFanins(pNtk), Counter, CounterRes, 1.0*CounterRes/Counter );
    }
    // start the resulting network
    pNtkNew = Abc_NtkStrash( pNtk, 0, 1, 0 );

    // collect nodes to be used for resynthesis
    Counter = CounterRes = 0;
    vTimeCries = Vec_PtrAlloc( 16 );
    vTimeFanins = Vec_PtrAlloc( 16 );
    Abc_NtkForEachNode( pNtk, pNode, i )
    {
        if ( Abc_ObjSlack(pNode) >= tDelta )
            continue;
        // count the number of non-PI timing-critical nodes
        nTimeCris = 0;
        Abc_ObjForEachFanin( pNode, pFanin, k )
            if ( !Abc_ObjIsCi(pFanin) && (puTCEdges[pNode->Id] & (1<<k)) )
                nTimeCris++;
        if ( !fVeryVerbose && nTimeCris == 0 )
            continue;
        Counter++;
        // count the total number of timing critical second-generation nodes
        Vec_PtrClear( vTimeCries );
        if ( nTimeCris )
        {
            Abc_ObjForEachFanin( pNode, pFanin, k )
                if ( !Abc_ObjIsCi(pFanin) && (puTCEdges[pNode->Id] & (1<<k)) )
                    Abc_ObjForEachFanin( pFanin, pFanin2, k2 )
                        if ( puTCEdges[pFanin->Id] & (1<<k2) )
                            Vec_PtrPushUnique( vTimeCries, pFanin2 );
        }
//        if ( !fVeryVerbose && (Vec_PtrSize(vTimeCries) == 0 || Vec_PtrSize(vTimeCries) > Degree) )
        if ( (Vec_PtrSize(vTimeCries) == 0 || Vec_PtrSize(vTimeCries) > Degree) )
            continue;
        CounterRes++;
        // collect second generation nodes
        Vec_PtrClear( vTimeFanins );
        Abc_ObjForEachFanin( pNode, pFanin, k )
        {
            if ( Abc_ObjIsCi(pFanin) )
                Vec_PtrPushUnique( vTimeFanins, pFanin );
            else
                Abc_ObjForEachFanin( pFanin, pFanin2, k2 )
                    Vec_PtrPushUnique( vTimeFanins, pFanin2 );                    
        }
        // print the results
        if ( fVeryVerbose )
        {
        printf( "%5d Node %5d : %d %2d %2d  ", Counter, pNode->Id, 
            nTimeCris, Vec_PtrSize(vTimeCries), Vec_PtrSize(vTimeFanins) );
        Abc_ObjForEachFanin( pNode, pFanin, k )
            printf( "%d(%.2f)%s ", pFanin->Id, Abc_ObjSlack(pFanin), (puTCEdges[pNode->Id] & (1<<k))? "*":"" );
        printf( "\n" );
        }
        // add the node to choices
        if ( Vec_PtrSize(vTimeCries) == 0 || Vec_PtrSize(vTimeCries) > Degree )
            continue;
        // order the fanins in the increasing order of criticalily
        if ( Vec_PtrSize(vTimeCries) > 1 )
        {
            pFanin = (Abc_Obj_t *)Vec_PtrEntry( vTimeCries, 0 );
            pFanin2 = (Abc_Obj_t *)Vec_PtrEntry( vTimeCries, 1 );
            if ( Abc_ObjSlack(pFanin) < Abc_ObjSlack(pFanin2) )
            {
                Vec_PtrWriteEntry( vTimeCries, 0, pFanin2 );
                Vec_PtrWriteEntry( vTimeCries, 1, pFanin );
            }
        }
        if ( Vec_PtrSize(vTimeCries) > 2 )
        {
            pFanin = (Abc_Obj_t *)Vec_PtrEntry( vTimeCries, 1 );
            pFanin2 = (Abc_Obj_t *)Vec_PtrEntry( vTimeCries, 2 );
            if ( Abc_ObjSlack(pFanin) < Abc_ObjSlack(pFanin2) )
            {
                Vec_PtrWriteEntry( vTimeCries, 1, pFanin2 );
                Vec_PtrWriteEntry( vTimeCries, 2, pFanin );
            }
            pFanin = (Abc_Obj_t *)Vec_PtrEntry( vTimeCries, 0 );
            pFanin2 = (Abc_Obj_t *)Vec_PtrEntry( vTimeCries, 1 );
            if ( Abc_ObjSlack(pFanin) < Abc_ObjSlack(pFanin2) )
            {
                Vec_PtrWriteEntry( vTimeCries, 0, pFanin2 );
                Vec_PtrWriteEntry( vTimeCries, 1, pFanin );
            }
        }
        // add choice
        Abc_NtkSpeedupNode( pNtk, pNtkNew, pNode, vTimeFanins, vTimeCries );
    }
    Vec_PtrFree( vTimeCries );
    Vec_PtrFree( vTimeFanins );
    ABC_FREE( puTCEdges );
    if ( fVerbose )
        printf( "Nodes: Total = %7d. 0-slack = %7d. Workable = %7d. Ratio = %4.2f\n", 
            Abc_NtkNodeNum(pNtk), Counter, CounterRes, 1.0*CounterRes/Counter ); 

    // remove invalid choice nodes
    Abc_AigForEachAnd( pNtkNew, pNode, i )
        if ( pNode->pData )
        {
            if ( Abc_ObjFanoutNum((Abc_Obj_t *)pNode->pData) > 0 )
                pNode->pData = NULL;
        }

    // return the result
    return pNtkNew;
}

void Abc_NtkSpeedupNode	(	Abc_Ntk_t *	pNtk,
		Abc_Ntk_t *	pAig,
		Abc_Obj_t *	pNode,
		Vec_Ptr_t *	vLeaves,
		Vec_Ptr_t *	vTimes
	)

Function*************************************************************

Synopsis [Adds strashed nodes for one node.]

Description []

SideEffects []

SeeAlso []

Definition at line 376 of file abcSpeedup.c.

{
    Vec_Ptr_t * vNodes;
    Abc_Obj_t * pObj, * pObj2, * pAnd;
    Abc_Obj_t * ppCofs[32];
    int nCofs, i, k, nSkip;

    // quit of regulars are the same
    Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pObj, i )
    Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pObj2, k )
        if ( i != k && Abc_ObjRegular(pObj->pCopy) == Abc_ObjRegular(pObj2->pCopy) )
        {
//            printf( "Identical after structural hashing!!!\n" );
            return;
        }

    // collect the AIG nodes
    vNodes = Vec_PtrAlloc( 100 );
    Abc_NtkIncrementTravId( pAig );
    Abc_NodeSetTravIdCurrent( Abc_AigConst1(pAig) );
    Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pObj, i )
    {
        pAnd = pObj->pCopy;
        Abc_NodeSetTravIdCurrent( Abc_ObjRegular(pAnd) );
    }
    // traverse from the root node
    pAnd = pNode->pCopy;
    if ( !Abc_NtkSpeedupNode_rec( Abc_ObjRegular(pAnd), vNodes ) )
    {
//        printf( "Bad node!!!\n" );
        Vec_PtrFree( vNodes );
        return;
    }

    // derive cofactors
    nCofs = (1 << Vec_PtrSize(vTimes));
    for ( i = 0; i < nCofs; i++ )
    {
        Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pObj, k )
        {
            pAnd = pObj->pCopy;
            Abc_ObjRegular(pAnd)->pCopy = Abc_ObjRegular(pAnd);
        }
        Vec_PtrForEachEntry( Abc_Obj_t *, vTimes, pObj, k )
        {
            pAnd = pObj->pCopy;
            Abc_ObjRegular(pAnd)->pCopy = Abc_ObjNotCond( Abc_AigConst1(pAig), ((i & (1<<k)) == 0) );
        }
        Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, k )
            pObj->pCopy = Abc_AigAnd( (Abc_Aig_t *)pAig->pManFunc, Abc_ObjChild0Copy(pObj), Abc_ObjChild1Copy(pObj) );
        // save the result
        pAnd = pNode->pCopy;
        ppCofs[i] = Abc_ObjNotCond( Abc_ObjRegular(pAnd)->pCopy, Abc_ObjIsComplement(pAnd) );
    }
    Vec_PtrFree( vNodes );

//Abc_ObjAddFanin( Abc_NtkCreatePo(pAig), ppCofs[0] );
//Abc_ObjAddFanin( Abc_NtkCreatePo(pAig), ppCofs[1] );

    // collect the resulting tree
    Vec_PtrForEachEntry( Abc_Obj_t *, vTimes, pObj, k )
        for ( nSkip = (1<<k), i = 0; i < nCofs; i += 2*nSkip )
        {
            pAnd = pObj->pCopy;
            ppCofs[i] = Abc_AigMux( (Abc_Aig_t *)pAig->pManFunc, Abc_ObjRegular(pAnd), ppCofs[i+nSkip], ppCofs[i] );
        }
//Abc_ObjAddFanin( Abc_NtkCreatePo(pAig), ppCofs[0] );

    // create choice node
    pAnd = Abc_ObjRegular(pNode->pCopy); // repr
    pObj = Abc_ObjRegular(ppCofs[0]);    // new
    if ( pAnd->pData == NULL && pObj->pData == NULL && !Abc_AigNodeIsConst(pObj) && !Abc_AigCheckTfi(pObj, pAnd) )
    {
        pObj->pData = pAnd->pData;
        pAnd->pData = pObj;
    }

}

int Abc_NtkSpeedupNode_rec	(	Abc_Obj_t *	pNode,
		Vec_Ptr_t *	vNodes
	)

Function*************************************************************

Synopsis [Adds strashed nodes for one node.]

Description []

SideEffects []

SeeAlso []

Definition at line 349 of file abcSpeedup.c.

{
    if ( Abc_NodeIsTravIdCurrent(pNode) )
        return 1;
    if ( Abc_ObjIsCi(pNode) )
        return 0;
    assert( Abc_ObjIsNode(pNode) );
    Abc_NodeSetTravIdCurrent( pNode );
    if ( !Abc_NtkSpeedupNode_rec( Abc_ObjFanin0(pNode), vNodes ) )
        return 0;
    if ( !Abc_NtkSpeedupNode_rec( Abc_ObjFanin1(pNode), vNodes ) )
        return 0;
    Vec_PtrPush( vNodes, pNode );
    return 1;
}

static ABC_NAMESPACE_IMPL_START float Abc_ObjArrival ( Abc_Obj_t *  pNode )

inlinestatic

DECLARATIONS ///.

CFile****************************************************************

FileName [abcSpeedup.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Network and node package.]

Synopsis [Delay trace and speedup.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - June 20, 2005.]

Revision [

Id:

abcSpeedup.c,v 1.00 2005/06/20 00:00:00 alanmi Exp

]

Definition at line 33 of file abcSpeedup.c.

{ return pNode->pNtk->pLutTimes[3*pNode->Id+0]; }

static float Abc_ObjRequired ( Abc_Obj_t *  pNode )

inlinestatic

Definition at line 34 of file abcSpeedup.c.

{ return pNode->pNtk->pLutTimes[3*pNode->Id+1]; }

static void Abc_ObjSetArrival ( Abc_Obj_t *  pNode, float  Time  )

inlinestatic

Definition at line 37 of file abcSpeedup.c.

{ pNode->pNtk->pLutTimes[3*pNode->Id+0] = Time; }

static void Abc_ObjSetRequired ( Abc_Obj_t *  pNode, float  Time  )

inlinestatic

Definition at line 38 of file abcSpeedup.c.

{ pNode->pNtk->pLutTimes[3*pNode->Id+1] = Time; }

static void Abc_ObjSetSlack ( Abc_Obj_t *  pNode, float  Time  )

inlinestatic

Definition at line 39 of file abcSpeedup.c.

{ pNode->pNtk->pLutTimes[3*pNode->Id+2] = Time; }

static float Abc_ObjSlack ( Abc_Obj_t *  pNode )

inlinestatic

Definition at line 35 of file abcSpeedup.c.

{ return pNode->pNtk->pLutTimes[3*pNode->Id+2]; }