diff options
Diffstat (limited to 'src/opt/sfm/sfmMit.c')
| -rw-r--r-- | src/opt/sfm/sfmMit.c | 483 |
1 files changed, 483 insertions, 0 deletions
diff --git a/src/opt/sfm/sfmMit.c b/src/opt/sfm/sfmMit.c new file mode 100644 index 00000000..64ea0c0f --- /dev/null +++ b/src/opt/sfm/sfmMit.c @@ -0,0 +1,483 @@ +/**CFile**************************************************************** + + FileName [sfmMit.c] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [SAT-based optimization using internal don't-cares.] + + Synopsis [Timing manager.] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - June 20, 2005.] + + Revision [$Id: sfmMit.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "sfmInt.h" + +ABC_NAMESPACE_IMPL_START + + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +struct Sfm_Mit_t_ +{ + // external + Mio_Library_t * pLib; // library + Scl_Con_t * pExt; // external timing + Abc_Ntk_t * pNtk; // mapped network + int Delay; // the largest delay + int DeltaCrit; // critical delay delta + // timing info + Vec_Int_t vTimArrs; // arrivals (rise/fall) + Vec_Int_t vTimReqs; // required (rise/fall) + Vec_Int_t vTimSlews; // slews (rise/fall) + Vec_Int_t vTimLoads; // loads (rise/fall) + // timing edges + Vec_Int_t vObjOffs; // object offsets + Vec_Int_t vTimEdges; // edge timings (rise/fall) + // incremental timing + Vec_Wec_t vLevels; // levels + // critical path + Vec_Int_t vPath; // critical path + Vec_Wrd_t vSortData; // node priority order +}; + +static inline int * Sfm_MitArrId( Sfm_Mit_t * p, int Id ) { return Vec_IntEntryP( &p->vTimArrs, Abc_Var2Lit(Id, 0) ); } +static inline int * Sfm_MitReqId( Sfm_Mit_t * p, int Id ) { return Vec_IntEntryP( &p->vTimReqs, Abc_Var2Lit(Id, 0) ); } +static inline int * Sfm_MitSlewId( Sfm_Mit_t * p, int Id ) { return Vec_IntEntryP( &p->vTimSlews, Abc_Var2Lit(Id, 0) ); } +static inline int * Sfm_MitLoadId( Sfm_Mit_t * p, int Id ) { return Vec_IntEntryP( &p->vTimLoads, Abc_Var2Lit(Id, 0) ); } + +static inline int * Sfm_MitArr( Sfm_Mit_t * p, Abc_Obj_t * pNode ) { return Vec_IntEntryP( &p->vTimArrs, Abc_Var2Lit(Abc_ObjId(pNode), 0) ); } +static inline int * Sfm_MitReq( Sfm_Mit_t * p, Abc_Obj_t * pNode ) { return Vec_IntEntryP( &p->vTimReqs, Abc_Var2Lit(Abc_ObjId(pNode), 0) ); } +static inline int * Sfm_MitSlew( Sfm_Mit_t * p, Abc_Obj_t * pNode ) { return Vec_IntEntryP( &p->vTimSlews, Abc_Var2Lit(Abc_ObjId(pNode), 0) ); } +static inline int * Sfm_MitLoad( Sfm_Mit_t * p, Abc_Obj_t * pNode ) { return Vec_IntEntryP( &p->vTimLoads, Abc_Var2Lit(Abc_ObjId(pNode), 0) ); } + +static inline int Sfm_MitArrMaxId( Sfm_Mit_t * p, int Id ) { int * a = Sfm_MitArrId(p, Id); return Abc_MaxInt(a[0], a[1]); } + +static inline int Sfm_MitArrMax( Sfm_Mit_t * p, Abc_Obj_t * pNode ) { int * a = Sfm_MitArr(p, pNode); return Abc_MaxInt(a[0], a[1]); } +static inline void Sfm_MitSetReq( Sfm_Mit_t * p, Abc_Obj_t * pNode, int t ) { int * r = Sfm_MitReq(p, pNode); r[0] = r[1] = t; } +static inline int Sfm_MitSlack( Sfm_Mit_t * p, Abc_Obj_t * pNode ) { int * r = Sfm_MitReq(p, pNode), * a = Sfm_MitArr(p, pNode); return Abc_MinInt(r[0]-a[0], r[1]-a[1]); } + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void Sfm_MitEdgeArrival( Sfm_Mit_t * p, Mio_Pin_t * pPin, int * pTimeIn, int * pTimeOut ) +{ + Mio_PinPhase_t PinPhase = Mio_PinReadPhase(pPin); + int tDelayBlockRise = (int)(MIO_NUM*Mio_PinReadDelayBlockRise(pPin)); + int tDelayBlockFall = (int)(MIO_NUM*Mio_PinReadDelayBlockFall(pPin)); + if ( PinPhase != MIO_PHASE_INV ) // NONINV phase is present + { + pTimeOut[0] = Abc_MaxInt( pTimeOut[0], pTimeIn[0] + tDelayBlockRise ); + pTimeOut[1] = Abc_MaxInt( pTimeOut[1], pTimeIn[1] + tDelayBlockFall ); + } + if ( PinPhase != MIO_PHASE_NONINV ) // INV phase is present + { + pTimeOut[0] = Abc_MaxInt( pTimeOut[0], pTimeIn[1] + tDelayBlockRise ); + pTimeOut[1] = Abc_MaxInt( pTimeOut[1], pTimeIn[0] + tDelayBlockFall ); + } +} +static inline void Sfm_MitGateArrival( Sfm_Mit_t * p, Mio_Gate_t * pGate, int ** pTimesIn, int * pTimeOut ) +{ + Mio_Pin_t * pPin; int i = 0; + pTimeOut[0] = pTimeOut[1] = 0; + Mio_GateForEachPin( pGate, pPin ) + Sfm_MitEdgeArrival( p, pPin, pTimesIn[i++], pTimeOut ); + assert( i == Mio_GateReadPinNum(pGate) ); +} +static inline void Sfm_MitNodeArrival( Sfm_Mit_t * p, Abc_Obj_t * pNode ) +{ + int i, iFanin, * pTimesIn[6]; + int * pTimeOut = Sfm_MitArr(p, pNode); + assert( Abc_ObjFaninNum(pNode) <= 6 ); + Abc_ObjForEachFaninId( pNode, iFanin, i ) + pTimesIn[i] = Sfm_MitArrId( p, iFanin ); + Sfm_MitGateArrival( p, (Mio_Gate_t *)pNode->pData, pTimesIn, pTimeOut ); +} + +static inline void Sfm_MitEdgeRequired( Sfm_Mit_t * p, Mio_Pin_t * pPin, int * pTimeIn, int * pTimeOut ) +{ + Mio_PinPhase_t PinPhase = Mio_PinReadPhase(pPin); + int tDelayBlockRise = (int)(MIO_NUM*Mio_PinReadDelayBlockRise(pPin)); + int tDelayBlockFall = (int)(MIO_NUM*Mio_PinReadDelayBlockFall(pPin)); + if ( PinPhase != MIO_PHASE_INV ) // NONINV phase is present + { + pTimeIn[0] = Abc_MinInt( pTimeIn[0], pTimeOut[0] - tDelayBlockRise ); + pTimeIn[1] = Abc_MinInt( pTimeIn[1], pTimeOut[1] - tDelayBlockFall ); + } + if ( PinPhase != MIO_PHASE_NONINV ) // INV phase is present + { + pTimeIn[0] = Abc_MinInt( pTimeIn[0], pTimeOut[1] - tDelayBlockRise ); + pTimeIn[1] = Abc_MinInt( pTimeIn[1], pTimeOut[0] - tDelayBlockFall ); + } +} +static inline void Sfm_MitGateRequired( Sfm_Mit_t * p, Mio_Gate_t * pGate, int ** pTimesIn, int * pTimeOut ) +{ + Mio_Pin_t * pPin; int i = 0; + Mio_GateForEachPin( pGate, pPin ) + Sfm_MitEdgeRequired( p, pPin, pTimesIn[i++], pTimeOut ); + assert( i == Mio_GateReadPinNum(pGate) ); +} +void Sfm_MitNodeRequired( Sfm_Mit_t * p, Abc_Obj_t * pNode ) +{ + int i, iFanin, * pTimesIn[6]; + int * pTimeOut = Sfm_MitReq(p, pNode); + assert( Abc_ObjFaninNum(pNode) <= 6 ); + Abc_ObjForEachFaninId( pNode, iFanin, i ) + pTimesIn[i] = Sfm_MitReqId( p, iFanin ); + Sfm_MitGateRequired( p, (Mio_Gate_t *)pNode->pData, pTimesIn, pTimeOut ); +} + + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Sfm_MitCriticalPath_int( Sfm_Mit_t * p, Abc_Obj_t * pObj, Vec_Int_t * vPath, int SlackMax ) +{ + Abc_Obj_t * pNext; int i; + if ( Abc_NodeIsTravIdCurrent( pObj ) ) + return; + Abc_NodeSetTravIdCurrent( pObj ); + assert( Abc_ObjIsNode(pObj) ); + Abc_ObjForEachFanin( pObj, pNext, i ) + { + if ( Abc_ObjIsCi(pNext) || Abc_ObjFaninNum(pNext) == 0 ) + continue; + assert( Abc_ObjIsNode(pNext) ); + if ( Sfm_MitSlack(p, pNext) <= SlackMax ) + Sfm_MitCriticalPath_int( p, pNext, vPath, SlackMax ); + } + if ( Abc_ObjFaninNum(pObj) > 0 ) + Vec_IntPush( vPath, Abc_ObjId(pObj) ); +} +int Sfm_MitCriticalPath( Sfm_Mit_t * p, int Window ) +{ + int i, SlackMax = p->Delay * Window / 100; + Abc_Obj_t * pObj, * pNext; + Vec_IntClear( &p->vPath ); + Abc_NtkIncrementTravId( p->pNtk ); + Abc_NtkForEachCo( p->pNtk, pObj, i ) + { + pNext = Abc_ObjFanin0(pObj); + if ( Abc_ObjIsCi(pNext) || Abc_ObjFaninNum(pNext) == 0 ) + continue; + assert( Abc_ObjIsNode(pNext) ); + if ( Sfm_MitSlack(p, pNext) <= SlackMax ) + Sfm_MitCriticalPath_int( p, pNext, &p->vPath, SlackMax ); + } + return Vec_IntSize(&p->vPath); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Sfm_MitTrace( Sfm_Mit_t * p ) +{ + Abc_Obj_t * pObj; int i, Delay = 0; + Vec_Ptr_t * vNodes = Abc_NtkDfs( p->pNtk, 1 ); + Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, i ) + Sfm_MitNodeArrival( p, pObj ); + Abc_NtkForEachCo( p->pNtk, pObj, i ) + Delay = Abc_MaxInt( Delay, Sfm_MitArrMax(p, Abc_ObjFanin0(pObj)) ); + Vec_IntFill( &p->vTimReqs, 2*Abc_NtkObjNumMax(p->pNtk), ABC_INFINITY ); + Abc_NtkForEachCo( p->pNtk, pObj, i ) + Sfm_MitSetReq( p, Abc_ObjFanin0(pObj), Delay ); + Vec_PtrForEachEntryReverse( Abc_Obj_t *, vNodes, pObj, i ) + Sfm_MitNodeRequired( p, pObj ); + Vec_PtrFree( vNodes ); + return Delay; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Sfm_Mit_t * Sfm_MitStart( Mio_Library_t * pLib, Scl_Con_t * pExt, Abc_Ntk_t * pNtk, int DeltaCrit ) +{ +// Abc_Obj_t * pObj; int i; + Sfm_Mit_t * p = ABC_CALLOC( Sfm_Mit_t, 1 ); + p->pLib = pLib; + p->pExt = pExt; + p->pNtk = pNtk; + Vec_IntFill( &p->vTimArrs, 3*Abc_NtkObjNumMax(pNtk), 0 ); + Vec_IntFill( &p->vTimReqs, 3*Abc_NtkObjNumMax(pNtk), 0 ); +// Vec_IntFill( &p->vTimSlews, 3*Abc_NtkObjNumMax(pNtk), 0 ); +// Vec_IntFill( &p->vTimLoads, 3*Abc_NtkObjNumMax(pNtk), 0 ); +// Vec_IntFill( &p->vObjOffs, 2*Abc_NtkObjNumMax(pNtk), 0 ); +// Abc_NtkForEachNode( pNtk, pObj, i ) +// { +// Vec_IntWriteEntry( &p->vObjOffs, i, Vec_IntSize(Vec_IntSize(&p->vTimEdges)) ); +// Vec_IntFillExtra( &p->vTimEdges, Vec_IntSize(Vec_IntSize(&p->vTimEdges)) + Abc_ObjFaninNum(pObj), 0 ); +// } + p->Delay = Sfm_MitTrace( p ); + assert( DeltaCrit > 0 && DeltaCrit < MIO_NUM*1000 ); + p->DeltaCrit = DeltaCrit; + return p; +} +void Sfm_MitStop( Sfm_Mit_t * p ) +{ + Vec_IntErase( &p->vTimArrs ); + Vec_IntErase( &p->vTimReqs ); + Vec_IntErase( &p->vTimSlews ); + Vec_IntErase( &p->vTimLoads ); + Vec_IntErase( &p->vObjOffs ); + Vec_IntErase( &p->vTimEdges ); + Vec_WecErase( &p->vLevels ); + Vec_IntErase( &p->vPath ); + Vec_WrdErase( &p->vSortData ); + ABC_FREE( p ); +} +int Sfm_MitReadNtkDelay( Sfm_Mit_t * p ) +{ + return p->Delay; +} +int Sfm_MitReadObjDelay( Sfm_Mit_t * p, int iObj ) +{ + return Sfm_MitArrMaxId(p, iObj); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Sfm_MitTest( Abc_Ntk_t * pNtk ) +{ + Mio_Library_t * pLib = (Mio_Library_t *)pNtk->pManFunc; + Sfm_Mit_t * p = Sfm_MitStart( pLib, NULL, pNtk, 100 ); + printf( "Max delay = %.2f. Path = %d (%d).\n", MIO_NUMINV*p->Delay, Sfm_MitCriticalPath(p, 1), Abc_NtkNodeNum(p->pNtk) ); + Sfm_MitStop( p ); +} + +/**Function************************************************************* + + Synopsis [Levelized structure.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void Sfm_MitUpdateClean( Sfm_Mit_t * p ) +{ + Vec_Int_t * vLevel; + Abc_Obj_t * pObj; + int i, k; + Vec_WecForEachLevel( &p->vLevels, vLevel, i ) + { + Abc_NtkForEachObjVec( vLevel, p->pNtk, pObj, k ) + { + assert( pObj->fMarkC == 1 ); + pObj->fMarkC = 0; + } + Vec_IntClear( vLevel ); + } +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Sfm_MitUpdateTiming( Sfm_Mit_t * p, Vec_Int_t * vTimeNodes ) +{ + assert( Vec_IntSize(vTimeNodes) > 0 && Vec_IntSize(vTimeNodes) <= 2 ); + Vec_IntFillExtra( &p->vTimArrs, 2*Abc_NtkObjNumMax(p->pNtk), 0 ); + Vec_IntFillExtra( &p->vTimReqs, 2*Abc_NtkObjNumMax(p->pNtk), 0 ); + p->Delay = Sfm_MitTrace( p ); +} + +/**Function************************************************************* + + Synopsis [Sort an array of nodes using their max arrival times.] + + Description [Returns the number of new divisor nodes.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Sfm_MitSortArrayByArrival( Sfm_Mit_t * p, Vec_Int_t * vNodes, int iPivot ) +{ + word Entry; + int i, Id, nDivNew = -1; + int MaxDelay = Sfm_MitArrMaxId(p, iPivot); + assert( p->DeltaCrit > 0 ); + // collect nodes + Vec_WrdClear( &p->vSortData ); + Vec_IntForEachEntry( vNodes, Id, i ) + Vec_WrdPush( &p->vSortData, ((word)Id << 32) | Sfm_MitArrMaxId(p, Id) ); + // sort nodes by delay + Abc_QuickSort3( Vec_WrdArray(&p->vSortData), Vec_WrdSize(&p->vSortData), 0 ); + // collect sorted nodes and find place where divisors end + Vec_IntClear( vNodes ); + Vec_WrdForEachEntry( &p->vSortData, Entry, i ) + { + Vec_IntPush( vNodes, (int)(Entry >> 32) ); + if ( nDivNew == -1 && ((int)Entry) + p->DeltaCrit > MaxDelay ) + nDivNew = i; + } + return nDivNew; +} + +/**Function************************************************************* + + Synopsis [Priority of nodes to try remapping for delay.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Sfm_MitPriorityNodes( Sfm_Mit_t * p, Vec_Int_t * vCands, int Window ) +{ + Vec_Int_t * vLevel; + Abc_Obj_t * pObj; + int i, k; + assert( Window >= 0 && Window <= 100 ); + // collect critical path + Sfm_MitCriticalPath( p, Window ); + // add nodes to the levelized structure + Sfm_MitUpdateClean( p ); + Abc_NtkForEachObjVec( &p->vPath, p->pNtk, pObj, i ) + { + assert( pObj->fMarkC == 0 ); + pObj->fMarkC = 1; + Vec_WecPush( &p->vLevels, Abc_ObjLevel(pObj), Abc_ObjId(pObj) ); + } + // prioritize nodes by expected gain + Vec_WecSort( &p->vLevels, 0 ); + Vec_IntClear( vCands ); + Vec_WecForEachLevel( &p->vLevels, vLevel, i ) + { +// printf( "%d ", Vec_IntSize(vLevel) ); + Abc_NtkForEachObjVec( vLevel, p->pNtk, pObj, k ) + if ( !pObj->fMarkA ) + Vec_IntPush( vCands, Abc_ObjId(pObj) ); +// if ( Vec_IntSize(vCands) > 10 ) +// break; + } +// printf( "\n" ); +// printf( "Path = %5d ", Vec_IntSize(&p->vPath) ); +// printf( "Cand = %5d ", Vec_IntSize(vCands) ); + return Vec_IntSize(vCands) > 0; +} + +/**Function************************************************************* + + Synopsis [Returns 1 if node is relatively non-critical compared to the pivot.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Sfm_MitNodeIsNonCritical( Sfm_Mit_t * p, Abc_Obj_t * pPivot, Abc_Obj_t * pNode ) +{ + return Sfm_MitArrMax(p, pNode) + p->DeltaCrit <= Sfm_MitArrMax(p, pPivot); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Sfm_MitEvalRemapping( Sfm_Mit_t * p, Vec_Int_t * vFanins, Vec_Int_t * vMap, Mio_Gate_t * pGate1, char * pFans1, Mio_Gate_t * pGate2, char * pFans2 ) +{ + int TimeOut[2][2]; + int * pTimesIn1[6], * pTimesIn2[6]; + int i, nFanins1, nFanins2; + // process the first gate + nFanins1 = Mio_GateReadPinNum( pGate1 ); + for ( i = 0; i < nFanins1; i++ ) + pTimesIn1[i] = Sfm_MitArrId( p, Vec_IntEntry(vMap, Vec_IntEntry(vFanins, (int)pFans1[i])) ); + Sfm_MitGateArrival( p, pGate1, pTimesIn1, TimeOut[0] ); + if ( pGate2 == NULL ) + return Abc_MaxInt(TimeOut[0][0], TimeOut[0][1]); + // process the second gate + nFanins2 = Mio_GateReadPinNum( pGate2 ); + for ( i = 0; i < nFanins2; i++ ) + if ( (int)pFans2[i] == 16 ) + pTimesIn2[i] = TimeOut[0]; + else + pTimesIn2[i] = Sfm_MitArrId( p, Vec_IntEntry(vMap, Vec_IntEntry(vFanins, (int)pFans2[i])) ); + Sfm_MitGateArrival( p, pGate2, pTimesIn2, TimeOut[1] ); + return Abc_MaxInt(TimeOut[1][0], TimeOut[1][1]); +} + + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + +ABC_NAMESPACE_IMPL_END + |