diff options
Diffstat (limited to 'src/base/abci/abcSpeedup.c')
| -rw-r--r-- | src/base/abci/abcSpeedup.c | 965 |
1 files changed, 965 insertions, 0 deletions
diff --git a/src/base/abci/abcSpeedup.c b/src/base/abci/abcSpeedup.c new file mode 100644 index 00000000..779fde62 --- /dev/null +++ b/src/base/abci/abcSpeedup.c @@ -0,0 +1,965 @@ +/**CFile**************************************************************** + + FileName [abcSpeedup.c] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [Network and node package.] + + Synopsis [Delay trace and speedup.] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - June 20, 2005.] + + Revision [$Id: abcSpeedup.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "abc.h" +#include "main.h" +#include "if.h" +#include "aig.h" + +ABC_NAMESPACE_IMPL_START + + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +static inline float Abc_ObjArrival( Abc_Obj_t * pNode ) { return pNode->pNtk->pLutTimes[3*pNode->Id+0]; } +static inline float Abc_ObjRequired( Abc_Obj_t * pNode ) { return pNode->pNtk->pLutTimes[3*pNode->Id+1]; } +static inline float Abc_ObjSlack( Abc_Obj_t * pNode ) { return pNode->pNtk->pLutTimes[3*pNode->Id+2]; } + +static inline void Abc_ObjSetArrival( Abc_Obj_t * pNode, float Time ) { pNode->pNtk->pLutTimes[3*pNode->Id+0] = Time; } +static inline void Abc_ObjSetRequired( Abc_Obj_t * pNode, float Time ) { pNode->pNtk->pLutTimes[3*pNode->Id+1] = Time; } +static inline void Abc_ObjSetSlack( Abc_Obj_t * pNode, float Time ) { pNode->pNtk->pLutTimes[3*pNode->Id+2] = Time; } + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Sorts the pins in the decreasing order of delays.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_NtkDelayTraceSortPins( Abc_Obj_t * pNode, int * pPinPerm, float * pPinDelays ) +{ + Abc_Obj_t * pFanin; + int i, j, best_i, temp; + // start the trivial permutation and collect pin delays + Abc_ObjForEachFanin( pNode, pFanin, i ) + { + pPinPerm[i] = i; + pPinDelays[i] = Abc_ObjArrival(pFanin); + } + // selection sort the pins in the decreasible order of delays + // this order will match the increasing order of LUT input pins + for ( i = 0; i < Abc_ObjFaninNum(pNode)-1; i++ ) + { + best_i = i; + for ( j = i+1; j < Abc_ObjFaninNum(pNode); j++ ) + if ( pPinDelays[pPinPerm[j]] > pPinDelays[pPinPerm[best_i]] ) + best_i = j; + if ( best_i == i ) + continue; + temp = pPinPerm[i]; + pPinPerm[i] = pPinPerm[best_i]; + pPinPerm[best_i] = temp; + } + // verify + assert( Abc_ObjFaninNum(pNode) == 0 || pPinPerm[0] < Abc_ObjFaninNum(pNode) ); + for ( i = 1; i < Abc_ObjFaninNum(pNode); i++ ) + { + assert( pPinPerm[i] < Abc_ObjFaninNum(pNode) ); + assert( pPinDelays[pPinPerm[i-1]] >= pPinDelays[pPinPerm[i]] ); + } +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +float Abc_NtkDelayTraceLut( Abc_Ntk_t * pNtk, int fUseLutLib ) +{ + int fUseSorting = 1; + int pPinPerm[32]; + float pPinDelays[32]; + If_Lib_t * pLutLib; + Abc_Obj_t * pNode, * pFanin; + Vec_Ptr_t * vNodes; + float tArrival, tRequired, tSlack, * pDelays; + int i, k; + + assert( Abc_NtkIsLogic(pNtk) ); + // get the library + pLutLib = fUseLutLib? (If_Lib_t *)Abc_FrameReadLibLut() : NULL; + if ( pLutLib && pLutLib->LutMax < Abc_NtkGetFaninMax(pNtk) ) + { + printf( "The max LUT size (%d) is less than the max fanin count (%d).\n", + pLutLib->LutMax, Abc_NtkGetFaninMax(pNtk) ); + return -ABC_INFINITY; + } + + // initialize the arrival times + ABC_FREE( pNtk->pLutTimes ); + pNtk->pLutTimes = ABC_ALLOC( float, 3 * Abc_NtkObjNumMax(pNtk) ); + for ( i = 0; i < Abc_NtkObjNumMax(pNtk); i++ ) + { + pNtk->pLutTimes[3*i+0] = pNtk->pLutTimes[3*i+2] = 0; + pNtk->pLutTimes[3*i+1] = ABC_INFINITY; + } + + // propagate arrival times + vNodes = Abc_NtkDfs( pNtk, 1 ); + Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pNode, i ) + { + tArrival = -ABC_INFINITY; + if ( pLutLib == NULL ) + { + Abc_ObjForEachFanin( pNode, pFanin, k ) + if ( tArrival < Abc_ObjArrival(pFanin) + 1.0 ) + tArrival = Abc_ObjArrival(pFanin) + 1.0; + } + else if ( !pLutLib->fVarPinDelays ) + { + pDelays = pLutLib->pLutDelays[Abc_ObjFaninNum(pNode)]; + Abc_ObjForEachFanin( pNode, pFanin, k ) + if ( tArrival < Abc_ObjArrival(pFanin) + pDelays[0] ) + tArrival = Abc_ObjArrival(pFanin) + pDelays[0]; + } + else + { + pDelays = pLutLib->pLutDelays[Abc_ObjFaninNum(pNode)]; + if ( fUseSorting ) + { + Abc_NtkDelayTraceSortPins( pNode, pPinPerm, pPinDelays ); + Abc_ObjForEachFanin( pNode, pFanin, k ) + if ( tArrival < Abc_ObjArrival(Abc_ObjFanin(pNode,pPinPerm[k])) + pDelays[k] ) + tArrival = Abc_ObjArrival(Abc_ObjFanin(pNode,pPinPerm[k])) + pDelays[k]; + } + else + { + Abc_ObjForEachFanin( pNode, pFanin, k ) + if ( tArrival < Abc_ObjArrival(pFanin) + pDelays[k] ) + tArrival = Abc_ObjArrival(pFanin) + pDelays[k]; + } + } + if ( Abc_ObjFaninNum(pNode) == 0 ) + tArrival = 0.0; + Abc_ObjSetArrival( pNode, tArrival ); + } + Vec_PtrFree( vNodes ); + + // get the latest arrival times + tArrival = -ABC_INFINITY; + Abc_NtkForEachCo( pNtk, pNode, i ) + if ( tArrival < Abc_ObjArrival(Abc_ObjFanin0(pNode)) ) + tArrival = Abc_ObjArrival(Abc_ObjFanin0(pNode)); + + // initialize the required times + Abc_NtkForEachCo( pNtk, pNode, i ) + if ( Abc_ObjRequired(Abc_ObjFanin0(pNode)) > tArrival ) + Abc_ObjSetRequired( Abc_ObjFanin0(pNode), tArrival ); + + // propagate the required times + vNodes = Abc_NtkDfsReverse( pNtk ); + Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pNode, i ) + { + if ( pLutLib == NULL ) + { + tRequired = Abc_ObjRequired(pNode) - (float)1.0; + Abc_ObjForEachFanin( pNode, pFanin, k ) + if ( Abc_ObjRequired(pFanin) > tRequired ) + Abc_ObjSetRequired( pFanin, tRequired ); + } + else if ( !pLutLib->fVarPinDelays ) + { + pDelays = pLutLib->pLutDelays[Abc_ObjFaninNum(pNode)]; + tRequired = Abc_ObjRequired(pNode) - pDelays[0]; + Abc_ObjForEachFanin( pNode, pFanin, k ) + if ( Abc_ObjRequired(pFanin) > tRequired ) + Abc_ObjSetRequired( pFanin, tRequired ); + } + else + { + pDelays = pLutLib->pLutDelays[Abc_ObjFaninNum(pNode)]; + if ( fUseSorting ) + { + Abc_NtkDelayTraceSortPins( pNode, pPinPerm, pPinDelays ); + Abc_ObjForEachFanin( pNode, pFanin, k ) + { + tRequired = Abc_ObjRequired(pNode) - pDelays[k]; + if ( Abc_ObjRequired(Abc_ObjFanin(pNode,pPinPerm[k])) > tRequired ) + Abc_ObjSetRequired( Abc_ObjFanin(pNode,pPinPerm[k]), tRequired ); + } + } + else + { + Abc_ObjForEachFanin( pNode, pFanin, k ) + { + tRequired = Abc_ObjRequired(pNode) - pDelays[k]; + if ( Abc_ObjRequired(pFanin) > tRequired ) + Abc_ObjSetRequired( pFanin, tRequired ); + } + } + } + // set slack for this object + tSlack = Abc_ObjRequired(pNode) - Abc_ObjArrival(pNode); + assert( tSlack + 0.001 > 0.0 ); + Abc_ObjSetSlack( pNode, tSlack < 0.0 ? 0.0 : tSlack ); + } + Vec_PtrFree( vNodes ); + return tArrival; +} + +/**Function************************************************************* + + Synopsis [Delay tracing of the LUT mapped network.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_NtkDelayTracePrint( Abc_Ntk_t * pNtk, int fUseLutLib, int fVerbose ) +{ + Abc_Obj_t * pNode; + If_Lib_t * pLutLib; + int i, Nodes, * pCounters; + float tArrival, tDelta, nSteps, Num; + // get the library + pLutLib = fUseLutLib? (If_Lib_t *)Abc_FrameReadLibLut() : NULL; + if ( pLutLib && pLutLib->LutMax < Abc_NtkGetFaninMax(pNtk) ) + { + printf( "The max LUT size (%d) is less than the max fanin count (%d).\n", + pLutLib->LutMax, Abc_NtkGetFaninMax(pNtk) ); + return; + } + // decide how many steps + nSteps = fUseLutLib ? 20 : Abc_NtkLevel(pNtk); + pCounters = ABC_ALLOC( int, nSteps + 1 ); + memset( pCounters, 0, sizeof(int)*(nSteps + 1) ); + // perform delay trace + tArrival = Abc_NtkDelayTraceLut( pNtk, fUseLutLib ); + tDelta = tArrival / nSteps; + // count how many nodes have slack in the corresponding intervals + Abc_NtkForEachNode( pNtk, pNode, i ) + { + if ( Abc_ObjFaninNum(pNode) == 0 ) + continue; + Num = Abc_ObjSlack(pNode) / tDelta; + assert( Num >=0 && Num <= nSteps ); + pCounters[(int)Num]++; + } + // print the results + printf( "Max delay = %6.2f. Delay trace using %s model:\n", tArrival, fUseLutLib? "LUT library" : "unit-delay" ); + Nodes = 0; + for ( i = 0; i < nSteps; i++ ) + { + Nodes += pCounters[i]; + printf( "%3d %s : %5d (%6.2f %%)\n", fUseLutLib? 5*(i+1) : i+1, + fUseLutLib? "%":"lev", Nodes, 100.0*Nodes/Abc_NtkNodeNum(pNtk) ); + } + ABC_FREE( pCounters ); +} + +/**Function************************************************************* + + Synopsis [Returns 1 if pOld is in the TFI of pNew.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_AigCheckTfi_rec( Abc_Obj_t * pNode, Abc_Obj_t * pOld ) +{ + // check the trivial cases + if ( pNode == NULL ) + return 0; + if ( Abc_ObjIsCi(pNode) ) + return 0; + if ( pNode == pOld ) + return 1; + // skip the visited node + if ( Abc_NodeIsTravIdCurrent( pNode ) ) + return 0; + Abc_NodeSetTravIdCurrent( pNode ); + // check the children + if ( Abc_AigCheckTfi_rec( Abc_ObjFanin0(pNode), pOld ) ) + return 1; + if ( Abc_AigCheckTfi_rec( Abc_ObjFanin1(pNode), pOld ) ) + return 1; + // check equivalent nodes + return Abc_AigCheckTfi_rec( (Abc_Obj_t *)pNode->pData, pOld ); +} + +/**Function************************************************************* + + Synopsis [Returns 1 if pOld is in the TFI of pNew.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_AigCheckTfi( Abc_Obj_t * pNew, Abc_Obj_t * pOld ) +{ + assert( !Abc_ObjIsComplement(pNew) ); + assert( !Abc_ObjIsComplement(pOld) ); + Abc_NtkIncrementTravId( pNew->pNtk ); + return Abc_AigCheckTfi_rec( pNew, pOld ); +} + +/**Function************************************************************* + + Synopsis [Adds strashed nodes for one node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_NtkSpeedupNode_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vNodes ) +{ + if ( Abc_NodeIsTravIdCurrent(pNode) ) + return 1; + if ( Abc_ObjIsCi(pNode) ) + return 0; + assert( Abc_ObjIsNode(pNode) ); + Abc_NodeSetTravIdCurrent( pNode ); + if ( !Abc_NtkSpeedupNode_rec( Abc_ObjFanin0(pNode), vNodes ) ) + return 0; + if ( !Abc_NtkSpeedupNode_rec( Abc_ObjFanin1(pNode), vNodes ) ) + return 0; + Vec_PtrPush( vNodes, pNode ); + return 1; +} + +/**Function************************************************************* + + Synopsis [Adds strashed nodes for one node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_NtkSpeedupNode( Abc_Ntk_t * pNtk, Abc_Ntk_t * pAig, Abc_Obj_t * pNode, Vec_Ptr_t * vLeaves, Vec_Ptr_t * vTimes ) +{ + Vec_Ptr_t * vNodes; + Abc_Obj_t * pObj, * pObj2, * pAnd; + Abc_Obj_t * ppCofs[32]; + int nCofs, i, k, nSkip; + + // quit of regulars are the same + Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pObj, i ) + Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pObj2, k ) + if ( i != k && Abc_ObjRegular(pObj->pCopy) == Abc_ObjRegular(pObj2->pCopy) ) + { +// printf( "Identical after structural hashing!!!\n" ); + return; + } + + // collect the AIG nodes + vNodes = Vec_PtrAlloc( 100 ); + Abc_NtkIncrementTravId( pAig ); + Abc_NodeSetTravIdCurrent( Abc_AigConst1(pAig) ); + Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pObj, i ) + { + pAnd = pObj->pCopy; + Abc_NodeSetTravIdCurrent( Abc_ObjRegular(pAnd) ); + } + // traverse from the root node + pAnd = pNode->pCopy; + if ( !Abc_NtkSpeedupNode_rec( Abc_ObjRegular(pAnd), vNodes ) ) + { +// printf( "Bad node!!!\n" ); + Vec_PtrFree( vNodes ); + return; + } + + // derive cofactors + nCofs = (1 << Vec_PtrSize(vTimes)); + for ( i = 0; i < nCofs; i++ ) + { + Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pObj, k ) + { + pAnd = pObj->pCopy; + Abc_ObjRegular(pAnd)->pCopy = Abc_ObjRegular(pAnd); + } + Vec_PtrForEachEntry( Abc_Obj_t *, vTimes, pObj, k ) + { + pAnd = pObj->pCopy; + Abc_ObjRegular(pAnd)->pCopy = Abc_ObjNotCond( Abc_AigConst1(pAig), ((i & (1<<k)) == 0) ); + } + Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, k ) + pObj->pCopy = Abc_AigAnd( (Abc_Aig_t *)pAig->pManFunc, Abc_ObjChild0Copy(pObj), Abc_ObjChild1Copy(pObj) ); + // save the result + pAnd = pNode->pCopy; + ppCofs[i] = Abc_ObjNotCond( Abc_ObjRegular(pAnd)->pCopy, Abc_ObjIsComplement(pAnd) ); + } + Vec_PtrFree( vNodes ); + +//Abc_ObjAddFanin( Abc_NtkCreatePo(pAig), ppCofs[0] ); +//Abc_ObjAddFanin( Abc_NtkCreatePo(pAig), ppCofs[1] ); + + // collect the resulting tree + Vec_PtrForEachEntry( Abc_Obj_t *, vTimes, pObj, k ) + for ( nSkip = (1<<k), i = 0; i < nCofs; i += 2*nSkip ) + { + pAnd = pObj->pCopy; + ppCofs[i] = Abc_AigMux( (Abc_Aig_t *)pAig->pManFunc, Abc_ObjRegular(pAnd), ppCofs[i+nSkip], ppCofs[i] ); + } +//Abc_ObjAddFanin( Abc_NtkCreatePo(pAig), ppCofs[0] ); + + // create choice node + pAnd = Abc_ObjRegular(pNode->pCopy); // repr + pObj = Abc_ObjRegular(ppCofs[0]); // new + if ( pAnd->pData == NULL && pObj->pData == NULL && !Abc_AigCheckTfi(pObj, pAnd) ) + { + pObj->pData = pAnd->pData; + pAnd->pData = pObj; + } + +} + +/**Function************************************************************* + + Synopsis [Determines timing-critical edges of the node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +unsigned Abc_NtkDelayTraceTCEdges( Abc_Ntk_t * pNtk, Abc_Obj_t * pNode, float tDelta, int fUseLutLib ) +{ + int pPinPerm[32]; + float pPinDelays[32]; + If_Lib_t * pLutLib; + Abc_Obj_t * pFanin; + unsigned uResult = 0; + float tRequired, * pDelays; + int k; + pLutLib = fUseLutLib? (If_Lib_t *)Abc_FrameReadLibLut() : NULL; + tRequired = Abc_ObjRequired(pNode); + if ( pLutLib == NULL ) + { + Abc_ObjForEachFanin( pNode, pFanin, k ) + if ( tRequired < Abc_ObjArrival(pFanin) + 1.0 + tDelta ) + uResult |= (1 << k); + } + else if ( !pLutLib->fVarPinDelays ) + { + pDelays = pLutLib->pLutDelays[Abc_ObjFaninNum(pNode)]; + Abc_ObjForEachFanin( pNode, pFanin, k ) + if ( tRequired < Abc_ObjArrival(pFanin) + pDelays[0] + tDelta ) + uResult |= (1 << k); + } + else + { + pDelays = pLutLib->pLutDelays[Abc_ObjFaninNum(pNode)]; + Abc_NtkDelayTraceSortPins( pNode, pPinPerm, pPinDelays ); + Abc_ObjForEachFanin( pNode, pFanin, k ) + if ( tRequired < Abc_ObjArrival(Abc_ObjFanin(pNode,pPinPerm[k])) + pDelays[k] + tDelta ) + uResult |= (1 << pPinPerm[k]); + } + return uResult; +} + +/**Function************************************************************* + + Synopsis [Adds choices to speed up the network by the given percentage.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Abc_Ntk_t * Abc_NtkSpeedup( Abc_Ntk_t * pNtk, int fUseLutLib, int Percentage, int Degree, int fVerbose, int fVeryVerbose ) +{ + Abc_Ntk_t * pNtkNew; + Vec_Ptr_t * vTimeCries, * vTimeFanins; + Abc_Obj_t * pNode, * pFanin, * pFanin2; + float tDelta, tArrival; + int i, k, k2, Counter, CounterRes, nTimeCris; + unsigned * puTCEdges; + // perform delay trace + tArrival = Abc_NtkDelayTraceLut( pNtk, fUseLutLib ); + tDelta = fUseLutLib ? tArrival*Percentage/100.0 : 1.0; + if ( fVerbose ) + { + printf( "Max delay = %.2f. Delta = %.2f. ", tArrival, tDelta ); + printf( "Using %s model. ", fUseLutLib? "LUT library" : "unit-delay" ); + if ( fUseLutLib ) + printf( "Percentage = %d. ", Percentage ); + printf( "\n" ); + } + // mark the timing critical nodes and edges + puTCEdges = ABC_ALLOC( unsigned, Abc_NtkObjNumMax(pNtk) ); + memset( puTCEdges, 0, sizeof(unsigned) * Abc_NtkObjNumMax(pNtk) ); + Abc_NtkForEachNode( pNtk, pNode, i ) + { + if ( Abc_ObjSlack(pNode) >= tDelta ) + continue; + puTCEdges[pNode->Id] = Abc_NtkDelayTraceTCEdges( pNtk, pNode, tDelta, fUseLutLib ); + } + if ( fVerbose ) + { + Counter = CounterRes = 0; + Abc_NtkForEachNode( pNtk, pNode, i ) + { + Abc_ObjForEachFanin( pNode, pFanin, k ) + if ( !Abc_ObjIsCi(pFanin) && Abc_ObjSlack(pFanin) < tDelta ) + Counter++; + CounterRes += Extra_WordCountOnes( puTCEdges[pNode->Id] ); + } + printf( "Edges: Total = %7d. 0-slack = %7d. Critical = %7d. Ratio = %4.2f\n", + Abc_NtkGetTotalFanins(pNtk), Counter, CounterRes, 1.0*CounterRes/Counter ); + } + // start the resulting network + pNtkNew = Abc_NtkStrash( pNtk, 0, 1, 0 ); + + // collect nodes to be used for resynthesis + Counter = CounterRes = 0; + vTimeCries = Vec_PtrAlloc( 16 ); + vTimeFanins = Vec_PtrAlloc( 16 ); + Abc_NtkForEachNode( pNtk, pNode, i ) + { + if ( Abc_ObjSlack(pNode) >= tDelta ) + continue; + // count the number of non-PI timing-critical nodes + nTimeCris = 0; + Abc_ObjForEachFanin( pNode, pFanin, k ) + if ( !Abc_ObjIsCi(pFanin) && (puTCEdges[pNode->Id] & (1<<k)) ) + nTimeCris++; + if ( !fVeryVerbose && nTimeCris == 0 ) + continue; + Counter++; + // count the total number of timing critical second-generation nodes + Vec_PtrClear( vTimeCries ); + if ( nTimeCris ) + { + Abc_ObjForEachFanin( pNode, pFanin, k ) + if ( !Abc_ObjIsCi(pFanin) && (puTCEdges[pNode->Id] & (1<<k)) ) + Abc_ObjForEachFanin( pFanin, pFanin2, k2 ) + if ( puTCEdges[pFanin->Id] & (1<<k2) ) + Vec_PtrPushUnique( vTimeCries, pFanin2 ); + } +// if ( !fVeryVerbose && (Vec_PtrSize(vTimeCries) == 0 || Vec_PtrSize(vTimeCries) > Degree) ) + if ( (Vec_PtrSize(vTimeCries) == 0 || Vec_PtrSize(vTimeCries) > Degree) ) + continue; + CounterRes++; + // collect second generation nodes + Vec_PtrClear( vTimeFanins ); + Abc_ObjForEachFanin( pNode, pFanin, k ) + { + if ( Abc_ObjIsCi(pFanin) ) + Vec_PtrPushUnique( vTimeFanins, pFanin ); + else + Abc_ObjForEachFanin( pFanin, pFanin2, k2 ) + Vec_PtrPushUnique( vTimeFanins, pFanin2 ); + } + // print the results + if ( fVeryVerbose ) + { + printf( "%5d Node %5d : %d %2d %2d ", Counter, pNode->Id, + nTimeCris, Vec_PtrSize(vTimeCries), Vec_PtrSize(vTimeFanins) ); + Abc_ObjForEachFanin( pNode, pFanin, k ) + printf( "%d(%.2f)%s ", pFanin->Id, Abc_ObjSlack(pFanin), (puTCEdges[pNode->Id] & (1<<k))? "*":"" ); + printf( "\n" ); + } + // add the node to choices + if ( Vec_PtrSize(vTimeCries) == 0 || Vec_PtrSize(vTimeCries) > Degree ) + continue; + // order the fanins in the increasing order of criticalily + if ( Vec_PtrSize(vTimeCries) > 1 ) + { + pFanin = (Abc_Obj_t *)Vec_PtrEntry( vTimeCries, 0 ); + pFanin2 = (Abc_Obj_t *)Vec_PtrEntry( vTimeCries, 1 ); + if ( Abc_ObjSlack(pFanin) < Abc_ObjSlack(pFanin2) ) + { + Vec_PtrWriteEntry( vTimeCries, 0, pFanin2 ); + Vec_PtrWriteEntry( vTimeCries, 1, pFanin ); + } + } + if ( Vec_PtrSize(vTimeCries) > 2 ) + { + pFanin = (Abc_Obj_t *)Vec_PtrEntry( vTimeCries, 1 ); + pFanin2 = (Abc_Obj_t *)Vec_PtrEntry( vTimeCries, 2 ); + if ( Abc_ObjSlack(pFanin) < Abc_ObjSlack(pFanin2) ) + { + Vec_PtrWriteEntry( vTimeCries, 1, pFanin2 ); + Vec_PtrWriteEntry( vTimeCries, 2, pFanin ); + } + pFanin = (Abc_Obj_t *)Vec_PtrEntry( vTimeCries, 0 ); + pFanin2 = (Abc_Obj_t *)Vec_PtrEntry( vTimeCries, 1 ); + if ( Abc_ObjSlack(pFanin) < Abc_ObjSlack(pFanin2) ) + { + Vec_PtrWriteEntry( vTimeCries, 0, pFanin2 ); + Vec_PtrWriteEntry( vTimeCries, 1, pFanin ); + } + } + // add choice + Abc_NtkSpeedupNode( pNtk, pNtkNew, pNode, vTimeFanins, vTimeCries ); + } + Vec_PtrFree( vTimeCries ); + Vec_PtrFree( vTimeFanins ); + ABC_FREE( puTCEdges ); + if ( fVerbose ) + printf( "Nodes: Total = %7d. 0-slack = %7d. Workable = %7d. Ratio = %4.2f\n", + Abc_NtkNodeNum(pNtk), Counter, CounterRes, 1.0*CounterRes/Counter ); + + // remove invalid choice nodes + Abc_AigForEachAnd( pNtkNew, pNode, i ) + if ( pNode->pData ) + { + if ( Abc_ObjFanoutNum((Abc_Obj_t *)pNode->pData) > 0 ) + pNode->pData = NULL; + } + + // return the result + return pNtkNew; +} + +/**Function************************************************************* + + Synopsis [Marks nodes for power-optimization.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Vec_Int_t * Abc_NtkPowerEstimate( Abc_Ntk_t * pNtk, int fProbOne ) +{ + extern Aig_Man_t * Abc_NtkToDar( Abc_Ntk_t * pNtk, int fExors, int fRegisters ); + extern Vec_Int_t * Saig_ManComputeSwitchProbs( Aig_Man_t * p, int nFrames, int nPref, int fProbOne ); + Vec_Int_t * vProbs; + Vec_Int_t * vSwitching; + float * pProbability; + float * pSwitching; + Abc_Ntk_t * pNtkStr; + Aig_Man_t * pAig; + Aig_Obj_t * pObjAig; + Abc_Obj_t * pObjAbc, * pObjAbc2; + int i; + // start the resulting array + vProbs = Vec_IntStart( Abc_NtkObjNumMax(pNtk) ); + pProbability = (float *)vProbs->pArray; + // strash the network + pNtkStr = Abc_NtkStrash( pNtk, 0, 1, 0 ); + Abc_NtkForEachObj( pNtk, pObjAbc, i ) + if ( Abc_ObjRegular((Abc_Obj_t *)pObjAbc->pTemp)->Type == ABC_FUNC_NONE ) + pObjAbc->pTemp = NULL; + // map network into an AIG + pAig = Abc_NtkToDar( pNtkStr, 0, (int)(Abc_NtkLatchNum(pNtk) > 0) ); + vSwitching = Saig_ManComputeSwitchProbs( pAig, 48, 16, fProbOne ); + pSwitching = (float *)vSwitching->pArray; + Abc_NtkForEachObj( pNtk, pObjAbc, i ) + { + if ( (pObjAbc2 = Abc_ObjRegular((Abc_Obj_t *)pObjAbc->pTemp)) && (pObjAig = Aig_Regular((Aig_Obj_t *)pObjAbc2->pTemp)) ) + pProbability[pObjAbc->Id] = pSwitching[pObjAig->Id]; + } + Vec_IntFree( vSwitching ); + Aig_ManStop( pAig ); + Abc_NtkDelete( pNtkStr ); + return vProbs; +} + +/**Function************************************************************* + + Synopsis [Marks nodes for power-optimization.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_NtkPowerPrint( Abc_Ntk_t * pNtk, Vec_Int_t * vProbs ) +{ + Abc_Obj_t * pObj; + float * pProb, TotalProb = 0.0, ProbThis, Probs[6] = {0.0}; + int i, nNodes = 0, nEdges = 0, Counter[6] = {0}; + pProb = (float *)vProbs->pArray; + assert( Vec_IntSize(vProbs) >= Abc_NtkObjNumMax(pNtk) ); + Abc_NtkForEachObj( pNtk, pObj, i ) + { + if ( !Abc_ObjIsNode(pObj) && !Abc_ObjIsPi(pObj) ) + continue; + nNodes++; + nEdges += Abc_ObjFanoutNum(pObj); + ProbThis = pProb[i] * Abc_ObjFanoutNum(pObj); + TotalProb += ProbThis; + assert( pProb[i] >= 0.0 && pProb[i] <= 1.0 ); + if ( pProb[i] >= 0.5 ) + { + Counter[5]++; + Probs[5] += ProbThis; + } + else if ( pProb[i] >= 0.4 ) + { + Counter[4]++; + Probs[4] += ProbThis; + } + else if ( pProb[i] >= 0.3 ) + { + Counter[3]++; + Probs[3] += ProbThis; + } + else if ( pProb[i] >= 0.2 ) + { + Counter[2]++; + Probs[2] += ProbThis; + } + else if ( pProb[i] >= 0.1 ) + { + Counter[1]++; + Probs[1] += ProbThis; + } + else + { + Counter[0]++; + Probs[0] += ProbThis; + } + } + printf( "Node distribution: " ); + for ( i = 0; i < 6; i++ ) + printf( "n%d%d = %6.2f%% ", i, i+1, 100.0 * Counter[i]/nNodes ); + printf( "\n" ); + printf( "Power distribution: " ); + for ( i = 0; i < 6; i++ ) + printf( "p%d%d = %6.2f%% ", i, i+1, 100.0 * Probs[i]/TotalProb ); + printf( "\n" ); + printf( "Total probs = %7.2f. ", TotalProb ); + printf( "Total edges = %d. ", nEdges ); + printf( "Average = %7.2f. ", TotalProb / nEdges ); + printf( "\n" ); +} + +/**Function************************************************************* + + Synopsis [Determines timing-critical edges of the node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +unsigned Abc_NtkPowerCriticalEdges( Abc_Ntk_t * pNtk, Abc_Obj_t * pNode, float Limit, Vec_Int_t * vProbs ) +{ + Abc_Obj_t * pFanin; + float * pProb = (float *)vProbs->pArray; + unsigned uResult = 0; + int k; + Abc_ObjForEachFanin( pNode, pFanin, k ) + if ( pProb[pFanin->Id] >= Limit ) + uResult |= (1 << k); + return uResult; +} + +/**Function************************************************************* + + Synopsis [Adds choices to speed up the network by the given percentage.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Abc_Ntk_t * Abc_NtkPowerdown( Abc_Ntk_t * pNtk, int fUseLutLib, int Percentage, int Degree, int fVerbose, int fVeryVerbose ) +{ + Abc_Ntk_t * pNtkNew; + Vec_Int_t * vProbs; + Vec_Ptr_t * vTimeCries, * vTimeFanins; + Abc_Obj_t * pNode, * pFanin, * pFanin2; + float * pProb, Limit; + int i, k, k2, Counter, CounterRes, nTimeCris; + unsigned * puPCEdges; + // compute the limit + Limit = 0.5 - (1.0 * Percentage / 100); + // perform computation of switching probability + vProbs = Abc_NtkPowerEstimate( pNtk, 0 ); + pProb = (float *)vProbs->pArray; + // compute percentage of wires of each type + if ( fVerbose ) + Abc_NtkPowerPrint( pNtk, vProbs ); + // mark the power critical nodes and edges + puPCEdges = ABC_ALLOC( unsigned, Abc_NtkObjNumMax(pNtk) ); + memset( puPCEdges, 0, sizeof(unsigned) * Abc_NtkObjNumMax(pNtk) ); + Abc_NtkForEachNode( pNtk, pNode, i ) + { + if ( pProb[pNode->Id] < Limit ) + continue; + puPCEdges[pNode->Id] = Abc_NtkPowerCriticalEdges( pNtk, pNode, Limit, vProbs ); + } +/* + if ( fVerbose ) + { + Counter = CounterRes = 0; + Abc_NtkForEachNode( pNtk, pNode, i ) + { + Counter += Abc_ObjFaninNum(pNode); + CounterRes += Extra_WordCountOnes( puPCEdges[pNode->Id] ); + } + printf( "Edges: Total = %7d. Critical = %7d. Ratio = %4.2f\n", + Counter, CounterRes, 1.0*CounterRes/Counter ); + } +*/ + // start the resulting network + pNtkNew = Abc_NtkStrash( pNtk, 0, 1, 0 ); + + // collect nodes to be used for resynthesis + Counter = CounterRes = 0; + vTimeCries = Vec_PtrAlloc( 16 ); + vTimeFanins = Vec_PtrAlloc( 16 ); + Abc_NtkForEachNode( pNtk, pNode, i ) + { +// if ( pProb[pNode->Id] < Limit ) +// continue; + // count the number of non-PI power-critical nodes + nTimeCris = 0; + Abc_ObjForEachFanin( pNode, pFanin, k ) + if ( !Abc_ObjIsCi(pFanin) && (puPCEdges[pNode->Id] & (1<<k)) ) + nTimeCris++; + if ( !fVeryVerbose && nTimeCris == 0 ) + continue; + Counter++; + // count the total number of power-critical second-generation nodes + Vec_PtrClear( vTimeCries ); + if ( nTimeCris ) + { + Abc_ObjForEachFanin( pNode, pFanin, k ) + if ( !Abc_ObjIsCi(pFanin) && (puPCEdges[pNode->Id] & (1<<k)) ) + Abc_ObjForEachFanin( pFanin, pFanin2, k2 ) + if ( puPCEdges[pFanin->Id] & (1<<k2) ) + Vec_PtrPushUnique( vTimeCries, pFanin2 ); + } +// if ( !fVeryVerbose && (Vec_PtrSize(vTimeCries) == 0 || Vec_PtrSize(vTimeCries) > Degree) ) + if ( (Vec_PtrSize(vTimeCries) == 0 || Vec_PtrSize(vTimeCries) > Degree) ) + continue; + CounterRes++; + // collect second generation nodes + Vec_PtrClear( vTimeFanins ); + Abc_ObjForEachFanin( pNode, pFanin, k ) + { + if ( Abc_ObjIsCi(pFanin) ) + Vec_PtrPushUnique( vTimeFanins, pFanin ); + else + Abc_ObjForEachFanin( pFanin, pFanin2, k2 ) + Vec_PtrPushUnique( vTimeFanins, pFanin2 ); + } + // print the results + if ( fVeryVerbose ) + { + printf( "%5d Node %5d : %d %2d %2d ", Counter, pNode->Id, + nTimeCris, Vec_PtrSize(vTimeCries), Vec_PtrSize(vTimeFanins) ); + Abc_ObjForEachFanin( pNode, pFanin, k ) + printf( "%d(%.2f)%s ", pFanin->Id, pProb[pFanin->Id], (puPCEdges[pNode->Id] & (1<<k))? "*":"" ); + printf( "\n" ); + } + // add the node to choices + if ( Vec_PtrSize(vTimeCries) == 0 || Vec_PtrSize(vTimeCries) > Degree ) + continue; + // order the fanins in the increasing order of criticalily + if ( Vec_PtrSize(vTimeCries) > 1 ) + { + pFanin = (Abc_Obj_t *)Vec_PtrEntry( vTimeCries, 0 ); + pFanin2 = (Abc_Obj_t *)Vec_PtrEntry( vTimeCries, 1 ); +// if ( Abc_ObjSlack(pFanin) < Abc_ObjSlack(pFanin2) ) + if ( pProb[pFanin->Id] > pProb[pFanin2->Id] ) + { + Vec_PtrWriteEntry( vTimeCries, 0, pFanin2 ); + Vec_PtrWriteEntry( vTimeCries, 1, pFanin ); + } + } + if ( Vec_PtrSize(vTimeCries) > 2 ) + { + pFanin = (Abc_Obj_t *)Vec_PtrEntry( vTimeCries, 1 ); + pFanin2 = (Abc_Obj_t *)Vec_PtrEntry( vTimeCries, 2 ); +// if ( Abc_ObjSlack(pFanin) < Abc_ObjSlack(pFanin2) ) + if ( pProb[pFanin->Id] > pProb[pFanin2->Id] ) + { + Vec_PtrWriteEntry( vTimeCries, 1, pFanin2 ); + Vec_PtrWriteEntry( vTimeCries, 2, pFanin ); + } + pFanin = (Abc_Obj_t *)Vec_PtrEntry( vTimeCries, 0 ); + pFanin2 = (Abc_Obj_t *)Vec_PtrEntry( vTimeCries, 1 ); +// if ( Abc_ObjSlack(pFanin) < Abc_ObjSlack(pFanin2) ) + if ( pProb[pFanin->Id] > pProb[pFanin2->Id] ) + { + Vec_PtrWriteEntry( vTimeCries, 0, pFanin2 ); + Vec_PtrWriteEntry( vTimeCries, 1, pFanin ); + } + } + // add choice + Abc_NtkSpeedupNode( pNtk, pNtkNew, pNode, vTimeFanins, vTimeCries ); + } + Vec_PtrFree( vTimeCries ); + Vec_PtrFree( vTimeFanins ); + ABC_FREE( puPCEdges ); + if ( fVerbose ) + printf( "Nodes: Total = %7d. Power-critical = %7d. Workable = %7d. Ratio = %4.2f\n", + Abc_NtkNodeNum(pNtk), Counter, CounterRes, 1.0*CounterRes/Counter ); + + // remove invalid choice nodes + Abc_AigForEachAnd( pNtkNew, pNode, i ) + if ( pNode->pData ) + { + if ( Abc_ObjFanoutNum((Abc_Obj_t *)pNode->pData) > 0 ) + pNode->pData = NULL; + } + + // return the result + Vec_IntFree( vProbs ); + return pNtkNew; +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + +ABC_NAMESPACE_IMPL_END + |