/**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 $]
***********************************************************************/
#include "retInt.h"
ABC_NAMESPACE_IMPL_START
////////////////////////////////////////////////////////////////////////
/// DECLARATIONS ///
////////////////////////////////////////////////////////////////////////
// node status after updating its arrival time
enum { ABC_RET_UPDATE_FAIL, ABC_RET_UPDATE_NO, ABC_RET_UPDATE_YES };
// the internal procedures
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 inline int Abc_NodeComputeLag( int LValue, int Fi ) { return (LValue + (1<<16)*Fi)/Fi - (1<<16) - (int)(LValue % Fi == 0); }
static inline int Abc_NodeGetLValue( Abc_Obj_t * pNode ) { return (int)(ABC_PTRUINT_T)pNode->pCopy; }
static inline void Abc_NodeSetLValue( Abc_Obj_t * pNode, int Value ) { pNode->pCopy = (Abc_Obj_t *)(ABC_PTRUINT_T)Value; }
////////////////////////////////////////////////////////////////////////
/// FUNCTION DEFINITIONS ///
////////////////////////////////////////////////////////////////////////
/**Function*************************************************************
Synopsis [Implements Pan's retiming algorithm.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Abc_NtkRetimeLValue( Abc_Ntk_t * pNtk, int nIterLimit, int fVerbose )
{
Vec_Int_t * vLags;
int nLatches = Abc_NtkLatchNum(pNtk);
assert( Abc_NtkIsLogic( pNtk ) );
// get the lags
vLags = Abc_NtkRetimeGetLags( pNtk, nIterLimit, fVerbose );
// compute the retiming
// Abc_NtkRetimeUsingLags( pNtk, vLags, fVerbose );
Vec_IntFree( vLags );
// fix the COs
// Abc_NtkLogicMakeSimpleCos( pNtk, 0 );
// check for correctness
if ( !Abc_NtkCheck( pNtk ) )
fprintf( stdout, "Abc_NtkRetimeLValue(): Network check has failed.\n" );
// return the number of latches saved
return nLatches - Abc_NtkLatchNum(pNtk);
}
/**Function*************************************************************
Synopsis [Computes the retiming lags.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Vec_Int_t * Abc_NtkRetimeGetLags( Abc_Ntk_t * pNtk, int nIterLimit, int fVerbose )
{
Vec_Int_t * vLags;
Vec_Ptr_t * vNodes, * vLatches;
Abc_Obj_t * pNode;
int i, FiMax, FiBest, RetValue;
abctime clk, clkIter;
char NodeLag;
// get the upper bound on the clock period
FiMax = Abc_NtkLevel(pNtk);
// make sure this clock period is feasible
vNodes = Abc_NtkDfs( pNtk, 0 );
vLatches = Abc_ManCollectLatches( pNtk );
if ( !Abc_NtkRetimeForPeriod( pNtk, vNodes, vLatches, FiMax, nIterLimit, fVerbose ) )
{
Vec_PtrFree( vLatches );
Vec_PtrFree( vNodes );
printf( "Abc_NtkRetimeGetLags() error: The upper bound on the clock period cannot be computed.\n" );
return Vec_IntStart( Abc_NtkObjNumMax(pNtk) + 1 );
}
// search for the optimal clock period between 0 and nLevelMax
clk = Abc_Clock();
FiBest = Abc_NtkRetimeSearch_rec( pNtk, vNodes, vLatches, 0, FiMax, nIterLimit, fVerbose );
clkIter = Abc_Clock() - clk;
// recompute the best l-values
RetValue = Abc_NtkRetimeForPeriod( pNtk, vNodes, vLatches, FiBest, nIterLimit, fVerbose );
assert( RetValue );
// fix the problem with non-converged delays
Abc_NtkForEachNode( pNtk, pNode, i )
if ( Abc_NodeGetLValue(pNode) < -ABC_INFINITY/2 )
Abc_NodeSetLValue( pNode, 0 );
// write the retiming lags
vLags = Vec_IntStart( Abc_NtkObjNumMax(pNtk) + 1 );
Abc_NtkForEachNode( pNtk, pNode, i )
{
NodeLag = Abc_NodeComputeLag( Abc_NodeGetLValue(pNode), FiBest );
Vec_IntWriteEntry( vLags, pNode->Id, NodeLag );
}
/*
Abc_NtkForEachPo( pNtk, pNode, i )
printf( "%d ", Abc_NodeGetLValue(Abc_ObjFanin0(pNode)) );
printf( "\n" );
Abc_NtkForEachLatch( pNtk, pNode, i )
printf( "%d/%d ", Abc_NodeGetLValue(Abc_ObjFanout0(pNode)), Abc_NodeGetLValue(Abc_ObjFanout0(pNode)) + FiBest );
printf( "\n" );
*/
// print the result
// if ( fVerbose )
printf( "The best clock period is %3d. (Currently, network is not modified.)\n", FiBest );
/*
{
FILE * pTable;
pTable = fopen( "iscas/seqmap__stats2.txt", "a+" );
fprintf( pTable, "%d ", FiBest );
fprintf( pTable, "\n" );
fclose( pTable );
}
*/
Vec_PtrFree( vNodes );
Vec_PtrFree( vLatches );
return vLags;
}
/**Function*************************************************************
Synopsis [Performs binary search for the optimal clock period.]
Description [Assumes that FiMin is infeasible while FiMax is feasible.]
SideEffects []
SeeAlso []
***********************************************************************/
int Abc_NtkRetimeSearch_rec( Abc_Ntk_t * pNtk, Vec_Ptr_t * vNodes, Vec_Ptr_t * vLatches, int FiMin, int FiMax, int nMaxIters, int fVerbose )
{
int Median;
assert( FiMin < FiMax );
if ( FiMin + 1 == FiMax )
return FiMax;
Median = FiMin + (FiMax - FiMin)/2;
if ( Abc_NtkRetimeForPeriod( pNtk, vNodes, vLatches, Median, nMaxIters, fVerbose ) )
return Abc_NtkRetimeSearch_rec( pNtk, vNodes, vLatches, FiMin, Median, nMaxIters, fVerbose ); // Median is feasible
else
return Abc_NtkRetimeSearch_rec( pNtk, vNodes, vLatches, Median, FiMax, nMaxIters, fVerbose ); // Median is infeasible
}
/**Function*************************************************************
Synopsis [Returns 1 if retiming with this clock period is feasible.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Abc_NtkRetimeForPeriod( Abc_Ntk_t * pNtk, Vec_Ptr_t * vNodes, Vec_Ptr_t * vLatches, int Fi, int nMaxIters, int fVerbose )
{
Abc_Obj_t * pObj;
int c, i, fConverged;
// set l-values of all nodes to be minus infinity, except PIs and constants
Abc_NtkForEachObj( pNtk, pObj, i )
if ( Abc_ObjFaninNum(pObj) == 0 )
Abc_NodeSetLValue( pObj, 0 );
else
Abc_NodeSetLValue( pObj, -ABC_INFINITY );
// update all values iteratively
fConverged = 0;
for ( c = 1; c <= nMaxIters; c++ )
{
if ( !Abc_NtkRetimeUpdateLValue( pNtk, vNodes, vLatches, Fi ) )
{
fConverged = 1;
break;
}
if ( Abc_NtkRetimePosOverLimit(pNtk, Fi) )
break;
}
// report the results
if ( fVerbose )
{
if ( !fConverged )
printf( "Period = %3d. Iterations = %3d. Infeasible %s\n", Fi, c, (c > nMaxIters)? "(timeout)" : "" );
else
printf( "Period = %3d. Iterations = %3d. Feasible\n", Fi, c );
}
/*
// check if any AND gates have infinite delay
Counter = 0;
Abc_NtkForEachNode( pNtk, pObj, i )
Counter += (Abc_NodeGetLValue(pObj) < -ABC_INFINITY/2);
if ( Counter > 0 )
printf( "Warning: %d internal nodes have wrong l-values!\n", Counter );
*/
return fConverged;
}
/**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 []
***********************************************************************/
int Abc_NtkRetimeUpdateLValue( Abc_Ntk_t * pNtk, Vec_Ptr_t * vNodes, Vec_Ptr_t * vLatches, int Fi )
{
Abc_Obj_t * pObj, * pFanin;
int i, k, lValueNew, fChange;
// go through the nodes and detect change
fChange = 0;
Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, i )
{
assert( Abc_ObjIsNode(pObj) );
lValueNew = -ABC_INFINITY;
Abc_ObjForEachFanin( pObj, pFanin, k )
{
if ( lValueNew < Abc_NodeGetLValue(pFanin) )
lValueNew = Abc_NodeGetLValue(pFanin);
}
lValueNew++;
if ( Abc_NodeGetLValue(pObj) < lValueNew )
{
Abc_NodeSetLValue( pObj, lValueNew );
fChange = 1;
}
}
// propagate values through the latches
Vec_PtrForEachEntry( Abc_Obj_t *, vLatches, pObj, i )
Abc_NodeSetLValue( Abc_ObjFanout0(pObj), Abc_NodeGetLValue(Abc_ObjFanin0(Abc_ObjFanin0(pObj))) - Fi );
return fChange;
}
/**Function*************************************************************
Synopsis [Detects the case when l-values exceeded the limit.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Abc_NtkRetimePosOverLimit( Abc_Ntk_t * pNtk, int Fi )
{
Abc_Obj_t * pObj;
int i;
Abc_NtkForEachPo( pNtk, pObj, i )
if ( Abc_NodeGetLValue(Abc_ObjFanin0(pObj)) > Fi )
return 1;
return 0;
}
/**Function*************************************************************
Synopsis [Collects latches in the topological order.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Abc_ManCollectLatches_rec( Abc_Obj_t * pObj, Vec_Ptr_t * vLatches )
{
Abc_Obj_t * pDriver;
if ( !Abc_ObjIsLatch(pObj) )
return;
// skip already collected latches
if ( Abc_NodeIsTravIdCurrent(pObj) )
return;
Abc_NodeSetTravIdCurrent(pObj);
// get the driver node feeding into the latch
pDriver = Abc_ObjFanin0(Abc_ObjFanin0(pObj));
// call recursively if the driver looks like a latch output
if ( Abc_ObjIsBo(pDriver) )
Abc_ManCollectLatches_rec( Abc_ObjFanin0(pDriver), vLatches );
// collect the latch
Vec_PtrPush( vLatches, pObj );
}
/**Function*************************************************************
Synopsis [Collects latches in the topological order.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Vec_Ptr_t * Abc_ManCollectLatches( Abc_Ntk_t * pNtk )
{
Vec_Ptr_t * vLatches;
Abc_Obj_t * pObj;
int i;
vLatches = Vec_PtrAlloc( Abc_NtkLatchNum(pNtk) );
Abc_NtkIncrementTravId( pNtk );
Abc_NtkForEachLatch( pNtk, pObj, i )
Abc_ManCollectLatches_rec( pObj, vLatches );
assert( Vec_PtrSize(vLatches) == Abc_NtkLatchNum(pNtk) );
return vLatches;
}
/**Function*************************************************************
Synopsis [Implements the retiming given as the array of retiming lags.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Abc_NtkRetimeUsingLags( Abc_Ntk_t * pNtk, Vec_Int_t * vLags, int fVerbose )
{
Abc_Obj_t * pObj;
int fChanges, fForward, nTotalMoves, Lag, Counter, i;
// iterate over the nodes
nTotalMoves = 0;
do {
fChanges = 0;
Abc_NtkForEachNode( pNtk, pObj, i )
{
Lag = Vec_IntEntry( vLags, pObj->Id );
if ( !Lag )
continue;
fForward = (Lag < 0);
if ( Abc_NtkRetimeNodeIsEnabled( pObj, fForward ) )
{
Abc_NtkRetimeNode( pObj, fForward, 0 );
fChanges = 1;
nTotalMoves++;
Vec_IntAddToEntry( vLags, pObj->Id, fForward? 1 : -1 );
}
}
} while ( fChanges );
if ( fVerbose )
printf( "Total latch moves = %d.\n", nTotalMoves );
// check if there are remaining lags
Counter = 0;
Abc_NtkForEachNode( pNtk, pObj, i )
Counter += (Vec_IntEntry( vLags, pObj->Id ) != 0);
if ( Counter )
printf( "Warning! The number of nodes with unrealized lag = %d.\n", Counter );
return 1;
}
////////////////////////////////////////////////////////////////////////
/// END OF FILE ///
////////////////////////////////////////////////////////////////////////
ABC_NAMESPACE_IMPL_END