src/aig/ivy/ivyMulti.c File Reference

#include "ivy.h"
Include dependency graph for ivyMulti.c:

Go to the source code of this file.

Data Structures

struct  Ivy_Eva_t_

Defines

#define IVY_EVAL_LIMIT   128

Typedefs

typedef struct Ivy_Eva_t_ Ivy_Eva_t

Functions

static void Ivy_MultiPrint (Ivy_Man_t *p, Ivy_Eva_t *pEvals, int nLeaves, int nEvals)
static int Ivy_MultiCover (Ivy_Man_t *p, Ivy_Eva_t *pEvals, int nLeaves, int nEvals, int nLimit, Vec_Ptr_t *vSols)
int Ivy_MultiPlus (Ivy_Man_t *p, Vec_Ptr_t *vLeaves, Vec_Ptr_t *vCone, Ivy_Type_t Type, int nLimit, Vec_Ptr_t *vSols)
static int Ivy_MultiWeight (unsigned uMask, int nMaskOnes, unsigned uFound)

Define Documentation

#define IVY_EVAL_LIMIT   128

CFile****************************************************************

FileName [ivyMulti.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [And-Inverter Graph package.]

Synopsis [Constructing multi-input AND/EXOR gates.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - May 11, 2006.]

Revision [

Id
ivyMulti.c,v 1.00 2006/05/11 00:00:00 alanmi Exp

] DECLARATIONS ///

Definition at line 27 of file ivyMulti.c.

Typedef Documentation

typedef struct Ivy_Eva_t_ Ivy_Eva_t

Definition at line 29 of file ivyMulti.c.

Function Documentation

int Ivy_MultiCover ( Ivy_Man_t *  p,
Ivy_Eva_t *  pEvals,
int  nLeaves,
int  nEvals,
int  nLimit,
Vec_Ptr_t *  vSols 
) [static]

Function*************************************************************

Synopsis [Finds the cover.]

Description [Returns 1 if the cover is found.]

SideEffects []

SeeAlso []

Definition at line 218 of file ivyMulti.c.

00219 {
00220     int fVerbose = 0;
00221     Ivy_Eva_t * pEval, * pEvalBest;
00222     unsigned uMaskAll, uFound, uTemp;
00223     int i, k, BestK, WeightBest, WeightCur, LevelBest, LevelCur;
00224     uMaskAll = (nLeaves == 32)? (~(unsigned)0) : ((1 << nLeaves) - 1);
00225     uFound = 0;
00226     // solve the covering problem
00227     if ( fVerbose )
00228     printf( "Solution:  " );
00229     Vec_PtrClear( vSols );
00230     for ( i = 0; i < nLimit; i++ )
00231     {
00232         BestK = -1;
00233         for ( k = nEvals - 1; k >= 0; k-- )
00234         {
00235             pEval = pEvals + k;
00236             if ( (pEval->Mask & ~uFound) == 0 )
00237                 continue;
00238             if ( BestK == -1 )
00239             {
00240                 BestK      = k;
00241                 pEvalBest  = pEval;
00242                 WeightBest = Ivy_MultiWeight( pEvalBest->Mask, pEvalBest->Weight, uFound );
00243                 LevelBest  = Ivy_ObjLevel( Ivy_Regular(pEvalBest->pArg) );
00244                 continue;
00245             }
00246             // compare BestK and the new one (k)
00247             WeightCur = Ivy_MultiWeight( pEval->Mask, pEval->Weight, uFound );
00248             LevelCur = Ivy_ObjLevel( Ivy_Regular(pEval->pArg) );
00249             if ( WeightBest < WeightCur || 
00250                 (WeightBest == WeightCur && LevelBest > LevelCur) )
00251             {
00252                 BestK      = k;
00253                 pEvalBest  = pEval;
00254                 WeightBest = WeightCur;
00255                 LevelBest  = LevelCur;
00256             }
00257         }
00258         assert( BestK != -1 );
00259         // if the cost is only 1, take the leaf
00260         if ( WeightBest == 1 && BestK >= nLeaves )
00261         {
00262             uTemp = (pEvalBest->Mask & ~uFound);
00263             for ( k = 0; k < nLeaves; k++ )
00264                 if ( uTemp & (1 << k) )
00265                     break;
00266             assert( k < nLeaves );
00267             BestK     = k;
00268             pEvalBest = pEvals + BestK;
00269         }
00270         if ( fVerbose )
00271         {
00272             if ( BestK < nLeaves )
00273                 printf( "L(%d) ", BestK );
00274             else
00275                 printf( "%d ", BestK - nLeaves );
00276         }
00277         // update the found set
00278         Vec_PtrPush( vSols, pEvalBest->pArg );
00279         uFound |= pEvalBest->Mask;
00280         if ( uFound == uMaskAll )
00281             break;
00282     }
00283     if ( uFound == uMaskAll )
00284     {
00285         if ( fVerbose )
00286             printf( "  Found \n\n" );
00287         return 1;
00288     }
00289     else
00290     {
00291         if ( fVerbose )
00292             printf( "  Not found \n\n" );
00293         return 0;
00294     }
00295 }

int Ivy_MultiPlus ( Ivy_Man_t *  p,
Vec_Ptr_t *  vLeaves,
Vec_Ptr_t *  vCone,
Ivy_Type_t  Type,
int  nLimit,
Vec_Ptr_t *  vSols 
)

FUNCTION DEFINITIONS ///Function*************************************************************

Synopsis [Constructs a balanced tree while taking sharing into account.]

Description [Returns 1 if the implementation exists.]

SideEffects []

SeeAlso []

Definition at line 55 of file ivyMulti.c.

00056 {
00057     static Ivy_Eva_t pEvals[IVY_EVAL_LIMIT];
00058     Ivy_Eva_t * pEval, * pFan0, * pFan1;
00059     Ivy_Obj_t * pObj, * pTemp;
00060     int nEvals, nEvalsOld, i, k, x, nLeaves;
00061     unsigned uMaskAll;
00062 
00063     // consider special cases
00064     nLeaves = Vec_PtrSize(vLeaves);
00065     assert( nLeaves > 2 );
00066     if ( nLeaves > 32 || nLeaves + Vec_PtrSize(vCone) > IVY_EVAL_LIMIT )
00067         return 0;
00068 //    if ( nLeaves == 1 )
00069 //        return Vec_PtrEntry( vLeaves, 0 );
00070 //    if ( nLeaves == 2 )
00071 //        return Ivy_Oper( Vec_PtrEntry(vLeaves, 0), Vec_PtrEntry(vLeaves, 1), Type );
00072 
00073     // set the leaf entries
00074     uMaskAll = ((1 << nLeaves) - 1);
00075     nEvals = 0;
00076     Vec_PtrForEachEntry( vLeaves, pObj, i )
00077     {
00078         pEval = pEvals + nEvals;
00079         pEval->pArg   = pObj;
00080         pEval->Mask   = (1 << nEvals);
00081         pEval->Weight = 1;
00082         // mark the leaf
00083         Ivy_Regular(pObj)->TravId = nEvals;
00084         nEvals++;
00085     }
00086 
00087     // propagate masks through the cone
00088     Vec_PtrForEachEntry( vCone, pObj, i )
00089     {
00090         pObj->TravId = nEvals + i;
00091         if ( Ivy_ObjIsBuf(pObj) )
00092             pEvals[pObj->TravId].Mask = pEvals[Ivy_ObjFanin0(pObj)->TravId].Mask;
00093         else
00094             pEvals[pObj->TravId].Mask = pEvals[Ivy_ObjFanin0(pObj)->TravId].Mask | pEvals[Ivy_ObjFanin1(pObj)->TravId].Mask;
00095     }
00096 
00097     // set the internal entries
00098     Vec_PtrForEachEntry( vCone, pObj, i )
00099     {
00100         if ( i == Vec_PtrSize(vCone) - 1 )
00101             break;
00102         // skip buffers
00103         if ( Ivy_ObjIsBuf(pObj) )
00104             continue;
00105         // skip nodes without external fanout
00106         if ( Ivy_ObjRefs(pObj) == 0 )
00107             continue;
00108         assert( !Ivy_IsComplement(pObj) );
00109         pEval = pEvals + nEvals;
00110         pEval->pArg   = pObj;
00111         pEval->Mask   = pEvals[pObj->TravId].Mask;
00112         pEval->Weight = Extra_WordCountOnes(pEval->Mask);
00113         // mark the node
00114         pObj->TravId = nEvals;
00115         nEvals++;
00116     }
00117 
00118     // find the available nodes
00119     nEvalsOld = nEvals;
00120     for ( i = 1; i < nEvals; i++ )
00121     for ( k = 0; k < i; k++ )
00122     {
00123         pFan0 = pEvals + i;
00124         pFan1 = pEvals + k;
00125         pTemp = Ivy_TableLookup(p, Ivy_ObjCreateGhost(p, pFan0->pArg, pFan1->pArg, Type, IVY_INIT_NONE));
00126         // skip nodes in the cone
00127         if ( pTemp == NULL || pTemp->fMarkB )
00128             continue;
00129         // skip the leaves
00130         for ( x = 0; x < nLeaves; x++ )
00131             if ( pTemp == Ivy_Regular(vLeaves->pArray[x]) )
00132                 break;
00133         if ( x < nLeaves )
00134             continue;
00135         pEval = pEvals + nEvals;
00136         pEval->pArg   = pTemp;
00137         pEval->Mask   = pFan0->Mask | pFan1->Mask;
00138         pEval->Weight = (pFan0->Mask & pFan1->Mask) ? Extra_WordCountOnes(pEval->Mask) : pFan0->Weight + pFan1->Weight;
00139         // save the argument
00140         pObj->TravId = nEvals;
00141         nEvals++;
00142         // quit if the number of entries exceeded the limit
00143         if ( nEvals == IVY_EVAL_LIMIT )
00144             goto Outside;
00145         // quit if we found an acceptable implementation
00146         if ( pEval->Mask == uMaskAll )
00147             goto Outside;
00148     }
00149 Outside:
00150 
00151 //    Ivy_MultiPrint( pEvals, nLeaves, nEvals );
00152     if ( !Ivy_MultiCover( p, pEvals, nLeaves, nEvals, nLimit, vSols ) )
00153         return 0;
00154     assert( Vec_PtrSize( vSols ) > 0 );
00155     return 1;
00156 }

void Ivy_MultiPrint ( Ivy_Man_t *  p,
Ivy_Eva_t *  pEvals,
int  nLeaves,
int  nEvals 
) [static]

Function*************************************************************

Synopsis [Computes how many uncovered ones this one covers.]

Description []

SideEffects []

SeeAlso []

Definition at line 169 of file ivyMulti.c.

00170 {
00171     Ivy_Eva_t * pEval;
00172     int i, k;
00173     for ( i = nLeaves; i < nEvals; i++ )
00174     {
00175         pEval = pEvals + i;
00176         printf( "%2d  (id = %5d)  : |", i-nLeaves, Ivy_ObjId(pEval->pArg) );
00177         for ( k = 0; k < nLeaves; k++ )
00178         {
00179             if ( pEval->Mask & (1 << k) )
00180                 printf( "+" );
00181             else
00182                 printf( " " );
00183         }
00184         printf( "|  Lev = %d.\n", Ivy_ObjLevel(pEval->pArg) );
00185     }
00186 }

static int Ivy_MultiWeight ( unsigned  uMask,
int  nMaskOnes,
unsigned  uFound 
) [inline, static]

Function*************************************************************

Synopsis [Computes how many uncovered ones this one covers.]

Description []

SideEffects []

SeeAlso []

Definition at line 199 of file ivyMulti.c.

00200 {
00201     assert( uMask & ~uFound );
00202     if ( (uMask & uFound) == 0 )
00203         return nMaskOnes;
00204     return Extra_WordCountOnes( uMask & ~uFound );
00205 }

Generated on Tue Jan 5 12:18:24 2010 for abc70930 by  doxygen 1.6.1