cgtDecide.c 9.68 KB
Newer Older
Alan Mishchenko committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
/**CFile****************************************************************

  FileName    [cgtMan.c]

  SystemName  [ABC: Logic synthesis and verification system.]

  PackageName [Clock gating package.]

  Synopsis    [Decide what gate to use for what flop.]

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]

  Date        [Ver. 1.0. Started - June 20, 2005.]

  Revision    [$Id: cgtMan.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]

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

#include "cgtInt.h"
22
#include "proof/ssw/sswInt.h"
Alan Mishchenko committed
23

24 25 26
ABC_NAMESPACE_IMPL_START


Alan Mishchenko committed
27 28 29 30 31
////////////////////////////////////////////////////////////////////////
///                        DECLARATIONS                              ///
////////////////////////////////////////////////////////////////////////

extern int Ssw_SmlCheckXorImplication( Ssw_Sml_t * p, Aig_Obj_t * pObjLi, Aig_Obj_t * pObjLo, Aig_Obj_t * pCand );
Alan Mishchenko committed
32 33 34 35
extern int Ssw_SmlCountXorImplication( Ssw_Sml_t * p, Aig_Obj_t * pObjLi, Aig_Obj_t * pObjLo, Aig_Obj_t * pCand );
extern int Ssw_SmlCountEqual( Ssw_Sml_t * p, Aig_Obj_t * pObjLi, Aig_Obj_t * pObjLo );
extern int Ssw_SmlNodeCountOnesReal( Ssw_Sml_t * p, Aig_Obj_t * pObj );
extern int Ssw_SmlNodeCountOnesRealVec( Ssw_Sml_t * p, Vec_Ptr_t * vObjs );
Alan Mishchenko committed
36 37 38 39 40 41 42

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

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

Alan Mishchenko committed
43
  Synopsis    [Collects POs in the transitive fanout.]
Alan Mishchenko committed
44 45 46 47 48 49 50 51

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Alan Mishchenko committed
52 53 54
void Cgt_ManCollectFanoutPos_rec( Aig_Man_t * pAig, Aig_Obj_t * pObj, Vec_Ptr_t * vFanout )
{
    Aig_Obj_t * pFanout;
55
    int f, iFanout = -1;
Alan Mishchenko committed
56 57 58
    if ( Aig_ObjIsTravIdCurrent(pAig, pObj) )
        return;
    Aig_ObjSetTravIdCurrent(pAig, pObj);
59
    if ( Aig_ObjIsCo(pObj) )
Alan Mishchenko committed
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
    {
        Vec_PtrPush( vFanout, pObj );
        return;
    }
    Aig_ObjForEachFanout( pAig, pObj, pFanout, iFanout, f )
        Cgt_ManCollectFanoutPos_rec( pAig, pFanout, vFanout );
}

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

  Synopsis    [Collects POs in the transitive fanout.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Cgt_ManCollectFanoutPos( Aig_Man_t * pAig, Aig_Obj_t * pObj, Vec_Ptr_t * vFanout )
{
    Vec_PtrClear( vFanout );
    Aig_ManIncrementTravId( pAig );
    Cgt_ManCollectFanoutPos_rec( pAig, pObj, vFanout );
}

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

  Synopsis    [Checks if all PO fanouts can be gated by this node.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Cgt_ManCheckGateComplete( Aig_Man_t * pAig, Vec_Vec_t * vGatesAll, Aig_Obj_t * pGate, Vec_Ptr_t * vFanout )
Alan Mishchenko committed
98 99
{
    Vec_Ptr_t * vGates;
Alan Mishchenko committed
100 101
    Aig_Obj_t * pObj;
    int i;
102
    Vec_PtrForEachEntry( Aig_Obj_t *, vFanout, pObj, i )
Alan Mishchenko committed
103 104 105
    {
        if ( Saig_ObjIsPo(pAig, pObj) )
            return 0;
106
        vGates = Vec_VecEntry( vGatesAll, Aig_ObjCioId(pObj) - Saig_ManPoNum(pAig) );
Alan Mishchenko committed
107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130
        if ( Vec_PtrFind( vGates, pGate ) == -1 )
            return 0;            
    }
    return 1;
}

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

  Synopsis    [Computes the set of complete clock gates.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Ptr_t * Cgt_ManCompleteGates( Aig_Man_t * pAig, Vec_Vec_t * vGatesAll, int nOdcMax, int fVerbose )
{
    Vec_Ptr_t * vFanout, * vGatesFull;
    Aig_Obj_t * pGate, * pGateR;
    int i, k;
    vFanout    = Vec_PtrAlloc( 100 );
    vGatesFull = Vec_PtrAlloc( 100 );
131
    Vec_VecForEachEntry( Aig_Obj_t *, vGatesAll, pGate, i, k )
Alan Mishchenko committed
132 133 134 135 136 137 138 139 140 141
    {
        pGateR = Aig_Regular(pGate);
        if ( pGateR->fMarkA )
            continue;
        pGateR->fMarkA = 1;
        Cgt_ManCollectFanoutPos( pAig, pGateR, vFanout );
        if ( Cgt_ManCheckGateComplete( pAig, vGatesAll, pGate, vFanout ) )
            Vec_PtrPush( vGatesFull, pGate );
    }
    Vec_PtrFree( vFanout );
142
    Vec_VecForEachEntry( Aig_Obj_t *, vGatesAll, pGate, i, k )
Alan Mishchenko committed
143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172
        Aig_Regular(pGate)->fMarkA = 0;
    return vGatesFull;
}

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

  Synopsis    [Calculates coverage.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
float Cgt_ManComputeCoverage( Aig_Man_t * pAig, Vec_Vec_t * vGates )
{
    int nFrames = 32;
    int nWords  =  1;
    Ssw_Sml_t * pSml;
    Vec_Ptr_t * vOne;
    int i, nTransTotal = 0, nTransSaved = 0;
    pSml = Ssw_SmlSimulateSeq( pAig, 0, nFrames, nWords );
    Vec_VecForEachLevel( vGates, vOne, i )
    {
        nTransSaved += Ssw_SmlNodeCountOnesRealVec( pSml, vOne );
        nTransTotal += 32 * nFrames * nWords;
    }
    Ssw_SmlStop( pSml );
    return (float)100.0*nTransSaved/nTransTotal;
Alan Mishchenko committed
173 174 175 176 177 178 179 180 181 182 183 184 185 186
}

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

  Synopsis    [Chooses what clock-gate to use for this register.]

  Description [Currently uses the naive approach: For each register, 
  choose the clock gate, which covers most of the transitions.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Alan Mishchenko committed
187
Vec_Vec_t * Cgt_ManDecideSimple( Aig_Man_t * pAig, Vec_Vec_t * vGatesAll, int nOdcMax, int fVerbose )
Alan Mishchenko committed
188
{
Alan Mishchenko committed
189 190
    int nFrames = 32;
    int nWords  =  1;
Alan Mishchenko committed
191
    Ssw_Sml_t * pSml;
Alan Mishchenko committed
192 193
    Vec_Vec_t * vGates;
    Vec_Ptr_t * vCands;
Alan Mishchenko committed
194
    Aig_Obj_t * pObjLi, * pObjLo, * pCand, * pCandBest;
195 196
    int i, k, nHitsCur, nHitsMax, Counter = 0;
    clock_t clk = clock();
Alan Mishchenko committed
197 198 199
    int nTransTotal = 0, nTransSaved = 0;
    vGates = Vec_VecStart( Saig_ManRegNum(pAig) );
    pSml = Ssw_SmlSimulateSeq( pAig, 0, nFrames, nWords );
Alan Mishchenko committed
200 201 202 203
    Saig_ManForEachLiLo( pAig, pObjLi, pObjLo, i )
    {
        nHitsMax = 0;
        pCandBest = NULL;
204
        vCands = Vec_VecEntry( vGatesAll, i );
205
        Vec_PtrForEachEntry( Aig_Obj_t *, vCands, pCand, k )
Alan Mishchenko committed
206 207
        {
            // check if this is indeed a clock-gate
Alan Mishchenko committed
208
            if ( nOdcMax == 0 && !Ssw_SmlCheckXorImplication( pSml, pObjLi, pObjLo, pCand ) )
Alan Mishchenko committed
209 210
                printf( "Clock gate candidate is invalid!\n" );
            // find its characteristic number
Alan Mishchenko committed
211
            nHitsCur = Ssw_SmlNodeCountOnesReal( pSml, pCand );
Alan Mishchenko committed
212 213 214 215 216 217 218
            if ( nHitsMax < nHitsCur )
            {
                nHitsMax = nHitsCur;
                pCandBest = pCand;
            }
        }
        if ( pCandBest != NULL )
Alan Mishchenko committed
219 220 221 222 223 224
        {
            Vec_VecPush( vGates, i, pCandBest );
            Counter++;
            nTransSaved += nHitsMax;
        }
        nTransTotal += 32 * nFrames * nWords;
Alan Mishchenko committed
225 226
    }
    Ssw_SmlStop( pSml );
Alan Mishchenko committed
227 228 229 230 231 232 233
    if ( fVerbose )
    {
        printf( "Gating signals = %6d. Gated flops = %6d. (Total flops = %6d.)\n", 
            Vec_VecSizeSize(vGatesAll), Counter, Saig_ManRegNum(pAig) );
//        printf( "Gated transitions = %5.2f %%. (%5.2f %%.) ", 
//            100.0*nTransSaved/nTransTotal, Cgt_ManComputeCoverage(pAig, vGates) );
        printf( "Gated transitions = %5.2f %%. ", Cgt_ManComputeCoverage(pAig, vGates) );
Alan Mishchenko committed
234
        ABC_PRT( "Time", clock() - clk );
Alan Mishchenko committed
235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262
    }
/*
    {
        Vec_Ptr_t * vCompletes;
        vCompletes = Cgt_ManCompleteGates( pAig, vGatesAll, nOdcMax, fVerbose );
        printf( "Complete gates = %d. \n", Vec_PtrSize(vCompletes) );
        Vec_PtrFree( vCompletes );
    }
*/
    return vGates;
}

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

  Synopsis    [Computes the set of complete clock gates.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Vec_t * Cgt_ManDecideArea( Aig_Man_t * pAig, Vec_Vec_t * vGatesAll, int nOdcMax, int fVerbose )
{
    Vec_Vec_t * vGates;
    Vec_Ptr_t * vCompletes, * vOne;
    Aig_Obj_t * pGate;
263 264
    int i, k, Counter = 0;
    clock_t clk = clock();
Alan Mishchenko committed
265 266 267
    // derive and label complete gates
    vCompletes = Cgt_ManCompleteGates( pAig, vGatesAll, nOdcMax, fVerbose );
    // label complete gates
268
    Vec_PtrForEachEntry( Aig_Obj_t *, vCompletes, pGate, i )
Alan Mishchenko committed
269 270 271
        Aig_Regular(pGate)->fMarkA = 1;
    // select only complete gates
    vGates = Vec_VecStart( Saig_ManRegNum(pAig) );
272
    Vec_VecForEachEntry( Aig_Obj_t *, vGatesAll, pGate, i, k )
Alan Mishchenko committed
273 274 275
        if ( Aig_Regular(pGate)->fMarkA )
            Vec_VecPush( vGates, i, pGate );
    // unlabel complete gates
276
    Vec_PtrForEachEntry( Aig_Obj_t *, vCompletes, pGate, i )
Alan Mishchenko committed
277 278 279 280 281 282 283 284 285 286 287 288 289 290
        Aig_Regular(pGate)->fMarkA = 0;
    // count the number of gated flops
    Vec_VecForEachLevel( vGates, vOne, i )
    {
        Counter += (int)(Vec_PtrSize(vOne) > 0);
//        printf( "%d ", Vec_PtrSize(vOne) );
    }
//    printf( "\n" );
    if ( fVerbose )
    {
        printf( "Gating signals = %6d. Gated flops = %6d. (Total flops = %6d.)\n", 
            Vec_VecSizeSize(vGatesAll), Counter, Saig_ManRegNum(pAig) );
        printf( "Complete gates = %6d. Gated transitions = %5.2f %%. ", 
            Vec_PtrSize(vCompletes), Cgt_ManComputeCoverage(pAig, vGates) );
Alan Mishchenko committed
291
        ABC_PRT( "Time", clock() - clk );
Alan Mishchenko committed
292 293
    }
    Vec_PtrFree( vCompletes );
Alan Mishchenko committed
294 295 296 297 298 299 300 301
    return vGates;
}

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


302 303
ABC_NAMESPACE_IMPL_END