sclDnsize.c 12.5 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
/**CFile****************************************************************

  FileName    [sclDnsize.c]

  SystemName  [ABC: Logic synthesis and verification system.]

  PackageName [Standard-cell library representation.]

  Synopsis    [Selective decrease of gate sizes.]

  Author      [Alan Mishchenko, Niklas Een]
  
  Affiliation [UC Berkeley]

  Date        [Ver. 1.0. Started - August 24, 2012.]

  Revision    [$Id: sclDnsize.c,v 1.0 2012/08/24 00:00:00 alanmi Exp $]

***********************************************************************/

21
#include "sclSize.h"
22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55

ABC_NAMESPACE_IMPL_START


////////////////////////////////////////////////////////////////////////
///                        DECLARATIONS                              ///
////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////
///                     FUNCTION DEFINITIONS                         ///
////////////////////////////////////////////////////////////////////////

/**Function*************************************************************

  Synopsis    [Find the array of nodes to be updated.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_SclFindWindow( Abc_Obj_t * pPivot, Vec_Int_t ** pvNodes, Vec_Int_t ** pvEvals )
{
    Abc_Ntk_t * p = Abc_ObjNtk(pPivot);
    Abc_Obj_t * pObj, * pNext, * pNext2;
    Vec_Int_t * vNodes = *pvNodes;
    Vec_Int_t * vEvals = *pvEvals;
    int i, k;
    assert( Abc_ObjIsNode(pPivot) );
    // collect fanins, node, and fanouts
    Vec_IntClear( vNodes );
    Abc_ObjForEachFanin( pPivot, pNext, i )
56 57
//        if ( Abc_ObjIsNode(pNext) && Abc_ObjFaninNum(pNext) > 0 )
        if ( Abc_ObjIsCi(pNext) || Abc_ObjFaninNum(pNext) > 0 )
58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101
            Vec_IntPush( vNodes, Abc_ObjId(pNext) );
    Vec_IntPush( vNodes, Abc_ObjId(pPivot) );
    Abc_ObjForEachFanout( pPivot, pNext, i )
        if ( Abc_ObjIsNode(pNext) )
        {
            Vec_IntPush( vNodes, Abc_ObjId(pNext) );
            Abc_ObjForEachFanout( pNext, pNext2, k )
                if ( Abc_ObjIsNode(pNext2) )
                    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 visible from the critical paths
    Vec_IntClear( vEvals );
    Abc_NtkForEachObjVec( vNodes, p, pObj, i )
        Abc_ObjForEachFanout( pObj, pNext, k )
            if ( !pNext->fMarkB )
            {
                assert( pObj->fMarkB );
                Vec_IntPush( vEvals, Abc_ObjId(pObj) );
                break;
            }
    assert( Vec_IntSize(vEvals) > 0 );
    // label nodes
    Abc_NtkForEachObjVec( vNodes, p, pObj, i )
        pObj->fMarkB = 0;
}

/**Function*************************************************************

  Synopsis    [Returns 1 if the node can be improved.]

  Description [Updated the node to have a new gate.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
102
int Abc_SclCheckImprovement( SC_Man * p, Abc_Obj_t * pObj, Vec_Int_t * vNodes, Vec_Int_t * vEvals, int Notches, int DelayGap )
103 104 105
{
    Abc_Obj_t * pTemp;
    SC_Cell * pCellOld, * pCellNew;
106
    float dGain, dGainBest;
107 108 109 110 111
    int i, k, gateBest;
    abctime clk;
clk = Abc_Clock();
//    printf( "%d -> %d\n", Vec_IntSize(vNodes), Vec_IntSize(vEvals) );
    // save old gate, timing, fanin load
112
    pCellOld = Abc_SclObjCell( pObj );
113
    Abc_SclConeStore( p, vNodes );
114
    Abc_SclEvalStore( p, vEvals );
115 116 117
    Abc_SclLoadStore( p, pObj );
    // try different gate sizes for this node
    gateBest = -1;
118 119
    dGainBest = -SC_LibTimeFromPs(p->pLib, (float)DelayGap);
    SC_RingForEachCellRev( pCellOld, pCellNew, i )
120 121 122
    {
        if ( pCellNew->area >= pCellOld->area )
            continue;
123 124
        if ( i > Notches )
            break;
125
        if ( p->vInDrive && !Abc_SclInputDriveOk( p, pObj, pCellNew ) )
126
            continue;
127
        // set new cell
128
        Abc_SclObjSetCell( pObj, pCellNew );
129 130 131 132
        Abc_SclUpdateLoad( p, pObj, pCellOld, pCellNew );
        // recompute timing
        Abc_SclTimeCone( p, vNodes );
        // set old cell
133
        Abc_SclObjSetCell( pObj, pCellOld );
134 135
        Abc_SclLoadRestore( p, pObj );
        // evaluate gain
136 137 138
        dGain = Abc_SclEvalPerformLegal( p, vEvals, p->MaxDelay0 );
        if ( dGain == -1 )
            continue;
139 140 141 142 143 144 145 146
        // save best gain
        if ( dGainBest < dGain )
        {
            dGainBest = dGain;
            gateBest = pCellNew->Id;
        }
    } 
    // put back old cell and timing
147
    Abc_SclObjSetCell( pObj, pCellOld );
148 149 150 151 152
    Abc_SclConeRestore( p, vNodes );
p->timeSize += Abc_Clock() - clk;
    if ( gateBest >= 0 )
    {
        pCellNew = SC_LibCell( p->pLib, gateBest );
153
        Abc_SclObjSetCell( pObj, pCellNew );
154 155 156 157 158 159
        p->SumArea += pCellNew->area - pCellOld->area;
//        printf( "%f   %f -> %f\n", pCellNew->area - pCellOld->area, p->SumArea - (pCellNew->area - pCellOld->area), p->SumArea );
//        printf( "%6d  %20s -> %20s  %f -> %f\n", Abc_ObjId(pObj), pCellOld->pName, pCellNew->pName, pCellOld->area, pCellNew->area );
        // mark used nodes with the current trav ID
        Abc_NtkForEachObjVec( vNodes, p->pNtk, pTemp, k )
            Abc_NodeSetTravIdCurrent( pTemp );
160 161 162
        // update load and timing...
        Abc_SclUpdateLoad( p, pObj, pCellOld, pCellNew );
        Abc_SclTimeIncInsert( p, pObj );
163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187
        return 1;
    }
    return 0;
}

/**Function*************************************************************

  Synopsis    [Collect nodes by area.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_NtkCollectNodesByArea( SC_Man * p, Abc_Ntk_t * pNtk )
{
    Abc_Obj_t * pObj;
    int i;
    assert( Vec_QueSize(p->vNodeByGain) == 0 );
    Vec_QueClear( p->vNodeByGain );
    Abc_NtkForEachNode( pNtk, pObj, i )
    if ( Abc_ObjFaninNum(pObj) > 0 )
    {
188
        Vec_FltWriteEntry( p->vNode2Gain, Abc_ObjId(pObj), Abc_SclObjCell(pObj)->area );
189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228
        Vec_QuePush( p->vNodeByGain, Abc_ObjId(pObj) );
    }
}
int Abc_SclCheckOverlap( Abc_Ntk_t * pNtk, Vec_Int_t * vNodes )
{
    Abc_Obj_t * pObj;
    int i;
    Abc_NtkForEachObjVec( vNodes, pNtk, pObj, i )
        if ( Abc_NodeIsTravIdCurrent(pObj) )
            return 1;
    return 0;
}

/**Function*************************************************************

  Synopsis    [Print cumulative statistics.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_SclDnsizePrint( SC_Man * p, int Iter, int nAttempts, int nOverlaps, int nChanges, int fVerbose )
{
    if ( Iter == -1 )
        printf( "Total : " );
    else
        printf( "%5d : ",    Iter );
    printf( "Try =%6d  ",    nAttempts );
    printf( "Over =%6d  ",   nOverlaps );
    printf( "Fail =%6d  ",   nAttempts-nOverlaps-nChanges );
    printf( "Win =%6d  ",    nChanges );
    printf( "A: " );
    printf( "%.2f ",         p->SumArea );
    printf( "(%+5.1f %%)  ", 100.0 * (p->SumArea - p->SumArea0)/ p->SumArea0 );
    printf( "D: " );
    printf( "%.2f ps ",      SC_LibTimePs(p->pLib, p->MaxDelay) );
    printf( "(%+5.1f %%)  ", 100.0 * (p->MaxDelay - p->MaxDelay0)/ p->MaxDelay0 );
229
    printf( "%8.2f sec    ", 1.0*(Abc_Clock() - p->timeTotal)/(CLOCKS_PER_SEC) );
230 231 232 233 234 235 236 237 238 239 240 241 242 243
    printf( "%c", fVerbose ? '\n' : '\r' );
}

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
244
void Abc_SclDnsizePerform( SC_Lib * pLib, Abc_Ntk_t * pNtk, SC_SizePars * pPars )
245 246 247 248 249 250 251 252 253
{
    SC_Man * p;
    Abc_Obj_t * pObj;
    Vec_Int_t * vNodes, * vEvals, * vTryLater; 
    abctime clk, nRuntimeLimit = pPars->TimeOut ? pPars->TimeOut * CLOCKS_PER_SEC + Abc_Clock() : 0;
    int i, k;

    if ( pPars->fVerbose )
    {
254 255 256 257 258 259 260
        printf( "Parameters: " );
        printf( "Iters =%5d.  ",          pPars->nIters    );
        printf( "UseDept =%2d. ",         pPars->fUseDept  );
        printf( "UseWL =%2d. ",           pPars->fUseWireLoads );
        printf( "Target =%5d ps. ",       pPars->DelayUser );
        printf( "DelayGap =%3d ps. ",     pPars->DelayGap );
        printf( "Timeout =%4d sec",       pPars->TimeOut   );
261 262 263 264
        printf( "\n" );
    }

    // prepare the manager; collect init stats
265
    p = Abc_SclManStart( pLib, pNtk, pPars->fUseWireLoads, pPars->fUseDept, SC_LibTimeFromPs(pLib, pPars->DelayUser), pPars->BuffTreeEst );
266 267
    p->timeTotal  = Abc_Clock();
    assert( p->vGatesBest == NULL );
268
    p->vGatesBest = Vec_IntDup( p->pNtk->vGates );
269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285

    // perform upsizing
    vNodes = Vec_IntAlloc( 1000 );
    vEvals = Vec_IntAlloc( 1000 );
    vTryLater = Vec_IntAlloc( 1000 );
    for ( i = 0; i < pPars->nIters; i++ )
    {
        int nRounds = 0;
        int nAttemptAll = 0, nOverlapAll = 0, nChangesAll = 0;
        Abc_NtkCollectNodesByArea( p, pNtk );
        while ( Vec_QueSize(p->vNodeByGain) > 0 )
        {
            int nAttempt = 0, nOverlap = 0, nChanges = 0;
            Vec_IntClear( vTryLater );
            Abc_NtkIncrementTravId( pNtk );
            while ( Vec_QueSize(p->vNodeByGain) > 0 )
            {
286
                clk = Abc_Clock();
287 288
                pObj = Abc_NtkObj( p->pNtk, Vec_QuePop(p->vNodeByGain) );
                Abc_SclFindWindow( pObj, &vNodes, &vEvals );
289
                p->timeCone += Abc_Clock() - clk;
290 291 292
                if ( Abc_SclCheckOverlap( p->pNtk, vNodes ) )
                    nOverlap++, Vec_IntPush( vTryLater, Abc_ObjId(pObj) );
                else 
293
                    nChanges += Abc_SclCheckImprovement( p, pObj, vNodes, vEvals, pPars->Notches, pPars->DelayGap );
294 295 296 297
                nAttempt++;
            }
            Abc_NtkForEachObjVec( vTryLater, pNtk, pObj, k )
                Vec_QuePush( p->vNodeByGain, Abc_ObjId(pObj) );
298 299

            clk = Abc_Clock();
300
            if ( Vec_IntSize(p->vChanged) )
301 302 303
                Abc_SclTimeIncUpdate( p );
            else
                Abc_SclTimeNtkRecompute( p, &p->SumArea, &p->MaxDelay, pPars->fUseDept, pPars->DelayUser );
304
            p->timeTime += Abc_Clock() - clk;
305 306

            p->MaxDelay = Abc_SclReadMaxDelay( p );
307 308
            if ( pPars->fUseDept && pPars->DelayUser > 0 && p->MaxDelay < pPars->DelayUser )
                p->MaxDelay = pPars->DelayUser;
309
            Abc_SclDnsizePrint( p, nRounds++, nAttempt, nOverlap, nChanges, pPars->fVeryVerbose ); 
310
            nAttemptAll += nAttempt; nOverlapAll += nOverlap; nChangesAll += nChanges;
311 312 313 314
            if ( nRuntimeLimit && Abc_Clock() > nRuntimeLimit )
                break;
        }
        // recompute
315
//        Abc_SclTimeNtkRecompute( p, &p->SumArea, &p->MaxDelay, pPars->fUseDept, pPars->DelayUser );
316 317 318 319 320 321 322 323 324 325
        if ( pPars->fVerbose )
            Abc_SclDnsizePrint( p, -1, nAttemptAll, nOverlapAll, nChangesAll, 1 ); 
        if ( nRuntimeLimit && Abc_Clock() > nRuntimeLimit )
            break;
        if ( nAttemptAll == 0 )
            break;
    }
    Vec_IntFree( vNodes );
    Vec_IntFree( vEvals );
    Vec_IntFree( vTryLater );
326 327
    if ( !pPars->fVerbose )
        printf( "                                                                                                                               \r" );
328 329 330 331 332 333 334 335 336 337 338 339

    // report runtime
    p->timeTotal = Abc_Clock() - p->timeTotal;
    if ( pPars->fVerbose )
    {
        p->timeOther = p->timeTotal - p->timeCone - p->timeSize - p->timeTime;
        ABC_PRTP( "Runtime: Critical path", p->timeCone,  p->timeTotal );
        ABC_PRTP( "Runtime: Sizing eval  ", p->timeSize,  p->timeTotal );
        ABC_PRTP( "Runtime: Timing update", p->timeTime,  p->timeTotal );
        ABC_PRTP( "Runtime: Other        ", p->timeOther, p->timeTotal );
        ABC_PRTP( "Runtime: TOTAL        ", p->timeTotal, p->timeTotal );
    }
340 341
    if ( pPars->fDumpStats )
        Abc_SclDumpStats( p, "stats2.txt", p->timeTotal );
342 343 344 345
    if ( nRuntimeLimit && Abc_Clock() > nRuntimeLimit )
        printf( "Gate sizing timed out at %d seconds.\n", pPars->TimeOut );

    // save the result and quit
346
    Abc_SclSclGates2MioGates( pLib, pNtk ); // updates gate pointers
347 348 349 350 351 352 353 354 355 356 357
    Abc_SclManFree( p );
//    Abc_NtkCleanMarkAB( pNtk );
}

////////////////////////////////////////////////////////////////////////
///                       END OF FILE                                ///
////////////////////////////////////////////////////////////////////////


ABC_NAMESPACE_IMPL_END