| /**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 |
| |
