From e0eb270324ab71403ded07e9700152c2755e5095 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Tue, 18 Sep 2012 13:23:58 -0700 Subject: Changes to command 'upsize'. --- src/map/scl/sclUpsize.c | 309 +++++++++++++++++++++++++++++++++++++++++++----- 1 file changed, 280 insertions(+), 29 deletions(-) (limited to 'src/map/scl/sclUpsize.c') diff --git a/src/map/scl/sclUpsize.c b/src/map/scl/sclUpsize.c index 27631d0a..916fe57e 100644 --- a/src/map/scl/sclUpsize.c +++ b/src/map/scl/sclUpsize.c @@ -28,13 +28,15 @@ ABC_NAMESPACE_IMPL_START /// DECLARATIONS /// //////////////////////////////////////////////////////////////////////// +extern Vec_Int_t * Abc_SclFindCriticalCoWindow( SC_Man * p, int Window ); + //////////////////////////////////////////////////////////////////////// /// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* - Synopsis [Begin by upsizing gates will many fanouts.] + Synopsis [Collect near-critical COs.] Description [] @@ -43,30 +45,123 @@ ABC_NAMESPACE_IMPL_START SeeAlso [] ***********************************************************************/ -int Abc_SclManUpsize( SC_Man * p, int Degree ) +Vec_Int_t * Abc_SclFindCriticalCoWindow( SC_Man * p, int Window ) { - SC_Cell * pOld, * pNew; + float fMaxArr = Abc_SclGetMaxDelay( p ) * (100.0 - Window) / 100.0; + Vec_Int_t * vPivots; Abc_Obj_t * pObj; - int i, Count = 0; - Abc_NtkForEachNode1( p->pNtk, pObj, i ) + int i; + vPivots = Vec_IntAlloc( 100 ); + Abc_NtkForEachCo( p->pNtk, pObj, i ) + if ( Abc_SclObjTimeMax(p, pObj) >= fMaxArr ) + Vec_IntPush( vPivots, Abc_ObjId(pObj) ); + assert( Vec_IntSize(vPivots) > 0 ); + return vPivots; +} + +/**Function************************************************************* + + Synopsis [Collect near-critical internal nodes.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_SclFindCriticalNodeWindow_rec( SC_Man * p, Abc_Obj_t * pObj, Vec_Int_t * vPath, float fSlack ) +{ + Abc_Obj_t * pNext; + float fArrMax, fSlackFan; + int i; + if ( Abc_ObjIsCi(pObj) ) + return; + if ( Abc_NodeIsTravIdCurrent( pObj ) ) + return; + Abc_NodeSetTravIdCurrent( pObj ); + assert( Abc_ObjIsNode(pObj) ); + // compute the max arrival time of the fanins + fArrMax = Abc_SclGetMaxDelayNodeFanins( p, pObj ); + // traverse all fanins whose arrival times are within a window + Abc_ObjForEachFanin( pObj, pNext, i ) { - if ( Abc_ObjFanoutNum(pObj) < Degree ) - continue; - // find new gate - pOld = Abc_SclObjCell( p, pObj ); - pNew = Abc_SclObjResiable( p, pObj, 1 ); - if ( pNew == NULL ) - continue; - Vec_IntWriteEntry( p->vGates, Abc_ObjId(pObj), Abc_SclCellFind(p->pLib, pNew->pName) ); - Count++; + fSlackFan = fSlack - (fArrMax - Abc_SclObjTimeMax(p, pNext)); + if ( fSlackFan >= 0 ) + Abc_SclFindCriticalNodeWindow_rec( p, pNext, vPath, fSlackFan ); } - return Count; + Vec_IntPush( vPath, Abc_ObjId(pObj) ); +} +Vec_Int_t * Abc_SclFindCriticalNodeWindow( SC_Man * p, Vec_Int_t * vPathCos, int Window ) +{ + float fMaxArr = Abc_SclGetMaxDelay( p ); + float fSlack = fMaxArr * Window / 100.0; + Vec_Int_t * vPath = Vec_IntAlloc( 100 ); + Abc_Obj_t * pObj; + int i; + Abc_NtkIncrementTravId( p->pNtk ); + 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( vPath, p->pNtk, pObj, i ) + pObj->fMarkA = 1; + return vPath; +} +void Abc_SclUnmarkCriticalNodeWindow( SC_Man * p, Vec_Int_t * vPath ) +{ + Abc_Obj_t * pObj; + int i; + Abc_NtkForEachObjVec( vPath, p->pNtk, pObj, i ) + pObj->fMarkA = 0; +} + +/**Function************************************************************* + + Synopsis [Find the array of nodes to be updated.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Vec_Int_t * Abc_SclFindNodesToUpdate( Abc_Obj_t * pObj ) +{ + Vec_Int_t * vNodes; + Abc_Obj_t * pNext, * pNext2; + int i, k, Start; + assert( Abc_ObjIsNode(pObj) ); + assert( pObj->fMarkA ); + vNodes = Vec_IntAlloc( 16 ); + // collect fanins, node, and fanouts + Abc_ObjForEachFanin( pObj, 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 ) + if ( Abc_ObjIsNode(pNext) && pNext->fMarkA ) + 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 ); + return vNodes; } /**Function************************************************************* - Synopsis [] + Synopsis [Compute gain in changing the gate size.] Description [] @@ -75,29 +170,185 @@ int Abc_SclManUpsize( SC_Man * p, int Degree ) SeeAlso [] ***********************************************************************/ -void Abc_SclUpsizingPerform( SC_Lib * pLib, Abc_Ntk_t * pNtk, int Degree, int nRange, int fVerbose ) +float Abc_SclFindGain( SC_Man * p, Vec_Int_t * vCone ) { - SC_Man * p; - int nUpsizes; + double dGain = 0; + Abc_Obj_t * pObj; + int i, Start; + Start = Vec_IntEntryLast( vCone ); + vCone->nSize--; + + Abc_SclConeStore( p, vCone ); + Abc_SclTimeCone( p, vCone ); + Abc_NtkForEachObjVecStart( vCone, p->pNtk, pObj, i, Start ) + dGain += Abc_SclObjGain( p, pObj ); + Abc_SclConeRestore( p, vCone ); + dGain /= (Vec_IntSize(vCone) - Start); + + vCone->nSize++; + return (float)dGain; +} - // prepare the manager; collect init stats - p = Abc_SclManStart( pLib, pNtk, 1 ); +/**Function************************************************************* - // perform upsizing - nUpsizes = Abc_SclManUpsize( p, Degree ); + Synopsis [Begin by upsizing gates will many fanouts.] + + Description [] + + SideEffects [] + + SeeAlso [] - // recompute timing - Abc_SclTimeNtkRecompute( p, &p->SumArea, &p->MaxDelay ); +***********************************************************************/ +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; + Abc_Obj_t * pObj; + float dGain, dGainBest = 0; + int i, k, Entry, gateBest = -1; + int nUpsizes = 0; + + 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 ); + SC_RingForEachCell( pCellOld, pCellNew, k ) + { + Vec_IntWriteEntry( p->vGates, Abc_ObjId(pObj), pCellNew->Id ); + //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 ); + Abc_SclUpdateLoad( p, pObj, pCellNew, pCellOld ); + //printf( "gain is %f\n", dGain ); + if ( dGainBest < dGain ) + { + dGainBest = dGain; + gateBest = pCellNew->Id; + } + } + Vec_IntFree( vCone ); + Vec_IntWriteEntry( p->vGates, Abc_ObjId(pObj), pCellOld->Id ); + Vec_FltPush( vSavings, dGainBest ); + Vec_IntPush( vBests, gateBest ); + } + assert( Vec_IntSize(vBests) == Vec_IntSize(vPathNodes) ); + + // 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; + // find a good factor + vCosts = Vec_IntAlloc( Vec_FltSize(vSavings) ); + Vec_FltForEachEntry( vSavings, This, i ) + { + Vec_IntPush( vCosts, (int)(This * Factor) ); + assert( (int)(This * Factor) < (1<<30) ); + } + 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)) ); + vUpdates = Vec_IntAlloc( Limit ); + for ( i = 0; i < Limit; i++ ) + if ( Vec_FltEntry(vSavings, pPerm[i]) > 0 ) + Vec_IntPush( vUpdates, pPerm[i] ); + } + + // update the network + Vec_IntForEachEntry( vUpdates, Entry, i ) + { + 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)) ); + 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 ); + } + + + Vec_IntFree( vUpdates ); + Vec_IntFree( vBests ); + Vec_FltFree( vSavings ); + return nUpsizes; +} + + +/**Function************************************************************* + + Synopsis [Print cumulative statistics.] + + Description [] + + SideEffects [] + + SeeAlso [] - // print cumulative statistics - printf( "Resized: %d. ", nUpsizes ); - printf( "Delay: " ); +***********************************************************************/ +void Abc_SclUpsizePrint( SC_Man * p, int Iter, Vec_Int_t * vPathPos, Vec_Int_t * vPathNodes, int nUpsizes ) +{ + printf( "Iter %3d ", Iter ); + printf( "PathPOs:%5d. ", Vec_IntSize(vPathPos) ); + printf( "PathNodes:%6d. ", Vec_IntSize(vPathNodes) ); + printf( "Resized:%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( "Area: " ); + 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 ); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_SclUpsizePerform( SC_Lib * pLib, Abc_Ntk_t * pNtk, int Window, int Ratio, int nIters, int fVerbose ) +{ + SC_Man * p; + Vec_Int_t * vPathPos; // critical POs + Vec_Int_t * vPathNodes; // critical nodes and PIs + int i, nUpsizes; + + // prepare the manager; collect init stats + p = Abc_SclManStart( pLib, pNtk, 1 ); + + // perform upsizing + for ( i = 0; 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 ); + Vec_IntFree( vPathPos ); + Vec_IntFree( vPathNodes ); + } +// Abc_NtkCleanMarkAB( pNtk ); // save the result and quit Abc_SclManSetGates( pLib, pNtk, p->vGates ); // updates gate pointers -- cgit v1.2.3