/**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