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