| /**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 $] | |
| ***********************************************************************/ | |
| #include "retInt.h" | |
| ABC_NAMESPACE_IMPL_START | |
| //////////////////////////////////////////////////////////////////////// | |
| /// DECLARATIONS /// | |
| //////////////////////////////////////////////////////////////////////// | |
| static int Abc_NtkRetimeMinDelayTry( Abc_Ntk_t * pNtk, int nDelayLim, int fForward, int fInitial, int nIterLimit, int * pIterBest, int fVerbose ); | |
| 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 ); | |
| //////////////////////////////////////////////////////////////////////// | |
| /// 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 [] | |
| ***********************************************************************/ | |
| int Abc_NtkRetimeMinDelay( Abc_Ntk_t * pNtk, Abc_Ntk_t * pNtkCopy, int nDelayLim, int nIterLimit, int fForward, int fVerbose ) | |
| { | |
| 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; | |
| } | |
| /**Function************************************************************* | |
| Synopsis [Returns the best delay and the number of best iteration.] | |
| Description [] | |
| SideEffects [] | |
| SeeAlso [] | |
| ***********************************************************************/ | |
| int Abc_NtkRetimeMinDelayTry( Abc_Ntk_t * pNtk, int nDelayLim, int fForward, int fInitial, int nIterLimit, int * pIterBest, int fVerbose ) | |
| { | |
| 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; | |
| } | |
| /**Function************************************************************* | |
| Synopsis [Returns the set of timing-critical nodes.] | |
| Description [Performs static timing analysis on the network. Uses | |
| unit-delay model.] | |
| SideEffects [] | |
| SeeAlso [] | |
| ***********************************************************************/ | |
| int Abc_NtkRetimeTiming( Abc_Ntk_t * pNtk, int fForward, Vec_Ptr_t * vCritical ) | |
| { | |
| 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; | |
| } | |
| /**Function************************************************************* | |
| Synopsis [Recursively performs timing analysis.] | |
| Description [Performs static timing analysis on the network. Uses | |
| unit-delay model.] | |
| SideEffects [] | |
| SeeAlso [] | |
| ***********************************************************************/ | |
| int Abc_NtkRetimeTiming_rec( Abc_Obj_t * pObj, int fForward ) | |
| { | |
| 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; | |
| } | |
| //////////////////////////////////////////////////////////////////////// | |
| /// END OF FILE /// | |
| //////////////////////////////////////////////////////////////////////// | |
| ABC_NAMESPACE_IMPL_END | |