diff options
Diffstat (limited to 'src/map/scl/sclBuffer.c')
| -rw-r--r-- | src/map/scl/sclBuffer.c | 301 |
1 files changed, 238 insertions, 63 deletions
diff --git a/src/map/scl/sclBuffer.c b/src/map/scl/sclBuffer.c index f25ea277..d9afdbe5 100644 --- a/src/map/scl/sclBuffer.c +++ b/src/map/scl/sclBuffer.c @@ -59,6 +59,7 @@ struct Buf_Man_t_ int nDuplicate; int nBranch0; int nBranch1; + int nBranchCrit; }; static inline int Abc_BufNodeArr( Buf_Man_t * p, Abc_Obj_t * pObj ) { return Vec_IntEntry( p->vArr, Abc_ObjId(pObj) ); } @@ -76,6 +77,177 @@ static inline int Abc_BufEdgeSlack( Buf_Man_t * p, Abc_Obj_t * pObj, Abc_Obj_t /**Function************************************************************* + Synopsis [Make sure the network is in topo order without dangling nodes.] + + Description [Returns 1 iff the network is fine.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_SclCheckNtk( Abc_Ntk_t * p, int fVerbose ) +{ + Abc_Obj_t * pObj, * pFanin; + int i, k, fFlag = 1; + Abc_NtkIncrementTravId( p ); + Abc_NtkForEachCi( p, pObj, i ) + Abc_NodeSetTravIdCurrent( pObj ); + Abc_NtkForEachNode( p, pObj, i ) + { + Abc_ObjForEachFanin( pObj, pFanin, k ) + if ( !Abc_NodeIsTravIdCurrent( pFanin ) ) + printf( "obj %d and its fanin %d are not in the topo order\n", Abc_ObjId(pObj), Abc_ObjId(pFanin) ), fFlag = 0; + Abc_NodeSetTravIdCurrent( pObj ); + if ( Abc_ObjFanoutNum(pObj) == 0 ) + printf( "node %d has no fanout\n", Abc_ObjId(pObj) ), fFlag = 0; + if ( !fFlag ) + break; + } + if ( fFlag && fVerbose ) + printf( "The network is in topo order and no dangling nodes.\n" ); + return fFlag; +} + +/**Function************************************************************* + + Synopsis [Performs buffering of the mapped network (old code).] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_NodeCompareLevels( Abc_Obj_t ** pp1, Abc_Obj_t ** pp2 ) +{ + int Diff = Abc_ObjLevel(*pp1) - Abc_ObjLevel(*pp2); + if ( Diff < 0 ) + return -1; + if ( Diff > 0 ) + return 1; + Diff = (*pp1)->Id - (*pp2)->Id; // needed to make qsort() platform-infependent + if ( Diff < 0 ) + return -1; + if ( Diff > 0 ) + return 1; + return 0; +} +int Abc_SclComputeReverseLevel( Abc_Obj_t * pObj ) +{ + Abc_Obj_t * pFanout; + int i, Level = 0; + Abc_ObjForEachFanout( pObj, pFanout, i ) + Level = Abc_MaxInt( Level, pFanout->Level ); + return Level + 1; +} +Abc_Obj_t * Abc_SclPerformBufferingOne( Abc_Obj_t * pObj, int Degree, int fUseInvs, int fVerbose ) +{ + Vec_Ptr_t * vFanouts; + Abc_Obj_t * pBuffer, * pFanout; + int i, Degree0 = Degree; + assert( Abc_ObjFanoutNum(pObj) > Degree ); + // collect fanouts and sort by reverse level + vFanouts = Vec_PtrAlloc( Abc_ObjFanoutNum(pObj) ); + Abc_NodeCollectFanouts( pObj, vFanouts ); + Vec_PtrSort( vFanouts, (int (*)(void))Abc_NodeCompareLevels ); + // select the first Degree fanouts + if ( fUseInvs ) + pBuffer = Abc_NtkCreateNodeInv( pObj->pNtk, NULL ); + else + pBuffer = Abc_NtkCreateNodeBuf( pObj->pNtk, NULL ); + // check if it is possible to not increase level + if ( Vec_PtrSize(vFanouts) < 2 * Degree ) + { + Abc_Obj_t * pFanPrev = (Abc_Obj_t *)Vec_PtrEntry(vFanouts, Vec_PtrSize(vFanouts)-1-Degree); + Abc_Obj_t * pFanThis = (Abc_Obj_t *)Vec_PtrEntry(vFanouts, Degree-1); + Abc_Obj_t * pFanLast = (Abc_Obj_t *)Vec_PtrEntryLast(vFanouts); + if ( Abc_ObjLevel(pFanThis) == Abc_ObjLevel(pFanLast) && + Abc_ObjLevel(pFanPrev) < Abc_ObjLevel(pFanThis) ) + { + // find the first one whose level is the same as last + Vec_PtrForEachEntry( Abc_Obj_t *, vFanouts, pFanout, i ) + if ( Abc_ObjLevel(pFanout) == Abc_ObjLevel(pFanLast) ) + break; + assert( i < Vec_PtrSize(vFanouts) ); + if ( i > 1 ) + Degree = i; + } + // make the last two more well-balanced + if ( Degree == Degree0 && Degree > Vec_PtrSize(vFanouts) - Degree ) + Degree = Vec_PtrSize(vFanouts)/2 + (Vec_PtrSize(vFanouts) & 1); + assert( Degree <= Degree0 ); + } + // select fanouts + Vec_PtrForEachEntryStop( Abc_Obj_t *, vFanouts, pFanout, i, Degree ) + Abc_ObjPatchFanin( pFanout, pObj, pBuffer ); + if ( fVerbose ) + { + printf( "%5d : ", Abc_ObjId(pObj) ); + Vec_PtrForEachEntry( Abc_Obj_t *, vFanouts, pFanout, i ) + printf( "%d%s ", Abc_ObjLevel(pFanout), i == Degree-1 ? " " : "" ); + printf( "\n" ); + } + Vec_PtrFree( vFanouts ); + Abc_ObjAddFanin( pBuffer, pObj ); + pBuffer->Level = Abc_SclComputeReverseLevel( pBuffer ); + return pBuffer; +} +void Abc_SclPerformBuffering_rec( Abc_Obj_t * pObj, int Degree, int fUseInvs, int fVerbose ) +{ + Abc_Obj_t * pFanout; + int i; + if ( Abc_NodeIsTravIdCurrent( pObj ) ) + return; + Abc_NodeSetTravIdCurrent( pObj ); + pObj->Level = 0; + if ( Abc_ObjIsCo(pObj) ) + return; + assert( Abc_ObjIsCi(pObj) || Abc_ObjIsNode(pObj) ); + // buffer fanouts and collect reverse levels + Abc_ObjForEachFanout( pObj, pFanout, i ) + Abc_SclPerformBuffering_rec( pFanout, Degree, fUseInvs, fVerbose ); + // perform buffering as long as needed + while ( Abc_ObjFanoutNum(pObj) > Degree ) + Abc_SclPerformBufferingOne( pObj, Degree, fUseInvs, fVerbose ); + // compute the new level of the node + pObj->Level = Abc_SclComputeReverseLevel( pObj ); +} +Abc_Ntk_t * Abc_SclPerformBuffering( Abc_Ntk_t * p, int Degree, int fUseInvs, int fVerbose ) +{ + Vec_Int_t * vCiLevs; + Abc_Ntk_t * pNew; + Abc_Obj_t * pObj; + int i; + assert( Abc_NtkHasMapping(p) ); + if ( fUseInvs ) + printf( "Warning!!! Using inverters instead of buffers.\n" ); + // remember CI levels + vCiLevs = Vec_IntAlloc( Abc_NtkCiNum(p) ); + Abc_NtkForEachCi( p, pObj, i ) + Vec_IntPush( vCiLevs, Abc_ObjLevel(pObj) ); + // perform buffering + Abc_NtkIncrementTravId( p ); + Abc_NtkForEachCi( p, pObj, i ) + Abc_SclPerformBuffering_rec( pObj, Degree, fUseInvs, fVerbose ); + // recompute logic levels + Abc_NtkForEachCi( p, pObj, i ) + pObj->Level = Vec_IntEntry( vCiLevs, i ); + Abc_NtkForEachNode( p, pObj, i ) + Abc_ObjLevelNew( pObj ); + Vec_IntFree( vCiLevs ); + // duplication in topo order + pNew = Abc_NtkDupDfs( p ); + Abc_SclCheckNtk( pNew, fVerbose ); +// Abc_NtkDelete( pNew ); + return pNew; +} + + + +/**Function************************************************************* + Synopsis [] Description [] @@ -134,8 +306,10 @@ void Abc_BufAddToQue( Buf_Man_t * p, Abc_Obj_t * pObj ) if ( Abc_ObjFanoutNum(pObj) < p->nFanMin ) return; Vec_FltWriteEntry( p->vCounts, Abc_ObjId(pObj), Abc_ObjFanoutNum(pObj) ); - assert( !Vec_QueIsMember(p->vQue, Abc_ObjId(pObj)) ); - Vec_QuePush( p->vQue, Abc_ObjId(pObj) ); + if ( Vec_QueIsMember(p->vQue, Abc_ObjId(pObj)) ) + Vec_QueUpdate( p->vQue, Abc_ObjId(pObj) ); + else + Vec_QuePush( p->vQue, Abc_ObjId(pObj) ); } @@ -241,7 +415,7 @@ void Abc_BufUpdateDep( Buf_Man_t * p, Abc_Obj_t * pObj ) SeeAlso [] ***********************************************************************/ -Buf_Man_t * Buf_ManStart( Abc_Ntk_t * pNtk ) +Buf_Man_t * Buf_ManStart( Abc_Ntk_t * pNtk, int FanMin, int FanMax ) { Buf_Man_t * p; Abc_Obj_t * pObj; @@ -249,8 +423,8 @@ Buf_Man_t * Buf_ManStart( Abc_Ntk_t * pNtk ) int i; p = ABC_CALLOC( Buf_Man_t, 1 ); p->pNtk = pNtk; - p->nFanMin = 6; -// p->nFanMax = 16; + p->nFanMin = FanMin; + p->nFanMax = FanMax; // allocate arrays p->nObjStart = Abc_NtkObjNumMax(p->pNtk); p->nObjAlloc = (6 * Abc_NtkObjNumMax(p->pNtk) / 3) + 100; @@ -279,15 +453,14 @@ Buf_Man_t * Buf_ManStart( Abc_Ntk_t * pNtk ) Vec_PtrForEachEntryReverse( Abc_Obj_t *, vNodes, pObj, i ) Abc_BufComputeDep( p, pObj ); Abc_BufUpdateGlobal( p ); +// Abc_NtkForEachNode( p->pNtk, pObj, i ) +// printf( "%4d : %4d %4d\n", i, Abc_BufNodeArr(p, pObj), Abc_BufNodeDep(p, pObj) ); // create fanout queue Abc_NtkForEachCi( p->pNtk, pObj, i ) Abc_BufAddToQue( p, pObj ); Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, i ) Abc_BufAddToQue( p, pObj ); Vec_PtrFree( vNodes ); - // print everything -// Abc_NtkForEachNode( p->pNtk, pObj, i ) -// printf( "%4d : %4d %4d\n", i, Abc_BufNodeArr(p, pObj), Abc_BufNodeDep(p, pObj) ); p->vDelays = Vec_IntAlloc( 100 ); p->vOrder = Vec_IntAlloc( 100 ); p->vNonCrit = Vec_IntAlloc( 100 ); @@ -297,8 +470,8 @@ Buf_Man_t * Buf_ManStart( Abc_Ntk_t * pNtk ) } void Buf_ManStop( Buf_Man_t * p ) { - printf( "Sep = %d. Dup = %d. Br0 = %d. Br1 = %d. ", - p->nSeparate, p->nDuplicate, p->nBranch0, p->nBranch1 ); + printf( "Sep = %d. Dup = %d. Br0 = %d. Br1 = %d. BrC = %d. ", + p->nSeparate, p->nDuplicate, p->nBranch0, p->nBranch1, p->nBranchCrit ); printf( "Orig = %d. Add = %d. Rem = %d.\n", p->nObjStart, Abc_NtkObjNumMax(p->pNtk) - p->nObjStart, p->nObjAlloc - Abc_NtkObjNumMax(p->pNtk) ); @@ -337,17 +510,14 @@ Vec_Int_t * Abc_BufSortByDelay( Buf_Man_t * p, int iPivot ) Abc_ObjForEachFanout( pObj, pFanout, i ) { int Slack = Abc_BufEdgeSlack(p, pObj, pFanout); - if ( Slack < 0 ) - printf( "%d ", Slack ); + assert( Slack >= 0 ); Vec_IntPush( p->vDelays, Abc_MaxInt(0, Slack) ); } pOrder = Abc_QuickSortCost( Vec_IntArray(p->vDelays), Vec_IntSize(p->vDelays), 0 ); -//Vec_IntPrint( p->vDelays ); Vec_IntClear( p->vOrder ); for ( i = 0; i < Vec_IntSize(p->vDelays); i++ ) Vec_IntPush( p->vOrder, Abc_ObjId(Abc_ObjFanout(pObj, pOrder[i])) ); ABC_FREE( pOrder ); - // print // for ( i = 0; i < Vec_IntSize(p->vDelays); i++ ) // printf( "%5d - %5d ", Vec_IntEntry(p->vOrder, i), Abc_BufEdgeSlack(p, pObj, Abc_NtkObj(p->pNtk, Vec_IntEntry(p->vOrder, i))) ); return p->vOrder; @@ -379,6 +549,34 @@ void Abc_BufPrintOne( Buf_Man_t * p, int iPivot ) SeeAlso [] ***********************************************************************/ +void Abc_BufReplaceBufsByInvs( Abc_Ntk_t * pNtk ) +{ + Abc_Obj_t * pObj, * pInv; + int i, Counter = 0; + Abc_NtkForEachNode( pNtk, pObj, i ) + { + if ( !Abc_NodeIsBuf(pObj) ) + continue; + assert( pObj->pData == Mio_LibraryReadBuf((Mio_Library_t *)pNtk->pManFunc) ); + pObj->pData = Mio_LibraryReadInv((Mio_Library_t *)pNtk->pManFunc); + pInv = Abc_NtkCreateNodeInv( pNtk, Abc_ObjFanin0(pObj) ); + Abc_ObjPatchFanin( pObj, Abc_ObjFanin0(pObj), pInv ); + Counter++; + } + printf( "Replaced %d buffers by invertor pairs.\n", Counter ); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ int Abc_BufComputeAverage( Buf_Man_t * p, int iPivot, Vec_Int_t * vOrder ) { Abc_Obj_t * pObj, * pFanout; @@ -388,17 +586,6 @@ int Abc_BufComputeAverage( Buf_Man_t * p, int iPivot, Vec_Int_t * vOrder ) Average += Abc_BufEdgeSlack( p, pObj, pFanout ); return Average / Vec_IntSize(vOrder); } -int Abc_BufCountNonCritical_( Buf_Man_t * p, int iPivot, Vec_Int_t * vOrder ) -{ - Abc_Obj_t * pObj, * pFanout; - int i; - Vec_IntClear( p->vNonCrit ); - pObj = Abc_NtkObj( p->pNtk, iPivot ); - Abc_NtkForEachObjVec( vOrder, p->pNtk, pFanout, i ) - if ( Abc_BufEdgeSlack( p, pObj, pFanout ) > 5*BUF_SCALE/2 ) - Vec_IntPush( p->vNonCrit, Abc_ObjId(pFanout) ); - return Vec_IntSize(p->vNonCrit); -} Abc_Obj_t * Abc_BufFindNonBuffDriver( Buf_Man_t * p, Abc_Obj_t * pObj ) { return (Abc_ObjIsNode(pObj) && Abc_NodeIsBuf(pObj)) ? Abc_BufFindNonBuffDriver(p, Abc_ObjFanin0(pObj)) : pObj; @@ -421,35 +608,30 @@ int Abc_BufCountNonCritical( Buf_Man_t * p, Abc_Obj_t * pObj ) int i; Vec_IntClear( p->vNonCrit ); Abc_ObjForEachFanout( pObj, pFanout, i ) - if ( Abc_BufEdgeSlack( p, pObj, pFanout ) > 3*BUF_SCALE ) + if ( Abc_BufEdgeSlack( p, pObj, pFanout ) > 5*BUF_SCALE/2 ) Vec_IntPush( p->vNonCrit, Abc_ObjId(pFanout) ); return Vec_IntSize(p->vNonCrit); } void Abc_BufPerformOne( Buf_Man_t * p, int iPivot, int fVerbose ) { Abc_Obj_t * pObj, * pFanout; - Vec_Int_t * vOrder; - int Fastest, Slowest, Average; int i, j, nCrit, nNonCrit; int DelayMax = p->DelayMax; + assert( Abc_NtkObjNumMax(p->pNtk) + 30 < p->nObjAlloc ); pObj = Abc_NtkObj( p->pNtk, iPivot ); +// assert( Vec_FltEntry(p->vCounts, iPivot) == (float)Abc_ObjFanoutNum(pObj) ); nNonCrit = Abc_BufCountNonCritical( p, pObj ); nCrit = Abc_ObjFanoutNum(pObj) - nNonCrit; if ( fVerbose ) { -vOrder = Abc_BufSortByDelay( p, iPivot ); //Abc_BufPrintOne( p, iPivot ); -Fastest = Abc_BufEdgeSlack( p, pObj, Abc_NtkObj(p->pNtk, Vec_IntEntry(vOrder,0)) ); -Slowest = Abc_BufEdgeSlack( p, pObj, Abc_NtkObj(p->pNtk, Vec_IntEntryLast(vOrder)) ); -Average = Abc_BufComputeAverage( p, iPivot, vOrder ); -printf( "FI =%2d. FO =%4d. ", Abc_ObjFaninNum(pObj), Abc_ObjFanoutNum(pObj) ); -printf( "Fastest =%5d. Slowest =%5d. Ave =%5d. Crit =%3d. NonCrit =%3d. ", Fastest, Slowest, Average, nCrit, nNonCrit ); +printf( "ObjId = %6d : %-10s FI = %d. FO =%4d. Crit =%4d. ", + Abc_ObjId(pObj), Mio_GateReadName((Mio_Gate_t *)pObj->pData), Abc_ObjFaninNum(pObj), Abc_ObjFanoutNum(pObj), nCrit ); } - // decide based on these - assert( Abc_NtkObjNumMax(p->pNtk) + 30 < p->nObjAlloc ); + // consider three cases if ( nCrit > 0 && nNonCrit > 1 ) { - // separate using buffer + // (1) both critical and non-critical are present - split them by adding buffer Abc_Obj_t * pBuffer = Abc_NtkCreateNodeBuf( p->pNtk, pObj ); Abc_NtkForEachObjVec( p->vNonCrit, p->pNtk, pFanout, i ) Abc_ObjPatchFanin( pFanout, pObj, pBuffer ); @@ -463,10 +645,9 @@ printf( "Fastest =%5d. Slowest =%5d. Ave =%5d. Crit =%3d. NonCrit =%3d. ", Fas if ( fVerbose ) printf( "Adding buffer\n" ); } - - else if ( nNonCrit < 2 && Abc_ObjFanoutNum(pObj) > 4 && Abc_ObjFanoutNum(pObj) < 12 && Abc_ObjIsNode(pObj) ) + else if ( nCrit > 0 && Abc_ObjIsNode(pObj) && Abc_ObjFanoutNum(pObj) > p->nFanMin )//&& Abc_ObjFaninNum(pObj) < 2 ) { - // duplicate + // (2) only critical are present - duplicate Abc_Obj_t * pClone = Abc_NtkDupObj( p->pNtk, pObj, 0 ); Abc_ObjForEachFanin( pObj, pFanout, i ) Abc_ObjAddFanin( pClone, pFanout ); @@ -480,26 +661,24 @@ printf( "Adding buffer\n" ); Abc_BufUpdateDep( p, pClone ); Abc_BufAddToQue( p, pObj ); Abc_BufAddToQue( p, pClone ); + Abc_ObjForEachFanin( pObj, pFanout, i ) + Abc_BufAddToQue( p, pFanout ); p->nDuplicate++; - // add fanins to queue if ( fVerbose ) printf( "Duplicating node\n" ); } - - else if ( Abc_ObjFanoutNum(pObj) >= 12 ) + else if ( (nCrit > 0 && Abc_ObjFanoutNum(pObj) > 8) || Abc_ObjFanoutNum(pObj) > p->nFanMax ) { - // branch (consider buffer) -// int nFan = Abc_ObjFanoutNum(pObj); - int nFan = 64; - double Res = pow(nFan, 0.34); - int Temp = (int)pow(Abc_ObjFanoutNum(pObj), 0.34); - int nDegree = Abc_MinInt( 4, (int)pow(Abc_ObjFanoutNum(pObj), 0.34) ); - int n1Degree = Abc_ObjFanoutNum(pObj) / nDegree + 1; - int n1Number = Abc_ObjFanoutNum(pObj) % nDegree; - int nFirst = n1Degree * n1Number; -// Abc_Obj_t * pNonBuff = Abc_BufFindNonBuffDriver( p, pObj ); - // create inverters + // (2) only critical or only non-critical - add buffer/inverter tree + int nDegree, n1Degree, n1Number, nFirst; int iFirstBuf = Abc_NtkObjNumMax( p->pNtk ); +// nDegree = Abc_MinInt( 3, (int)pow(Abc_ObjFanoutNum(pObj), 0.34) ); + nDegree = Abc_MinInt( 10, (int)pow(Abc_ObjFanoutNum(pObj), 0.5) ); + n1Degree = Abc_ObjFanoutNum(pObj) / nDegree + 1; + n1Number = Abc_ObjFanoutNum(pObj) % nDegree; + nFirst = n1Degree * n1Number; + p->nBranchCrit += (nCrit > 0); + // create inverters Abc_NodeCollectFanouts( pObj, p->vFanouts ); if ( Abc_ObjIsNode(pObj) && Abc_NodeIsBuf(pObj) ) { @@ -520,16 +699,13 @@ printf( "Adding %d inverters\n", nDegree ); if ( fVerbose ) printf( "Adding %d buffers\n", nDegree ); } - // create inverters + // connect inverters Vec_PtrForEachEntry( Abc_Obj_t *, p->vFanouts, pFanout, i ) { j = (i < nFirst) ? i/n1Degree : n1Number + ((i - nFirst)/(n1Degree - 1)); assert( j >= 0 && j < nDegree ); Abc_ObjPatchFanin( pFanout, pObj, Abc_NtkObj(p->pNtk, iFirstBuf + j) ); } - // remove node -// if ( Abc_ObjIsNode(pObj) && Abc_ObjFanoutNum(pObj) == 0 ) -// Abc_NtkDeleteObj_rec( pObj, 1 ); // update timing for ( i = 0; i < nDegree; i++ ) Abc_BufCreateEdges( p, Abc_NtkObj(p->pNtk, iFirstBuf + i) ); @@ -548,19 +724,18 @@ printf( "Doing nothing\n" ); // if ( DelayMax != p->DelayMax ) // printf( "%d (%.2f) ", p->DelayMax, 1.0 * p->DelayMax * p->DelayInv / BUF_SCALE ); } -Abc_Ntk_t * Abc_SclBufPerform( Abc_Ntk_t * pNtk, int fVerbose ) +Abc_Ntk_t * Abc_SclBufPerform( Abc_Ntk_t * pNtk, int FanMin, int FanMax, int fVerbose ) { Abc_Ntk_t * pNew; - Buf_Man_t * p = Buf_ManStart( pNtk ); + Buf_Man_t * p = Buf_ManStart( pNtk, FanMin, FanMax ); int i, Limit = ABC_INFINITY; -// int i, Limit = 3; for ( i = 0; i < Limit && Vec_QueSize(p->vQue); i++ ) Abc_BufPerformOne( p, Vec_QuePop(p->vQue), fVerbose ); Buf_ManStop( p ); - // duplication in topo order +// Abc_BufReplaceBufsByInvs( pNtk ); + // duplicate network in topo order pNew = Abc_NtkDupDfs( pNtk ); Abc_SclCheckNtk( pNew, fVerbose ); -// Abc_NtkDelete( pNew ); return pNew; } |