From 48996f7a3698a3f3f8d3d03ffba5c51e9065649d Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Tue, 18 Sep 2012 19:12:54 -0700 Subject: Changes to command 'upsize'. --- src/map/scl/sclUpsize.c | 195 +++++++++++++++++++++++++++++++++--------------- 1 file changed, 133 insertions(+), 62 deletions(-) (limited to 'src/map/scl/sclUpsize.c') diff --git a/src/map/scl/sclUpsize.c b/src/map/scl/sclUpsize.c index 916fe57e..8f4d2ca0 100644 --- a/src/map/scl/sclUpsize.c +++ b/src/map/scl/sclUpsize.c @@ -34,6 +34,48 @@ extern Vec_Int_t * Abc_SclFindCriticalCoWindow( SC_Man * p, int Window ); /// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// +/**Function************************************************************* + + Synopsis [Collect TFO of nodes.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_SclFindTFO_rec( Abc_Obj_t * pObj, Vec_Int_t * vVisited ) +{ + Abc_Obj_t * pNext; + int i; +// if ( Abc_ObjIsCo(pObj) ) +// return; + if ( Abc_NodeIsTravIdCurrent( pObj ) ) + return; + Abc_NodeSetTravIdCurrent( pObj ); + Abc_ObjForEachFanout( pObj, pNext, i ) + Abc_SclFindTFO_rec( pNext, vVisited ); + Vec_IntPush( vVisited, Abc_ObjId(pObj) ); +} +Vec_Int_t * Abc_SclFindTFO( Abc_Ntk_t * p, Vec_Int_t * vPath ) +{ + Vec_Int_t * vVisited; + Abc_Obj_t * pObj, * pFanin; + int i, k; + assert( Vec_IntSize(vPath) > 0 ); + vVisited = Vec_IntAlloc( 100 ); + // collect nodes in the TFO + Abc_NtkIncrementTravId( p ); + Abc_NtkForEachObjVec( vPath, p, pObj, i ) + Abc_ObjForEachFanin( pObj, pFanin, k ) + if ( Abc_ObjIsNode(pFanin) ) + Abc_SclFindTFO_rec( pFanin, vVisited ); + // reverse order + Vec_IntReverseOrder( vVisited ); + return vVisited; +} + /**Function************************************************************* Synopsis [Collect near-critical COs.] @@ -103,6 +145,8 @@ Vec_Int_t * Abc_SclFindCriticalNodeWindow( SC_Man * p, Vec_Int_t * vPathCos, int Abc_NtkForEachObjVec( vPathCos, p->pNtk, pObj, i ) Abc_SclFindCriticalNodeWindow_rec( p, Abc_ObjFanin0(pObj), vPath, fSlack - (fMaxArr - Abc_SclObjTimeMax(p, pObj)) ); // label critical nodes + Abc_NtkForEachObjVec( vPathCos, p->pNtk, pObj, i ) + pObj->fMarkA = 1; Abc_NtkForEachObjVec( vPath, p->pNtk, pObj, i ) pObj->fMarkA = 1; return vPath; @@ -126,35 +170,48 @@ void Abc_SclUnmarkCriticalNodeWindow( SC_Man * p, Vec_Int_t * vPath ) SeeAlso [] ***********************************************************************/ -Vec_Int_t * Abc_SclFindNodesToUpdate( Abc_Obj_t * pObj ) +Vec_Int_t * Abc_SclFindNodesToUpdate( Abc_Obj_t * pPivot, Vec_Int_t ** pvEvals ) { + Abc_Ntk_t * p = Abc_ObjNtk(pPivot); + Abc_Obj_t * pObj, * pNext, * pNext2; Vec_Int_t * vNodes; - Abc_Obj_t * pNext, * pNext2; - int i, k, Start; - assert( Abc_ObjIsNode(pObj) ); - assert( pObj->fMarkA ); - vNodes = Vec_IntAlloc( 16 ); + int i, k; + assert( Abc_ObjIsNode(pPivot) ); + assert( pPivot->fMarkA ); // collect fanins, node, and fanouts - Abc_ObjForEachFanin( pObj, pNext, i ) + vNodes = Vec_IntAlloc( 16 ); + Abc_ObjForEachFanin( pPivot, pNext, i ) if ( Abc_ObjIsNode(pNext) ) Vec_IntPush( vNodes, Abc_ObjId(pNext) ); - Vec_IntPush( vNodes, Abc_ObjId(pObj) ); - Abc_ObjForEachFanout( pObj, pNext, i ) - if ( Abc_ObjIsNode(pNext) && pNext->fMarkA ) - Vec_IntPush( vNodes, Abc_ObjId(pNext) ), pNext->fMarkB = 1; - // remember this position - Start = Vec_IntSize(vNodes); - // label collected nodes - Abc_ObjForEachFanout( pObj, pNext, i ) + Vec_IntPush( vNodes, Abc_ObjId(pPivot) ); + Abc_ObjForEachFanout( pPivot, pNext, i ) if ( Abc_ObjIsNode(pNext) && pNext->fMarkA ) + { + Vec_IntPush( vNodes, Abc_ObjId(pNext) ); Abc_ObjForEachFanout( pNext, pNext2, k ) - if ( Abc_ObjIsNode(pNext2) && pNext2->fMarkA && !pNext2->fMarkB ) - Vec_IntPush( vNodes, Abc_ObjId(pNext2) ), pNext2->fMarkB = 1; - // clean the fanouts - Abc_NtkForEachObjVec( vNodes, pObj->pNtk, pNext, i ) - pNext->fMarkB = 0; - // save position at the last entry - Vec_IntPush( vNodes, Start ); + if ( Abc_ObjIsNode(pNext2) && pNext2->fMarkA ) + Vec_IntPush( vNodes, Abc_ObjId(pNext2) ); + } + Vec_IntUniqify( vNodes ); + // label nodes + Abc_NtkForEachObjVec( vNodes, p, pObj, i ) + { + assert( pObj->fMarkB == 0 ); + pObj->fMarkB = 1; + } + // collect nodes pointed to by non-labeled nodes + *pvEvals = Vec_IntAlloc( 10 ); + Abc_NtkForEachObjVec( vNodes, p, pObj, i ) + Abc_ObjForEachFanout( pObj, pNext, k ) + if ( pNext->fMarkA && !pNext->fMarkB ) + { + Vec_IntPush( *pvEvals, Abc_ObjId(pObj) ); + break; + } + assert( Vec_IntSize(*pvEvals) > 0 ); + // label nodes + Abc_NtkForEachObjVec( vNodes, p, pObj, i ) + pObj->fMarkB = 0; return vNodes; } @@ -170,22 +227,17 @@ Vec_Int_t * Abc_SclFindNodesToUpdate( Abc_Obj_t * pObj ) SeeAlso [] ***********************************************************************/ -float Abc_SclFindGain( SC_Man * p, Vec_Int_t * vCone ) +float Abc_SclFindGain( SC_Man * p, Vec_Int_t * vCone, Vec_Int_t * vEvals ) { double dGain = 0; Abc_Obj_t * pObj; - int i, Start; - Start = Vec_IntEntryLast( vCone ); - vCone->nSize--; - + int i; Abc_SclConeStore( p, vCone ); Abc_SclTimeCone( p, vCone ); - Abc_NtkForEachObjVecStart( vCone, p->pNtk, pObj, i, Start ) + Abc_NtkForEachObjVec( vEvals, p->pNtk, pObj, i ) dGain += Abc_SclObjGain( p, pObj ); Abc_SclConeRestore( p, vCone ); - dGain /= (Vec_IntSize(vCone) - Start); - - vCone->nSize++; + dGain /= Vec_IntSize(vEvals); return (float)dGain; } @@ -203,30 +255,32 @@ float Abc_SclFindGain( SC_Man * p, Vec_Int_t * vCone ) int Abc_SclFindUpsizes( SC_Man * p, Vec_Int_t * vPathNodes, int Ratio ) { SC_Cell * pCellOld, * pCellNew; - Vec_Flt_t * vSavings; - Vec_Int_t * vBests; - Vec_Int_t * vCone; - Vec_Int_t * vUpdates; + Vec_Flt_t * vSavings; // best gain for each node + Vec_Int_t * vBests; // best gate for each node + Vec_Int_t * vCone, * vEvals, * vUpdates; Abc_Obj_t * pObj; float dGain, dGainBest = 0; int i, k, Entry, gateBest = -1; int nUpsizes = 0; +// return nUpsizes; + vSavings = Vec_FltAlloc( Vec_IntSize(vPathNodes) ); vBests = Vec_IntAlloc( Vec_IntSize(vPathNodes) ); Abc_NtkForEachObjVec( vPathNodes, p->pNtk, pObj, i ) { dGainBest = 0; pCellOld = Abc_SclObjCell( p, pObj ); - assert( pCellOld->Id == Vec_IntEntry(p->vGates, Abc_ObjId(pObj)) ); // try different gate sizes for this node - vCone = Abc_SclFindNodesToUpdate( pObj ); + vCone = Abc_SclFindNodesToUpdate( pObj, &vEvals ); SC_RingForEachCell( pCellOld, pCellNew, k ) { - Vec_IntWriteEntry( p->vGates, Abc_ObjId(pObj), pCellNew->Id ); + if ( pCellNew == pCellOld ) + continue; + Abc_SclObjSetCell( p, pObj, pCellNew ); //printf( "changing %s for %s at node %d ", pCellOld->pName, pCellNew->pName, Abc_ObjId(pObj) ); Abc_SclUpdateLoad( p, pObj, pCellOld, pCellNew ); - dGain = Abc_SclFindGain( p, vCone ); + dGain = Abc_SclFindGain( p, vCone, vEvals ); Abc_SclUpdateLoad( p, pObj, pCellNew, pCellOld ); //printf( "gain is %f\n", dGain ); if ( dGainBest < dGain ) @@ -235,8 +289,10 @@ int Abc_SclFindUpsizes( SC_Man * p, Vec_Int_t * vPathNodes, int Ratio ) gateBest = pCellNew->Id; } } + assert( dGainBest >= 0.0 ); Vec_IntFree( vCone ); - Vec_IntWriteEntry( p->vGates, Abc_ObjId(pObj), pCellOld->Id ); + Vec_IntFree( vEvals ); + Abc_SclObjSetCell( p, pObj, pCellOld ); Vec_FltPush( vSavings, dGainBest ); Vec_IntPush( vBests, gateBest ); } @@ -245,11 +301,9 @@ int Abc_SclFindUpsizes( SC_Man * p, Vec_Int_t * vPathNodes, int Ratio ) // we have computed the gains - find the best ones { Vec_Int_t * vCosts; - int * pPerm; float Max = Vec_FltFindMax( vSavings ); - float Factor = 1.0 * (1<<28) / Max; - float This; - int i, Limit; + float Factor = 1.0 * (1<<28) / Max, This; + int i, Limit, * pPerm; // find a good factor vCosts = Vec_IntAlloc( Vec_FltSize(vSavings) ); Vec_FltForEachEntry( vSavings, This, i ) @@ -260,28 +314,31 @@ int Abc_SclFindUpsizes( SC_Man * p, Vec_Int_t * vPathNodes, int Ratio ) pPerm = Abc_QuickSortCost( Vec_IntArray(vCosts), Vec_IntSize(vCosts), 1 ); assert( Vec_FltEntry(vSavings, pPerm[0]) >= Vec_FltEntry(vSavings, pPerm[Vec_FltSize(vSavings)-1]) ); // find those that are good to update - Limit = Abc_MinInt( 1, (int)(0.01 * Ratio * Vec_IntSize(vBests)) ); + Limit = Abc_MaxInt( 1, (int)(0.01 * Ratio * Vec_IntSize(vBests)) ); vUpdates = Vec_IntAlloc( Limit ); for ( i = 0; i < Limit; i++ ) if ( Vec_FltEntry(vSavings, pPerm[i]) > 0 ) Vec_IntPush( vUpdates, pPerm[i] ); + Vec_IntFree( vCosts ); + ABC_FREE( pPerm ); } // update the network Vec_IntForEachEntry( vUpdates, Entry, i ) { + // get the object pObj = Abc_NtkObj( p->pNtk, Vec_IntEntry(vPathNodes, Entry) ); // find new gate pCellOld = Abc_SclObjCell( p, pObj ); - pCellNew = SC_LibCell( p->pLib, Vec_IntEntry(vBests, Abc_ObjId(pObj)) ); + pCellNew = SC_LibCell( p->pLib, Vec_IntEntry(vBests, Entry) ); assert( pCellNew != NULL ); // update gate Abc_SclUpdateLoad( p, pObj, pCellOld, pCellNew ); p->SumArea += pCellNew->area - pCellOld->area; - Vec_IntWriteEntry( p->vGates, Abc_ObjId(pObj), pCellNew->Id ); + Abc_SclObjSetCell( p, pObj, pCellNew ); + nUpsizes++; } - Vec_IntFree( vUpdates ); Vec_IntFree( vBests ); Vec_FltFree( vSavings ); @@ -300,19 +357,20 @@ int Abc_SclFindUpsizes( SC_Man * p, Vec_Int_t * vPathNodes, int Ratio ) SeeAlso [] ***********************************************************************/ -void Abc_SclUpsizePrint( SC_Man * p, int Iter, Vec_Int_t * vPathPos, Vec_Int_t * vPathNodes, int nUpsizes ) +void Abc_SclUpsizePrint( SC_Man * p, int Iter, Vec_Int_t * vPathPos, Vec_Int_t * vPathNodes, Vec_Int_t * vTFO, int nUpsizes ) { - printf( "Iter %3d ", Iter ); - printf( "PathPOs:%5d. ", Vec_IntSize(vPathPos) ); - printf( "PathNodes:%6d. ", Vec_IntSize(vPathNodes) ); - printf( "Resized:%5d. ", nUpsizes ); + printf( "Iter %3d ", Iter ); + printf( "PO:%5d. ", Vec_IntSize(vPathPos) ); + printf( "Node:%6d. ", Vec_IntSize(vPathNodes) ); + printf( "TFO:%6d. ", Vec_IntSize(vTFO) ); + printf( "Size:%5d. ", nUpsizes ); printf( "D: " ); - printf( "%.2f -> %.2f ps ", SC_LibTimePs(p->pLib, p->MaxDelay0), SC_LibTimePs(p->pLib, p->MaxDelay) ); - printf( "(%+.1f %%). ", 100.0 * (p->MaxDelay - p->MaxDelay0)/ p->MaxDelay0 ); + printf( "%.2f ps ", SC_LibTimePs(p->pLib, p->MaxDelay) ); + printf( "(%+5.1f %%) ", 100.0 * (p->MaxDelay - p->MaxDelay0)/ p->MaxDelay0 ); printf( "A: " ); - printf( "%.2f -> %.2f ", p->SumArea0, p->SumArea ); - printf( "(%+.1f %%). ", 100.0 * (p->SumArea - p->SumArea0)/ p->SumArea0 ); - Abc_PrintTime( 1, "Time", clock() - p->clkStart ); + printf( "%.2f ", p->SumArea ); + printf( "(%+5.1f %%) ", 100.0 * (p->SumArea - p->SumArea0)/ p->SumArea0 ); + Abc_PrintTime( 1, "Time", clock() - p->clkStart ); } /**Function************************************************************* @@ -331,22 +389,35 @@ void Abc_SclUpsizePerform( SC_Lib * pLib, Abc_Ntk_t * pNtk, int Window, int Rati SC_Man * p; Vec_Int_t * vPathPos; // critical POs Vec_Int_t * vPathNodes; // critical nodes and PIs - int i, nUpsizes; + Vec_Int_t * vTFO; + int i, nUpsizes = -1; // prepare the manager; collect init stats p = Abc_SclManStart( pLib, pNtk, 1 ); // perform upsizing - for ( i = 0; i < nIters; i++ ) + for ( i = 0; nUpsizes && i < nIters; i++ ) { vPathPos = Abc_SclFindCriticalCoWindow( p, Window ); vPathNodes = Abc_SclFindCriticalNodeWindow( p, vPathPos, Window ); nUpsizes = Abc_SclFindUpsizes( p, vPathNodes, Ratio ); Abc_SclUnmarkCriticalNodeWindow( p, vPathNodes ); - Abc_SclTimeNtkRecompute( p, &p->SumArea, &p->MaxDelay ); - Abc_SclUpsizePrint( p, i, vPathPos, vPathNodes, nUpsizes ); + Abc_SclUnmarkCriticalNodeWindow( p, vPathPos ); + + // update info + vTFO = Abc_SclFindTFO( p->pNtk, vPathNodes ); +// Abc_SclTimeNtkRecompute( p, &p->SumArea, &p->MaxDelay ); + Abc_SclConeStore( p, vTFO ); + Abc_SclTimeCone( p, vTFO ); + p->MaxDelay = Abc_SclGetMaxDelay( p ); + + Abc_SclUpsizePrint( p, i, vPathPos, vPathNodes, vTFO, nUpsizes ); Vec_IntFree( vPathPos ); Vec_IntFree( vPathNodes ); + Vec_IntFree( vTFO ); + + if ( i && i % 50 == 0 ) + Abc_SclComputeLoad( p ); } // Abc_NtkCleanMarkAB( pNtk ); -- cgit v1.2.3