| /**CFile**************************************************************** |
| |
| FileName [nwkSpeedup.c] |
| |
| SystemName [ABC: Logic synthesis and verification system.] |
| |
| PackageName [Netlist representation.] |
| |
| Synopsis [Global delay optimization using structural choices.] |
| |
| Author [Alan Mishchenko] |
| |
| Affiliation [UC Berkeley] |
| |
| Date [Ver. 1.0. Started - June 20, 2005.] |
| |
| Revision [$Id: nwkSpeedup.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] |
| |
| ***********************************************************************/ |
| |
| #include "nwk.h" |
| |
| ABC_NAMESPACE_IMPL_START |
| |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// DECLARATIONS /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// FUNCTION DEFINITIONS /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| /**Function************************************************************* |
| |
| Synopsis [Adds strashed nodes for one node.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Aig_ManSpeedupNode_rec( Aig_Man_t * pAig, Aig_Obj_t * pNode, Vec_Ptr_t * vNodes ) |
| { |
| if ( Aig_ObjIsTravIdCurrent(pAig, pNode) ) |
| return 1; |
| if ( Aig_ObjIsCi(pNode) ) |
| return 0; |
| assert( Aig_ObjIsNode(pNode) ); |
| Aig_ObjSetTravIdCurrent( pAig, pNode ); |
| if ( !Aig_ManSpeedupNode_rec( pAig, Aig_ObjFanin0(pNode), vNodes ) ) |
| return 0; |
| if ( !Aig_ManSpeedupNode_rec( pAig, Aig_ObjFanin1(pNode), vNodes ) ) |
| return 0; |
| Vec_PtrPush( vNodes, pNode ); |
| return 1; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Adds strashed nodes for one node.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Aig_ManSpeedupNode( Nwk_Man_t * pNtk, Aig_Man_t * pAig, Nwk_Obj_t * pNode, Vec_Ptr_t * vLeaves, Vec_Ptr_t * vTimes ) |
| { |
| Vec_Ptr_t * vNodes; |
| Nwk_Obj_t * pObj, * pObj2; |
| Aig_Obj_t * ppCofs[32], * pAnd, * pTemp; |
| int nCofs, i, k, nSkip; |
| |
| // quit of regulars are the same |
| Vec_PtrForEachEntry( Nwk_Obj_t *, vLeaves, pObj, i ) |
| Vec_PtrForEachEntry( Nwk_Obj_t *, vLeaves, pObj2, k ) |
| if ( i != k && Aig_Regular((Aig_Obj_t *)pObj->pCopy) == Aig_Regular((Aig_Obj_t *)pObj2->pCopy) ) |
| { |
| // printf( "Identical after structural hashing!!!\n" ); |
| return; |
| } |
| |
| // collect the AIG nodes |
| vNodes = Vec_PtrAlloc( 100 ); |
| Aig_ManIncrementTravId( pAig ); |
| Aig_ObjSetTravIdCurrent( pAig, Aig_ManConst1(pAig) ); |
| Vec_PtrForEachEntry( Nwk_Obj_t *, vLeaves, pObj, i ) |
| { |
| pAnd = (Aig_Obj_t *)pObj->pCopy; |
| Aig_ObjSetTravIdCurrent( pAig, Aig_Regular(pAnd) ); |
| } |
| // traverse from the root node |
| pAnd = (Aig_Obj_t *)pNode->pCopy; |
| if ( !Aig_ManSpeedupNode_rec( pAig, Aig_Regular(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( Nwk_Obj_t *, vLeaves, pObj, k ) |
| { |
| pAnd = (Aig_Obj_t *)pObj->pCopy; |
| Aig_Regular(pAnd)->pData = Aig_Regular(pAnd); |
| } |
| Vec_PtrForEachEntry( Nwk_Obj_t *, vTimes, pObj, k ) |
| { |
| pAnd = (Aig_Obj_t *)pObj->pCopy; |
| Aig_Regular(pAnd)->pData = Aig_NotCond( Aig_ManConst1(pAig), ((i & (1<<k)) == 0) ); |
| } |
| Vec_PtrForEachEntry( Aig_Obj_t *, vNodes, pTemp, k ) |
| pTemp->pData = Aig_And( pAig, Aig_ObjChild0Copy(pTemp), Aig_ObjChild1Copy(pTemp) ); |
| // save the result |
| pAnd = (Aig_Obj_t *)pNode->pCopy; |
| ppCofs[i] = Aig_NotCond( (Aig_Obj_t *)Aig_Regular(pAnd)->pData, Aig_IsComplement(pAnd) ); |
| } |
| Vec_PtrFree( vNodes ); |
| |
| //Nwk_ObjAddFanin( Nwk_ManCreatePo(pAig), ppCofs[0] ); |
| //Nwk_ObjAddFanin( Nwk_ManCreatePo(pAig), ppCofs[1] ); |
| |
| // collect the resulting tree |
| Vec_PtrForEachEntry( Nwk_Obj_t *, vTimes, pObj, k ) |
| for ( nSkip = (1<<k), i = 0; i < nCofs; i += 2*nSkip ) |
| { |
| pAnd = (Aig_Obj_t *)pObj->pCopy; |
| ppCofs[i] = Aig_Mux( pAig, Aig_Regular(pAnd), ppCofs[i+nSkip], ppCofs[i] ); |
| } |
| //Nwk_ObjAddFanin( Nwk_ManCreatePo(pAig), ppCofs[0] ); |
| |
| // create choice node |
| pAnd = Aig_Regular((Aig_Obj_t *)pNode->pCopy); // repr |
| pTemp = Aig_Regular(ppCofs[0]); // new |
| if ( Aig_ObjEquiv(pAig, pAnd) == NULL && Aig_ObjEquiv(pAig, pTemp) == NULL && !Aig_ObjCheckTfi(pAig, pTemp, pAnd) ) |
| pAig->pEquivs[pAnd->Id] = pTemp; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Determines timing-critical edges of the node.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| unsigned Nwk_ManDelayTraceTCEdges( Nwk_Man_t * pNtk, Nwk_Obj_t * pNode, float tDelta, int fUseLutLib ) |
| { |
| int pPinPerm[32]; |
| float pPinDelays[32]; |
| If_LibLut_t * pLutLib = fUseLutLib? pNtk->pLutLib : NULL; |
| Nwk_Obj_t * pFanin; |
| unsigned uResult = 0; |
| float tRequired, * pDelays; |
| int k; |
| tRequired = Nwk_ObjRequired(pNode); |
| if ( pLutLib == NULL ) |
| { |
| Nwk_ObjForEachFanin( pNode, pFanin, k ) |
| if ( tRequired < Nwk_ObjArrival(pFanin) + 1.0 + tDelta ) |
| uResult |= (1 << k); |
| } |
| else if ( !pLutLib->fVarPinDelays ) |
| { |
| pDelays = pLutLib->pLutDelays[Nwk_ObjFaninNum(pNode)]; |
| Nwk_ObjForEachFanin( pNode, pFanin, k ) |
| if ( tRequired < Nwk_ObjArrival(pFanin) + pDelays[0] + tDelta ) |
| uResult |= (1 << k); |
| } |
| else |
| { |
| pDelays = pLutLib->pLutDelays[Nwk_ObjFaninNum(pNode)]; |
| Nwk_ManDelayTraceSortPins( pNode, pPinPerm, pPinDelays ); |
| Nwk_ObjForEachFanin( pNode, pFanin, k ) |
| if ( tRequired < Nwk_ObjArrival(Nwk_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 [] |
| |
| ***********************************************************************/ |
| Aig_Man_t * Nwk_ManSpeedup( Nwk_Man_t * pNtk, int fUseLutLib, int Percentage, int Degree, int fVerbose, int fVeryVerbose ) |
| { |
| Aig_Man_t * pAig, * pTemp; |
| Vec_Ptr_t * vTimeCries, * vTimeFanins; |
| Nwk_Obj_t * pNode, * pFanin, * pFanin2; |
| Aig_Obj_t * pAnd; |
| If_LibLut_t * pTempLib = pNtk->pLutLib; |
| Tim_Man_t * pTempTim = NULL; |
| float tDelta, tArrival; |
| int i, k, k2, Counter, CounterRes, nTimeCris; |
| unsigned * puTCEdges; |
| // perform delay trace |
| if ( !fUseLutLib ) |
| { |
| pNtk->pLutLib = NULL; |
| if ( pNtk->pManTime ) |
| { |
| pTempTim = pNtk->pManTime; |
| pNtk->pManTime = Tim_ManDup( pTempTim, 1 ); |
| } |
| } |
| tArrival = Nwk_ManDelayTraceLut( pNtk ); |
| 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, Nwk_ManObjNumMax(pNtk) ); |
| memset( puTCEdges, 0, sizeof(unsigned) * Nwk_ManObjNumMax(pNtk) ); |
| Nwk_ManForEachNode( pNtk, pNode, i ) |
| { |
| if ( Nwk_ObjSlack(pNode) >= tDelta ) |
| continue; |
| puTCEdges[pNode->Id] = Nwk_ManDelayTraceTCEdges( pNtk, pNode, tDelta, fUseLutLib ); |
| } |
| if ( fVerbose ) |
| { |
| Counter = CounterRes = 0; |
| Nwk_ManForEachNode( pNtk, pNode, i ) |
| { |
| Nwk_ObjForEachFanin( pNode, pFanin, k ) |
| if ( !Nwk_ObjIsCi(pFanin) && Nwk_ObjSlack(pFanin) < tDelta ) |
| Counter++; |
| CounterRes += Aig_WordCountOnes( puTCEdges[pNode->Id] ); |
| } |
| printf( "Edges: Total = %7d. 0-slack = %7d. Critical = %7d. Ratio = %4.2f\n", |
| Nwk_ManGetTotalFanins(pNtk), Counter, CounterRes, Counter? 1.0*CounterRes/Counter : 0.0 ); |
| } |
| // start the resulting network |
| pAig = Nwk_ManStrash( pNtk ); |
| pAig->pEquivs = ABC_ALLOC( Aig_Obj_t *, 3 * Aig_ManObjNumMax(pAig) ); |
| memset( pAig->pEquivs, 0, sizeof(Aig_Obj_t *) * 3 * Aig_ManObjNumMax(pAig) ); |
| |
| // collect nodes to be used for resynthesis |
| Counter = CounterRes = 0; |
| vTimeCries = Vec_PtrAlloc( 16 ); |
| vTimeFanins = Vec_PtrAlloc( 16 ); |
| Nwk_ManForEachNode( pNtk, pNode, i ) |
| { |
| if ( Nwk_ObjSlack(pNode) >= tDelta ) |
| continue; |
| // count the number of non-PI timing-critical nodes |
| nTimeCris = 0; |
| Nwk_ObjForEachFanin( pNode, pFanin, k ) |
| if ( !Nwk_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 ) |
| { |
| Nwk_ObjForEachFanin( pNode, pFanin, k ) |
| if ( !Nwk_ObjIsCi(pFanin) && (puTCEdges[pNode->Id] & (1<<k)) ) |
| Nwk_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 ); |
| Nwk_ObjForEachFanin( pNode, pFanin, k ) |
| { |
| if ( Nwk_ObjIsCi(pFanin) ) |
| Vec_PtrPushUnique( vTimeFanins, pFanin ); |
| else |
| Nwk_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) ); |
| Nwk_ObjForEachFanin( pNode, pFanin, k ) |
| printf( "%d(%.2f)%s ", pFanin->Id, Nwk_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 = (Nwk_Obj_t *)Vec_PtrEntry( vTimeCries, 0 ); |
| pFanin2 = (Nwk_Obj_t *)Vec_PtrEntry( vTimeCries, 1 ); |
| if ( Nwk_ObjSlack(pFanin) < Nwk_ObjSlack(pFanin2) ) |
| { |
| Vec_PtrWriteEntry( vTimeCries, 0, pFanin2 ); |
| Vec_PtrWriteEntry( vTimeCries, 1, pFanin ); |
| } |
| } |
| if ( Vec_PtrSize(vTimeCries) > 2 ) |
| { |
| pFanin = (Nwk_Obj_t *)Vec_PtrEntry( vTimeCries, 1 ); |
| pFanin2 = (Nwk_Obj_t *)Vec_PtrEntry( vTimeCries, 2 ); |
| if ( Nwk_ObjSlack(pFanin) < Nwk_ObjSlack(pFanin2) ) |
| { |
| Vec_PtrWriteEntry( vTimeCries, 1, pFanin2 ); |
| Vec_PtrWriteEntry( vTimeCries, 2, pFanin ); |
| } |
| pFanin = (Nwk_Obj_t *)Vec_PtrEntry( vTimeCries, 0 ); |
| pFanin2 = (Nwk_Obj_t *)Vec_PtrEntry( vTimeCries, 1 ); |
| if ( Nwk_ObjSlack(pFanin) < Nwk_ObjSlack(pFanin2) ) |
| { |
| Vec_PtrWriteEntry( vTimeCries, 0, pFanin2 ); |
| Vec_PtrWriteEntry( vTimeCries, 1, pFanin ); |
| } |
| } |
| // add choice |
| Aig_ManSpeedupNode( pNtk, pAig, 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", |
| Nwk_ManNodeNum(pNtk), Counter, CounterRes, Counter? 1.0*CounterRes/Counter : 0.0 ); |
| |
| // remove invalid choice nodes |
| Aig_ManForEachNode( pAig, pAnd, i ) |
| if ( Aig_ObjEquiv(pAig, pAnd) ) |
| { |
| if ( Aig_ObjRefs(Aig_ObjEquiv(pAig, pAnd)) > 0 ) |
| pAig->pEquivs[pAnd->Id] = NULL; |
| } |
| |
| // put back the library |
| if ( !fUseLutLib ) |
| pNtk->pLutLib = pTempLib; |
| if ( pTempTim ) |
| { |
| Tim_ManStop( pNtk->pManTime ); |
| pNtk->pManTime = pTempTim; |
| } |
| |
| // reconstruct the network |
| pAig = Aig_ManDupDfs( pTemp = pAig ); |
| Aig_ManStop( pTemp ); |
| // reset levels |
| Aig_ManChoiceLevel( pAig ); |
| return pAig; |
| } |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// END OF FILE /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| |
| ABC_NAMESPACE_IMPL_END |
| |
