abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
Functions
llb1Cluster.c File Reference
#include "llbInt.h"

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 ///. More...
 
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

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.

325 {
326  int RetValue;
327  do
328  {
329  do {
330  RetValue = Llb_ManComputeBestQuant( p );
331  if ( RetValue > 0 )
332  Llb_ManClusterOne( p, RetValue >> 16, RetValue & 0xffff );
333  }
334  while ( RetValue > 0 );
335 
336  RetValue = Llb_ManComputeBestAttr( p );
337  if ( RetValue > 0 )
338  Llb_ManClusterOne( p, RetValue >> 16, RetValue & 0xffff );
339 
340  Llb_MtrVerifyMatrix( p );
341  }
342  while ( RetValue > 0 );
343 
344  Llb_ManClusterCompress( p );
345 
346  Llb_MtrVerifyMatrix( p );
347 }
Llb_MtrVerifyMatrix
void Llb_MtrVerifyMatrix(Llb_Mtr_t *p)
Definition: llb1Matrix.c:115
Llb_ManClusterOne
void Llb_ManClusterOne(Llb_Mtr_t *p, int iCol1, int iCol2)
Definition: llb1Cluster.c:258
Llb_ManClusterCompress
void Llb_ManClusterCompress(Llb_Mtr_t *p)
Definition: llb1Cluster.c:293
Llb_ManComputeBestAttr
int Llb_ManComputeBestAttr(Llb_Mtr_t *p)
Definition: llb1Cluster.c:164
Llb_ManComputeBestQuant
int Llb_ManComputeBestQuant(Llb_Mtr_t *p)
Definition: llb1Cluster.c:72
void Llb_ManClusterCompress ( Llb_Mtr_t *  p)

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

Synopsis [Removes empty columns.]

Description []

SideEffects []

SeeAlso []

Definition at line 293 of file llb1Cluster.c.

294 {
295  int i, k = 0;
296  for ( i = 0; i < p->nCols; i++ )
297  {
298  if ( p->pColGrps[i] == NULL )
299  {
300  assert( p->pColSums[i] == 0 );
301  assert( p->pMatrix[i] != NULL );
302  ABC_FREE( p->pMatrix[i] );
303  continue;
304  }
305  p->pMatrix[k] = p->pMatrix[i];
306  p->pColGrps[k] = p->pColGrps[i];
307  p->pColSums[k] = p->pColSums[i];
308  k++;
309  }
310  p->nCols = k;
311 }
Llb_Mtr_t_::pMatrix
char ** pMatrix
Definition: llbInt.h:87
Llb_Mtr_t_::nCols
int nCols
Definition: llbInt.h:83
ABC_FREE
#define ABC_FREE(obj)
Definition: abc_global.h:232
assert
#define assert(ex)
Definition: util_old.h:213
Llb_Mtr_t_::pColSums
int * pColSums
Definition: llbInt.h:84
Llb_Mtr_t_::pColGrps
Llb_Grp_t ** pColGrps
Definition: llbInt.h:85
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.

259 {
260  int fVerbose = 0;
261  Llb_Grp_t * pGrp;
262  int iVar;
263 
264  if ( fVerbose )
265  {
266  printf( "Combining %d and %d\n", iCol1, iCol2 );
267  for ( iVar = 0; iVar < p->nRows; iVar++ )
268  {
269  if ( p->pMatrix[iCol1][iVar] == 0 && p->pMatrix[iCol2][iVar] == 0 )
270  continue;
271  printf( "%3d : %c%c\n", iVar,
272  p->pMatrix[iCol1][iVar]? '*':' ',
273  p->pMatrix[iCol2][iVar]? '*':' ' );
274  }
275  }
276  pGrp = Llb_ManGroupsCombine( p->pColGrps[iCol1], p->pColGrps[iCol2] );
277  Llb_MtrCombineSelectedColumns( p, iCol1, iCol2 );
278  p->pColGrps[iCol1] = pGrp;
279  p->pColGrps[iCol2] = NULL;
280 }
Llb_MtrCombineSelectedColumns
void Llb_MtrCombineSelectedColumns(Llb_Mtr_t *p, int iGrp1, int iGrp2)
Definition: llb1Cluster.c:224
Llb_ManGroupsCombine
Llb_Grp_t * Llb_ManGroupsCombine(Llb_Grp_t *p1, Llb_Grp_t *p2)
Definition: llb1Group.c:251
Llb_Mtr_t_::pMatrix
char ** pMatrix
Definition: llbInt.h:87
Llb_Mtr_t_::nRows
int nRows
Definition: llbInt.h:82
Llb_Grp_t_
Definition: llbInt.h:94
Llb_Mtr_t_::pColGrps
Llb_Grp_t ** pColGrps
Definition: llbInt.h:85
float** Llb_ManComputeAttr ( Llb_Mtr_t *  p)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 196 of file llb1Cluster.c.

197 {
198  float ** pCosts;
199  int i, k;
200  // alloc and clean
201  pCosts = (float **)Extra_ArrayAlloc( p->nCols, p->nCols, sizeof(float) );
202  for ( i = 0; i < p->nCols; i++ )
203  for ( k = 0; k < p->nCols; k++ )
204  pCosts[i][i] = 0.0;
205  // fill up
206  for ( i = 1; i < p->nCols-1; i++ )
207  for ( k = i+1; k < p->nCols-1; k++ )
208  pCosts[i][k] = pCosts[k][i] = Llb_ManComputeCommonAttr( p, i, k );
209  return pCosts;
210 }
Llb_ManComputeCommonAttr
float Llb_ManComputeCommonAttr(Llb_Mtr_t *p, int iCol1, int iCol2)
Definition: llb1Cluster.c:134
Extra_ArrayAlloc
void ** Extra_ArrayAlloc(int nCols, int nRows, int Size)
Definition: extraUtilMisc.c:880
Llb_Mtr_t_::nCols
int nCols
Definition: llbInt.h:83
int Llb_ManComputeBestAttr ( Llb_Mtr_t *  p)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 164 of file llb1Cluster.c.

165 {
166  float WeightBest = -100000, WeightCur;
167  int i, k, RetValue = -1;
168  for ( i = 1; i < p->nCols-1; i++ )
169  for ( k = i+1; k < p->nCols-1; k++ )
170  {
171  if ( p->pColSums[i] == 0 || p->pColSums[i] > p->pMan->pPars->nClusterMax )
172  continue;
173  if ( p->pColSums[k] == 0 || p->pColSums[k] > p->pMan->pPars->nClusterMax )
174  continue;
175  WeightCur = Llb_ManComputeCommonAttr( p, i, k );
176  if ( WeightBest < WeightCur )
177  {
178  WeightBest = WeightCur;
179  RetValue = (i << 16) | k;
180  }
181  }
182  return RetValue;
183 }
Llb_Mtr_t_::pMan
Llb_Man_t * pMan
Definition: llbInt.h:88
Llb_ManComputeCommonAttr
float Llb_ManComputeCommonAttr(Llb_Mtr_t *p, int iCol1, int iCol2)
Definition: llb1Cluster.c:134
Llb_Mtr_t_::nCols
int nCols
Definition: llbInt.h:83
Llb_Mtr_t_::pColSums
int * pColSums
Definition: llbInt.h:84
int Llb_ManComputeBestQuant ( Llb_Mtr_t *  p)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 72 of file llb1Cluster.c.

73 {
74  int i, k, WeightBest = -100000, WeightCur, RetValue = -1;
75  for ( i = 1; i < p->nCols-1; i++ )
76  for ( k = i+1; k < p->nCols-1; k++ )
77  {
78  if ( p->pColSums[i] == 0 || p->pColSums[i] > p->pMan->pPars->nClusterMax )
79  continue;
80  if ( p->pColSums[k] == 0 || p->pColSums[k] > p->pMan->pPars->nClusterMax )
81  continue;
82 
83  WeightCur = Llb_ManComputeCommonQuant( p, i, k );
84  if ( WeightCur <= 0 )
85  continue;
86  if ( WeightBest < WeightCur )
87  {
88  WeightBest = WeightCur;
89  RetValue = (i << 16) | k;
90  }
91  }
92 // printf( "Choosing best quant Weight %4d\n", WeightCur );
93  return RetValue;
94 }
Llb_Mtr_t_::pMan
Llb_Man_t * pMan
Definition: llbInt.h:88
Llb_ManComputeCommonQuant
ABC_NAMESPACE_IMPL_START int Llb_ManComputeCommonQuant(Llb_Mtr_t *p, int iCol1, int iCol2)
DECLARATIONS ///.
Definition: llb1Cluster.c:45
Llb_Mtr_t_::nCols
int nCols
Definition: llbInt.h:83
Llb_Mtr_t_::pColSums
int * pColSums
Definition: llbInt.h:84
float Llb_ManComputeCommonAttr ( Llb_Mtr_t *  p,
int  iCol1,
int  iCol2 
)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 134 of file llb1Cluster.c.

135 {
136  int iVar, CountComm = 0, CountDiff = 0;
137  for ( iVar = 0; iVar < p->nRows - p->nFfs; iVar++ )
138  {
139  if ( p->pMatrix[iCol1][iVar] == 1 && p->pMatrix[iCol2][iVar] == 1 )
140  CountComm++;
141  else if ( p->pMatrix[iCol1][iVar] == 1 || p->pMatrix[iCol2][iVar] == 1 )
142  CountDiff++;
143  }
144 /*
145  printf( "Attr cost for %4d and %4d: %4d %4d (%5.2f)\n",
146  iCol1, iCol2,
147  CountDiff, CountComm,
148  -1.0 * CountDiff / ( CountComm + CountDiff ) );
149 */
150  return -1.0 * CountDiff / ( CountComm + CountDiff );
151 }
Llb_Mtr_t_::pMatrix
char ** pMatrix
Definition: llbInt.h:87
Llb_Mtr_t_::nFfs
int nFfs
Definition: llbInt.h:81
Llb_Mtr_t_::nRows
int nRows
Definition: llbInt.h:82
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.

46 {
47  int iVar, Weight = 0;
48  for ( iVar = 0; iVar < p->nRows - p->nFfs; iVar++ )
49  {
50  // count each removed variable as 2
51  if ( p->pMatrix[iCol1][iVar] == 1 && p->pMatrix[iCol2][iVar] == 1 && p->pRowSums[iVar] == 2 )
52  Weight += 2;
53  // count each added variale as -1
54  else if ( (p->pMatrix[iCol1][iVar] == 1 && p->pMatrix[iCol2][iVar] == 0) ||
55  (p->pMatrix[iCol1][iVar] == 0 && p->pMatrix[iCol2][iVar] == 1) )
56  Weight--;
57  }
58  return Weight;
59 }
Llb_Mtr_t_::pRowSums
int * pRowSums
Definition: llbInt.h:86
Llb_Mtr_t_::pMatrix
char ** pMatrix
Definition: llbInt.h:87
Llb_Mtr_t_::nFfs
int nFfs
Definition: llbInt.h:81
Llb_Mtr_t_::nRows
int nRows
Definition: llbInt.h:82
float** Llb_ManComputeQuant ( Llb_Mtr_t *  p)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 107 of file llb1Cluster.c.

108 {
109  float ** pCosts;
110  int i, k;
111  // alloc and clean
112  pCosts = (float **)Extra_ArrayAlloc( p->nCols, p->nCols, sizeof(float) );
113  for ( i = 0; i < p->nCols; i++ )
114  for ( k = 0; k < p->nCols; k++ )
115  pCosts[i][i] = 0.0;
116  // fill up
117  for ( i = 1; i < p->nCols-1; i++ )
118  for ( k = i+1; k < p->nCols-1; k++ )
119  pCosts[i][k] = pCosts[k][i] = Llb_ManComputeCommonQuant( p, i, k );
120  return pCosts;
121 }
Extra_ArrayAlloc
void ** Extra_ArrayAlloc(int nCols, int nRows, int Size)
Definition: extraUtilMisc.c:880
Llb_ManComputeCommonQuant
ABC_NAMESPACE_IMPL_START int Llb_ManComputeCommonQuant(Llb_Mtr_t *p, int iCol1, int iCol2)
DECLARATIONS ///.
Definition: llb1Cluster.c:45
Llb_Mtr_t_::nCols
int nCols
Definition: llbInt.h:83
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.

225 {
226  int iVar;
227  assert( iGrp1 >= 1 && iGrp1 < p->nCols - 1 );
228  assert( iGrp2 >= 1 && iGrp2 < p->nCols - 1 );
229  assert( p->pColGrps[iGrp1] != NULL );
230  assert( p->pColGrps[iGrp2] != NULL );
231  for ( iVar = 0; iVar < p->nRows; iVar++ )
232  {
233  if ( p->pMatrix[iGrp1][iVar] == 1 && p->pMatrix[iGrp2][iVar] == 1 )
234  p->pRowSums[iVar]--;
235  if ( p->pMatrix[iGrp1][iVar] == 0 && p->pMatrix[iGrp2][iVar] == 1 )
236  {
237  p->pMatrix[iGrp1][iVar] = 1;
238  p->pColSums[iGrp1]++;
239  }
240  if ( p->pMatrix[iGrp2][iVar] == 1 )
241  p->pMatrix[iGrp2][iVar] = 0;
242  }
243  p->pColSums[iGrp2] = 0;
244 }
Llb_Mtr_t_::pRowSums
int * pRowSums
Definition: llbInt.h:86
Llb_Mtr_t_::pMatrix
char ** pMatrix
Definition: llbInt.h:87
assert
#define assert(ex)
Definition: util_old.h:213
Llb_Mtr_t_::nRows
int nRows
Definition: llbInt.h:82
Llb_Mtr_t_::pColSums
int * pColSums
Definition: llbInt.h:84
Llb_Mtr_t_::pColGrps
Llb_Grp_t ** pColGrps
Definition: llbInt.h:85