abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
llb1Cluster.c
Go to the documentation of this file.
1 /**CFile****************************************************************
2 
3  FileName [llb1Cluster.c]
4 
5  SystemName [ABC: Logic synthesis and verification system.]
6 
7  PackageName [BDD based reachability.]
8 
9  Synopsis [Clustering algorithm.]
10 
11  Author [Alan Mishchenko]
12 
13  Affiliation [UC Berkeley]
14 
15  Date [Ver. 1.0. Started - June 20, 2005.]
16 
17  Revision [$Id: llb1Cluster.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
18 
19 ***********************************************************************/
20 
21 #include "llbInt.h"
22 
23 ABC_NAMESPACE_IMPL_START
24 
25 
26 ////////////////////////////////////////////////////////////////////////
27 /// DECLARATIONS ///
28 ////////////////////////////////////////////////////////////////////////
29 
30 ////////////////////////////////////////////////////////////////////////
31 /// FUNCTION DEFINITIONS ///
32 ////////////////////////////////////////////////////////////////////////
33 
34 /**Function*************************************************************
35 
36  Synopsis []
37 
38  Description []
39 
40  SideEffects []
41 
42  SeeAlso []
43 
44 ***********************************************************************/
45 int Llb_ManComputeCommonQuant( Llb_Mtr_t * p, int iCol1, int iCol2 )
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 }
60 
61 /**Function*************************************************************
62 
63  Synopsis []
64 
65  Description []
66 
67  SideEffects []
68 
69  SeeAlso []
70 
71 ***********************************************************************/
72 int Llb_ManComputeBestQuant( Llb_Mtr_t * p )
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 }
95 
96 /**Function*************************************************************
97 
98  Synopsis []
99 
100  Description []
101 
102  SideEffects []
103 
104  SeeAlso []
105 
106 ***********************************************************************/
107 float ** Llb_ManComputeQuant( Llb_Mtr_t * p )
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 }
122 
123 /**Function*************************************************************
124 
125  Synopsis []
126 
127  Description []
128 
129  SideEffects []
130 
131  SeeAlso []
132 
133 ***********************************************************************/
134 float Llb_ManComputeCommonAttr( Llb_Mtr_t * p, int iCol1, int iCol2 )
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 }
152 
153 /**Function*************************************************************
154 
155  Synopsis []
156 
157  Description []
158 
159  SideEffects []
160 
161  SeeAlso []
162 
163 ***********************************************************************/
164 int Llb_ManComputeBestAttr( Llb_Mtr_t * p )
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 }
184 
185 /**Function*************************************************************
186 
187  Synopsis []
188 
189  Description []
190 
191  SideEffects []
192 
193  SeeAlso []
194 
195 ***********************************************************************/
196 float ** Llb_ManComputeAttr( Llb_Mtr_t * p )
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 }
211 
212 
213 /**Function*************************************************************
214 
215  Synopsis [Returns the number of variables that will be saved.]
216 
217  Description []
218 
219  SideEffects []
220 
221  SeeAlso []
222 
223 ***********************************************************************/
224 void Llb_MtrCombineSelectedColumns( Llb_Mtr_t * p, int iGrp1, int iGrp2 )
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 }
245 
246 
247 /**Function*************************************************************
248 
249  Synopsis [Combines one pair of columns.]
250 
251  Description []
252 
253  SideEffects []
254 
255  SeeAlso []
256 
257 ***********************************************************************/
258 void Llb_ManClusterOne( Llb_Mtr_t * p, int iCol1, int iCol2 )
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 }
281 
282 /**Function*************************************************************
283 
284  Synopsis [Removes empty columns.]
285 
286  Description []
287 
288  SideEffects []
289 
290  SeeAlso []
291 
292 ***********************************************************************/
293 void Llb_ManClusterCompress( Llb_Mtr_t * p )
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 }
312 
313 /**Function*************************************************************
314 
315  Synopsis [Combines one pair of columns.]
316 
317  Description []
318 
319  SideEffects []
320 
321  SeeAlso []
322 
323 ***********************************************************************/
324 void Llb_ManCluster( Llb_Mtr_t * p )
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 }
348 
349 
350 ////////////////////////////////////////////////////////////////////////
351 /// END OF FILE ///
352 ////////////////////////////////////////////////////////////////////////
353 
354 
355 ABC_NAMESPACE_IMPL_END
356 
Llb_MtrCombineSelectedColumns
void Llb_MtrCombineSelectedColumns(Llb_Mtr_t *p, int iGrp1, int iGrp2)
Definition: llb1Cluster.c:224
Llb_MtrVerifyMatrix
void Llb_MtrVerifyMatrix(Llb_Mtr_t *p)
Definition: llb1Matrix.c:115
Llb_Mtr_t_::pMan
Llb_Man_t * pMan
Definition: llbInt.h:88
Llb_ManClusterOne
void Llb_ManClusterOne(Llb_Mtr_t *p, int iCol1, int iCol2)
Definition: llb1Cluster.c:258
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Llb_ManComputeCommonAttr
float Llb_ManComputeCommonAttr(Llb_Mtr_t *p, int iCol1, int iCol2)
Definition: llb1Cluster.c:134
Llb_ManComputeQuant
float ** Llb_ManComputeQuant(Llb_Mtr_t *p)
Definition: llb1Cluster.c:107
Llb_ManComputeAttr
float ** Llb_ManComputeAttr(Llb_Mtr_t *p)
Definition: llb1Cluster.c:196
Extra_ArrayAlloc
void ** Extra_ArrayAlloc(int nCols, int nRows, int Size)
Definition: extraUtilMisc.c:880
Llb_Mtr_t_::pRowSums
int * pRowSums
Definition: llbInt.h:86
Llb_ManComputeCommonQuant
ABC_NAMESPACE_IMPL_START int Llb_ManComputeCommonQuant(Llb_Mtr_t *p, int iCol1, int iCol2)
DECLARATIONS ///.
Definition: llb1Cluster.c:45
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_ManGroupsCombine
Llb_Grp_t * Llb_ManGroupsCombine(Llb_Grp_t *p1, Llb_Grp_t *p2)
Definition: llb1Group.c:251
Llb_ManCluster
void Llb_ManCluster(Llb_Mtr_t *p)
Definition: llb1Cluster.c:324
Llb_Mtr_t_
Definition: llbInt.h:78
ABC_NAMESPACE_IMPL_END
#define ABC_NAMESPACE_IMPL_END
Definition: abc_global.h:108
Llb_Mtr_t_::pMatrix
char ** pMatrix
Definition: llbInt.h:87
Llb_Mtr_t_::nCols
int nCols
Definition: llbInt.h:83
Llb_ManComputeBestQuant
int Llb_ManComputeBestQuant(Llb_Mtr_t *p)
Definition: llb1Cluster.c:72
ABC_NAMESPACE_IMPL_START
#define ABC_NAMESPACE_IMPL_START
Definition: abc_global.h:107
Llb_Mtr_t_::nFfs
int nFfs
Definition: llbInt.h:81
ABC_FREE
#define ABC_FREE(obj)
Definition: abc_global.h:232
assert
#define assert(ex)
Definition: util_old.h:213
Llb_Mtr_t_::nRows
int nRows
Definition: llbInt.h:82
Llb_Grp_t_
Definition: llbInt.h:94
Llb_Mtr_t_::pColSums
int * pColSums
Definition: llbInt.h:84
Llb_Mtr_t_::pColGrps
Llb_Grp_t ** pColGrps
Definition: llbInt.h:85