| /**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 "base/abc/abc.h" |
| #include "base/main/main.h" |
| #include "map/if/if.h" |
| #include "aig/aig/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_LibLut_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_LibLut_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_LibLut_t * pLutLib; |
| int i, Nodes, * pCounters; |
| float tArrival, tDelta, nSteps, Num; |
| // get the library |
| pLutLib = fUseLutLib? (If_LibLut_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_AigNodeIsConst(pObj) && !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_LibLut_t * pLutLib; |
| Abc_Obj_t * pFanin; |
| unsigned uResult = 0; |
| float tRequired, * pDelays; |
| int k; |
| pLutLib = fUseLutLib? (If_LibLut_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 |
| |
