/**CFile****************************************************************
FileName [seqMapIter.c]
SystemName [ABC: Logic synthesis and verification system.]
PackageName [Construction and manipulation of sequential AIGs.]
Synopsis [Iterative delay computation in SC mapping/retiming package.]
Author [Alan Mishchenko]
Affiliation [UC Berkeley]
Date [Ver. 1.0. Started - June 20, 2005.]
Revision [$Id: seqMapIter.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
***********************************************************************/
#include "seqInt.h"
#include "main.h"
#include "mio.h"
#include "mapperInt.h"
ABC_NAMESPACE_IMPL_START
// the internal procedures
static float Seq_MapRetimeDelayLagsInternal( Abc_Ntk_t * pNtk, int fVerbose );
static float Seq_MapRetimeSearch_rec( Abc_Ntk_t * pNtk, float FiMin, float FiMax, float Delta, int fVerbose );
static int Seq_MapRetimeForPeriod( Abc_Ntk_t * pNtk, float Fi, int fVerbose );
static int Seq_MapNodeUpdateLValue( Abc_Obj_t * pObj, float Fi, float DelayInv );
static float Seq_MapCollectNode_rec( Abc_Obj_t * pAnd, float FiBest, Vec_Ptr_t * vMapping, Vec_Vec_t * vMapCuts );
static void Seq_MapCanonicizeTruthTables( Abc_Ntk_t * pNtk );
extern Cut_Man_t * Abc_NtkSeqCuts( Abc_Ntk_t * pNtk, Cut_Params_t * pParams );
////////////////////////////////////////////////////////////////////////
/// FUNCTION DEFINITIONS ///
////////////////////////////////////////////////////////////////////////
/**Function*************************************************************
Synopsis [Computes the retiming lags for FPGA mapping.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Seq_MapRetimeDelayLags( Abc_Ntk_t * pNtk, int fVerbose )
{
Abc_Seq_t * p = pNtk->pManFunc;
Cut_Params_t Params, * pParams = &Params;
Abc_Obj_t * pObj;
float TotalArea;
int i, clk;
// set defaults for cut computation
memset( pParams, 0, sizeof(Cut_Params_t) );
pParams->nVarsMax = p->nVarsMax; // the max cut size ("k" of the k-feasible cuts)
pParams->nKeepMax = 1000; // the max number of cuts kept at a node
pParams->fTruth = 1; // compute truth tables
pParams->fFilter = 1; // filter dominated cuts
pParams->fSeq = 1; // compute sequential cuts
pParams->fVerbose = fVerbose; // the verbosiness flag
// compute the cuts
clk = clock();
p->pCutMan = Abc_NtkSeqCuts( pNtk, pParams );
p->timeCuts = clock() - clk;
if ( fVerbose )
Cut_ManPrintStats( p->pCutMan );
// compute canonical forms of the truth tables of the cuts
Seq_MapCanonicizeTruthTables( pNtk );
// compute area flows
// Seq_MapComputeAreaFlows( pNtk, fVerbose );
// compute the delays
clk = clock();
p->FiBestFloat = Seq_MapRetimeDelayLagsInternal( pNtk, fVerbose );
if ( p->FiBestFloat == 0.0 )
return 0;
p->timeDelay = clock() - clk;
/*
{
FILE * pTable;
pTable = fopen( "stats.txt", "a+" );
fprintf( pTable, "%s ", pNtk->pName );
fprintf( pTable, "%.2f ", p->FiBestFloat );
fprintf( pTable, "%.2f ", (float)(p->timeCuts)/(float)(CLOCKS_PER_SEC) );
fprintf( pTable, "%.2f ", (float)(p->timeDelay)/(float)(CLOCKS_PER_SEC) );
fprintf( pTable, "\n" );
fclose( pTable );
}
*/
// clean the marks
Abc_NtkForEachObj( pNtk, pObj, i )
assert( !pObj->fMarkA && !pObj->fMarkB );
// collect the nodes and cuts used in the mapping
p->vMapAnds = Vec_PtrAlloc( 1000 );
p->vMapCuts = Vec_VecAlloc( 1000 );
TotalArea = 0.0;
Abc_NtkForEachPo( pNtk, pObj, i )
TotalArea += Seq_MapCollectNode_rec( Abc_ObjChild0(pObj), p->FiBestFloat, p->vMapAnds, p->vMapCuts );
// clean the marks
Abc_NtkForEachObj( pNtk, pObj, i )
pObj->fMarkA = pObj->fMarkB = 0;
if ( fVerbose )
printf( "Total area = %6.2f.\n", TotalArea );
// remove the cuts
Cut_ManStop( p->pCutMan );
p->pCutMan = NULL;
return 1;
}
/**Function*************************************************************
Synopsis [Retimes AIG for optimal delay using Pan's algorithm.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
float Seq_MapRetimeDelayLagsInternal( Abc_Ntk_t * pNtk, int fVerbose )
{
Abc_Seq_t * p = pNtk->pManFunc;
Abc_Obj_t * pNode;
float FiMax, FiBest, Delta;
int i, RetValue;
char NodeLag;
assert( Abc_NtkIsSeq( pNtk ) );
// 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.0;
}
}
// get the upper bound on the clock period
FiMax = Delta * (5 + Seq_NtkLevelMax(pNtk));
Delta /= 2;
// make sure this clock period is feasible
if ( !Seq_MapRetimeForPeriod( pNtk, FiMax, fVerbose ) )
{
Vec_StrFill( p->vLags, p->nSize, 0 );
Vec_StrFill( p->vLagsN, 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
FiBest = Seq_MapRetimeSearch_rec( pNtk, 0.0, FiMax, Delta, fVerbose );
// recompute the best l-values
RetValue = Seq_MapRetimeForPeriod( pNtk, FiBest, fVerbose );
assert( RetValue );
// fix the problem with non-converged delays
Abc_AigForEachAnd( pNtk, pNode, i )
{
if ( Seq_NodeGetLValueP(pNode) < -ABC_INFINITY/2 )
Seq_NodeSetLValueP( pNode, 0 );
if ( Seq_NodeGetLValueN(pNode) < -ABC_INFINITY/2 )
Seq_NodeSetLValueN( pNode, 0 );
}
// write the retiming lags for both phases of each node
Vec_StrFill( p->vLags, p->nSize, 0 );
Vec_StrFill( p->vLagsN, p->nSize, 0 );
Abc_AigForEachAnd( pNtk, pNode, i )
{
NodeLag = Seq_NodeComputeLagFloat( Seq_NodeGetLValueP(pNode), FiBest );
Seq_NodeSetLag( pNode, NodeLag );
NodeLag = Seq_NodeComputeLagFloat( Seq_NodeGetLValueN(pNode), FiBest );
Seq_NodeSetLagN( pNode, NodeLag );
//printf( "%6d=(%d,%d) ", pNode->Id, Seq_NodeGetLag(pNode), Seq_NodeGetLagN(pNode) );
// if ( Seq_NodeGetLag(pNode) != Seq_NodeGetLagN(pNode) )
// {
//printf( "%6d=(%d,%d) ", pNode->Id, Seq_NodeGetLag(pNode), Seq_NodeGetLagN(pNode) );
// }
}
//printf( "\n\n" );
// print the result
if ( fVerbose )
printf( "The best clock period after mapping/retiming is %6.2f.\n", FiBest );
return FiBest;
}
/**Function*************************************************************
Synopsis [Performs binary search for the optimal clock period.]
Description [Assumes that FiMin is infeasible while FiMax is feasible.]
SideEffects []
SeeAlso []
***********************************************************************/
float Seq_MapRetimeSearch_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_MapRetimeForPeriod( pNtk, Median, fVerbose ) )
return Seq_MapRetimeSearch_rec( pNtk, FiMin, Median, Delta, fVerbose ); // Median is feasible
else
return Seq_MapRetimeSearch_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_MapRetimeForPeriod( Abc_Ntk_t * pNtk, float Fi, int fVerbose )
{
Abc_Seq_t * p = pNtk->pManFunc;
Abc_Obj_t * pObj;
float DelayInv = Mio_LibraryReadDelayInvMax(Abc_FrameReadLibGen());
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 ) );
Vec_IntFill( p->vLValuesN, p->nSize, Abc_Float2Int( (float)-ABC_INFINITY ) );
Vec_StrFill( p->vUses, p->nSize, 0 );
// set l-values of constants and PIs
pObj = Abc_NtkObj( pNtk, 0 );
Seq_NodeSetLValueP( pObj, 0.0 );
Seq_NodeSetLValueN( pObj, 0.0 );
Abc_NtkForEachPi( pNtk, pObj, i )
{
Seq_NodeSetLValueP( pObj, 0.0 );
Seq_NodeSetLValueN( pObj, DelayInv );
}
// update all values iteratively
Counter = 0;
for ( c = 0; c < p->nMaxIters; c++ )
{
fChange = 0;
Abc_AigForEachAnd( pNtk, pObj, i )
{
Counter++;
RetValue = Seq_MapNodeUpdateLValue( pObj, Fi, DelayInv );
if ( RetValue == SEQ_UPDATE_YES )
fChange = 1;
}
Abc_NtkForEachPo( pNtk, pObj, i )
{
RetValue = Seq_MapNodeUpdateLValue( pObj, Fi, DelayInv );
if ( RetValue == SEQ_UPDATE_FAIL )
break;
}
if ( RetValue == SEQ_UPDATE_FAIL )
break;
if ( fChange == 0 )
break;
//printf( "\n\n" );
}
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 cut.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
float Seq_MapSuperGetArrival( Abc_Obj_t * pObj, float Fi, Seq_Match_t * pMatch, float DelayMax )
{
Abc_Seq_t * p = pObj->pNtk->pManFunc;
Abc_Obj_t * pFanin;
float lValueCur, lValueMax;
int i;
lValueMax = -ABC_INFINITY;
for ( i = pMatch->pCut->nLeaves - 1; i >= 0; i-- )
{
// get the arrival time of the fanin
pFanin = Abc_NtkObj( pObj->pNtk, pMatch->pCut->pLeaves[i] >> 8 );
if ( pMatch->uPhase & (1 << i) )
lValueCur = Seq_NodeGetLValueN(pFanin) - Fi * (pMatch->pCut->pLeaves[i] & 255);
else
lValueCur = Seq_NodeGetLValueP(pFanin) - Fi * (pMatch->pCut->pLeaves[i] & 255);
// add the arrival time of this pin
if ( lValueMax < lValueCur + pMatch->pSuper->tDelaysR[i].Worst )
lValueMax = lValueCur + pMatch->pSuper->tDelaysR[i].Worst;
if ( lValueMax < lValueCur + pMatch->pSuper->tDelaysF[i].Worst )
lValueMax = lValueCur + pMatch->pSuper->tDelaysF[i].Worst;
if ( lValueMax > DelayMax + p->fEpsilon )
return ABC_INFINITY;
}
return lValueMax;
}
/**Function*************************************************************
Synopsis [Computes the l-value of the cut.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
float Seq_MapNodeComputeCut( Abc_Obj_t * pObj, Cut_Cut_t * pCut, int fCompl, float Fi, Seq_Match_t * pMatchBest )
{
Seq_Match_t Match, * pMatchCur = &Match;
Abc_Seq_t * p = pObj->pNtk->pManFunc;
Map_Super_t * pSuper, * pSuperList;
unsigned uCanon[2];
float lValueBest, lValueCur;
int i;
assert( pCut->nLeaves < 6 );
// get the canonical truth table of this cut
uCanon[0] = uCanon[1] = (fCompl? pCut->uCanon0 : pCut->uCanon1);
if ( uCanon[0] == 0 || ~uCanon[0] == 0 )
{
if ( pMatchBest )
{
memset( pMatchBest, 0, sizeof(Seq_Match_t) );
pMatchBest->pCut = pCut;
}
return (float)0.0;
}
// match the given phase of the cut
pSuperList = Map_SuperTableLookupC( p->pSuperLib, uCanon );
// compute the arrival times of each supergate
lValueBest = ABC_INFINITY;
for ( pSuper = pSuperList; pSuper; pSuper = pSuper->pNext )
{
// create the match
pMatchCur->pCut = pCut;
pMatchCur->pSuper = pSuper;
// get the phase
for ( i = 0; i < (int)pSuper->nPhases; i++ )
{
pMatchCur->uPhase = (fCompl? pCut->Num0 : pCut->Num1) ^ pSuper->uPhases[i];
// find the arrival time of this match
lValueCur = Seq_MapSuperGetArrival( pObj, Fi, pMatchCur, lValueBest );
if ( lValueBest > lValueCur )//&& lValueCur > -ABC_INFINITY/2 )
{
lValueBest = lValueCur;
if ( pMatchBest )
*pMatchBest = *pMatchCur;
}
}
}
// assert( lValueBest < ABC_INFINITY/2 );
return lValueBest;
}
/**Function*************************************************************
Synopsis [Computes the l-value of the node.]
Description [The node can be internal or a PO.]
SideEffects []
SeeAlso []
***********************************************************************/
float Seq_MapNodeComputePhase( Abc_Obj_t * pObj, int fCompl, float Fi, Seq_Match_t * pMatchBest )
{
Seq_Match_t Match, * pMatchCur = &Match;
Cut_Cut_t * pList, * pCut;
float lValueBest, lValueCut;
// get the list of cuts
pList = Abc_NodeReadCuts( Seq_NodeCutMan(pObj), pObj );
// get the arrival time of the best non-trivial cut
lValueBest = ABC_INFINITY;
for ( pCut = pList->pNext; pCut; pCut = pCut->pNext )
{
lValueCut = Seq_MapNodeComputeCut( pObj, pCut, fCompl, Fi, pMatchBest? pMatchCur : NULL );
if ( lValueBest > lValueCut )
{
lValueBest = lValueCut;
if ( pMatchBest )
*pMatchBest = *pMatchCur;
}
}
// assert( lValueBest < ABC_INFINITY/2 );
return lValueBest;
}
/**Function*************************************************************
Synopsis [Computes the l-value of the node.]
Description [The node can be internal or a PO.]
SideEffects []
SeeAlso []
***********************************************************************/
int Seq_MapNodeUpdateLValue( Abc_Obj_t * pObj, float Fi, float DelayInv )
{
Abc_Seq_t * p = pObj->pNtk->pManFunc;
Cut_Cut_t * pList;
char Use;
float lValueOld0, lValueOld1, lValue0, lValue1, lValue;
assert( !Abc_ObjIsPi(pObj) );
assert( Abc_ObjFaninNum(pObj) > 0 );
// consider the case of the PO
if ( Abc_ObjIsPo(pObj) )
{
if ( Abc_ObjFaninC0(pObj) ) // PO requires negative polarity
lValue = Seq_NodeGetLValueN(Abc_ObjFanin0(pObj)) - Fi * Seq_ObjFaninL0(pObj);
else
lValue = Seq_NodeGetLValueP(Abc_ObjFanin0(pObj)) - Fi * Seq_ObjFaninL0(pObj);
return (lValue > Fi + p->fEpsilon)? SEQ_UPDATE_FAIL : SEQ_UPDATE_NO;
}
// get the cuts
pList = Abc_NodeReadCuts( Seq_NodeCutMan(pObj), pObj );
if ( pList == NULL )
return SEQ_UPDATE_NO;
// compute the arrival time of both phases
lValue0 = Seq_MapNodeComputePhase( pObj, 1, Fi, NULL );
lValue1 = Seq_MapNodeComputePhase( pObj, 0, Fi, NULL );
// consider the case when negative phase is too slow
if ( lValue0 > lValue1 + DelayInv + p->fEpsilon )
lValue0 = lValue1 + DelayInv, Use = 2;
else if ( lValue1 > lValue0 + DelayInv + p->fEpsilon )
lValue1 = lValue0 + DelayInv, Use = 1;
else
Use = 3;
// set the uses of the phases
Seq_NodeSetUses( pObj, Use );
// get the old arrival times
lValueOld0 = Seq_NodeGetLValueN(pObj);
lValueOld1 = Seq_NodeGetLValueP(pObj);
// compare
if ( lValue0 <= lValueOld0 + p->fEpsilon && lValue1 <= lValueOld1 + p->fEpsilon )
return SEQ_UPDATE_NO;
assert( lValue0 < ABC_INFINITY/2 );
assert( lValue1 < ABC_INFINITY/2 );
// update the values
if ( lValue0 > lValueOld0 + p->fEpsilon )
Seq_NodeSetLValueN( pObj, lValue0 );
if ( lValue1 > lValueOld1 + p->fEpsilon )
Seq_NodeSetLValueP( pObj, lValue1 );
//printf( "%6d=(%4.2f,%4.2f) ", pObj->Id, Seq_NodeGetLValueP(pObj), Seq_NodeGetLValueN(pObj) );
return SEQ_UPDATE_YES;
}
/**Function*************************************************************
Synopsis [Derives the parameters of the best mapping/retiming for one node.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
float Seq_MapCollectNode_rec( Abc_Obj_t * pAnd, float FiBest, Vec_Ptr_t * vMapping, Vec_Vec_t * vMapCuts )
{
Seq_Match_t * pMatch;
Abc_Obj_t * pFanin;
int k, fCompl, Use;
float AreaInv = Mio_LibraryReadAreaInv(Abc_FrameReadLibGen());
float Area;
// get the polarity of the node
fCompl = Abc_ObjIsComplement(pAnd);
pAnd = Abc_ObjRegular(pAnd);
// skip visited nodes
if ( !fCompl )
{ // need the positive polarity
if ( pAnd->fMarkA )
return 0.0;
pAnd->fMarkA = 1;
}
else
{ // need the negative polarity
if ( pAnd->fMarkB )
return 0.0;
pAnd->fMarkB = 1;
}
// skip if this is a PI or a constant
if ( !Abc_AigNodeIsAnd(pAnd) )
{
if ( Abc_ObjIsPi(pAnd) && fCompl )
return AreaInv;
return 0.0;
}
// check the uses of this node
Use = Seq_NodeGetUses( pAnd );
if ( !fCompl && Use == 1 ) // the pos phase is required; only the neg phase is used
{
Area = Seq_MapCollectNode_rec( Abc_ObjNot(pAnd), FiBest, vMapping, vMapCuts );
return Area + AreaInv;
}
if ( fCompl && Use == 2 ) // the neg phase is required; only the pos phase is used
{
Area = Seq_MapCollectNode_rec( pAnd, FiBest, vMapping, vMapCuts );
return Area + AreaInv;
}
// both phases are used; the needed one can be selected
// get the best match
pMatch = ALLOC( Seq_Match_t, 1 );
memset( pMatch, 1, sizeof(Seq_Match_t) );
Seq_MapNodeComputePhase( pAnd, fCompl, FiBest, pMatch );
pMatch->pAnd = pAnd;
pMatch->fCompl = fCompl;
pMatch->fCutInv = pMatch->pCut->fCompl;
pMatch->PolUse = Use;
// call for the fanin cuts
Area = pMatch->pSuper? pMatch->pSuper->Area : (float)0.0;
for ( k = 0; k < (int)pMatch->pCut->nLeaves; k++ )
{
pFanin = Abc_NtkObj( pAnd->pNtk, pMatch->pCut->pLeaves[k] >> 8 );
if ( pMatch->uPhase & (1 << k) )
pFanin = Abc_ObjNot( pFanin );
Area += Seq_MapCollectNode_rec( pFanin, FiBest, vMapping, vMapCuts );
}
// add this node
Vec_PtrPush( vMapping, pMatch );
for ( k = 0; k < (int)pMatch->pCut->nLeaves; k++ )
Vec_VecPush( vMapCuts, Vec_PtrSize(vMapping)-1, (void *)pMatch->pCut->pLeaves[k] );
// the cut will become unavailable when the cuts are deallocated
pMatch->pCut = NULL;
return Area;
}
/**Function*************************************************************
Synopsis [Computes the canonical versions of the truth tables.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Seq_MapCanonicizeTruthTables( Abc_Ntk_t * pNtk )
{
Abc_Obj_t * pObj;
Cut_Cut_t * pCut, * pList;
int i;
Abc_AigForEachAnd( pNtk, pObj, i )
{
pList = Abc_NodeReadCuts( Seq_NodeCutMan(pObj), pObj );
if ( pList == NULL )
continue;
for ( pCut = pList->pNext; pCut; pCut = pCut->pNext )
Cut_TruthNCanonicize( pCut );
}
}
////////////////////////////////////////////////////////////////////////
/// END OF FILE ///
////////////////////////////////////////////////////////////////////////
ABC_NAMESPACE_IMPL_END