diff options
Diffstat (limited to 'src/base/seq/seqRetIter.c')
| -rw-r--r-- | src/base/seq/seqRetIter.c | 403 |
1 files changed, 403 insertions, 0 deletions
diff --git a/src/base/seq/seqRetIter.c b/src/base/seq/seqRetIter.c new file mode 100644 index 00000000..99c50914 --- /dev/null +++ b/src/base/seq/seqRetIter.c @@ -0,0 +1,403 @@ +/**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" + +//////////////////////////////////////////////////////////////////////// +/// 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( 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( p->vMapAnds, pNode, i ) +// Seq_NodeSetLValueP( pNode, Seq_NodeGetLValueP(pNode) - p->fEpsilon ); + + // save the retiming lags + // mark the nodes + Vec_PtrForEachEntry( p->vMapAnds, pNode, i ) + pNode->fMarkA = 1; + // process the nodes + Vec_StrFill( p->vLags, p->nSize, 0 ); + Vec_PtrForEachEntry( 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( 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( 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( 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( p->vMapAnds, pObj, Number ) + if ( pObj == pNode ) + break; + + // get the leaves + vLeaves = Vec_VecEntry( p->vMapCuts, Number ); + + // print the leaves + Vec_PtrForEachEntry( 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 /// +//////////////////////////////////////////////////////////////////////// + + |