summaryrefslogtreecommitdiffstats
path: root/src/base/seq/seqRetIter.c
diff options
context:
space:
mode:
authorAlan Mishchenko <alanmi@berkeley.edu>2008-01-30 08:01:00 -0800
committerAlan Mishchenko <alanmi@berkeley.edu>2008-01-30 08:01:00 -0800
commit4d30a1e4f1edecff86d5066ce4653a370e59e5e1 (patch)
tree366355938a4af0a92f848841ac65374f338d691b /src/base/seq/seqRetIter.c
parent6537f941887b06e588d3acfc97b5fdf48875cc4e (diff)
downloadabc-4d30a1e4f1edecff86d5066ce4653a370e59e5e1.tar.gz
abc-4d30a1e4f1edecff86d5066ce4653a370e59e5e1.tar.bz2
abc-4d30a1e4f1edecff86d5066ce4653a370e59e5e1.zip
Version abc80130
Diffstat (limited to 'src/base/seq/seqRetIter.c')
-rw-r--r--src/base/seq/seqRetIter.c403
1 files changed, 0 insertions, 403 deletions
diff --git a/src/base/seq/seqRetIter.c b/src/base/seq/seqRetIter.c
deleted file mode 100644
index 99c50914..00000000
--- a/src/base/seq/seqRetIter.c
+++ /dev/null
@@ -1,403 +0,0 @@
-/**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 ///
-////////////////////////////////////////////////////////////////////////
-
-