diff options
author | Alan Mishchenko <alanmi@berkeley.edu> | 2007-10-01 08:01:00 -0700 |
---|---|---|
committer | Alan Mishchenko <alanmi@berkeley.edu> | 2007-10-01 08:01:00 -0700 |
commit | 4812c90424dfc40d26725244723887a2d16ddfd9 (patch) | |
tree | b32ace96e7e2d84d586e09ba605463b6f49c3271 /src/base/seq/seqAigIter.c | |
parent | e54d9691616b9a0326e2fdb3156bb4eeb8abfcd7 (diff) | |
download | abc-4812c90424dfc40d26725244723887a2d16ddfd9.tar.gz abc-4812c90424dfc40d26725244723887a2d16ddfd9.tar.bz2 abc-4812c90424dfc40d26725244723887a2d16ddfd9.zip |
Version abc71001
Diffstat (limited to 'src/base/seq/seqAigIter.c')
-rw-r--r-- | src/base/seq/seqAigIter.c | 268 |
1 files changed, 268 insertions, 0 deletions
diff --git a/src/base/seq/seqAigIter.c b/src/base/seq/seqAigIter.c new file mode 100644 index 00000000..392638b8 --- /dev/null +++ b/src/base/seq/seqAigIter.c @@ -0,0 +1,268 @@ +/**CFile**************************************************************** + + FileName [seqRetIter.c] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [Construction and manipulation of sequential AIGs.] + + Synopsis [The iterative L-Value computation for retiming procedures.] + + 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" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +// the internal procedures +static int Seq_RetimeSearch_rec( Abc_Ntk_t * pNtk, int FiMin, int FiMax, int fVerbose ); +static int Seq_RetimeForPeriod( Abc_Ntk_t * pNtk, int Fi, int fVerbose ); +static int Seq_RetimeNodeUpdateLValue( Abc_Obj_t * pObj, int Fi ); + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Retimes AIG for optimal delay using Pan's algorithm.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Seq_AigRetimeDelayLags( Abc_Ntk_t * pNtk, int fVerbose ) +{ + Abc_Seq_t * p = pNtk->pManFunc; + Abc_Obj_t * pNode; + int i, FiMax, RetValue, clk, clkIter; + char NodeLag; + + assert( Abc_NtkIsSeq( pNtk ) ); + + // get the upper bound on the clock period + FiMax = 2 + Seq_NtkLevelMax(pNtk); + + // make sure this clock period is feasible + if ( !Seq_RetimeForPeriod( pNtk, FiMax, fVerbose ) ) + { + Vec_StrFill( p->vLags, p->nSize, 0 ); + 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 +clk = clock(); + p->FiBestInt = Seq_RetimeSearch_rec( pNtk, 0, FiMax, fVerbose ); +clkIter = clock() - clk; + + // recompute the best l-values + RetValue = Seq_RetimeForPeriod( pNtk, p->FiBestInt, fVerbose ); + assert( RetValue ); + + // fix the problem with non-converged delays + Abc_AigForEachAnd( pNtk, pNode, i ) + if ( Seq_NodeGetLValue(pNode) < -ABC_INFINITY/2 ) + Seq_NodeSetLValue( pNode, 0 ); + + // write the retiming lags + Vec_StrFill( p->vLags, p->nSize, 0 ); + Abc_AigForEachAnd( pNtk, pNode, i ) + { + NodeLag = Seq_NodeComputeLag( Seq_NodeGetLValue(pNode), p->FiBestInt ); + Seq_NodeSetLag( pNode, NodeLag ); + } + + // print the result + if ( fVerbose ) + printf( "The best clock period is %3d.\n", p->FiBestInt ); + +/* + printf( "lvalues and lags : " ); + Abc_AigForEachAnd( pNtk, pNode, i ) + printf( "%d=%d(%d) ", pNode->Id, Seq_NodeGetLValue(pNode), Seq_NodeGetLag(pNode) ); + printf( "\n" ); +*/ +/* + { + FILE * pTable; + pTable = fopen( "stats.txt", "a+" ); + fprintf( pTable, "%s ", pNtk->pName ); + fprintf( pTable, "%d ", FiBest ); + fprintf( pTable, "\n" ); + fclose( pTable ); + } +*/ +/* + { + FILE * pTable; + pTable = fopen( "stats.txt", "a+" ); + fprintf( pTable, "%s ", pNtk->pName ); + fprintf( pTable, "%.2f ", (float)(p->timeCuts)/(float)(CLOCKS_PER_SEC) ); + fprintf( pTable, "%.2f ", (float)(clkIter)/(float)(CLOCKS_PER_SEC) ); + fprintf( pTable, "\n" ); + fclose( pTable ); + } +*/ + return 1; + +} + +/**Function************************************************************* + + Synopsis [Performs binary search for the optimal clock period.] + + Description [Assumes that FiMin is infeasible while FiMax is feasible.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Seq_RetimeSearch_rec( Abc_Ntk_t * pNtk, int FiMin, int FiMax, int fVerbose ) +{ + int Median; + assert( FiMin < FiMax ); + if ( FiMin + 1 == FiMax ) + return FiMax; + Median = FiMin + (FiMax - FiMin)/2; + if ( Seq_RetimeForPeriod( pNtk, Median, fVerbose ) ) + return Seq_RetimeSearch_rec( pNtk, FiMin, Median, fVerbose ); // Median is feasible + else + return Seq_RetimeSearch_rec( pNtk, Median, FiMax, fVerbose ); // Median is infeasible +} + +/**Function************************************************************* + + Synopsis [Returns 1 if retiming with this clock period is feasible.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Seq_RetimeForPeriod( Abc_Ntk_t * pNtk, int Fi, int fVerbose ) +{ + Abc_Seq_t * p = pNtk->pManFunc; + 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_INFINITY ); + + // set l-values of constants and PIs + pObj = Abc_NtkObj( pNtk, 0 ); + Seq_NodeSetLValue( pObj, 0 ); + Abc_NtkForEachPi( pNtk, pObj, i ) + Seq_NodeSetLValue( pObj, 0 ); + + // update all values iteratively + Counter = 0; + for ( c = 0; c < p->nMaxIters; c++ ) + { + fChange = 0; + Abc_AigForEachAnd( pNtk, pObj, i ) + { + Counter++; + if ( Seq_NodeCutMan(pObj) ) + RetValue = Seq_FpgaNodeUpdateLValue( pObj, Fi ); + else + RetValue = Seq_RetimeNodeUpdateLValue( pObj, Fi ); + if ( RetValue == SEQ_UPDATE_YES ) + fChange = 1; + } + Abc_NtkForEachPo( pNtk, pObj, i ) + { + if ( Seq_NodeCutMan(pObj) ) + RetValue = Seq_FpgaNodeUpdateLValue( pObj, Fi ); + else + RetValue = Seq_RetimeNodeUpdateLValue( pObj, Fi ); + 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 = %3d. Iterations = %3d. Updates = %10d. Infeasible %s\n", Fi, c, Counter, pReason ); + else + printf( "Period = %3d. Iterations = %3d. Updates = %10d. Feasible\n", Fi, c, Counter ); + } +/* + // check if any AND gates have infinite delay + Counter = 0; + Abc_AigForEachAnd( pNtk, pObj, i ) + Counter += (Seq_NodeGetLValue(pObj) < -ABC_INFINITY/2); + if ( Counter > 0 ) + printf( "Warning: %d internal nodes have wrong l-values!\n", 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_RetimeNodeUpdateLValue( Abc_Obj_t * pObj, int Fi ) +{ + int lValueNew, lValueOld, lValue0, lValue1; + assert( !Abc_ObjIsPi(pObj) ); + assert( Abc_ObjFaninNum(pObj) > 0 ); + lValue0 = Seq_NodeGetLValue(Abc_ObjFanin0(pObj)) - Fi * Seq_ObjFaninL0(pObj); + if ( Abc_ObjIsPo(pObj) ) + return (lValue0 > Fi)? SEQ_UPDATE_FAIL : SEQ_UPDATE_NO; + if ( Abc_ObjFaninNum(pObj) == 2 ) + lValue1 = Seq_NodeGetLValue(Abc_ObjFanin1(pObj)) - Fi * Seq_ObjFaninL1(pObj); + else + lValue1 = -ABC_INFINITY; + lValueNew = 1 + ABC_MAX( lValue0, lValue1 ); + lValueOld = Seq_NodeGetLValue(pObj); +// if ( lValueNew == lValueOld ) + if ( lValueNew <= lValueOld ) + return SEQ_UPDATE_NO; + Seq_NodeSetLValue( pObj, lValueNew ); + return SEQ_UPDATE_YES; +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + |