src/opt/fxu/fxuSingle.c File Reference

#include "fxuInt.h"
#include "vec.h"
Include dependency graph for fxuSingle.c:

Go to the source code of this file.

Functions

static void Fxu_MatrixComputeSinglesOneCollect (Fxu_Matrix *p, Fxu_Var *pVar, Vec_Ptr_t *vSingles)
void Fxu_MatrixComputeSingles (Fxu_Matrix *p, int fUse0, int nSingleMax)
void Fxu_MatrixComputeSinglesOne (Fxu_Matrix *p, Fxu_Var *pVar)
int Fxu_SingleCountCoincidence (Fxu_Matrix *p, Fxu_Var *pVar1, Fxu_Var *pVar2)

Function Documentation

void Fxu_MatrixComputeSingles ( Fxu_Matrix *  p,
int  fUse0,
int  nSingleMax 
)

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

Synopsis [Computes and adds all single-cube divisors to storage.]

Description [This procedure should be called once when the matrix is already contructed before the process of logic extraction begins..]

SideEffects []

SeeAlso []

Definition at line 44 of file fxuSingle.c.

00045 {
00046     Fxu_Var * pVar;
00047     Vec_Ptr_t * vSingles;
00048     int i, k;
00049     // set the weight limit
00050     p->nWeightLimit = 1 - fUse0;
00051     // iterate through columns in the matrix and collect single-cube divisors
00052     vSingles = Vec_PtrAlloc( 10000 );
00053     Fxu_MatrixForEachVariable( p, pVar )
00054         Fxu_MatrixComputeSinglesOneCollect( p, pVar, vSingles );
00055     p->nSingleTotal = Vec_PtrSize(vSingles) / 3;
00056     // check if divisors should be filtered
00057     if ( Vec_PtrSize(vSingles) > nSingleMax )
00058     {
00059         int * pWeigtCounts, nDivCount, Weight, i, c;;
00060         assert( Vec_PtrSize(vSingles) % 3 == 0 );
00061         // count how many divisors have the given weight
00062         pWeigtCounts = ALLOC( int, 1000 );
00063         memset( pWeigtCounts, 0, sizeof(int) * 1000 );
00064         for ( i = 2; i < Vec_PtrSize(vSingles); i += 3 )
00065         {
00066             Weight = (int)Vec_PtrEntry(vSingles, i);
00067             if ( Weight >= 999 )
00068                 pWeigtCounts[999]++;
00069             else
00070                 pWeigtCounts[Weight]++;
00071         }
00072         // select the bound on the weight (above this bound, singles will be included)
00073         nDivCount = 0;
00074         for ( c = 999; c >= 0; c-- )
00075         {
00076             nDivCount += pWeigtCounts[c];
00077             if ( nDivCount >= nSingleMax )
00078                 break;
00079         }
00080         free( pWeigtCounts );
00081         // collect singles with the given costs
00082         k = 0;
00083         for ( i = 2; i < Vec_PtrSize(vSingles); i += 3 )
00084         {
00085             Weight = (int)Vec_PtrEntry(vSingles, i);
00086             if ( Weight < c )
00087                 continue;
00088             Vec_PtrWriteEntry( vSingles, k++, Vec_PtrEntry(vSingles, i-2) );
00089             Vec_PtrWriteEntry( vSingles, k++, Vec_PtrEntry(vSingles, i-1) );
00090             Vec_PtrWriteEntry( vSingles, k++, Vec_PtrEntry(vSingles, i) );
00091             if ( k/3 == nSingleMax )
00092                 break;
00093         }
00094         Vec_PtrShrink( vSingles, k );
00095         // adjust the weight limit
00096         p->nWeightLimit = c;
00097     }
00098     // collect the selected divisors
00099     assert( Vec_PtrSize(vSingles) % 3 == 0 );
00100     for ( i = 0; i < Vec_PtrSize(vSingles); i += 3 )
00101     {
00102         Fxu_MatrixAddSingle( p, 
00103             Vec_PtrEntry(vSingles,i), 
00104             Vec_PtrEntry(vSingles,i+1), 
00105             (int)Vec_PtrEntry(vSingles,i+2) );
00106     }
00107     Vec_PtrFree( vSingles );
00108 }

void Fxu_MatrixComputeSinglesOne ( Fxu_Matrix *  p,
Fxu_Var *  pVar 
)

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

Synopsis [Adds the single-cube divisors associated with a new column.]

Description []

SideEffects []

SeeAlso []

Definition at line 181 of file fxuSingle.c.

00182 {
00183     Fxu_Lit * pLitV, * pLitH;
00184     Fxu_Var * pVar2;
00185     int Coin;
00186     int WeightCur;
00187 
00188     // start collecting the affected vars
00189     Fxu_MatrixRingVarsStart( p );
00190     // go through all the literals of this variable
00191     for ( pLitV = pVar->lLits.pHead; pLitV; pLitV = pLitV->pVNext )
00192         // for this literal, go through all the horizontal literals
00193         for ( pLitH = pLitV->pHPrev; pLitH; pLitH = pLitH->pHPrev )
00194         {
00195             // get another variable
00196             pVar2 = pLitH->pVar;
00197             // skip the var if it is already used
00198             if ( pVar2->pOrder )
00199                 continue;
00200             // skip the var if it belongs to the same node
00201 //            if ( pValue2Node[pVar->iVar] == pValue2Node[pVar2->iVar] )
00202 //                continue;
00203             // collect the var
00204             Fxu_MatrixRingVarsAdd( p, pVar2 );
00205         }
00206     // stop collecting the selected vars
00207     Fxu_MatrixRingVarsStop( p );
00208 
00209     // iterate through the selected vars
00210     Fxu_MatrixForEachVarInRing( p, pVar2 )
00211     {
00212         // count the coincidence
00213         Coin = Fxu_SingleCountCoincidence( p, pVar2, pVar );
00214         assert( Coin > 0 );
00215         // get the new weight
00216         WeightCur = Coin - 2;
00217         // peformance fix (August 24, 2007)
00218 //        if ( WeightCur >= 0 )
00219 //        Fxu_MatrixAddSingle( p, pVar2, pVar, WeightCur );
00220         if ( WeightCur >= p->nWeightLimit )
00221             Fxu_MatrixAddSingle( p, pVar2, pVar, WeightCur );
00222     }
00223     // unmark the vars
00224     Fxu_MatrixRingVarsUnmark( p );
00225 }

void Fxu_MatrixComputeSinglesOneCollect ( Fxu_Matrix *  p,
Fxu_Var *  pVar,
Vec_Ptr_t *  vSingles 
) [static]

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

FileName [fxuSingle.c]

PackageName [MVSIS 2.0: Multi-valued logic synthesis system.]

Synopsis [Procedures to compute the set of single-cube divisors.]

Author [MVSIS Group]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - February 1, 2003.]

Revision [

Id
fxuSingle.c,v 1.0 2003/02/01 00:00:00 alanmi Exp

] DECLARATIONS ///

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

Synopsis [Adds the single-cube divisors associated with a new column.]

Description []

SideEffects []

SeeAlso []

Definition at line 121 of file fxuSingle.c.

00122 {
00123     Fxu_Lit * pLitV, * pLitH;
00124     Fxu_Var * pVar2;
00125     int Coin;
00126     int WeightCur;
00127 
00128     // start collecting the affected vars
00129     Fxu_MatrixRingVarsStart( p );
00130     // go through all the literals of this variable
00131     for ( pLitV = pVar->lLits.pHead; pLitV; pLitV = pLitV->pVNext )
00132         // for this literal, go through all the horizontal literals
00133         for ( pLitH = pLitV->pHPrev; pLitH; pLitH = pLitH->pHPrev )
00134         {
00135             // get another variable
00136             pVar2 = pLitH->pVar;
00137             // skip the var if it is already used
00138             if ( pVar2->pOrder )
00139                 continue;
00140             // skip the var if it belongs to the same node
00141 //            if ( pValue2Node[pVar->iVar] == pValue2Node[pVar2->iVar] )
00142 //                continue;
00143             // collect the var
00144             Fxu_MatrixRingVarsAdd( p, pVar2 );
00145         }
00146     // stop collecting the selected vars
00147     Fxu_MatrixRingVarsStop( p );
00148 
00149     // iterate through the selected vars
00150     Fxu_MatrixForEachVarInRing( p, pVar2 )
00151     {
00152         // count the coincidence
00153         Coin = Fxu_SingleCountCoincidence( p, pVar2, pVar );
00154         assert( Coin > 0 );
00155         // get the new weight
00156         WeightCur = Coin - 2;
00157         // peformance fix (August 24, 2007)
00158         if ( WeightCur >= p->nWeightLimit )
00159         {
00160             Vec_PtrPush( vSingles, pVar2 );
00161             Vec_PtrPush( vSingles, pVar );
00162             Vec_PtrPush( vSingles, (void *)WeightCur );
00163         }
00164     }
00165 
00166     // unmark the vars
00167     Fxu_MatrixRingVarsUnmark( p );
00168 }

int Fxu_SingleCountCoincidence ( Fxu_Matrix *  p,
Fxu_Var *  pVar1,
Fxu_Var *  pVar2 
)

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

Synopsis [Computes the coincidence count of two columns.]

Description []

SideEffects []

SeeAlso []

Definition at line 238 of file fxuSingle.c.

00239 {
00240         Fxu_Lit * pLit1, * pLit2;
00241         int Result;
00242 
00243         // compute the coincidence count
00244         Result = 0;
00245         pLit1  = pVar1->lLits.pHead;
00246         pLit2  = pVar2->lLits.pHead;
00247         while ( 1 )
00248         {
00249                 if ( pLit1 && pLit2 )
00250                 {
00251                         if ( pLit1->pCube->pVar->iVar == pLit2->pCube->pVar->iVar )
00252                         { // the variables are the same
00253                             if ( pLit1->iCube == pLit2->iCube )
00254                             { // the literals are the same
00255                                     pLit1 = pLit1->pVNext;
00256                                     pLit2 = pLit2->pVNext;
00257                                     // add this literal to the coincidence
00258                                     Result++;
00259                             }
00260                             else if ( pLit1->iCube < pLit2->iCube )
00261                                     pLit1 = pLit1->pVNext;
00262                             else
00263                                     pLit2 = pLit2->pVNext;
00264                         }
00265                         else if ( pLit1->pCube->pVar->iVar < pLit2->pCube->pVar->iVar )
00266                                 pLit1 = pLit1->pVNext;
00267                         else
00268                                 pLit2 = pLit2->pVNext;
00269                 }
00270                 else if ( pLit1 && !pLit2 )
00271                         pLit1 = pLit1->pVNext;
00272                 else if ( !pLit1 && pLit2 )
00273                         pLit2 = pLit2->pVNext;
00274                 else
00275                         break;
00276         }
00277         return Result;
00278 }

Generated on Tue Jan 5 12:19:27 2010 for abc70930 by  doxygen 1.6.1