abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
llb1Matrix.c
Go to the documentation of this file.
1 /**CFile****************************************************************
2 
3  FileName [llb1Matrix.c]
4 
5  SystemName [ABC: Logic synthesis and verification system.]
6 
7  PackageName [BDD based reachability.]
8 
9  Synopsis [Partition clustering as a matrix problem.]
10 
11  Author [Alan Mishchenko]
12 
13  Affiliation [UC Berkeley]
14 
15  Date [Ver. 1.0. Started - June 20, 2005.]
16 
17  Revision [$Id: llb1Matrix.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
18 
19 ***********************************************************************/
20 
21 #include "llbInt.h"
22 
24 
25 
26 ////////////////////////////////////////////////////////////////////////
27 /// DECLARATIONS ///
28 ////////////////////////////////////////////////////////////////////////
29 
30 // 0123 nCols
31 // +--------------------->
32 // pi 0 | 111 row0 pRowSums[0]
33 // pi 1 | 1 11 row1 pRowSums[1]
34 // pi 2 | 1 11 row2 pRowSums[2]
35 // CS |1 1
36 // CS |1 111
37 // CS |111 111
38 // int | 11111
39 // int | 111
40 // int | 111
41 // int | 111
42 // NS | 11 11
43 // NS | 11 1
44 // NS | 111
45 // nRows |
46 // v
47 // cccc pColSums[0]
48 // oooo pColSums[1]
49 // llll pColSums[2]
50 // 0123 pColSums[3]
51 
52 ////////////////////////////////////////////////////////////////////////
53 /// FUNCTION DEFINITIONS ///
54 ////////////////////////////////////////////////////////////////////////
55 
56 /**Function*************************************************************
57 
58  Synopsis [Verify columns.]
59 
60  Description []
61 
62  SideEffects []
63 
64  SeeAlso []
65 
66 ***********************************************************************/
68 {
69  int iRow, iCol, Counter;
70  for ( iCol = 0; iCol < p->nCols; iCol++ )
71  {
72  Counter = 0;
73  for ( iRow = 0; iRow < p->nRows; iRow++ )
74  if ( p->pMatrix[iCol][iRow] == 1 )
75  Counter++;
76  assert( Counter == p->pColSums[iCol] );
77  }
78 }
79 
80 /**Function*************************************************************
81 
82  Synopsis [Verify columns.]
83 
84  Description []
85 
86  SideEffects []
87 
88  SeeAlso []
89 
90 ***********************************************************************/
92 {
93  int iRow, iCol, Counter;
94  for ( iRow = 0; iRow < p->nRows; iRow++ )
95  {
96  Counter = 0;
97  for ( iCol = 0; iCol < p->nCols; iCol++ )
98  if ( p->pMatrix[iCol][iRow] == 1 )
99  Counter++;
100  assert( Counter == p->pRowSums[iRow] );
101  }
102 }
103 
104 /**Function*************************************************************
105 
106  Synopsis [Verify columns.]
107 
108  Description []
109 
110  SideEffects []
111 
112  SeeAlso []
113 
114 ***********************************************************************/
116 {
119 }
120 
121 /**Function*************************************************************
122 
123  Synopsis [Sort variables in the order of removal.]
124 
125  Description []
126 
127  SideEffects []
128 
129  SeeAlso []
130 
131 ***********************************************************************/
133 {
134  int * pOrder, * pLast;
135  int i, k, fChanges, Temp;
136  pOrder = ABC_CALLOC( int, p->nRows );
137  pLast = ABC_CALLOC( int, p->nRows );
138  for ( i = 0; i < p->nRows; i++ )
139  {
140  pOrder[i] = i;
141  for ( k = p->nCols - 1; k >= 0; k-- )
142  if ( p->pMatrix[k][i] )
143  {
144  pLast[i] = k;
145  break;
146  }
147  }
148  do
149  {
150  fChanges = 0;
151  for ( i = 0; i < p->nRows - 1; i++ )
152  if ( pLast[i] > pLast[i+1] )
153  {
154  Temp = pOrder[i];
155  pOrder[i] = pOrder[i+1];
156  pOrder[i+1] = Temp;
157 
158  Temp = pLast[i];
159  pLast[i] = pLast[i+1];
160  pLast[i+1] = Temp;
161 
162  fChanges = 1;
163  }
164  }
165  while ( fChanges );
166  ABC_FREE( pLast );
167  return pOrder;
168 }
169 
170 /**Function*************************************************************
171 
172  Synopsis [Returns type of a variable.]
173 
174  Description []
175 
176  SideEffects []
177 
178  SeeAlso []
179 
180 ***********************************************************************/
181 char * Llb_MtrVarName( Llb_Mtr_t * p, int iVar )
182 {
183  static char Buffer[10];
184  if ( iVar < p->nPis )
185  strcpy( Buffer, "pi" );
186  else if ( iVar < p->nPis + p->nFfs )
187  strcpy( Buffer, "CS" );
188  else if ( iVar >= p->nRows - p->nFfs )
189  strcpy( Buffer, "NS" );
190  else
191  strcpy( Buffer, "int" );
192  return Buffer;
193 }
194 
195 /**Function*************************************************************
196 
197  Synopsis [Creates one column with vars in the array.]
198 
199  Description []
200 
201  SideEffects []
202 
203  SeeAlso []
204 
205 ***********************************************************************/
206 void Llb_MtrPrint( Llb_Mtr_t * p, int fOrder )
207 {
208  int * pOrder = NULL;
209  int i, iRow, iCol;
210  if ( fOrder )
211  pOrder = Llb_MtrFindVarOrder( p );
212  for ( i = 0; i < p->nRows; i++ )
213  {
214  iRow = pOrder ? pOrder[i] : i;
215  printf( "%3d : ", iRow );
216  printf( "%3d ", p->pRowSums[iRow] );
217  printf( "%3s ", Llb_MtrVarName(p, iRow) );
218  for ( iCol = 0; iCol < p->nCols; iCol++ )
219  printf( "%c", p->pMatrix[iCol][iRow] ? '*' : ' ' );
220  printf( "\n" );
221  }
222  ABC_FREE( pOrder );
223 }
224 
225 /**Function*************************************************************
226 
227  Synopsis [Verify columns.]
228 
229  Description []
230 
231  SideEffects []
232 
233  SeeAlso []
234 
235 ***********************************************************************/
237 {
238  int iVar, iGrp, iGrp1, iGrp2, Span = 0, nCutSize = 0, nCutSizeMax = 0;
239  int * pGrp1 = ABC_CALLOC( int, p->nRows );
240  int * pGrp2 = ABC_CALLOC( int, p->nRows );
241  for ( iVar = 0; iVar < p->nRows; iVar++ )
242  {
243  if ( p->pRowSums[iVar] == 0 )
244  continue;
245  for ( iGrp1 = 0; iGrp1 < p->nCols; iGrp1++ )
246  if ( p->pMatrix[iGrp1][iVar] == 1 )
247  break;
248  for ( iGrp2 = p->nCols - 1; iGrp2 >= 0; iGrp2-- )
249  if ( p->pMatrix[iGrp2][iVar] == 1 )
250  break;
251  assert( iGrp1 <= iGrp2 );
252  pGrp1[iVar] = iGrp1;
253  pGrp2[iVar] = iGrp2;
254  Span += iGrp2 - iGrp1;
255  }
256  // compute span
257  for ( iGrp = 0; iGrp < p->nCols; iGrp++ )
258  {
259  for ( iVar = 0; iVar < p->nRows; iVar++ )
260  if ( pGrp1[iVar] == iGrp )
261  nCutSize++;
262  if ( nCutSizeMax < nCutSize )
263  nCutSizeMax = nCutSize;
264  for ( iVar = 0; iVar < p->nRows; iVar++ )
265  if ( pGrp2[iVar] == iGrp )
266  nCutSize--;
267  }
268  ABC_FREE( pGrp1 );
269  ABC_FREE( pGrp2 );
270  printf( "[%4d x %4d] Life-span =%6.2f Max-cut =%5d\n",
271  p->nCols, p->nRows, 1.0*Span/p->nRows, nCutSizeMax );
272  if ( nCutSize )
273  Abc_Print( -1, "Cut size is not zero (%d).\n", nCutSize );
274 }
275 
276 
277 
278 /**Function*************************************************************
279 
280  Synopsis [Starts the matrix representation.]
281 
282  Description []
283 
284  SideEffects []
285 
286  SeeAlso []
287 
288 ***********************************************************************/
289 Llb_Mtr_t * Llb_MtrAlloc( int nPis, int nFfs, int nCols, int nRows )
290 {
291  Llb_Mtr_t * p;
292  int i;
293  p = ABC_CALLOC( Llb_Mtr_t, 1 );
294  p->nPis = nPis;
295  p->nFfs = nFfs;
296  p->nRows = nRows;
297  p->nCols = nCols;
298  p->pRowSums = ABC_CALLOC( int, nRows );
299  p->pColSums = ABC_CALLOC( int, nCols );
300  p->pColGrps = ABC_CALLOC( Llb_Grp_t *, nCols );
301  p->pMatrix = ABC_CALLOC( char *, nCols );
302  for ( i = 0; i < nCols; i++ )
303  p->pMatrix[i] = ABC_CALLOC( char, nRows );
304  // partial product
305  p->pProdVars = ABC_CALLOC( char, nRows ); // variables in the partial product
306  p->pProdNums = ABC_CALLOC( int, nRows ); // var counts in the remaining partitions
307  return p;
308 }
309 
310 /**Function*************************************************************
311 
312  Synopsis [Stops the matrix representation.]
313 
314  Description []
315 
316  SideEffects []
317 
318  SeeAlso []
319 
320 ***********************************************************************/
322 {
323  int i;
324  ABC_FREE( p->pProdVars );
325  ABC_FREE( p->pProdNums );
326  for ( i = 0; i < p->nCols; i++ )
327  ABC_FREE( p->pMatrix[i] );
328  ABC_FREE( p->pRowSums );
329  ABC_FREE( p->pColSums );
330  ABC_FREE( p->pMatrix );
331  ABC_FREE( p->pColGrps );
332  ABC_FREE( p );
333 }
334 
335 /**Function*************************************************************
336 
337  Synopsis [Creates one column with vars in the array.]
338 
339  Description []
340 
341  SideEffects []
342 
343  SeeAlso []
344 
345 ***********************************************************************/
347 {
348  Aig_Obj_t * pVar;
349  int i, iRow, iCol = pGrp->Id;
350  assert( iCol >= 0 && iCol < p->nCols );
351  p->pColGrps[iCol] = pGrp;
352  Vec_PtrForEachEntry( Aig_Obj_t *, pGrp->vIns, pVar, i )
353  {
354  iRow = Vec_IntEntry( pGrp->pMan->vObj2Var, Aig_ObjId(pVar) );
355  assert( iRow >= 0 && iRow < p->nRows );
356  p->pMatrix[iCol][iRow] = 1;
357  p->pColSums[iCol]++;
358  p->pRowSums[iRow]++;
359  }
360  Vec_PtrForEachEntry( Aig_Obj_t *, pGrp->vOuts, pVar, i )
361  {
362  iRow = Vec_IntEntry( pGrp->pMan->vObj2Var, Aig_ObjId(pVar) );
363  assert( iRow >= 0 && iRow < p->nRows );
364  p->pMatrix[iCol][iRow] = 1;
365  p->pColSums[iCol]++;
366  p->pRowSums[iRow]++;
367  }
368 }
369 
370 /**Function*************************************************************
371 
372  Synopsis [Matrix reduce.]
373 
374  Description []
375 
376  SideEffects []
377 
378  SeeAlso []
379 
380 ***********************************************************************/
382 {
383  int i, k;
384  for ( i = 0; i < p->nRows; i++ )
385  if ( p->pRowSums[i] < 2 )
386  {
387  p->pRowSums[i] = 0;
388  for ( k = 0; k < p->nCols; k++ )
389  {
390  if ( p->pMatrix[k][i] == 1 )
391  {
392  p->pMatrix[k][i] = 0;
393  p->pColSums[k]--;
394  }
395  }
396  }
397 }
398 
399 /**Function*************************************************************
400 
401  Synopsis [Matrix reduce.]
402 
403  Description []
404 
405  SideEffects []
406 
407  SeeAlso []
408 
409 ***********************************************************************/
411 {
412  Llb_Mtr_t * pMatrix;
413  Llb_Grp_t * pGroup;
414  int i;
415  pMatrix = Llb_MtrAlloc( Saig_ManPiNum(p->pAig), Saig_ManRegNum(p->pAig),
416  Vec_PtrSize(p->vGroups), Vec_IntSize(p->vVar2Obj) );
417  Vec_PtrForEachEntry( Llb_Grp_t *, p->vGroups, pGroup, i )
418  Llb_MtrAddColumn( pMatrix, pGroup );
419 // Llb_MtrRemoveSingletonRows( pMatrix );
420  return pMatrix;
421 }
422 
423 
424 ////////////////////////////////////////////////////////////////////////
425 /// END OF FILE ///
426 ////////////////////////////////////////////////////////////////////////
427 
428 
430 
void Llb_MtrVerifyMatrix(Llb_Mtr_t *p)
Definition: llb1Matrix.c:115
Llb_Man_t * pMan
Definition: llbInt.h:100
static Llb_Mgr_t * p
Definition: llb3Image.c:950
int * pProdNums
Definition: llbInt.h:91
int * pRowSums
Definition: llbInt.h:86
static int Vec_PtrSize(Vec_Ptr_t *p)
Definition: vecPtr.h:295
void Llb_MtrRemoveSingletonRows(Llb_Mtr_t *p)
Definition: llb1Matrix.c:381
ABC_NAMESPACE_IMPL_START void Llb_MtrVerifyRowsAll(Llb_Mtr_t *p)
DECLARATIONS ///.
Definition: llb1Matrix.c:67
int nPis
Definition: llbInt.h:80
static int Vec_IntEntry(Vec_Int_t *p, int i)
Definition: bblif.c:268
#define ABC_NAMESPACE_IMPL_END
Definition: abc_global.h:108
char * Llb_MtrVarName(Llb_Mtr_t *p, int iVar)
Definition: llb1Matrix.c:181
char ** pMatrix
Definition: llbInt.h:87
Definition: aig.h:69
static int Counter
int nCols
Definition: llbInt.h:83
static void Abc_Print(int level, const char *format,...)
Definition: abc_global.h:313
Llb_Mtr_t * Llb_MtrCreate(Llb_Man_t *p)
Definition: llb1Matrix.c:410
static int Saig_ManRegNum(Aig_Man_t *p)
Definition: saig.h:77
char * strcpy()
#define ABC_NAMESPACE_IMPL_START
Definition: abc_global.h:107
void Llb_MtrAddColumn(Llb_Mtr_t *p, Llb_Grp_t *pGrp)
Definition: llb1Matrix.c:346
int nFfs
Definition: llbInt.h:81
static int Vec_IntSize(Vec_Int_t *p)
Definition: bblif.c:252
static int Saig_ManPiNum(Aig_Man_t *p)
MACRO DEFINITIONS ///.
Definition: saig.h:73
#define ABC_FREE(obj)
Definition: abc_global.h:232
void Llb_MtrPrint(Llb_Mtr_t *p, int fOrder)
Definition: llb1Matrix.c:206
#define ABC_CALLOC(type, num)
Definition: abc_global.h:230
void Llb_MtrPrintMatrixStats(Llb_Mtr_t *p)
Definition: llb1Matrix.c:236
int * Llb_MtrFindVarOrder(Llb_Mtr_t *p)
Definition: llb1Matrix.c:132
static int Aig_ObjId(Aig_Obj_t *pObj)
Definition: aig.h:286
#define assert(ex)
Definition: util_old.h:213
int Id
Definition: llbInt.h:96
Llb_Mtr_t * Llb_MtrAlloc(int nPis, int nFfs, int nCols, int nRows)
Definition: llb1Matrix.c:289
int nRows
Definition: llbInt.h:82
#define Vec_PtrForEachEntry(Type, vVec, pEntry, i)
MACRO DEFINITIONS ///.
Definition: vecPtr.h:55
char * pProdVars
Definition: llbInt.h:90
int * pColSums
Definition: llbInt.h:84
Llb_Grp_t ** pColGrps
Definition: llbInt.h:85
typedefABC_NAMESPACE_HEADER_START struct Llb_Man_t_ Llb_Man_t
INCLUDES ///.
Definition: llbInt.h:46
void Llb_MtrFree(Llb_Mtr_t *p)
Definition: llb1Matrix.c:321
Vec_Ptr_t * vOuts
Definition: llbInt.h:98
Vec_Ptr_t * vIns
Definition: llbInt.h:97
void Llb_MtrVerifyColumnsAll(Llb_Mtr_t *p)
Definition: llb1Matrix.c:91