src/opt/ret/retDelay.c File Reference

#include "retInt.h"
Include dependency graph for retDelay.c:

Go to the source code of this file.

Functions

static int Abc_NtkRetimeMinDelayTry (Abc_Ntk_t *pNtk, 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)
int Abc_NtkRetimeMinDelay (Abc_Ntk_t *pNtk, Abc_Ntk_t *pNtkCopy, int nIterLimit, int fForward, int fVerbose)

Function Documentation

int Abc_NtkRetimeMinDelay ( Abc_Ntk_t *  pNtk,
Abc_Ntk_t *  pNtkCopy,
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 47 of file retDelay.c.

00048 {
00049     int IterBest, DelayBest;
00050     int IterBest2, DelayBest2;
00051     // try to find the best delay iteration on a copy
00052     DelayBest = Abc_NtkRetimeMinDelayTry( pNtkCopy, fForward, 0, nIterLimit, &IterBest, fVerbose );
00053     if ( IterBest == 0 )
00054         return 1;
00055     // perform the given number of iterations on the original network
00056     DelayBest2 = Abc_NtkRetimeMinDelayTry( pNtk, fForward, 1, IterBest, &IterBest2, fVerbose );
00057     assert( DelayBest == DelayBest2 );
00058     assert( IterBest == IterBest2 );
00059     return 1;
00060 }

int Abc_NtkRetimeMinDelayTry ( Abc_Ntk_t *  pNtk,
int  fForward,
int  fInitial,
int  nIterLimit,
int *  pIterBest,
int  fVerbose 
) [static]

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

] DECLARATIONS ///

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

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

Description []

SideEffects []

SeeAlso []

Definition at line 73 of file retDelay.c.

00074 {
00075     Abc_Ntk_t * pNtkNew = NULL;
00076     Vec_Ptr_t * vCritical;
00077     Vec_Int_t * vValues;
00078     Abc_Obj_t * pObj;
00079     int i, k, IterBest, DelayCur, DelayBest, DelayStart, LatchesBest;
00080     // transfer intitial values
00081     if ( fInitial )
00082     {
00083         if ( fForward )
00084             Abc_NtkRetimeTranferToCopy( pNtk );
00085         else
00086         {
00087             // save initial value of the latches
00088             vValues = Abc_NtkRetimeCollectLatchValues( pNtk );
00089             // start the network for initial value computation
00090             pNtkNew = Abc_NtkRetimeBackwardInitialStart( pNtk );
00091         }
00092     }
00093 
00094 if ( fVerbose && !fInitial )
00095     printf( "Performing analysis:\n" );
00096     // find the best iteration
00097     DelayBest = ABC_INFINITY; IterBest = 0; LatchesBest = Abc_NtkLatchNum(pNtk);
00098     vCritical = Vec_PtrAlloc( 100 );
00099     for ( i = 0; ; i++ )
00100     {
00101         // perform moves for the timing-critical nodes
00102         DelayCur = Abc_NtkRetimeTiming( pNtk, fForward, vCritical );
00103         if ( i == 0 )
00104             DelayStart = DelayCur;
00105         // record this position if it has the best delay
00106         if ( DelayBest > DelayCur )
00107         {
00108 if ( fVerbose && !fInitial )
00109     printf( "%s Iter = %3d. Delay = %3d. Latches = %5d. Delta = %6.2f. Ratio = %4.2f %%\n", 
00110         fForward ? "Fwd": "Bwd", i, DelayCur, Abc_NtkLatchNum(pNtk), 
00111         1.0*(Abc_NtkLatchNum(pNtk)-LatchesBest)/(DelayBest-DelayCur), 
00112         100.0*(Abc_NtkLatchNum(pNtk)-LatchesBest)/Abc_NtkLatchNum(pNtk)/(DelayBest-DelayCur) );
00113 
00114             DelayBest = DelayCur;
00115             IterBest = i;
00116             LatchesBest = Abc_NtkLatchNum(pNtk);
00117         }
00118         // quit after timing analysis
00119         if ( i == nIterLimit )
00120             break;
00121         // skip if 10 interations did not give improvement
00122         if ( i - IterBest > 20 )
00123             break;
00124         // try retiming to improve the delay
00125         Vec_PtrForEachEntry( vCritical, pObj, k )
00126             if ( Abc_NtkRetimeNodeIsEnabled(pObj, fForward) )
00127                 Abc_NtkRetimeNode( pObj, fForward, fInitial );
00128         // share latches
00129         if ( !fForward )
00130             Abc_NtkRetimeShareLatches( pNtk, fInitial );    
00131     }
00132     Vec_PtrFree( vCritical );
00133     // transfer the initial state back to the latches
00134     if ( fInitial )
00135     {
00136         if ( fForward )
00137             Abc_NtkRetimeTranferFromCopy( pNtk );
00138         else
00139         {
00140             Abc_NtkRetimeBackwardInitialFinish( pNtk, pNtkNew, vValues, fVerbose );
00141             Abc_NtkDelete( pNtkNew );
00142             Vec_IntFree( vValues );
00143         }
00144     }
00145 if ( fVerbose && !fInitial )
00146     printf( "%s : Starting delay = %3d.  Final delay = %3d.  IterBest = %2d (out of %2d).\n", 
00147         fForward? "Forward " : "Backward", DelayStart, DelayBest, IterBest, nIterLimit );
00148     *pIterBest = (nIterLimit == 1) ? 1 : IterBest;
00149     return DelayBest;
00150 }

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 164 of file retDelay.c.

00165 {
00166     Vec_Ptr_t * vLatches;
00167     Abc_Obj_t * pObj, * pNext;
00168     int i, k, LevelCur, LevelMax = 0;
00169     // mark all objects except nodes
00170     Abc_NtkIncrementTravId(pNtk);
00171     vLatches = Vec_PtrAlloc( Abc_NtkLatchNum(pNtk) );
00172     Abc_NtkForEachObj( pNtk, pObj, i )
00173     {
00174         if ( Abc_ObjIsLatch(pObj) )
00175             Vec_PtrPush( vLatches, pObj );
00176         if ( Abc_ObjIsNode(pObj) )
00177             continue;
00178         pObj->Level = 0;
00179         Abc_NodeSetTravIdCurrent( pObj );
00180     }
00181     // perform analysis from CIs/COs
00182     if ( fForward )
00183     {
00184         Vec_PtrForEachEntry( vLatches, pObj, i )
00185         {
00186             Abc_ObjForEachFanout( pObj, pNext, k )
00187             {
00188                 LevelCur = Abc_NtkRetimeTiming_rec( pNext, fForward );
00189                 if ( LevelMax < LevelCur )
00190                     LevelMax = LevelCur;
00191             }
00192         }
00193         Abc_NtkForEachPi( pNtk, pObj, i )
00194         {
00195             Abc_ObjForEachFanout( pObj, pNext, k )
00196             {
00197                 LevelCur = Abc_NtkRetimeTiming_rec( pNext, fForward );
00198                 if ( LevelMax < LevelCur )
00199                     LevelMax = LevelCur;
00200             }
00201         }
00202     }
00203     else
00204     {
00205         Vec_PtrForEachEntry( vLatches, pObj, i )
00206         {
00207             LevelCur = Abc_NtkRetimeTiming_rec( Abc_ObjFanin0(pObj), fForward );
00208             if ( LevelMax < LevelCur )
00209                 LevelMax = LevelCur;
00210         }
00211         Abc_NtkForEachPo( pNtk, pObj, i )
00212         {
00213             LevelCur = Abc_NtkRetimeTiming_rec( Abc_ObjFanin0(pObj), fForward );
00214             if ( LevelMax < LevelCur )
00215                 LevelMax = LevelCur;
00216         }
00217     }
00218     // collect timing critical nodes, which should be retimed forward/backward
00219     Vec_PtrClear( vCritical );
00220     Abc_NtkIncrementTravId(pNtk);
00221     if ( fForward )
00222     {
00223         Vec_PtrForEachEntry( vLatches, pObj, i )
00224         {
00225             Abc_ObjForEachFanout( pObj, pNext, k )
00226             {
00227                 if ( Abc_NodeIsTravIdCurrent(pNext) )
00228                     continue;
00229                 if ( LevelMax != (int)pNext->Level )
00230                     continue;
00231                 // new critical node
00232                 Vec_PtrPush( vCritical, pNext );
00233                 Abc_NodeSetTravIdCurrent( pNext );
00234             }
00235         }
00236     }
00237     else
00238     {
00239         Vec_PtrForEachEntry( vLatches, pObj, i )
00240         {
00241             Abc_ObjForEachFanin( pObj, pNext, k )
00242             {
00243                 if ( Abc_NodeIsTravIdCurrent(pNext) )
00244                     continue;
00245                 if ( LevelMax != (int)pNext->Level )
00246                     continue;
00247                 // new critical node
00248                 Vec_PtrPush( vCritical, pNext );
00249                 Abc_NodeSetTravIdCurrent( pNext );
00250             }
00251         }
00252     }
00253     Vec_PtrFree( vLatches );
00254     return LevelMax;
00255 }

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 269 of file retDelay.c.

00270 {
00271     Abc_Obj_t * pNext;
00272     int i, LevelCur, LevelMax = 0;
00273     // skip visited nodes
00274     if ( Abc_NodeIsTravIdCurrent(pObj) )
00275         return pObj->Level;
00276     Abc_NodeSetTravIdCurrent(pObj);
00277     // visit the next nodes
00278     if ( fForward )
00279     {
00280         Abc_ObjForEachFanout( pObj, pNext, i )
00281         {
00282             LevelCur = Abc_NtkRetimeTiming_rec( pNext, fForward );
00283             if ( LevelMax < LevelCur )
00284                 LevelMax = LevelCur;
00285         }
00286     }
00287     else
00288     {
00289         Abc_ObjForEachFanin( pObj, pNext, i )
00290         {
00291             LevelCur = Abc_NtkRetimeTiming_rec( pNext, fForward );
00292             if ( LevelMax < LevelCur )
00293                 LevelMax = LevelCur;
00294         }
00295     }
00296 //    printf( "Node %3d -> Level %3d.\n", pObj->Id, LevelMax + 1 );
00297     pObj->Level = LevelMax + 1;
00298     return pObj->Level;
00299 }

Generated on Tue Jan 5 12:19:32 2010 for abc70930 by  doxygen 1.6.1