llb1Cluster.c File Reference

#include "llbInt.h"

Include dependency graph for llb1Cluster.c:

Go to the source code of this file.

Functions
ABC_NAMESPACE_IMPL_START int	Llb_ManComputeCommonQuant (Llb_Mtr_t *p, int iCol1, int iCol2)
	DECLARATIONS ///.
int	Llb_ManComputeBestQuant (Llb_Mtr_t *p)
float **	Llb_ManComputeQuant (Llb_Mtr_t *p)
float	Llb_ManComputeCommonAttr (Llb_Mtr_t *p, int iCol1, int iCol2)
int	Llb_ManComputeBestAttr (Llb_Mtr_t *p)
float **	Llb_ManComputeAttr (Llb_Mtr_t *p)
void	Llb_MtrCombineSelectedColumns (Llb_Mtr_t *p, int iGrp1, int iGrp2)
void	Llb_ManClusterOne (Llb_Mtr_t *p, int iCol1, int iCol2)
void	Llb_ManClusterCompress (Llb_Mtr_t *p)
void	Llb_ManCluster (Llb_Mtr_t *p)

Function Documentation

Llb_ManCluster()

void Llb_ManCluster

(

Llb_Mtr_t *

p

)

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

Synopsis [Combines one pair of columns.]

Description []

SideEffects []

SeeAlso []

Definition at line 324 of file llb1Cluster.c.

{
    int RetValue;
    do
    {
        do {
            RetValue = Llb_ManComputeBestQuant( p );
            if ( RetValue > 0 )
                Llb_ManClusterOne( p, RetValue >> 16, RetValue & 0xffff );
        }
        while ( RetValue > 0 );
 
        RetValue = Llb_ManComputeBestAttr( p );
        if ( RetValue > 0 )
            Llb_ManClusterOne( p, RetValue >> 16, RetValue & 0xffff );
 
        Llb_MtrVerifyMatrix( p );
    }
    while ( RetValue > 0 );
 
    Llb_ManClusterCompress( p );
 
    Llb_MtrVerifyMatrix( p );
}

Here is the call graph for this function:

Here is the caller graph for this function:

Llb_ManClusterCompress()

void Llb_ManClusterCompress

(

Llb_Mtr_t *

p

)

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

Synopsis [Removes empty columns.]

Description []

SideEffects []

SeeAlso []

Definition at line 293 of file llb1Cluster.c.

{
    int i, k = 0;
    for ( i = 0; i < p->nCols; i++ )
    {
        if ( p->pColGrps[i] == NULL )
        {
            assert( p->pColSums[i] == 0 );
            assert( p->pMatrix[i] != NULL );
            ABC_FREE( p->pMatrix[i] );
            continue;
        }
        p->pMatrix[k]  = p->pMatrix[i];
        p->pColGrps[k] = p->pColGrps[i];
        p->pColSums[k] = p->pColSums[i];
        k++;
    }
    p->nCols = k;
}

Here is the caller graph for this function:

Llb_ManClusterOne()

void Llb_ManClusterOne	(	Llb_Mtr_t *	p,
		int	iCol1,
		int	iCol2 )

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

Synopsis [Combines one pair of columns.]

Description []

SideEffects []

SeeAlso []

Definition at line 258 of file llb1Cluster.c.

{
    int fVerbose = 0;
    Llb_Grp_t * pGrp;
    int iVar;
 
    if ( fVerbose )
    {
        printf( "Combining %d and %d\n", iCol1, iCol2 );
        for ( iVar = 0; iVar < p->nRows; iVar++ )
        {
            if ( p->pMatrix[iCol1][iVar] == 0 && p->pMatrix[iCol2][iVar] == 0 )
                continue;
            printf( "%3d : %c%c\n", iVar, 
                p->pMatrix[iCol1][iVar]? '*':' ', 
                p->pMatrix[iCol2][iVar]? '*':' ' );
        }
    }
    pGrp = Llb_ManGroupsCombine( p->pColGrps[iCol1], p->pColGrps[iCol2] );
    Llb_MtrCombineSelectedColumns( p, iCol1, iCol2 );
    p->pColGrps[iCol1] = pGrp;
    p->pColGrps[iCol2] = NULL;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Llb_ManComputeAttr()

float ** Llb_ManComputeAttr

(

Llb_Mtr_t *

p

)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 196 of file llb1Cluster.c.

{
    float ** pCosts;
    int i, k;
    // alloc and clean
    pCosts = (float **)Extra_ArrayAlloc( p->nCols, p->nCols, sizeof(float) );
    for ( i = 0; i < p->nCols; i++ )
    for ( k = 0; k < p->nCols; k++ )
        pCosts[i][i] = 0.0;
    // fill up
    for ( i = 1; i < p->nCols-1; i++ )
    for ( k = i+1; k < p->nCols-1; k++ )
        pCosts[i][k] = pCosts[k][i] = Llb_ManComputeCommonAttr( p, i, k );
    return pCosts;
}

Here is the call graph for this function:

Llb_ManComputeBestAttr()

int Llb_ManComputeBestAttr

(

Llb_Mtr_t *

p

)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 164 of file llb1Cluster.c.

{
    float WeightBest = -100000, WeightCur;
    int i, k, RetValue = -1;
    for ( i = 1; i < p->nCols-1; i++ )
    for ( k = i+1; k < p->nCols-1; k++ )
    {
        if ( p->pColSums[i] == 0 || p->pColSums[i] > p->pMan->pPars->nClusterMax )
            continue;
        if ( p->pColSums[k] == 0 || p->pColSums[k] > p->pMan->pPars->nClusterMax )
            continue;
        WeightCur = Llb_ManComputeCommonAttr( p, i, k );
        if ( WeightBest < WeightCur )
        {
            WeightBest = WeightCur;
            RetValue   = (i << 16) | k;
        }
    }
    return RetValue;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Llb_ManComputeBestQuant()

int Llb_ManComputeBestQuant

(

Llb_Mtr_t *

p

)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 72 of file llb1Cluster.c.

{
    int i, k, WeightBest = -100000, WeightCur, RetValue = -1;
    for ( i = 1; i < p->nCols-1; i++ )
    for ( k = i+1; k < p->nCols-1; k++ )
    {
        if ( p->pColSums[i] == 0 || p->pColSums[i] > p->pMan->pPars->nClusterMax )
            continue;
        if ( p->pColSums[k] == 0 || p->pColSums[k] > p->pMan->pPars->nClusterMax )
            continue;
 
        WeightCur = Llb_ManComputeCommonQuant( p, i, k );
        if ( WeightCur <= 0 )
            continue;
        if ( WeightBest < WeightCur )
        {
            WeightBest = WeightCur;
            RetValue   = (i << 16) | k;
        }
    }
//    printf( "Choosing best quant Weight %4d\n", WeightCur );
    return RetValue;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Llb_ManComputeCommonAttr()

float Llb_ManComputeCommonAttr	(	Llb_Mtr_t *	p,
		int	iCol1,
		int	iCol2 )

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 134 of file llb1Cluster.c.

{
    int iVar, CountComm = 0, CountDiff = 0;
    for ( iVar = 0; iVar < p->nRows - p->nFfs; iVar++ )
    {
        if ( p->pMatrix[iCol1][iVar] == 1 && p->pMatrix[iCol2][iVar] == 1 )
            CountComm++;
        else if ( p->pMatrix[iCol1][iVar] == 1 || p->pMatrix[iCol2][iVar] == 1 )
            CountDiff++;
    }
/*
    printf( "Attr cost for %4d and %4d:  %4d %4d (%5.2f)\n", 
        iCol1, iCol2, 
        CountDiff, CountComm, 
        -1.0 * CountDiff / ( CountComm + CountDiff ) );
*/
    return -1.0 * CountDiff / ( CountComm + CountDiff );
}

Here is the caller graph for this function:

Llb_ManComputeCommonQuant()

ABC_NAMESPACE_IMPL_START int Llb_ManComputeCommonQuant	(	Llb_Mtr_t *	p,
		int	iCol1,
		int	iCol2 )

DECLARATIONS ///.

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

FileName [llb1Cluster.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [BDD based reachability.]

Synopsis [Clustering algorithm.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

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

Revision [

Id

llb1Cluster.c,v 1.00 2005/06/20 00:00:00 alanmi Exp

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 45 of file llb1Cluster.c.

{
    int iVar, Weight = 0;
    for ( iVar = 0; iVar < p->nRows - p->nFfs; iVar++ )
    {
        // count each removed variable as 2
        if ( p->pMatrix[iCol1][iVar] == 1 && p->pMatrix[iCol2][iVar] == 1 && p->pRowSums[iVar] == 2 )
            Weight += 2;
        // count each added variale as -1
        else if ( (p->pMatrix[iCol1][iVar] == 1 && p->pMatrix[iCol2][iVar] == 0) || 
                  (p->pMatrix[iCol1][iVar] == 0 && p->pMatrix[iCol2][iVar] == 1) )
            Weight--;
    }
    return Weight;
}

Here is the caller graph for this function:

Llb_ManComputeQuant()

float ** Llb_ManComputeQuant

(

Llb_Mtr_t *

p

)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 107 of file llb1Cluster.c.

{
    float ** pCosts;
    int i, k;
    // alloc and clean
    pCosts = (float **)Extra_ArrayAlloc( p->nCols, p->nCols, sizeof(float) );
    for ( i = 0; i < p->nCols; i++ )
    for ( k = 0; k < p->nCols; k++ )
        pCosts[i][i] = 0.0;
    // fill up
    for ( i = 1; i < p->nCols-1; i++ )
    for ( k = i+1; k < p->nCols-1; k++ )
        pCosts[i][k] = pCosts[k][i] = Llb_ManComputeCommonQuant( p, i, k );
    return pCosts;
}

Here is the call graph for this function:

Llb_MtrCombineSelectedColumns()

void Llb_MtrCombineSelectedColumns	(	Llb_Mtr_t *	p,
		int	iGrp1,
		int	iGrp2 )

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

Synopsis [Returns the number of variables that will be saved.]

Description []

SideEffects []

SeeAlso []

Definition at line 224 of file llb1Cluster.c.

{
    int iVar;
    assert( iGrp1 >= 1 && iGrp1 < p->nCols - 1 );
    assert( iGrp2 >= 1 && iGrp2 < p->nCols - 1 );
    assert( p->pColGrps[iGrp1] != NULL );
    assert( p->pColGrps[iGrp2] != NULL );
    for ( iVar = 0; iVar < p->nRows; iVar++ )
    {
        if ( p->pMatrix[iGrp1][iVar] == 1 && p->pMatrix[iGrp2][iVar] == 1 )
            p->pRowSums[iVar]--;
        if ( p->pMatrix[iGrp1][iVar] == 0 && p->pMatrix[iGrp2][iVar] == 1 )
        {
            p->pMatrix[iGrp1][iVar] = 1;
            p->pColSums[iGrp1]++;
        }
        if ( p->pMatrix[iGrp2][iVar] == 1 )
            p->pMatrix[iGrp2][iVar] = 0;
    }
    p->pColSums[iGrp2] = 0;
}

Here is the caller graph for this function: