/**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 $]
***********************************************************************/
#include "llbInt.h"
ABC_NAMESPACE_IMPL_START
////////////////////////////////////////////////////////////////////////
/// DECLARATIONS ///
////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////
/// FUNCTION DEFINITIONS ///
////////////////////////////////////////////////////////////////////////
/**Function*************************************************************
Synopsis []
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Llb_ManComputeCommonQuant( Llb_Mtr_t * p, int iCol1, int iCol2 )
{
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;
}
/**Function*************************************************************
Synopsis []
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Llb_ManComputeBestQuant( Llb_Mtr_t * p )
{
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;
}
/**Function*************************************************************
Synopsis []
Description []
SideEffects []
SeeAlso []
***********************************************************************/
float ** Llb_ManComputeQuant( Llb_Mtr_t * p )
{
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;
}
/**Function*************************************************************
Synopsis []
Description []
SideEffects []
SeeAlso []
***********************************************************************/
float Llb_ManComputeCommonAttr( Llb_Mtr_t * p, int iCol1, int iCol2 )
{
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 );
}
/**Function*************************************************************
Synopsis []
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Llb_ManComputeBestAttr( Llb_Mtr_t * p )
{
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;
}
/**Function*************************************************************
Synopsis []
Description []
SideEffects []
SeeAlso []
***********************************************************************/
float ** Llb_ManComputeAttr( Llb_Mtr_t * p )
{
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;
}
/**Function*************************************************************
Synopsis [Returns the number of variables that will be saved.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Llb_MtrCombineSelectedColumns( Llb_Mtr_t * p, int iGrp1, int iGrp2 )
{
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;
}
/**Function*************************************************************
Synopsis [Combines one pair of columns.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Llb_ManClusterOne( Llb_Mtr_t * p, int iCol1, int iCol2 )
{
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;
}
/**Function*************************************************************
Synopsis [Removes empty columns.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Llb_ManClusterCompress( Llb_Mtr_t * p )
{
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;
}
/**Function*************************************************************
Synopsis [Combines one pair of columns.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Llb_ManCluster( Llb_Mtr_t * p )
{
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 );
}
////////////////////////////////////////////////////////////////////////
/// END OF FILE ///
////////////////////////////////////////////////////////////////////////
ABC_NAMESPACE_IMPL_END