cnfMap.c 9.79 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 22
/**CFile****************************************************************

  FileName    [cnfMap.c]

  SystemName  [ABC: Logic synthesis and verification system.]

  PackageName [AIG-to-CNF conversion.]

  Synopsis    []

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]

  Date        [Ver. 1.0. Started - April 28, 2007.]

  Revision    [$Id: cnfMap.c,v 1.00 2007/04/28 00:00:00 alanmi Exp $]

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

#include "cnf.h"

23 24 25
ABC_NAMESPACE_IMPL_START


Alan Mishchenko committed
26 27 28 29 30 31 32 33
////////////////////////////////////////////////////////////////////////
///                        DECLARATIONS                              ///
////////////////////////////////////////////////////////////////////////

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

Alan Mishchenko committed
34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
/**Function*************************************************************

  Synopsis    [Computes area flow of the cut.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Cnf_CutAssignAreaFlow( Cnf_Man_t * p, Dar_Cut_t * pCut, int * pAreaFlows )
{
    Aig_Obj_t * pLeaf;
    int i;
    pCut->Value = 0;
Alan Mishchenko committed
50 51
//    pCut->uSign = 100 * Cnf_CutSopCost( p, pCut );
    pCut->uSign = 10 * Cnf_CutSopCost( p, pCut );
Alan Mishchenko committed
52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77
    Dar_CutForEachLeaf( p->pManAig, pCut, pLeaf, i )
    {
        pCut->Value += pLeaf->nRefs;
        if ( !Aig_ObjIsNode(pLeaf) )
            continue;
        assert( pLeaf->nRefs > 0 );
        pCut->uSign += pAreaFlows[pLeaf->Id] / (pLeaf->nRefs? pLeaf->nRefs : 1);
    }
}

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

  Synopsis    [Computes area flow of the supergate.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Cnf_CutSuperAreaFlow( Vec_Ptr_t * vSuper, int * pAreaFlows )
{
    Aig_Obj_t * pLeaf;
    int i, nAreaFlow;
    nAreaFlow = 100 * (Vec_PtrSize(vSuper) + 1);
78
    Vec_PtrForEachEntry( Aig_Obj_t *, vSuper, pLeaf, i )
Alan Mishchenko committed
79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106
    {
        pLeaf = Aig_Regular(pLeaf);
        if ( !Aig_ObjIsNode(pLeaf) )
            continue;
        assert( pLeaf->nRefs > 0 );
        nAreaFlow += pAreaFlows[pLeaf->Id] / (pLeaf->nRefs? pLeaf->nRefs : 1);
    }
    return nAreaFlow;
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Cnf_DeriveMapping( Cnf_Man_t * p )
{
    Vec_Ptr_t * vSuper;
    Aig_Obj_t * pObj;
    Dar_Cut_t * pCut, * pCutBest;
    int i, k, AreaFlow, * pAreaFlows;
    // allocate area flows
Alan Mishchenko committed
107
    pAreaFlows = ABC_ALLOC( int, Aig_ManObjNumMax(p->pManAig) );
Alan Mishchenko committed
108
    memset( pAreaFlows, 0, sizeof(int) * Aig_ManObjNumMax(p->pManAig) );
Alan Mishchenko committed
109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128
    // visit the nodes in the topological order and update their best cuts
    vSuper = Vec_PtrAlloc( 100 );
    Aig_ManForEachNode( p->pManAig, pObj, i )
    {
        // go through the cuts
        pCutBest = NULL;
        Dar_ObjForEachCut( pObj, pCut, k )
        {
            pCut->fBest = 0;
            if ( k == 0 )
                continue;
            Cnf_CutAssignAreaFlow( p, pCut, pAreaFlows );
            if ( pCutBest == NULL || pCutBest->uSign > pCut->uSign || 
                (pCutBest->uSign == pCut->uSign && pCutBest->Value < pCut->Value) )
                 pCutBest = pCut;
        }
        // check the big cut
//        Aig_ObjCollectSuper( pObj, vSuper );
        // get the area flow of this cut
//        AreaFlow = Cnf_CutSuperAreaFlow( vSuper, pAreaFlows );
Alan Mishchenko committed
129
        AreaFlow = ABC_INFINITY;
Alan Mishchenko committed
130 131 132 133 134 135 136 137 138 139 140 141
        if ( AreaFlow >= (int)pCutBest->uSign )
        {
            pAreaFlows[pObj->Id] = pCutBest->uSign;
            pCutBest->fBest = 1;
        }
        else
        {
            pAreaFlows[pObj->Id] = AreaFlow;
            pObj->fMarkB = 1; // mark the special node
        }
    }
    Vec_PtrFree( vSuper );
Alan Mishchenko committed
142
    ABC_FREE( pAreaFlows );
Alan Mishchenko committed
143 144 145 146

/*
    // compute the area of mapping
    AreaFlow = 0;
147
    Aig_ManForEachCo( p->pManAig, pObj, i )
Alan Mishchenko committed
148 149 150 151 152 153 154
        AreaFlow += Dar_ObjBestCut(Aig_ObjFanin0(pObj))->uSign / 100 / Aig_ObjFanin0(pObj)->nRefs;
    printf( "Area of the network = %d.\n", AreaFlow );
*/
}



Alan Mishchenko committed
155 156
#if 0

Alan Mishchenko committed
157 158 159 160 161 162 163 164 165 166 167
/**Function*************************************************************

  Synopsis    [Computes area of the first level.]

  Description [The cut need to be derefed.]
               
  SideEffects []

  SeeAlso     []
 
***********************************************************************/
Alan Mishchenko committed
168
void Aig_CutDeref( Aig_Man_t * p, Dar_Cut_t * pCut )
Alan Mishchenko committed
169
{ 
Alan Mishchenko committed
170
    Aig_Obj_t * pLeaf;
Alan Mishchenko committed
171 172 173 174
    int i;
    Dar_CutForEachLeaf( p, pCut, pLeaf, i )
    {
        assert( pLeaf->nRefs > 0 );
Alan Mishchenko committed
175
        if ( --pLeaf->nRefs > 0 || !Aig_ObjIsAnd(pLeaf) )
Alan Mishchenko committed
176
            continue;
Alan Mishchenko committed
177
        Aig_CutDeref( p, Aig_ObjBestCut(pLeaf) );
Alan Mishchenko committed
178 179 180 181 182 183 184 185 186 187 188 189 190 191
    }
}

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

  Synopsis    [Computes area of the first level.]

  Description [The cut need to be derefed.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Alan Mishchenko committed
192
int Aig_CutRef( Aig_Man_t * p, Dar_Cut_t * pCut )
Alan Mishchenko committed
193
{
Alan Mishchenko committed
194 195
    Aig_Obj_t * pLeaf;
    int i, Area = pCut->Value;
Alan Mishchenko committed
196 197 198
    Dar_CutForEachLeaf( p, pCut, pLeaf, i )
    {
        assert( pLeaf->nRefs >= 0 );
Alan Mishchenko committed
199
        if ( pLeaf->nRefs++ > 0 || !Aig_ObjIsAnd(pLeaf) )
Alan Mishchenko committed
200
            continue;
Alan Mishchenko committed
201
        Area += Aig_CutRef( p, Aig_ObjBestCut(pLeaf) );
Alan Mishchenko committed
202 203 204 205 206 207 208 209 210 211 212 213 214 215 216
    }
    return Area;
}

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

  Synopsis    [Computes exact area of the cut.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Alan Mishchenko committed
217
int Cnf_CutArea( Aig_Man_t * p, Dar_Cut_t * pCut )
Alan Mishchenko committed
218 219
{
    int Area;
Alan Mishchenko committed
220 221
    Area = Aig_CutRef( p, pCut );
    Aig_CutDeref( p, pCut );
Alan Mishchenko committed
222 223 224 225 226 227 228 229 230 231 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 260 261 262 263 264
    return Area;
}

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

  Synopsis    [Returns 1 if the second cut is better.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline int Cnf_CutCompare( Dar_Cut_t * pC0, Dar_Cut_t * pC1 )
{
    if ( pC0->Area < pC1->Area - 0.0001 )
        return -1;
    if ( pC0->Area > pC1->Area + 0.0001 ) // smaller area flow is better
        return 1;
//    if ( pC0->NoRefs < pC1->NoRefs )
//        return -1;
//    if ( pC0->NoRefs > pC1->NoRefs ) // fewer non-referenced fanins is better
//        return 1;
//    if ( pC0->FanRefs / pC0->nLeaves > pC1->FanRefs / pC1->nLeaves )
//        return -1;
//    if ( pC0->FanRefs / pC0->nLeaves < pC1->FanRefs / pC1->nLeaves )
//        return 1; // larger average fanin ref-counter is better
//    return 0;
    return 1;
}

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

  Synopsis    [Returns the cut with the smallest area flow.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Alan Mishchenko committed
265
Dar_Cut_t * Cnf_ObjFindBestCut( Aig_Obj_t * pObj )
Alan Mishchenko committed
266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288
{
    Dar_Cut_t * pCut, * pCutBest;
    int i;
    pCutBest = NULL;
    Dar_ObjForEachCut( pObj, pCut, i )
        if ( pCutBest == NULL || Cnf_CutCompare(pCutBest, pCut) == 1 )
            pCutBest = pCut;
    return pCutBest;
}

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

  Synopsis    [Computes area flow of the cut.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Cnf_CutAssignArea( Cnf_Man_t * p, Dar_Cut_t * pCut )
{
Alan Mishchenko committed
289
    Aig_Obj_t * pLeaf;
Alan Mishchenko committed
290 291 292 293 294 295
    int i;
    pCut->Area    = (float)pCut->Cost;
    pCut->NoRefs  = 0;
    pCut->FanRefs = 0;
    Dar_CutForEachLeaf( p->pManAig, pCut, pLeaf, i )
    {
Alan Mishchenko committed
296
        if ( !Aig_ObjIsNode(pLeaf) )
Alan Mishchenko committed
297 298 299
            continue;
        if ( pLeaf->nRefs == 0 )
        {
Alan Mishchenko committed
300
            pCut->Area += Aig_ObjBestCut(pLeaf)->Cost;
Alan Mishchenko committed
301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325
            pCut->NoRefs++;
        }
        else
        {
            if ( pCut->FanRefs + pLeaf->nRefs > 15 )
                pCut->FanRefs = 15;
            else
                pCut->FanRefs += pLeaf->nRefs;
        }
    }
}

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

  Synopsis    [Performs one round of "area recovery" using exact local area.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Cnf_ManMapForCnf( Cnf_Man_t * p )
{
Alan Mishchenko committed
326
    Aig_Obj_t * pObj;
Alan Mishchenko committed
327 328 329
    Dar_Cut_t * pCut, * pCutBest;
    int i, k;
    // visit the nodes in the topological order and update their best cuts
Alan Mishchenko committed
330
    Aig_ManForEachNode( p->pManAig, pObj, i )
Alan Mishchenko committed
331 332
    {
        // find the old best cut
Alan Mishchenko committed
333
        pCutBest = Aig_ObjBestCut(pObj);
Alan Mishchenko committed
334 335 336
        Dar_ObjClearBestCut(pCutBest);
        // if the node is used, dereference its cut
        if ( pObj->nRefs )
Alan Mishchenko committed
337
            Aig_CutDeref( p->pManAig, pCutBest );
Alan Mishchenko committed
338 339 340 341 342 343 344 345 346 347 348

        // evaluate the cuts of this node
        Dar_ObjForEachCut( pObj, pCut, k )
//            Cnf_CutAssignAreaFlow( p, pCut );
            pCut->Area = (float)Cnf_CutArea( p->pManAig, pCut );

        // find the new best cut
        pCutBest = Cnf_ObjFindBestCut(pObj);
        Dar_ObjSetBestCut( pCutBest );
        // if the node is used, reference its cut
        if ( pObj->nRefs )
Alan Mishchenko committed
349
            Aig_CutRef( p->pManAig, pCutBest );
Alan Mishchenko committed
350 351 352 353
    }
    return 1;
}

Alan Mishchenko committed
354 355
#endif

Alan Mishchenko committed
356 357 358 359 360
////////////////////////////////////////////////////////////////////////
///                       END OF FILE                                ///
////////////////////////////////////////////////////////////////////////


361 362
ABC_NAMESPACE_IMPL_END