cgtDecide.c 9.64 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
        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;
164
    int i, nTransSaved = 0;
Alan Mishchenko committed
165 166 167 168
    pSml = Ssw_SmlSimulateSeq( pAig, 0, nFrames, nWords );
    Vec_VecForEachLevel( vGates, vOne, i )
        nTransSaved += Ssw_SmlNodeCountOnesRealVec( pSml, vOne );
    Ssw_SmlStop( pSml );
169
    return (float)100.0*nTransSaved/32/nFrames/nWords/Vec_VecSize(vGates);
Alan Mishchenko committed
170 171 172 173 174 175 176 177 178 179 180 181 182 183
}

/**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
184
Vec_Vec_t * Cgt_ManDecideSimple( Aig_Man_t * pAig, Vec_Vec_t * vGatesAll, int nOdcMax, int fVerbose )
Alan Mishchenko committed
185
{
Alan Mishchenko committed
186 187
    int nFrames = 32;
    int nWords  =  1;
Alan Mishchenko committed
188
    Ssw_Sml_t * pSml;
Alan Mishchenko committed
189 190
    Vec_Vec_t * vGates;
    Vec_Ptr_t * vCands;
Alan Mishchenko committed
191
    Aig_Obj_t * pObjLi, * pObjLo, * pCand, * pCandBest;
192
    int i, k, nHitsCur, nHitsMax, Counter = 0;
193
    abctime clk = Abc_Clock();
Alan Mishchenko committed
194 195 196
    int nTransTotal = 0, nTransSaved = 0;
    vGates = Vec_VecStart( Saig_ManRegNum(pAig) );
    pSml = Ssw_SmlSimulateSeq( pAig, 0, nFrames, nWords );
Alan Mishchenko committed
197 198 199 200
    Saig_ManForEachLiLo( pAig, pObjLi, pObjLo, i )
    {
        nHitsMax = 0;
        pCandBest = NULL;
201
        vCands = Vec_VecEntry( vGatesAll, i );
202
        Vec_PtrForEachEntry( Aig_Obj_t *, vCands, pCand, k )
Alan Mishchenko committed
203 204
        {
            // check if this is indeed a clock-gate
Alan Mishchenko committed
205
            if ( nOdcMax == 0 && !Ssw_SmlCheckXorImplication( pSml, pObjLi, pObjLo, pCand ) )
Alan Mishchenko committed
206 207
                printf( "Clock gate candidate is invalid!\n" );
            // find its characteristic number
Alan Mishchenko committed
208
            nHitsCur = Ssw_SmlNodeCountOnesReal( pSml, pCand );
Alan Mishchenko committed
209 210 211 212 213 214 215
            if ( nHitsMax < nHitsCur )
            {
                nHitsMax = nHitsCur;
                pCandBest = pCand;
            }
        }
        if ( pCandBest != NULL )
Alan Mishchenko committed
216 217 218 219 220 221
        {
            Vec_VecPush( vGates, i, pCandBest );
            Counter++;
            nTransSaved += nHitsMax;
        }
        nTransTotal += 32 * nFrames * nWords;
Alan Mishchenko committed
222 223
    }
    Ssw_SmlStop( pSml );
Alan Mishchenko committed
224 225 226 227 228 229 230
    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) );
231
        ABC_PRT( "Time", Abc_Clock() - clk );
Alan Mishchenko committed
232 233 234 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
    }
/*
    {
        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;
260
    int i, k, Counter = 0;
261
    abctime clk = Abc_Clock();
Alan Mishchenko committed
262 263 264
    // derive and label complete gates
    vCompletes = Cgt_ManCompleteGates( pAig, vGatesAll, nOdcMax, fVerbose );
    // label complete gates
265
    Vec_PtrForEachEntry( Aig_Obj_t *, vCompletes, pGate, i )
Alan Mishchenko committed
266 267 268
        Aig_Regular(pGate)->fMarkA = 1;
    // select only complete gates
    vGates = Vec_VecStart( Saig_ManRegNum(pAig) );
269
    Vec_VecForEachEntry( Aig_Obj_t *, vGatesAll, pGate, i, k )
Alan Mishchenko committed
270 271 272
        if ( Aig_Regular(pGate)->fMarkA )
            Vec_VecPush( vGates, i, pGate );
    // unlabel complete gates
273
    Vec_PtrForEachEntry( Aig_Obj_t *, vCompletes, pGate, i )
Alan Mishchenko committed
274 275 276 277 278 279 280 281 282 283 284 285 286 287
        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) );
288
        ABC_PRT( "Time", Abc_Clock() - clk );
Alan Mishchenko committed
289 290
    }
    Vec_PtrFree( vCompletes );
Alan Mishchenko committed
291 292 293 294 295 296 297 298
    return vGates;
}

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


299 300
ABC_NAMESPACE_IMPL_END