summaryrefslogtreecommitdiffstats
path: root/src/base/seq/seqAigIter.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/base/seq/seqAigIter.c')
-rw-r--r--src/base/seq/seqAigIter.c268
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 ///
+////////////////////////////////////////////////////////////////////////
+
+
generated by cgit v1.2.3 (git 2.25.1) at 2024-08-04 05:23:23 +0000