From 0c4d314ef0460b94c3ccc4f8ddeedc8e49e35e96 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Fri, 4 Apr 2008 20:01:00 -0700 Subject: Version abc80404_2 --- src/aig/nwk/nwkSpeedup.c | 319 ++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 316 insertions(+), 3 deletions(-) (limited to 'src/aig/nwk/nwkSpeedup.c') diff --git a/src/aig/nwk/nwkSpeedup.c b/src/aig/nwk/nwkSpeedup.c index 1eb7cbdd..80404a44 100644 --- a/src/aig/nwk/nwkSpeedup.c +++ b/src/aig/nwk/nwkSpeedup.c @@ -30,7 +30,7 @@ /**Function************************************************************* - Synopsis [] + Synopsis [Adds strashed nodes for one node.] Description [] @@ -39,9 +39,322 @@ SeeAlso [] ***********************************************************************/ -Aig_Man_t * Nwk_ManSpeedup( Nwk_Man_t * pNtk ) +int Aig_ManSpeedupNode_rec( Aig_Man_t * pAig, Aig_Obj_t * pNode, Vec_Ptr_t * vNodes ) { - return NULL; + if ( Aig_ObjIsTravIdCurrent(pAig, pNode) ) + return 1; + if ( Aig_ObjIsPi(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( vLeaves, pObj, i ) + Vec_PtrForEachEntry( vLeaves, pObj2, k ) + if ( i != k && Aig_Regular(pObj->pCopy) == Aig_Regular(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( vLeaves, pObj, i ) + { + pAnd = pObj->pCopy; + Aig_ObjSetTravIdCurrent( pAig, Aig_Regular(pAnd) ); + } + // traverse from the root node + pAnd = 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( vLeaves, pObj, k ) + { + pAnd = pObj->pCopy; + Aig_Regular(pAnd)->pData = Aig_Regular(pAnd); + } + Vec_PtrForEachEntry( vTimes, pObj, k ) + { + pAnd = pObj->pCopy; + Aig_Regular(pAnd)->pData = Aig_NotCond( Aig_ManConst1(pAig), ((i & (1<pData = Aig_And( pAig, Aig_ObjChild0Copy(pTemp), Aig_ObjChild1Copy(pTemp) ); + // save the result + pAnd = pNode->pCopy; + ppCofs[i] = Aig_NotCond( 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( vTimes, pObj, k ) + for ( nSkip = (1<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(pNode->pCopy); // repr + pTemp = Aig_Regular(ppCofs[0]); // new + if ( pAig->pEquivs[pAnd->Id] == NULL && pAig->pEquivs[pTemp->Id] == 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_Lib_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_Lib_t * pTempLib = pNtk->pLutLib; + float tDelta, tArrival; + int i, k, k2, Counter, CounterRes, nTimeCris; + unsigned * puTCEdges; + // perform delay trace + if ( !fUseLutLib ) + pNtk->pLutLib = NULL; + 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 = ALLOC( int, Nwk_ManObjNumMax(pNtk) ); + memset( puTCEdges, 0, sizeof(int) * 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 = 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<Id] & (1<Id] & (1< 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< Degree ) + continue; + // order the fanins in the increasing order of criticalily + if ( Vec_PtrSize(vTimeCries) > 1 ) + { + pFanin = Vec_PtrEntry( vTimeCries, 0 ); + pFanin2 = 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 = Vec_PtrEntry( vTimeCries, 1 ); + pFanin2 = Vec_PtrEntry( vTimeCries, 2 ); + if ( Nwk_ObjSlack(pFanin) < Nwk_ObjSlack(pFanin2) ) + { + Vec_PtrWriteEntry( vTimeCries, 1, pFanin2 ); + Vec_PtrWriteEntry( vTimeCries, 2, pFanin ); + } + pFanin = Vec_PtrEntry( vTimeCries, 0 ); + pFanin2 = 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 ); + 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 ( pAig->pEquivs[pAnd->Id] ) + { + if ( Aig_ObjRefs(pAig->pEquivs[pAnd->Id]) > 0 ) + pAig->pEquivs[pAnd->Id] = NULL; + } + + // put back the library + if ( !fUseLutLib ) + pNtk->pLutLib = pTempLib; + + // reconstruct the network + pAig = Aig_ManDupDfs( pTemp = pAig ); + Aig_ManStop( pTemp ); + // reset levels + Aig_ManChoiceLevel( pAig ); + return pAig; } //////////////////////////////////////////////////////////////////////// -- cgit v1.2.3