src/opt/ret/retLvalue.c File Reference

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

Go to the source code of this file.

Enumerations

enum  { ABC_RET_UPDATE_FAIL, ABC_RET_UPDATE_NO, ABC_RET_UPDATE_YES }

Functions

static Vec_Int_t * Abc_NtkRetimeGetLags (Abc_Ntk_t *pNtk, int nIterLimit, int fVerbose)
static int Abc_NtkRetimeSearch_rec (Abc_Ntk_t *pNtk, Vec_Ptr_t *vNodes, Vec_Ptr_t *vLatches, int FiMin, int FiMax, int nMaxIters, int fVerbose)
static int Abc_NtkRetimeForPeriod (Abc_Ntk_t *pNtk, Vec_Ptr_t *vNodes, Vec_Ptr_t *vLatches, int Fi, int nMaxIters, int fVerbose)
static int Abc_NtkRetimeUpdateLValue (Abc_Ntk_t *pNtk, Vec_Ptr_t *vNodes, Vec_Ptr_t *vLatches, int Fi)
static int Abc_NtkRetimePosOverLimit (Abc_Ntk_t *pNtk, int Fi)
static Vec_Ptr_t * Abc_ManCollectLatches (Abc_Ntk_t *pNtk)
static int Abc_NtkRetimeUsingLags (Abc_Ntk_t *pNtk, Vec_Int_t *vLags, int fVerbose)
static int Abc_NodeComputeLag (int LValue, int Fi)
static int Abc_NodeGetLValue (Abc_Obj_t *pNode)
static void Abc_NodeSetLValue (Abc_Obj_t *pNode, int Value)
int Abc_NtkRetimeLValue (Abc_Ntk_t *pNtk, int nIterLimit, int fVerbose)
void Abc_ManCollectLatches_rec (Abc_Obj_t *pObj, Vec_Ptr_t *vLatches)

Enumeration Type Documentation

anonymous enum

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

FileName [retLvalue.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Retiming package.]

Synopsis [Implementation of Pan's retiming algorithm.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

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

Revision [

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

] DECLARATIONS ///

Enumerator:
ABC_RET_UPDATE_FAIL 
ABC_RET_UPDATE_NO 
ABC_RET_UPDATE_YES 

Definition at line 28 of file retLvalue.c.

00028 { ABC_RET_UPDATE_FAIL, ABC_RET_UPDATE_NO, ABC_RET_UPDATE_YES };

Function Documentation

Vec_Ptr_t * Abc_ManCollectLatches ( Abc_Ntk_t *  pNtk  )  [static]

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

Synopsis [Collects latches in the topological order.]

Description []

SideEffects []

SeeAlso []

Definition at line 333 of file retLvalue.c.

00334 {
00335     Vec_Ptr_t * vLatches;
00336     Abc_Obj_t * pObj;
00337     int i;
00338     vLatches = Vec_PtrAlloc( Abc_NtkLatchNum(pNtk) );
00339     Abc_NtkIncrementTravId( pNtk );
00340     Abc_NtkForEachLatch( pNtk, pObj, i )
00341         Abc_ManCollectLatches_rec( pObj, vLatches );
00342     assert( Vec_PtrSize(vLatches) == Abc_NtkLatchNum(pNtk) );
00343     return vLatches;
00344 }

void Abc_ManCollectLatches_rec ( Abc_Obj_t *  pObj,
Vec_Ptr_t *  vLatches 
)

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

Synopsis [Collects latches in the topological order.]

Description []

SideEffects []

SeeAlso []

Definition at line 304 of file retLvalue.c.

00305 {
00306     Abc_Obj_t * pDriver;
00307     if ( !Abc_ObjIsLatch(pObj) )
00308         return;
00309     // skip already collected latches
00310     if ( Abc_NodeIsTravIdCurrent(pObj)  )
00311         return;
00312     Abc_NodeSetTravIdCurrent(pObj);
00313     // get the driver node feeding into the latch
00314     pDriver = Abc_ObjFanin0(Abc_ObjFanin0(pObj));
00315     // call recursively if the driver looks like a latch output
00316     if ( Abc_ObjIsBo(pDriver) )
00317         Abc_ManCollectLatches_rec( Abc_ObjFanin0(pDriver), vLatches );
00318     // collect the latch
00319     Vec_PtrPush( vLatches, pObj );
00320 }

static int Abc_NodeComputeLag ( int  LValue,
int  Fi 
) [inline, static]

Definition at line 39 of file retLvalue.c.

00039 { return (LValue + (1<<16)*Fi)/Fi - (1<<16) - (int)(LValue % Fi == 0);     }

static int Abc_NodeGetLValue ( Abc_Obj_t *  pNode  )  [inline, static]

Definition at line 40 of file retLvalue.c.

00040 { return (int)pNode->pCopy;        }

static void Abc_NodeSetLValue ( Abc_Obj_t *  pNode,
int  Value 
) [inline, static]

Definition at line 41 of file retLvalue.c.

00041 { pNode->pCopy = (void *)Value;    }

int Abc_NtkRetimeForPeriod ( Abc_Ntk_t *  pNtk,
Vec_Ptr_t *  vNodes,
Vec_Ptr_t *  vLatches,
int  Fi,
int  nMaxIters,
int  fVerbose 
) [static]

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

Synopsis [Returns 1 if retiming with this clock period is feasible.]

Description []

SideEffects []

SeeAlso []

Definition at line 191 of file retLvalue.c.

00192 {
00193     Abc_Obj_t * pObj;
00194     int c, i, fConverged;
00195     // set l-values of all nodes to be minus infinity, except PIs and constants
00196     Abc_NtkForEachObj( pNtk, pObj, i )
00197         if ( Abc_ObjFaninNum(pObj) == 0 )
00198             Abc_NodeSetLValue( pObj, 0 );
00199         else
00200             Abc_NodeSetLValue( pObj, -ABC_INFINITY );
00201     // update all values iteratively
00202     fConverged = 0;
00203     for ( c = 1; c <= nMaxIters; c++ )
00204     {
00205         if ( !Abc_NtkRetimeUpdateLValue( pNtk, vNodes, vLatches, Fi ) )
00206         {
00207             fConverged = 1;
00208             break;
00209         }
00210         if ( Abc_NtkRetimePosOverLimit(pNtk, Fi) )
00211             break;
00212     }
00213     // report the results
00214     if ( fVerbose )
00215     {
00216         if ( !fConverged )
00217             printf( "Period = %3d.  Iterations = %3d.    Infeasible %s\n", Fi, c, (c > nMaxIters)? "(timeout)" : "" );
00218         else
00219             printf( "Period = %3d.  Iterations = %3d.      Feasible\n",    Fi, c );
00220     }
00221 /*
00222     // check if any AND gates have infinite delay
00223     Counter = 0;
00224     Abc_NtkForEachNode( pNtk, pObj, i )
00225         Counter += (Abc_NodeGetLValue(pObj) < -ABC_INFINITY/2);
00226     if ( Counter > 0 )
00227         printf( "Warning: %d internal nodes have wrong l-values!\n", Counter );
00228 */
00229     return fConverged;
00230 }

Vec_Int_t * Abc_NtkRetimeGetLags ( Abc_Ntk_t *  pNtk,
int  nIterLimit,
int  fVerbose 
) [static]

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

Synopsis [Computes the retiming lags.]

Description []

SideEffects []

SeeAlso []

Definition at line 88 of file retLvalue.c.

00089 {
00090     Vec_Int_t * vLags;
00091     Vec_Ptr_t * vNodes, * vLatches;
00092     Abc_Obj_t * pNode;
00093     int i, FiMax, FiBest, RetValue, clk, clkIter;
00094     char NodeLag;
00095 
00096     // get the upper bound on the clock period
00097     FiMax = Abc_NtkLevel(pNtk);
00098 
00099     // make sure this clock period is feasible
00100     vNodes = Abc_NtkDfs( pNtk, 0 );
00101     vLatches = Abc_ManCollectLatches( pNtk );
00102     if ( !Abc_NtkRetimeForPeriod( pNtk, vNodes, vLatches, FiMax, nIterLimit, fVerbose ) )
00103     {
00104         Vec_PtrFree( vNodes );
00105         printf( "Abc_NtkRetimeGetLags() error: The upper bound on the clock period cannot be computed.\n" );
00106         return Vec_IntStart( Abc_NtkObjNumMax(pNtk) + 1 );
00107     }
00108  
00109     // search for the optimal clock period between 0 and nLevelMax
00110 clk = clock();
00111     FiBest = Abc_NtkRetimeSearch_rec( pNtk, vNodes, vLatches, 0, FiMax, nIterLimit, fVerbose );
00112 clkIter = clock() - clk;
00113 
00114     // recompute the best l-values
00115     RetValue = Abc_NtkRetimeForPeriod( pNtk, vNodes, vLatches, FiBest, nIterLimit, fVerbose );
00116     assert( RetValue );
00117 
00118     // fix the problem with non-converged delays
00119     Abc_NtkForEachNode( pNtk, pNode, i )
00120         if ( Abc_NodeGetLValue(pNode) < -ABC_INFINITY/2 )
00121             Abc_NodeSetLValue( pNode, 0 );
00122 
00123     // write the retiming lags
00124     vLags = Vec_IntStart( Abc_NtkObjNumMax(pNtk) + 1 );
00125     Abc_NtkForEachNode( pNtk, pNode, i )
00126     {
00127         NodeLag = Abc_NodeComputeLag( Abc_NodeGetLValue(pNode), FiBest );
00128         Vec_IntWriteEntry( vLags, pNode->Id, NodeLag );
00129     }
00130 /*
00131     Abc_NtkForEachPo( pNtk, pNode, i )
00132         printf( "%d ", Abc_NodeGetLValue(Abc_ObjFanin0(pNode)) );
00133     printf( "\n" );
00134     Abc_NtkForEachLatch( pNtk, pNode, i )
00135         printf( "%d/%d ", Abc_NodeGetLValue(Abc_ObjFanout0(pNode)), Abc_NodeGetLValue(Abc_ObjFanout0(pNode)) + FiBest );
00136     printf( "\n" );
00137 */
00138 
00139     // print the result
00140 //    if ( fVerbose )
00141     printf( "The best clock period is %3d. (Currently, network is not modified.)\n", FiBest );
00142 /*
00143     {
00144         FILE * pTable;
00145         pTable = fopen( "iscas/seqmap__stats2.txt", "a+" );
00146         fprintf( pTable, "%d ", FiBest );
00147         fprintf( pTable, "\n" );
00148         fclose( pTable );
00149     }
00150 */
00151     Vec_PtrFree( vNodes );
00152     Vec_PtrFree( vLatches );
00153     return vLags;
00154 }

int Abc_NtkRetimeLValue ( Abc_Ntk_t *  pNtk,
int  nIterLimit,
int  fVerbose 
)

FUNCTION DEFINITIONS ///Function*************************************************************

Synopsis [Implements Pan's retiming algorithm.]

Description []

SideEffects []

SeeAlso []

Definition at line 58 of file retLvalue.c.

00059 {
00060     Vec_Int_t * vLags;
00061     int nLatches = Abc_NtkLatchNum(pNtk);
00062     assert( Abc_NtkIsLogic( pNtk ) );
00063     // get the lags
00064     vLags = Abc_NtkRetimeGetLags( pNtk, nIterLimit, fVerbose );
00065     // compute the retiming
00066 //    Abc_NtkRetimeUsingLags( pNtk, vLags, fVerbose );
00067     Vec_IntFree( vLags );
00068     // fix the COs
00069 //    Abc_NtkLogicMakeSimpleCos( pNtk, 0 );
00070     // check for correctness
00071     if ( !Abc_NtkCheck( pNtk ) )
00072         fprintf( stdout, "Abc_NtkRetimeLValue(): Network check has failed.\n" );
00073     // return the number of latches saved
00074     return nLatches - Abc_NtkLatchNum(pNtk);
00075 }

int Abc_NtkRetimePosOverLimit ( Abc_Ntk_t *  pNtk,
int  Fi 
) [static]

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

Synopsis [Detects the case when l-values exceeded the limit.]

Description []

SideEffects []

SeeAlso []

Definition at line 283 of file retLvalue.c.

00284 {
00285     Abc_Obj_t * pObj;
00286     int i;
00287     Abc_NtkForEachPo( pNtk, pObj, i )
00288         if ( Abc_NodeGetLValue(Abc_ObjFanin0(pObj)) > Fi )
00289             return 1;
00290     return 0;
00291 }

int Abc_NtkRetimeSearch_rec ( Abc_Ntk_t *  pNtk,
Vec_Ptr_t *  vNodes,
Vec_Ptr_t *  vLatches,
int  FiMin,
int  FiMax,
int  nMaxIters,
int  fVerbose 
) [static]

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

Synopsis [Performs binary search for the optimal clock period.]

Description [Assumes that FiMin is infeasible while FiMax is feasible.]

SideEffects []

SeeAlso []

Definition at line 167 of file retLvalue.c.

00168 {
00169     int Median;
00170     assert( FiMin < FiMax );
00171     if ( FiMin + 1 == FiMax )
00172         return FiMax;
00173     Median = FiMin + (FiMax - FiMin)/2;
00174     if ( Abc_NtkRetimeForPeriod( pNtk, vNodes, vLatches, Median, nMaxIters, fVerbose ) )
00175         return Abc_NtkRetimeSearch_rec( pNtk, vNodes, vLatches, FiMin, Median, nMaxIters, fVerbose ); // Median is feasible
00176     else 
00177         return Abc_NtkRetimeSearch_rec( pNtk, vNodes, vLatches, Median, FiMax, nMaxIters, fVerbose ); // Median is infeasible
00178 }

int Abc_NtkRetimeUpdateLValue ( Abc_Ntk_t *  pNtk,
Vec_Ptr_t *  vNodes,
Vec_Ptr_t *  vLatches,
int  Fi 
) [static]

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

Synopsis [Performs one iteration of l-value computation for the nodes.]

Description [Experimentally it was found that checking POs changes is not enough to detect the convergence of l-values in the network.]

SideEffects []

SeeAlso []

Definition at line 244 of file retLvalue.c.

00245 {
00246     Abc_Obj_t * pObj, * pFanin;
00247     int i, k, lValueNew, fChange;
00248     // go through the nodes and detect change
00249     fChange = 0;
00250     Vec_PtrForEachEntry( vNodes, pObj, i )
00251     {
00252         assert( Abc_ObjIsNode(pObj) );
00253         lValueNew = -ABC_INFINITY;
00254         Abc_ObjForEachFanin( pObj, pFanin, k )
00255         {
00256             if ( lValueNew < Abc_NodeGetLValue(pFanin) )
00257                 lValueNew = Abc_NodeGetLValue(pFanin);
00258         }
00259         lValueNew++;
00260         if ( Abc_NodeGetLValue(pObj) < lValueNew )
00261         {
00262             Abc_NodeSetLValue( pObj, lValueNew );
00263             fChange = 1;
00264         }
00265     }
00266     // propagate values through the latches
00267     Vec_PtrForEachEntry( vLatches, pObj, i )
00268         Abc_NodeSetLValue( Abc_ObjFanout0(pObj), Abc_NodeGetLValue(Abc_ObjFanin0(Abc_ObjFanin0(pObj))) - Fi );
00269     return fChange;
00270 }

int Abc_NtkRetimeUsingLags ( Abc_Ntk_t *  pNtk,
Vec_Int_t *  vLags,
int  fVerbose 
) [static]

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

Synopsis [Implements the retiming given as the array of retiming lags.]

Description []

SideEffects []

SeeAlso []

Definition at line 357 of file retLvalue.c.

00358 {
00359     Abc_Obj_t * pObj;
00360     int fChanges, fForward, nTotalMoves, Lag, Counter, i;
00361     // iterate over the nodes
00362     nTotalMoves = 0;
00363     do {
00364         fChanges = 0;
00365         Abc_NtkForEachNode( pNtk, pObj, i )
00366         {
00367             Lag = Vec_IntEntry( vLags, pObj->Id );
00368             if ( !Lag )
00369                 continue;
00370             fForward = (Lag < 0);
00371             if ( Abc_NtkRetimeNodeIsEnabled( pObj, fForward ) )
00372             {
00373                 Abc_NtkRetimeNode( pObj, fForward, 0 );
00374                 fChanges = 1;
00375                 nTotalMoves++;
00376                 Vec_IntAddToEntry( vLags, pObj->Id, fForward? 1 : -1 );
00377             }
00378         }
00379     } while ( fChanges );
00380     if ( fVerbose )
00381         printf( "Total latch moves = %d.\n", nTotalMoves );
00382     // check if there are remaining lags
00383     Counter = 0;
00384     Abc_NtkForEachNode( pNtk, pObj, i )
00385         Counter += (Vec_IntEntry( vLags, pObj->Id ) != 0);
00386     if ( Counter )
00387         printf( "Warning! The number of nodes with unrealized lag = %d.\n", Counter );
00388     return 1;
00389 }

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