retDelay.c File Reference

#include "retInt.h"

Go to the source code of this file.

Functions
static ABC_NAMESPACE_IMPL_START int	Abc_NtkRetimeMinDelayTry (Abc_Ntk_t *pNtk, int nDelayLim, int fForward, int fInitial, int nIterLimit, int *pIterBest, int fVerbose)
	DECLARATIONS ///. More...
static int	Abc_NtkRetimeTiming (Abc_Ntk_t *pNtk, int fForward, Vec_Ptr_t *vCritical)
static int	Abc_NtkRetimeTiming_rec (Abc_Obj_t *pObj, int fForward)
int	Abc_NtkRetimeMinDelay (Abc_Ntk_t *pNtk, Abc_Ntk_t *pNtkCopy, int nDelayLim, int nIterLimit, int fForward, int fVerbose)
	FUNCTION DEFINITIONS ///. More...

Function Documentation

int Abc_NtkRetimeMinDelay	(	Abc_Ntk_t *	pNtk,
		Abc_Ntk_t *	pNtkCopy,
		int	nDelayLim,
		int	nIterLimit,
		int	fForward,
		int	fVerbose
	)

FUNCTION DEFINITIONS ///.

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

Synopsis [Retimes incrementally for minimum delay.]

Description [This procedure cannot be called in the application code because it assumes that the network is preprocessed by removing LIs/LOs.]

SideEffects []

SeeAlso []

Definition at line 50 of file retDelay.c.

{
    int IterBest, DelayBest;
    int IterBest2, DelayBest2;
    // try to find the best delay iteration on a copy
    DelayBest = Abc_NtkRetimeMinDelayTry( pNtkCopy, nDelayLim, fForward, 0, nIterLimit, &IterBest, fVerbose );
    if ( IterBest == 0 )
        return 1;
    // perform the given number of iterations on the original network
    DelayBest2 = Abc_NtkRetimeMinDelayTry( pNtk, nDelayLim, fForward, 1, IterBest, &IterBest2, fVerbose );
    assert( DelayBest == DelayBest2 );
    assert( IterBest == IterBest2 );
    return 1;
}

int Abc_NtkRetimeMinDelayTry ( Abc_Ntk_t *  pNtk, int  nDelayLim, int  fForward, int  fInitial, int  nIterLimit, int *  pIterBest, int  fVerbose  )

static

DECLARATIONS ///.

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

FileName [retDelay.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Retiming package.]

Synopsis [Incremental retiming for optimum delay.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - Oct 31, 2006.]

Revision [

Id:

retDelay.c,v 1.00 2006/10/31 00:00:00 alanmi Exp

]

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

Synopsis [Returns the best delay and the number of best iteration.]

Description []

SideEffects []

SeeAlso []

Definition at line 76 of file retDelay.c.

{
    Abc_Ntk_t * pNtkNew = NULL;
    Vec_Ptr_t * vCritical;
    Vec_Int_t * vValues = NULL; // Suppress "might be used uninitialized"
    Abc_Obj_t * pObj;
    int i, k, IterBest, DelayCur, DelayBest;
    int DelayStart = -1; // Suppress "might be used uninitialized"
    int LatchesBest;
    // transfer intitial values
    if ( fInitial )
    {
        if ( fForward )
            Abc_NtkRetimeTranferToCopy( pNtk );
        else
        {
            // save initial value of the latches
            vValues = Abc_NtkRetimeCollectLatchValues( pNtk );
            // start the network for initial value computation
            pNtkNew = Abc_NtkRetimeBackwardInitialStart( pNtk );
        }
    }

if ( fVerbose && !fInitial )
    printf( "Performing analysis:\n" );
    // find the best iteration
    DelayBest = ABC_INFINITY; IterBest = 0; LatchesBest = Abc_NtkLatchNum(pNtk);
    vCritical = Vec_PtrAlloc( 100 );
    for ( i = 0; ; i++ )
    {
        // perform moves for the timing-critical nodes
        DelayCur = Abc_NtkRetimeTiming( pNtk, fForward, vCritical );
        if ( i == 0 )
            DelayStart = DelayCur;
        // record this position if it has the best delay
        if ( DelayBest > DelayCur )
        {
if ( fVerbose && !fInitial )
    printf( "%s Iter = %3d. Delay = %3d. Latches = %5d. Delta = %6.2f. Ratio = %4.2f %%\n", 
        fForward ? "Fwd": "Bwd", i, DelayCur, Abc_NtkLatchNum(pNtk), 
        1.0*(Abc_NtkLatchNum(pNtk)-LatchesBest)/(DelayBest-DelayCur), 
        100.0*(Abc_NtkLatchNum(pNtk)-LatchesBest)/Abc_NtkLatchNum(pNtk)/(DelayBest-DelayCur) );

            DelayBest = DelayCur;
            IterBest = i;
            LatchesBest = Abc_NtkLatchNum(pNtk);
        }
        // quit after timing analysis
        if ( i == nIterLimit )
            break;
        // skip if 10 interations did not give improvement
        if ( i - IterBest > 20 )
            break;
        // skip if delay limit is reached
        if ( nDelayLim > 0 && DelayCur <= nDelayLim )
            break;
        // try retiming to improve the delay
        Vec_PtrForEachEntry( Abc_Obj_t *, vCritical, pObj, k )
            if ( Abc_NtkRetimeNodeIsEnabled(pObj, fForward) )
                Abc_NtkRetimeNode( pObj, fForward, fInitial );
        // share latches
        if ( !fForward )
            Abc_NtkRetimeShareLatches( pNtk, fInitial );    
    }
    Vec_PtrFree( vCritical );
    // transfer the initial state back to the latches
    if ( fInitial )
    {
        if ( fForward )
            Abc_NtkRetimeTranferFromCopy( pNtk );
        else
        {
            Abc_NtkRetimeBackwardInitialFinish( pNtk, pNtkNew, vValues, fVerbose );
            Abc_NtkDelete( pNtkNew );
            Vec_IntFree( vValues );
        }
    }
if ( fVerbose && !fInitial )
    printf( "%s : Starting delay = %3d.  Final delay = %3d.  IterBest = %2d (out of %2d).\n", 
        fForward? "Forward " : "Backward", DelayStart, DelayBest, IterBest, nIterLimit );
    *pIterBest = (nIterLimit == 1) ? 1 : IterBest;
    return DelayBest;
}

int Abc_NtkRetimeTiming ( Abc_Ntk_t *  pNtk, int  fForward, Vec_Ptr_t *  vCritical  )

static

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

Synopsis [Returns the set of timing-critical nodes.]

Description [Performs static timing analysis on the network. Uses unit-delay model.]

SideEffects []

SeeAlso []

Definition at line 172 of file retDelay.c.

{
    Vec_Ptr_t * vLatches;
    Abc_Obj_t * pObj, * pNext;
    int i, k, LevelCur, LevelMax = 0;
    // mark all objects except nodes
    Abc_NtkIncrementTravId(pNtk);
    vLatches = Vec_PtrAlloc( Abc_NtkLatchNum(pNtk) );
    Abc_NtkForEachObj( pNtk, pObj, i )
    {
        if ( Abc_ObjIsLatch(pObj) )
            Vec_PtrPush( vLatches, pObj );
        if ( Abc_ObjIsNode(pObj) )
            continue;
        pObj->Level = 0;
        Abc_NodeSetTravIdCurrent( pObj );
    }
    // perform analysis from CIs/COs
    if ( fForward )
    {
        Vec_PtrForEachEntry( Abc_Obj_t *, vLatches, pObj, i )
        {
            Abc_ObjForEachFanout( pObj, pNext, k )
            {
                LevelCur = Abc_NtkRetimeTiming_rec( pNext, fForward );
                if ( LevelMax < LevelCur )
                    LevelMax = LevelCur;
            }
        }
        Abc_NtkForEachPi( pNtk, pObj, i )
        {
            Abc_ObjForEachFanout( pObj, pNext, k )
            {
                LevelCur = Abc_NtkRetimeTiming_rec( pNext, fForward );
                if ( LevelMax < LevelCur )
                    LevelMax = LevelCur;
            }
        }
    }
    else
    {
        Vec_PtrForEachEntry( Abc_Obj_t *, vLatches, pObj, i )
        {
            LevelCur = Abc_NtkRetimeTiming_rec( Abc_ObjFanin0(pObj), fForward );
            if ( LevelMax < LevelCur )
                LevelMax = LevelCur;
        }
        Abc_NtkForEachPo( pNtk, pObj, i )
        {
            LevelCur = Abc_NtkRetimeTiming_rec( Abc_ObjFanin0(pObj), fForward );
            if ( LevelMax < LevelCur )
                LevelMax = LevelCur;
        }
    }
    // collect timing critical nodes, which should be retimed forward/backward
    Vec_PtrClear( vCritical );
    Abc_NtkIncrementTravId(pNtk);
    if ( fForward )
    {
        Vec_PtrForEachEntry( Abc_Obj_t *, vLatches, pObj, i )
        {
            Abc_ObjForEachFanout( pObj, pNext, k )
            {
                if ( Abc_NodeIsTravIdCurrent(pNext) )
                    continue;
                if ( LevelMax != (int)pNext->Level )
                    continue;
                // new critical node
                Vec_PtrPush( vCritical, pNext );
                Abc_NodeSetTravIdCurrent( pNext );
            }
        }
    }
    else
    {
        Vec_PtrForEachEntry( Abc_Obj_t *, vLatches, pObj, i )
        {
            Abc_ObjForEachFanin( pObj, pNext, k )
            {
                if ( Abc_NodeIsTravIdCurrent(pNext) )
                    continue;
                if ( LevelMax != (int)pNext->Level )
                    continue;
                // new critical node
                Vec_PtrPush( vCritical, pNext );
                Abc_NodeSetTravIdCurrent( pNext );
            }
        }
    }
    Vec_PtrFree( vLatches );
    return LevelMax;
}

int Abc_NtkRetimeTiming_rec ( Abc_Obj_t *  pObj, int  fForward  )

static

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

Synopsis [Recursively performs timing analysis.]

Description [Performs static timing analysis on the network. Uses unit-delay model.]

SideEffects []

SeeAlso []

Definition at line 277 of file retDelay.c.

{
    Abc_Obj_t * pNext;
    int i, LevelCur, LevelMax = 0;
    // skip visited nodes
    if ( Abc_NodeIsTravIdCurrent(pObj) )
        return pObj->Level;
    Abc_NodeSetTravIdCurrent(pObj);
    // visit the next nodes
    if ( fForward )
    {
        Abc_ObjForEachFanout( pObj, pNext, i )
        {
            LevelCur = Abc_NtkRetimeTiming_rec( pNext, fForward );
            if ( LevelMax < LevelCur )
                LevelMax = LevelCur;
        }
    }
    else
    {
        Abc_ObjForEachFanin( pObj, pNext, i )
        {
            LevelCur = Abc_NtkRetimeTiming_rec( pNext, fForward );
            if ( LevelMax < LevelCur )
                LevelMax = LevelCur;
        }
    }
//    printf( "Node %3d -> Level %3d.\n", pObj->Id, LevelMax + 1 );
    pObj->Level = LevelMax + 1;
    return pObj->Level;
}