/**CFile****************************************************************
FileName [seqRetIter.c]
SystemName [ABC: Logic synthesis and verification system.]
PackageName [Construction and manipulation of sequential AIGs.]
Synopsis [Iterative delay computation in FPGA mapping/retiming package.]
Author [Alan Mishchenko]
Affiliation [UC Berkeley]
Date [Ver. 1.0. Started - June 20, 2005.]
Revision [$Id: seqRetIter.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
***********************************************************************/
#include "seqInt.h"
#include "main.h"
#include "fpga.h"
ABC_NAMESPACE_IMPL_START
////////////////////////////////////////////////////////////////////////
/// DECLARATIONS ///
////////////////////////////////////////////////////////////////////////
static float Seq_NtkMappingSearch_rec( Abc_Ntk_t * pNtk, float FiMin, float FiMax, float Delta, int fVerbose );
static int Seq_NtkMappingForPeriod( Abc_Ntk_t * pNtk, float Fi, int fVerbose );
static int Seq_NtkNodeUpdateLValue( Abc_Obj_t * pObj, float Fi, Vec_Ptr_t * vLeaves, Vec_Ptr_t * vDelays );
static void Seq_NodeRetimeSetLag_rec( Abc_Obj_t * pNode, char Lag );
static void Seq_NodePrintInfo( Abc_Obj_t * pNode );
static void Seq_NodePrintInfoPlus( Abc_Obj_t * pNode );
////////////////////////////////////////////////////////////////////////
/// FUNCTION DEFINITIONS ///
////////////////////////////////////////////////////////////////////////
/**Function*************************************************************
Synopsis [Computes the retiming lags for arbitrary network.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Seq_NtkRetimeDelayLags( Abc_Ntk_t * pNtkOld, Abc_Ntk_t * pNtk, int fVerbose )
{
Abc_Seq_t * p = pNtk->pManFunc;
Abc_Obj_t * pNode;
float FiMax, Delta;
int i, RetValue;
char NodeLag;
assert( Abc_NtkIsSeq( pNtk ) );
// the root AND gates and node delay should be assigned
assert( p->vMapAnds );
assert( p->vMapCuts );
assert( p->vMapDelays );
assert( p->vMapFanins );
// guess the upper bound on the clock period
if ( Abc_NtkHasMapping(pNtkOld) )
{
// assign the accuracy for min-period computation
Delta = Mio_LibraryReadDelayNand2Max(Abc_FrameReadLibGen());
if ( Delta == 0.0 )
{
Delta = Mio_LibraryReadDelayAnd2Max(Abc_FrameReadLibGen());
if ( Delta == 0.0 )
{
printf( "Cannot retime/map if the library does not have NAND2 or AND2.\n" );
return 0;
}
}
// get the upper bound on the clock period
FiMax = Delta * 2 + Abc_NtkDelayTrace(pNtkOld);
Delta /= 2;
}
else
{
FiMax = (float)2.0 + Abc_NtkGetLevelNum(pNtkOld);
Delta = 1;
}
// make sure this clock period is feasible
if ( !Seq_NtkMappingForPeriod( pNtk, FiMax, fVerbose ) )
{
printf( "Error: The upper bound on the clock period cannot be computed.\n" );
printf( "The reason for this error may be the presence in the circuit of logic\n" );
printf( "that is not reachable from the PIs. Mapping/retiming is not performed.\n" );
return 0;
}
// search for the optimal clock period between 0 and nLevelMax
p->FiBestFloat = Seq_NtkMappingSearch_rec( pNtk, 0.0, FiMax, Delta, fVerbose );
// recompute the best l-values
RetValue = Seq_NtkMappingForPeriod( pNtk, p->FiBestFloat, fVerbose );
assert( RetValue );
// fix the problem with non-converged delays
Vec_PtrForEachEntry( Abc_Obj_t *, p->vMapAnds, pNode, i )
if ( Seq_NodeGetLValueP(pNode) < -ABC_INFINITY/2 )
Seq_NodeSetLValueP( pNode, 0 );
// experiment by adding an epsilon to all LValues
// Vec_PtrForEachEntry( Abc_Obj_t *, p->vMapAnds, pNode, i )
// Seq_NodeSetLValueP( pNode, Seq_NodeGetLValueP(pNode) - p->fEpsilon );
// save the retiming lags
// mark the nodes
Vec_PtrForEachEntry( Abc_Obj_t *, p->vMapAnds, pNode, i )
pNode->fMarkA = 1;
// process the nodes
Vec_StrFill( p->vLags, p->nSize, 0 );
Vec_PtrForEachEntry( Abc_Obj_t *, p->vMapAnds, pNode, i )
{
if ( Vec_PtrSize( Vec_VecEntry(p->vMapCuts, i) ) == 0 )
{
Seq_NodeSetLag( pNode, 0 );
continue;
}
NodeLag = Seq_NodeComputeLagFloat( Seq_NodeGetLValueP(pNode), p->FiBestFloat );
Seq_NodeRetimeSetLag_rec( pNode, NodeLag );
}
// unmark the nodes
Vec_PtrForEachEntry( Abc_Obj_t *, p->vMapAnds, pNode, i )
pNode->fMarkA = 0;
// print the result
if ( fVerbose )
printf( "The best clock period is %6.2f.\n", p->FiBestFloat );
/*
{
FILE * pTable;
pTable = fopen( "stats.txt", "a+" );
fprintf( pTable, "%s ", pNtk->pName );
fprintf( pTable, "%.2f ", FiBest );
fprintf( pTable, "\n" );
fclose( pTable );
}
*/
// Seq_NodePrintInfo( Abc_NtkObj(pNtk, 847) );
return 1;
}
/**Function*************************************************************
Synopsis [Performs binary search for the optimal clock period.]
Description [Assumes that FiMin is infeasible while FiMax is feasible.]
SideEffects []
SeeAlso []
***********************************************************************/
float Seq_NtkMappingSearch_rec( Abc_Ntk_t * pNtk, float FiMin, float FiMax, float Delta, int fVerbose )
{
float Median;
assert( FiMin < FiMax );
if ( FiMin + Delta >= FiMax )
return FiMax;
Median = FiMin + (FiMax - FiMin)/2;
if ( Seq_NtkMappingForPeriod( pNtk, Median, fVerbose ) )
return Seq_NtkMappingSearch_rec( pNtk, FiMin, Median, Delta, fVerbose ); // Median is feasible
else
return Seq_NtkMappingSearch_rec( pNtk, Median, FiMax, Delta, fVerbose ); // Median is infeasible
}
/**Function*************************************************************
Synopsis [Returns 1 if retiming with this clock period is feasible.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Seq_NtkMappingForPeriod( Abc_Ntk_t * pNtk, float Fi, int fVerbose )
{
Abc_Seq_t * p = pNtk->pManFunc;
Vec_Ptr_t * vLeaves, * vDelays;
Abc_Obj_t * pObj;
int i, c, RetValue, fChange, Counter;
char * pReason = "";
// set l-values of all nodes to be minus infinity
Vec_IntFill( p->vLValues, p->nSize, Abc_Float2Int( (float)-ABC_INFINITY ) );
// set l-values of constants and PIs
pObj = Abc_NtkObj( pNtk, 0 );
Seq_NodeSetLValueP( pObj, 0.0 );
Abc_NtkForEachPi( pNtk, pObj, i )
Seq_NodeSetLValueP( pObj, 0.0 );
// update all values iteratively
Counter = 0;
for ( c = 0; c < p->nMaxIters; c++ )
{
fChange = 0;
Vec_PtrForEachEntry( Abc_Obj_t *, p->vMapAnds, pObj, i )
{
Counter++;
vLeaves = Vec_VecEntry( p->vMapCuts, i );
vDelays = Vec_VecEntry( p->vMapDelays, i );
if ( Vec_PtrSize(vLeaves) == 0 )
{
Seq_NodeSetLValueP( pObj, 0.0 );
continue;
}
RetValue = Seq_NtkNodeUpdateLValue( pObj, Fi, vLeaves, vDelays );
if ( RetValue == SEQ_UPDATE_YES )
fChange = 1;
}
Abc_NtkForEachPo( pNtk, pObj, i )
{
RetValue = Seq_NtkNodeUpdateLValue( pObj, Fi, NULL, NULL );
if ( RetValue == SEQ_UPDATE_FAIL )
break;
}
if ( RetValue == SEQ_UPDATE_FAIL )
break;
if ( fChange == 0 )
break;
}
if ( c == p->nMaxIters )
{
RetValue = SEQ_UPDATE_FAIL;
pReason = "(timeout)";
}
else
c++;
// report the results
if ( fVerbose )
{
if ( RetValue == SEQ_UPDATE_FAIL )
printf( "Period = %6.2f. Iterations = %3d. Updates = %10d. Infeasible %s\n", Fi, c, Counter, pReason );
else
printf( "Period = %6.2f. Iterations = %3d. Updates = %10d. Feasible\n", Fi, c, Counter );
}
return RetValue != SEQ_UPDATE_FAIL;
}
/**Function*************************************************************
Synopsis [Computes the l-value of the node.]
Description [The node can be internal or a PO.]
SideEffects []
SeeAlso []
***********************************************************************/
int Seq_NtkNodeUpdateLValue( Abc_Obj_t * pObj, float Fi, Vec_Ptr_t * vLeaves, Vec_Ptr_t * vDelays )
{
Abc_Seq_t * p = pObj->pNtk->pManFunc;
float lValueOld, lValueNew, lValueCur, lValuePin;
unsigned SeqEdge;
Abc_Obj_t * pLeaf;
int i;
assert( !Abc_ObjIsPi(pObj) );
assert( Abc_ObjFaninNum(pObj) > 0 );
// consider the case of the PO
if ( Abc_ObjIsPo(pObj) )
{
lValueCur = Seq_NodeGetLValueP(Abc_ObjFanin0(pObj)) - Fi * Seq_ObjFaninL0(pObj);
return (lValueCur > Fi + p->fEpsilon)? SEQ_UPDATE_FAIL : SEQ_UPDATE_NO;
}
// get the new arrival time of the cut output
lValueNew = -ABC_INFINITY;
Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pLeaf, i )
{
SeqEdge = (unsigned)pLeaf;
pLeaf = Abc_NtkObj( pObj->pNtk, SeqEdge >> 8 );
lValueCur = Seq_NodeGetLValueP(pLeaf) - Fi * (SeqEdge & 255);
lValuePin = Abc_Int2Float( (int)Vec_PtrEntry(vDelays, i) );
if ( lValueNew < lValuePin + lValueCur )
lValueNew = lValuePin + lValueCur;
}
// compare
lValueOld = Seq_NodeGetLValueP( pObj );
if ( lValueNew <= lValueOld + p->fEpsilon )
return SEQ_UPDATE_NO;
// update the values
if ( lValueNew > lValueOld + p->fEpsilon )
Seq_NodeSetLValueP( pObj, lValueNew );
return SEQ_UPDATE_YES;
}
/**Function*************************************************************
Synopsis [Add sequential edges.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Seq_NodeRetimeSetLag_rec( Abc_Obj_t * pNode, char Lag )
{
Abc_Obj_t * pFanin;
if ( !Abc_AigNodeIsAnd(pNode) )
return;
Seq_NodeSetLag( pNode, Lag );
// consider the first fanin
pFanin = Abc_ObjFanin0(pNode);
if ( pFanin->fMarkA == 0 ) // internal node
Seq_NodeRetimeSetLag_rec( pFanin, Lag );
// consider the second fanin
pFanin = Abc_ObjFanin1(pNode);
if ( pFanin->fMarkA == 0 ) // internal node
Seq_NodeRetimeSetLag_rec( pFanin, Lag );
}
/**Function*************************************************************
Synopsis [Add sequential edges.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Seq_NodePrintInfo( Abc_Obj_t * pNode )
{
Abc_Seq_t * p = pNode->pNtk->pManFunc;
Abc_Obj_t * pFanin, * pObj, * pLeaf;
Vec_Ptr_t * vLeaves;
unsigned SeqEdge;
int i, Number;
// print the node
printf( " Node = %6d. LValue = %7.2f. Lag = %2d.\n",
pNode->Id, Seq_NodeGetLValueP(pNode), Seq_NodeGetLag(pNode) );
// find the number
Vec_PtrForEachEntry( Abc_Obj_t *, p->vMapAnds, pObj, Number )
if ( pObj == pNode )
break;
// get the leaves
vLeaves = Vec_VecEntry( p->vMapCuts, Number );
// print the leaves
Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pLeaf, i )
{
SeqEdge = (unsigned)pLeaf;
pFanin = Abc_NtkObj( pNode->pNtk, SeqEdge >> 8 );
// print the leaf
printf( " Fanin%d(%d) = %6d. LValue = %7.2f. Lag = %2d.\n", i, SeqEdge & 255,
pFanin->Id, Seq_NodeGetLValueP(pFanin), Seq_NodeGetLag(pFanin) );
}
}
/**Function*************************************************************
Synopsis [Add sequential edges.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Seq_NodePrintInfoPlus( Abc_Obj_t * pNode )
{
Abc_Obj_t * pFanout;
int i;
printf( "CENTRAL NODE:\n" );
Seq_NodePrintInfo( pNode );
Abc_ObjForEachFanout( pNode, pFanout, i )
{
printf( "FANOUT%d:\n", i );
Seq_NodePrintInfo( pFanout );
}
}
////////////////////////////////////////////////////////////////////////
/// END OF FILE ///
////////////////////////////////////////////////////////////////////////
ABC_NAMESPACE_IMPL_END