1 /**CFile****************************************************************
2
3 FileName [nwkMerge.c]
4
5 SystemName [ABC: Logic synthesis and verification system.]
6
7 PackageName [Netlist representation.]
8
9 Synopsis [LUT merging 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: nwkMerge.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
18
19 ***********************************************************************/
20
21 #include "nwk.h"
22 #include "nwkMerge.h"
23
24 ABC_NAMESPACE_IMPL_START
25
26
27 ////////////////////////////////////////////////////////////////////////
28 /// DECLARATIONS ///
29 ////////////////////////////////////////////////////////////////////////
30
31 ////////////////////////////////////////////////////////////////////////
32 /// FUNCTION DEFINITIONS ///
33 ////////////////////////////////////////////////////////////////////////
34
35 /**Function*************************************************************
36
37 Synopsis [Allocates the graph.]
38
39 Description []
40
41 SideEffects []
42
43 SeeAlso []
44
45 ***********************************************************************/
Nwk_ManGraphAlloc(int nVertsMax)46 Nwk_Grf_t * Nwk_ManGraphAlloc( int nVertsMax )
47 {
48 Nwk_Grf_t * p;
49 p = ABC_ALLOC( Nwk_Grf_t, 1 );
50 memset( p, 0, sizeof(Nwk_Grf_t) );
51 p->nVertsMax = nVertsMax;
52 p->nEdgeHash = Abc_PrimeCudd( 3 * nVertsMax );
53 p->pEdgeHash = ABC_CALLOC( Nwk_Edg_t *, p->nEdgeHash );
54 p->pMemEdges = Aig_MmFixedStart( sizeof(Nwk_Edg_t), p->nEdgeHash );
55 p->vPairs = Vec_IntAlloc( 1000 );
56 return p;
57 }
58
59 /**Function*************************************************************
60
61 Synopsis [Deallocates the graph.]
62
63 Description []
64
65 SideEffects []
66
67 SeeAlso []
68
69 ***********************************************************************/
Nwk_ManGraphFree(Nwk_Grf_t * p)70 void Nwk_ManGraphFree( Nwk_Grf_t * p )
71 {
72 if ( p->vPairs ) Vec_IntFree( p->vPairs );
73 if ( p->pMemEdges ) Aig_MmFixedStop( p->pMemEdges, 0 );
74 if ( p->pMemVerts ) Aig_MmFlexStop( p->pMemVerts, 0 );
75 ABC_FREE( p->pVerts );
76 ABC_FREE( p->pEdgeHash );
77 ABC_FREE( p->pMapLut2Id );
78 ABC_FREE( p->pMapId2Lut );
79 ABC_FREE( p );
80 }
81
82 /**Function*************************************************************
83
84 Synopsis [Prepares the graph for solving the problem.]
85
86 Description []
87
88 SideEffects []
89
90 SeeAlso []
91
92 ***********************************************************************/
Nwk_ManGraphReportMemoryUsage(Nwk_Grf_t * p)93 void Nwk_ManGraphReportMemoryUsage( Nwk_Grf_t * p )
94 {
95 p->nMemBytes1 =
96 sizeof(Nwk_Grf_t) +
97 sizeof(void *) * p->nEdgeHash +
98 sizeof(int) * (p->nObjs + p->nVertsMax) +
99 sizeof(Nwk_Edg_t) * p->nEdges;
100 p->nMemBytes2 =
101 sizeof(Nwk_Vrt_t) * p->nVerts +
102 sizeof(int) * 2 * p->nEdges;
103 printf( "Memory usage stats: Preprocessing = %.2f MB. Solving = %.2f MB.\n",
104 1.0 * p->nMemBytes1 / (1<<20), 1.0 * p->nMemBytes2 / (1<<20) );
105 }
106
107
108 /**Function*************************************************************
109
110 Synopsis [Finds or adds the edge to the graph.]
111
112 Description []
113
114 SideEffects []
115
116 SeeAlso []
117
118 ***********************************************************************/
Nwk_ManGraphHashEdge(Nwk_Grf_t * p,int iLut1,int iLut2)119 void Nwk_ManGraphHashEdge( Nwk_Grf_t * p, int iLut1, int iLut2 )
120 {
121 Nwk_Edg_t * pEntry;
122 unsigned Key;
123 if ( iLut1 == iLut2 )
124 return;
125 if ( iLut1 > iLut2 )
126 {
127 Key = iLut1;
128 iLut1 = iLut2;
129 iLut2 = Key;
130 }
131 assert( iLut1 < iLut2 );
132 if ( p->nObjs < iLut2 )
133 p->nObjs = iLut2;
134 Key = (unsigned)(741457 * iLut1 + 4256249 * iLut2) % p->nEdgeHash;
135 for ( pEntry = p->pEdgeHash[Key]; pEntry; pEntry = pEntry->pNext )
136 if ( pEntry->iNode1 == iLut1 && pEntry->iNode2 == iLut2 )
137 return;
138 pEntry = (Nwk_Edg_t *)Aig_MmFixedEntryFetch( p->pMemEdges );
139 pEntry->iNode1 = iLut1;
140 pEntry->iNode2 = iLut2;
141 pEntry->pNext = p->pEdgeHash[Key];
142 p->pEdgeHash[Key] = pEntry;
143 p->nEdges++;
144 }
145
146 /**Function*************************************************************
147
148 Synopsis [Adds one entry to the list.]
149
150 Description []
151
152 SideEffects []
153
154 SeeAlso []
155
156 ***********************************************************************/
Nwk_ManGraphListAdd(Nwk_Grf_t * p,int * pList,Nwk_Vrt_t * pVertex)157 static inline void Nwk_ManGraphListAdd( Nwk_Grf_t * p, int * pList, Nwk_Vrt_t * pVertex )
158 {
159 if ( *pList )
160 {
161 Nwk_Vrt_t * pHead;
162 pHead = p->pVerts[*pList];
163 pVertex->iPrev = 0;
164 pVertex->iNext = pHead->Id;
165 pHead->iPrev = pVertex->Id;
166 }
167 *pList = pVertex->Id;
168 }
169
170 /**Function*************************************************************
171
172 Synopsis [Deletes one entry from the list.]
173
174 Description []
175
176 SideEffects []
177
178 SeeAlso []
179
180 ***********************************************************************/
Nwk_ManGraphListDelete(Nwk_Grf_t * p,int * pList,Nwk_Vrt_t * pVertex)181 static inline void Nwk_ManGraphListDelete( Nwk_Grf_t * p, int * pList, Nwk_Vrt_t * pVertex )
182 {
183 assert( *pList );
184 if ( pVertex->iPrev )
185 {
186 // assert( p->pVerts[pVertex->iPrev]->iNext == pVertex->Id );
187 p->pVerts[pVertex->iPrev]->iNext = pVertex->iNext;
188 }
189 if ( pVertex->iNext )
190 {
191 // assert( p->pVerts[pVertex->iNext]->iPrev == pVertex->Id );
192 p->pVerts[pVertex->iNext]->iPrev = pVertex->iPrev;
193 }
194 if ( *pList == pVertex->Id )
195 *pList = pVertex->iNext;
196 pVertex->iPrev = pVertex->iNext = 0;
197 }
198
199 /**Function*************************************************************
200
201 Synopsis [Inserts the edge into one of the linked lists.]
202
203 Description []
204
205 SideEffects []
206
207 SeeAlso []
208
209 ***********************************************************************/
Nwk_ManGraphListInsert(Nwk_Grf_t * p,Nwk_Vrt_t * pVertex)210 static inline void Nwk_ManGraphListInsert( Nwk_Grf_t * p, Nwk_Vrt_t * pVertex )
211 {
212 Nwk_Vrt_t * pNext;
213 assert( pVertex->nEdges > 0 );
214
215 if ( pVertex->nEdges == 1 )
216 {
217 pNext = p->pVerts[ pVertex->pEdges[0] ];
218 if ( pNext->nEdges >= NWK_MAX_LIST )
219 Nwk_ManGraphListAdd( p, p->pLists1 + NWK_MAX_LIST, pVertex );
220 else
221 Nwk_ManGraphListAdd( p, p->pLists1 + pNext->nEdges, pVertex );
222 }
223 else
224 {
225 if ( pVertex->nEdges >= NWK_MAX_LIST )
226 Nwk_ManGraphListAdd( p, p->pLists2 + NWK_MAX_LIST, pVertex );
227 else
228 Nwk_ManGraphListAdd( p, p->pLists2 + pVertex->nEdges, pVertex );
229 }
230 }
231
232 /**Function*************************************************************
233
234 Synopsis [Extracts the edge from one of the linked lists.]
235
236 Description []
237
238 SideEffects []
239
240 SeeAlso []
241
242 ***********************************************************************/
Nwk_ManGraphListExtract(Nwk_Grf_t * p,Nwk_Vrt_t * pVertex)243 static inline void Nwk_ManGraphListExtract( Nwk_Grf_t * p, Nwk_Vrt_t * pVertex )
244 {
245 Nwk_Vrt_t * pNext;
246 assert( pVertex->nEdges > 0 );
247
248 if ( pVertex->nEdges == 1 )
249 {
250 pNext = p->pVerts[ pVertex->pEdges[0] ];
251 if ( pNext->nEdges >= NWK_MAX_LIST )
252 Nwk_ManGraphListDelete( p, p->pLists1 + NWK_MAX_LIST, pVertex );
253 else
254 Nwk_ManGraphListDelete( p, p->pLists1 + pNext->nEdges, pVertex );
255 }
256 else
257 {
258 if ( pVertex->nEdges >= NWK_MAX_LIST )
259 Nwk_ManGraphListDelete( p, p->pLists2 + NWK_MAX_LIST, pVertex );
260 else
261 Nwk_ManGraphListDelete( p, p->pLists2 + pVertex->nEdges, pVertex );
262 }
263 }
264
265 /**Function*************************************************************
266
267 Synopsis [Prepares the graph for solving the problem.]
268
269 Description []
270
271 SideEffects []
272
273 SeeAlso []
274
275 ***********************************************************************/
Nwk_ManGraphPrepare(Nwk_Grf_t * p)276 void Nwk_ManGraphPrepare( Nwk_Grf_t * p )
277 {
278 Nwk_Edg_t * pEntry;
279 Nwk_Vrt_t * pVertex;
280 int * pnEdges, nBytes, i;
281 // allocate memory for the present objects
282 p->pMapLut2Id = ABC_ALLOC( int, p->nObjs+1 );
283 p->pMapId2Lut = ABC_ALLOC( int, p->nVertsMax+1 );
284 memset( p->pMapLut2Id, 0xff, sizeof(int) * (p->nObjs+1) );
285 memset( p->pMapId2Lut, 0xff, sizeof(int) * (p->nVertsMax+1) );
286 // mark present objects
287 Nwk_GraphForEachEdge( p, pEntry, i )
288 {
289 assert( pEntry->iNode1 <= p->nObjs );
290 assert( pEntry->iNode2 <= p->nObjs );
291 p->pMapLut2Id[ pEntry->iNode1 ] = 0;
292 p->pMapLut2Id[ pEntry->iNode2 ] = 0;
293 }
294 // map objects
295 p->nVerts = 0;
296 for ( i = 0; i <= p->nObjs; i++ )
297 {
298 if ( p->pMapLut2Id[i] == 0 )
299 {
300 p->pMapLut2Id[i] = ++p->nVerts;
301 p->pMapId2Lut[p->nVerts] = i;
302 }
303 }
304 // count the edges and mark present objects
305 pnEdges = ABC_CALLOC( int, p->nVerts+1 );
306 Nwk_GraphForEachEdge( p, pEntry, i )
307 {
308 // translate into vertices
309 assert( pEntry->iNode1 <= p->nObjs );
310 assert( pEntry->iNode2 <= p->nObjs );
311 pEntry->iNode1 = p->pMapLut2Id[pEntry->iNode1];
312 pEntry->iNode2 = p->pMapLut2Id[pEntry->iNode2];
313 // count the edges
314 assert( pEntry->iNode1 <= p->nVerts );
315 assert( pEntry->iNode2 <= p->nVerts );
316 pnEdges[pEntry->iNode1]++;
317 pnEdges[pEntry->iNode2]++;
318 }
319 // allocate the real graph
320 p->pMemVerts = Aig_MmFlexStart();
321 p->pVerts = ABC_ALLOC( Nwk_Vrt_t *, p->nVerts + 1 );
322 p->pVerts[0] = NULL;
323 for ( i = 1; i <= p->nVerts; i++ )
324 {
325 assert( pnEdges[i] > 0 );
326 nBytes = sizeof(Nwk_Vrt_t) + sizeof(int) * pnEdges[i];
327 p->pVerts[i] = (Nwk_Vrt_t *)Aig_MmFlexEntryFetch( p->pMemVerts, nBytes );
328 memset( p->pVerts[i], 0, nBytes );
329 p->pVerts[i]->Id = i;
330 }
331 // add edges to the real graph
332 Nwk_GraphForEachEdge( p, pEntry, i )
333 {
334 pVertex = p->pVerts[pEntry->iNode1];
335 pVertex->pEdges[ pVertex->nEdges++ ] = pEntry->iNode2;
336 pVertex = p->pVerts[pEntry->iNode2];
337 pVertex->pEdges[ pVertex->nEdges++ ] = pEntry->iNode1;
338 }
339 // put vertices into the data structure
340 for ( i = 1; i <= p->nVerts; i++ )
341 {
342 assert( p->pVerts[i]->nEdges == pnEdges[i] );
343 Nwk_ManGraphListInsert( p, p->pVerts[i] );
344 }
345 // clean up
346 Aig_MmFixedStop( p->pMemEdges, 0 ); p->pMemEdges = NULL;
347 ABC_FREE( p->pEdgeHash );
348 // p->nEdgeHash = 0;
349 ABC_FREE( pnEdges );
350 }
351
352 /**Function*************************************************************
353
354 Synopsis [Sort pairs by the first vertex in the topological order.]
355
356 Description []
357
358 SideEffects []
359
360 SeeAlso []
361
362 ***********************************************************************/
Nwk_ManGraphSortPairs(Nwk_Grf_t * p)363 void Nwk_ManGraphSortPairs( Nwk_Grf_t * p )
364 {
365 int nSize = Vec_IntSize(p->vPairs);
366 int * pIdToPair, i;
367 // allocate storage
368 pIdToPair = ABC_ALLOC( int, p->nObjs+1 );
369 for ( i = 0; i <= p->nObjs; i++ )
370 pIdToPair[i] = -1;
371 // create mapping
372 for ( i = 0; i < p->vPairs->nSize; i += 2 )
373 {
374 assert( pIdToPair[ p->vPairs->pArray[i] ] == -1 );
375 pIdToPair[ p->vPairs->pArray[i] ] = p->vPairs->pArray[i+1];
376 }
377 // recreate pairs
378 Vec_IntClear( p->vPairs );
379 for ( i = 0; i <= p->nObjs; i++ )
380 if ( pIdToPair[i] >= 0 )
381 {
382 assert( i < pIdToPair[i] );
383 Vec_IntPush( p->vPairs, i );
384 Vec_IntPush( p->vPairs, pIdToPair[i] );
385 }
386 assert( nSize == Vec_IntSize(p->vPairs) );
387 ABC_FREE( pIdToPair );
388 }
389
390
391 /**Function*************************************************************
392
393 Synopsis [Updates the problem after pulling out one edge.]
394
395 Description []
396
397 SideEffects []
398
399 SeeAlso []
400
401 ***********************************************************************/
Nwk_ManGraphCheckLists(Nwk_Grf_t * p)402 void Nwk_ManGraphCheckLists( Nwk_Grf_t * p )
403 {
404 Nwk_Vrt_t * pVertex, * pNext;
405 int i, j;
406 assert( p->pLists1[0] == 0 );
407 for ( i = 1; i <= NWK_MAX_LIST; i++ )
408 if ( p->pLists1[i] )
409 {
410 pVertex = p->pVerts[ p->pLists1[i] ];
411 assert( pVertex->nEdges == 1 );
412 pNext = p->pVerts[ pVertex->pEdges[0] ];
413 assert( pNext->nEdges == i || pNext->nEdges > NWK_MAX_LIST );
414 }
415 // find the next vertext to extract
416 assert( p->pLists2[0] == 0 );
417 assert( p->pLists2[1] == 0 );
418 for ( j = 2; j <= NWK_MAX_LIST; j++ )
419 if ( p->pLists2[j] )
420 {
421 pVertex = p->pVerts[ p->pLists2[j] ];
422 assert( pVertex->nEdges == j || pVertex->nEdges > NWK_MAX_LIST );
423 }
424 }
425
426 /**Function*************************************************************
427
428 Synopsis [Extracts the edge from one of the linked lists.]
429
430 Description []
431
432 SideEffects []
433
434 SeeAlso []
435
436 ***********************************************************************/
Nwk_ManGraphVertexRemoveEdge(Nwk_Vrt_t * pThis,Nwk_Vrt_t * pNext)437 static inline void Nwk_ManGraphVertexRemoveEdge( Nwk_Vrt_t * pThis, Nwk_Vrt_t * pNext )
438 {
439 int k;
440 for ( k = 0; k < pThis->nEdges; k++ )
441 if ( pThis->pEdges[k] == pNext->Id )
442 break;
443 assert( k < pThis->nEdges );
444 pThis->nEdges--;
445 for ( ; k < pThis->nEdges; k++ )
446 pThis->pEdges[k] = pThis->pEdges[k+1];
447 }
448
449 /**Function*************************************************************
450
451 Synopsis [Updates the problem after pulling out one edge.]
452
453 Description []
454
455 SideEffects []
456
457 SeeAlso []
458
459 ***********************************************************************/
Nwk_ManGraphUpdate(Nwk_Grf_t * p,Nwk_Vrt_t * pVertex,Nwk_Vrt_t * pNext)460 void Nwk_ManGraphUpdate( Nwk_Grf_t * p, Nwk_Vrt_t * pVertex, Nwk_Vrt_t * pNext )
461 {
462 Nwk_Vrt_t * pChanged, * pOther;
463 int i, k;
464 // Nwk_ManGraphCheckLists( p );
465 Nwk_ManGraphListExtract( p, pVertex );
466 Nwk_ManGraphListExtract( p, pNext );
467 // update neihbors of pVertex
468 Nwk_VertexForEachAdjacent( p, pVertex, pChanged, i )
469 {
470 if ( pChanged == pNext )
471 continue;
472 Nwk_ManGraphListExtract( p, pChanged );
473 // move those that use this one
474 if ( pChanged->nEdges > 1 )
475 Nwk_VertexForEachAdjacent( p, pChanged, pOther, k )
476 {
477 if ( pOther == pVertex || pOther->nEdges > 1 )
478 continue;
479 assert( pOther->nEdges == 1 );
480 Nwk_ManGraphListExtract( p, pOther );
481 pChanged->nEdges--;
482 Nwk_ManGraphListInsert( p, pOther );
483 pChanged->nEdges++;
484 }
485 // remove the edge
486 Nwk_ManGraphVertexRemoveEdge( pChanged, pVertex );
487 // add the changed vertex back
488 if ( pChanged->nEdges > 0 )
489 Nwk_ManGraphListInsert( p, pChanged );
490 }
491 // update neihbors of pNext
492 Nwk_VertexForEachAdjacent( p, pNext, pChanged, i )
493 {
494 if ( pChanged == pVertex )
495 continue;
496 Nwk_ManGraphListExtract( p, pChanged );
497 // move those that use this one
498 if ( pChanged->nEdges > 1 )
499 Nwk_VertexForEachAdjacent( p, pChanged, pOther, k )
500 {
501 if ( pOther == pNext || pOther->nEdges > 1 )
502 continue;
503 assert( pOther->nEdges == 1 );
504 Nwk_ManGraphListExtract( p, pOther );
505 pChanged->nEdges--;
506 Nwk_ManGraphListInsert( p, pOther );
507 pChanged->nEdges++;
508 }
509 // remove the edge
510 Nwk_ManGraphVertexRemoveEdge( pChanged, pNext );
511 // add the changed vertex back
512 if ( pChanged->nEdges > 0 )
513 Nwk_ManGraphListInsert( p, pChanged );
514 }
515 // add to the result
516 if ( pVertex->Id < pNext->Id )
517 {
518 Vec_IntPush( p->vPairs, p->pMapId2Lut[pVertex->Id] );
519 Vec_IntPush( p->vPairs, p->pMapId2Lut[pNext->Id] );
520 }
521 else
522 {
523 Vec_IntPush( p->vPairs, p->pMapId2Lut[pNext->Id] );
524 Vec_IntPush( p->vPairs, p->pMapId2Lut[pVertex->Id] );
525 }
526 // Nwk_ManGraphCheckLists( p );
527 }
528
529 /**Function*************************************************************
530
531 Synopsis [Counts the number of entries in the list.]
532
533 Description []
534
535 SideEffects []
536
537 SeeAlso []
538
539 ***********************************************************************/
Nwk_ManGraphListLength(Nwk_Grf_t * p,int List)540 int Nwk_ManGraphListLength( Nwk_Grf_t * p, int List )
541 {
542 Nwk_Vrt_t * pThis;
543 int fVerbose = 0;
544 int Counter = 0;
545 Nwk_ListForEachVertex( p, List, pThis )
546 {
547 if ( fVerbose && Counter < 20 )
548 printf( "%d ", p->pVerts[pThis->pEdges[0]]->nEdges );
549 Counter++;
550 }
551 if ( fVerbose )
552 printf( "\n" );
553 return Counter;
554 }
555
556 /**Function*************************************************************
557
558 Synopsis [Returns the adjacent vertex with the mininum number of edges.]
559
560 Description []
561
562 SideEffects []
563
564 SeeAlso []
565
566 ***********************************************************************/
Nwk_ManGraphListFindMinEdge(Nwk_Grf_t * p,Nwk_Vrt_t * pVert)567 Nwk_Vrt_t * Nwk_ManGraphListFindMinEdge( Nwk_Grf_t * p, Nwk_Vrt_t * pVert )
568 {
569 Nwk_Vrt_t * pThis, * pMinCost = NULL;
570 int k;
571 Nwk_VertexForEachAdjacent( p, pVert, pThis, k )
572 {
573 if ( pMinCost == NULL || pMinCost->nEdges > pThis->nEdges )
574 pMinCost = pThis;
575 }
576 return pMinCost;
577 }
578
579 /**Function*************************************************************
580
581 Synopsis [Finds the best vertext in the list.]
582
583 Description []
584
585 SideEffects []
586
587 SeeAlso []
588
589 ***********************************************************************/
Nwk_ManGraphListFindMin(Nwk_Grf_t * p,int List)590 Nwk_Vrt_t * Nwk_ManGraphListFindMin( Nwk_Grf_t * p, int List )
591 {
592 Nwk_Vrt_t * pThis, * pMinCost = NULL;
593 int k, Counter = 10000, BestCost = 1000000;
594 Nwk_ListForEachVertex( p, List, pThis )
595 {
596 for ( k = 0; k < pThis->nEdges; k++ )
597 {
598 if ( pMinCost == NULL || BestCost > p->pVerts[pThis->pEdges[k]]->nEdges )
599 {
600 BestCost = p->pVerts[pThis->pEdges[k]]->nEdges;
601 pMinCost = pThis;
602 }
603 }
604 if ( --Counter == 0 )
605 break;
606 }
607 return pMinCost;
608 }
609
610 /**Function*************************************************************
611
612 Synopsis [Solves the problem by extracting one edge at a time.]
613
614 Description []
615
616 SideEffects []
617
618 SeeAlso []
619
620 ***********************************************************************/
Nwk_ManGraphSolve(Nwk_Grf_t * p)621 void Nwk_ManGraphSolve( Nwk_Grf_t * p )
622 {
623 Nwk_Vrt_t * pVertex, * pNext;
624 int i, j;
625 Nwk_ManGraphPrepare( p );
626 while ( 1 )
627 {
628 // find the next vertex to extract
629 assert( p->pLists1[0] == 0 );
630 for ( i = 1; i <= NWK_MAX_LIST; i++ )
631 if ( p->pLists1[i] )
632 {
633 // printf( "%d ", i );
634 // printf( "ListA = %2d. Length = %5d.\n", i, Nwk_ManGraphListLength(p,p->pLists1[i]) );
635 pVertex = p->pVerts[ p->pLists1[i] ];
636 assert( pVertex->nEdges == 1 );
637 pNext = p->pVerts[ pVertex->pEdges[0] ];
638 Nwk_ManGraphUpdate( p, pVertex, pNext );
639 break;
640 }
641 if ( i < NWK_MAX_LIST + 1 )
642 continue;
643 // find the next vertex to extract
644 assert( p->pLists2[0] == 0 );
645 assert( p->pLists2[1] == 0 );
646 for ( j = 2; j <= NWK_MAX_LIST; j++ )
647 if ( p->pLists2[j] )
648 {
649 // printf( "***%d ", j );
650 // printf( "ListB = %2d. Length = %5d.\n", j, Nwk_ManGraphListLength(p,p->pLists2[j]) );
651 pVertex = Nwk_ManGraphListFindMin( p, p->pLists2[j] );
652 assert( pVertex->nEdges == j || j == NWK_MAX_LIST );
653 pNext = Nwk_ManGraphListFindMinEdge( p, pVertex );
654 Nwk_ManGraphUpdate( p, pVertex, pNext );
655 break;
656 }
657 if ( j == NWK_MAX_LIST + 1 )
658 break;
659 }
660 Nwk_ManGraphSortPairs( p );
661 }
662
663 /**Function*************************************************************
664
665 Synopsis [Reads graph from file.]
666
667 Description []
668
669 SideEffects []
670
671 SeeAlso []
672
673 ***********************************************************************/
Nwk_ManLutMergeReadGraph(char * pFileName)674 Nwk_Grf_t * Nwk_ManLutMergeReadGraph( char * pFileName )
675 {
676 Nwk_Grf_t * p;
677 FILE * pFile;
678 char Buffer[100];
679 int nNodes, nEdges, iNode1, iNode2;
680 int RetValue;
681 pFile = fopen( pFileName, "r" );
682 RetValue = fscanf( pFile, "%s %d", Buffer, &nNodes );
683 RetValue = fscanf( pFile, "%s %d", Buffer, &nEdges );
684 p = Nwk_ManGraphAlloc( nNodes );
685 while ( fscanf( pFile, "%s %d %d", Buffer, &iNode1, &iNode2 ) == 3 )
686 Nwk_ManGraphHashEdge( p, iNode1, iNode2 );
687 assert( p->nEdges == nEdges );
688 fclose( pFile );
689 return p;
690 }
691
692 /**Function*************************************************************
693
694 Synopsis [Solves the graph coming from file.]
695
696 Description []
697
698 SideEffects []
699
700 SeeAlso []
701
702 ***********************************************************************/
Nwk_ManLutMergeGraphTest(char * pFileName)703 int Nwk_ManLutMergeGraphTest( char * pFileName )
704 {
705 int nPairs;
706 Nwk_Grf_t * p;
707 abctime clk = Abc_Clock();
708 p = Nwk_ManLutMergeReadGraph( pFileName );
709 ABC_PRT( "Reading", Abc_Clock() - clk );
710 clk = Abc_Clock();
711 Nwk_ManGraphSolve( p );
712 printf( "GRAPH: Nodes = %6d. Edges = %6d. Pairs = %6d. ",
713 p->nVerts, p->nEdges, Vec_IntSize(p->vPairs)/2 );
714 ABC_PRT( "Solving", Abc_Clock() - clk );
715 nPairs = Vec_IntSize(p->vPairs)/2;
716 Nwk_ManGraphReportMemoryUsage( p );
717 Nwk_ManGraphFree( p );
718 return nPairs;
719 }
720
721
722
723
724 /**Function*************************************************************
725
726 Synopsis [Marks the fanins of the node with the current trav ID.]
727
728 Description []
729
730 SideEffects []
731
732 SeeAlso []
733
734 ***********************************************************************/
Nwk_ManMarkFanins_rec(Nwk_Obj_t * pLut,int nLevMin)735 void Nwk_ManMarkFanins_rec( Nwk_Obj_t * pLut, int nLevMin )
736 {
737 Nwk_Obj_t * pNext;
738 int i;
739 if ( !Nwk_ObjIsNode(pLut) )
740 return;
741 if ( Nwk_ObjIsTravIdCurrent( pLut ) )
742 return;
743 Nwk_ObjSetTravIdCurrent( pLut );
744 if ( Nwk_ObjLevel(pLut) < nLevMin )
745 return;
746 Nwk_ObjForEachFanin( pLut, pNext, i )
747 Nwk_ManMarkFanins_rec( pNext, nLevMin );
748 }
749
750 /**Function*************************************************************
751
752 Synopsis [Marks the fanouts of the node with the current trav ID.]
753
754 Description []
755
756 SideEffects []
757
758 SeeAlso []
759
760 ***********************************************************************/
Nwk_ManMarkFanouts_rec(Nwk_Obj_t * pLut,int nLevMax,int nFanMax)761 void Nwk_ManMarkFanouts_rec( Nwk_Obj_t * pLut, int nLevMax, int nFanMax )
762 {
763 Nwk_Obj_t * pNext;
764 int i;
765 if ( !Nwk_ObjIsNode(pLut) )
766 return;
767 if ( Nwk_ObjIsTravIdCurrent( pLut ) )
768 return;
769 Nwk_ObjSetTravIdCurrent( pLut );
770 if ( Nwk_ObjLevel(pLut) > nLevMax )
771 return;
772 if ( Nwk_ObjFanoutNum(pLut) > nFanMax )
773 return;
774 Nwk_ObjForEachFanout( pLut, pNext, i )
775 Nwk_ManMarkFanouts_rec( pNext, nLevMax, nFanMax );
776 }
777
778 /**Function*************************************************************
779
780 Synopsis [Collects the circle of nodes around the given set.]
781
782 Description []
783
784 SideEffects []
785
786 SeeAlso []
787
788 ***********************************************************************/
Nwk_ManCollectCircle(Vec_Ptr_t * vStart,Vec_Ptr_t * vNext,int nFanMax)789 void Nwk_ManCollectCircle( Vec_Ptr_t * vStart, Vec_Ptr_t * vNext, int nFanMax )
790 {
791 Nwk_Obj_t * pObj, * pNext;
792 int i, k;
793 Vec_PtrClear( vNext );
794 Vec_PtrForEachEntry( Nwk_Obj_t *, vStart, pObj, i )
795 {
796 Nwk_ObjForEachFanin( pObj, pNext, k )
797 {
798 if ( !Nwk_ObjIsNode(pNext) )
799 continue;
800 if ( Nwk_ObjIsTravIdCurrent( pNext ) )
801 continue;
802 Nwk_ObjSetTravIdCurrent( pNext );
803 Vec_PtrPush( vNext, pNext );
804 }
805 Nwk_ObjForEachFanout( pObj, pNext, k )
806 {
807 if ( !Nwk_ObjIsNode(pNext) )
808 continue;
809 if ( Nwk_ObjIsTravIdCurrent( pNext ) )
810 continue;
811 Nwk_ObjSetTravIdCurrent( pNext );
812 if ( Nwk_ObjFanoutNum(pNext) > nFanMax )
813 continue;
814 Vec_PtrPush( vNext, pNext );
815 }
816 }
817 }
818
819 /**Function*************************************************************
820
821 Synopsis [Collects the circle of nodes removes from the given one.]
822
823 Description []
824
825 SideEffects []
826
827 SeeAlso []
828
829 ***********************************************************************/
Nwk_ManCollectNonOverlapCands(Nwk_Obj_t * pLut,Vec_Ptr_t * vStart,Vec_Ptr_t * vNext,Vec_Ptr_t * vCands,Nwk_LMPars_t * pPars)830 void Nwk_ManCollectNonOverlapCands( Nwk_Obj_t * pLut, Vec_Ptr_t * vStart, Vec_Ptr_t * vNext, Vec_Ptr_t * vCands, Nwk_LMPars_t * pPars )
831 {
832 Vec_Ptr_t * vTemp;
833 Nwk_Obj_t * pObj;
834 int i, k;
835 Vec_PtrClear( vCands );
836 if ( pPars->nMaxSuppSize - Nwk_ObjFaninNum(pLut) <= 1 )
837 return;
838
839 // collect nodes removed by this distance
840 assert( pPars->nMaxDistance > 0 );
841 Vec_PtrClear( vStart );
842 Vec_PtrPush( vStart, pLut );
843 Nwk_ManIncrementTravId( pLut->pMan );
844 Nwk_ObjSetTravIdCurrent( pLut );
845 for ( i = 1; i <= pPars->nMaxDistance; i++ )
846 {
847 Nwk_ManCollectCircle( vStart, vNext, pPars->nMaxFanout );
848 vTemp = vStart;
849 vStart = vNext;
850 vNext = vTemp;
851 // collect the nodes in vStart
852 Vec_PtrForEachEntry( Nwk_Obj_t *, vStart, pObj, k )
853 Vec_PtrPush( vCands, pObj );
854 }
855
856 // mark the TFI/TFO nodes
857 Nwk_ManIncrementTravId( pLut->pMan );
858 if ( pPars->fUseTfiTfo )
859 Nwk_ObjSetTravIdCurrent( pLut );
860 else
861 {
862 Nwk_ObjSetTravIdPrevious( pLut );
863 Nwk_ManMarkFanins_rec( pLut, Nwk_ObjLevel(pLut) - pPars->nMaxDistance );
864 Nwk_ObjSetTravIdPrevious( pLut );
865 Nwk_ManMarkFanouts_rec( pLut, Nwk_ObjLevel(pLut) + pPars->nMaxDistance, pPars->nMaxFanout );
866 }
867
868 // collect nodes satisfying the following conditions:
869 // - they are close enough in terms of distance
870 // - they are not in the TFI/TFO of the LUT
871 // - they have no more than the given number of fanins
872 // - they have no more than the given diff in delay
873 k = 0;
874 Vec_PtrForEachEntry( Nwk_Obj_t *, vCands, pObj, i )
875 {
876 if ( Nwk_ObjIsTravIdCurrent(pObj) )
877 continue;
878 if ( Nwk_ObjFaninNum(pLut) + Nwk_ObjFaninNum(pObj) > pPars->nMaxSuppSize )
879 continue;
880 if ( Nwk_ObjLevel(pLut) - Nwk_ObjLevel(pObj) > pPars->nMaxLevelDiff ||
881 Nwk_ObjLevel(pObj) - Nwk_ObjLevel(pLut) > pPars->nMaxLevelDiff )
882 continue;
883 Vec_PtrWriteEntry( vCands, k++, pObj );
884 }
885 Vec_PtrShrink( vCands, k );
886 }
887
888
889 /**Function*************************************************************
890
891 Synopsis [Count the total number of fanins.]
892
893 Description []
894
895 SideEffects []
896
897 SeeAlso []
898
899 ***********************************************************************/
Nwk_ManCountTotalFanins(Nwk_Obj_t * pLut,Nwk_Obj_t * pCand)900 int Nwk_ManCountTotalFanins( Nwk_Obj_t * pLut, Nwk_Obj_t * pCand )
901 {
902 Nwk_Obj_t * pFanin;
903 int i, nCounter = Nwk_ObjFaninNum(pLut);
904 Nwk_ObjForEachFanin( pCand, pFanin, i )
905 nCounter += !pFanin->MarkC;
906 return nCounter;
907 }
908
909 /**Function*************************************************************
910
911 Synopsis [Collects overlapping candidates.]
912
913 Description []
914
915 SideEffects []
916
917 SeeAlso []
918
919 ***********************************************************************/
Nwk_ManCollectOverlapCands(Nwk_Obj_t * pLut,Vec_Ptr_t * vCands,Nwk_LMPars_t * pPars)920 void Nwk_ManCollectOverlapCands( Nwk_Obj_t * pLut, Vec_Ptr_t * vCands, Nwk_LMPars_t * pPars )
921 {
922 Nwk_Obj_t * pFanin, * pObj;
923 int i, k;
924 // mark fanins of pLut
925 Nwk_ObjForEachFanin( pLut, pFanin, i )
926 pFanin->MarkC = 1;
927 // collect the matching fanouts of each fanin of the node
928 Vec_PtrClear( vCands );
929 Nwk_ManIncrementTravId( pLut->pMan );
930 Nwk_ObjSetTravIdCurrent( pLut );
931 Nwk_ObjForEachFanin( pLut, pFanin, i )
932 {
933 if ( !Nwk_ObjIsNode(pFanin) )
934 continue;
935 if ( Nwk_ObjFanoutNum(pFanin) > pPars->nMaxFanout )
936 continue;
937 Nwk_ObjForEachFanout( pFanin, pObj, k )
938 {
939 if ( !Nwk_ObjIsNode(pObj) )
940 continue;
941 if ( Nwk_ObjIsTravIdCurrent( pObj ) )
942 continue;
943 Nwk_ObjSetTravIdCurrent( pObj );
944 // check the difference in delay
945 if ( Nwk_ObjLevel(pLut) - Nwk_ObjLevel(pObj) > pPars->nMaxLevelDiff ||
946 Nwk_ObjLevel(pObj) - Nwk_ObjLevel(pLut) > pPars->nMaxLevelDiff )
947 continue;
948 // check the total number of fanins of the node
949 if ( Nwk_ManCountTotalFanins(pLut, pObj) > pPars->nMaxSuppSize )
950 continue;
951 Vec_PtrPush( vCands, pObj );
952 }
953 }
954 // unmark fanins of pLut
955 Nwk_ObjForEachFanin( pLut, pFanin, i )
956 pFanin->MarkC = 0;
957 }
958
959 /**Function*************************************************************
960
961 Synopsis [Performs LUT merging with parameters.]
962
963 Description []
964
965 SideEffects []
966
967 SeeAlso []
968
969 ***********************************************************************/
Nwk_ManLutMerge(Nwk_Man_t * pNtk,void * pParsInit)970 Vec_Int_t * Nwk_ManLutMerge( Nwk_Man_t * pNtk, void * pParsInit )
971 {
972 Nwk_LMPars_t * pPars = (Nwk_LMPars_t *)pParsInit;
973 Nwk_Grf_t * p;
974 Vec_Int_t * vResult;
975 Vec_Ptr_t * vStart, * vNext, * vCands1, * vCands2;
976 Nwk_Obj_t * pLut, * pCand;
977 int i, k, nVertsMax, nCands;
978 abctime clk = Abc_Clock();
979 // count the number of vertices
980 nVertsMax = 0;
981 Nwk_ManForEachNode( pNtk, pLut, i )
982 nVertsMax += (int)(Nwk_ObjFaninNum(pLut) <= pPars->nMaxLutSize);
983 p = Nwk_ManGraphAlloc( nVertsMax );
984 // create graph
985 vStart = Vec_PtrAlloc( 1000 );
986 vNext = Vec_PtrAlloc( 1000 );
987 vCands1 = Vec_PtrAlloc( 1000 );
988 vCands2 = Vec_PtrAlloc( 1000 );
989 nCands = 0;
990 Nwk_ManForEachNode( pNtk, pLut, i )
991 {
992 if ( Nwk_ObjFaninNum(pLut) > pPars->nMaxLutSize )
993 continue;
994 Nwk_ManCollectOverlapCands( pLut, vCands1, pPars );
995 if ( pPars->fUseDiffSupp )
996 Nwk_ManCollectNonOverlapCands( pLut, vStart, vNext, vCands2, pPars );
997 if ( Vec_PtrSize(vCands1) == 0 && Vec_PtrSize(vCands2) == 0 )
998 continue;
999 nCands += Vec_PtrSize(vCands1) + Vec_PtrSize(vCands2);
1000 // save candidates
1001 Vec_PtrForEachEntry( Nwk_Obj_t *, vCands1, pCand, k )
1002 Nwk_ManGraphHashEdge( p, Nwk_ObjId(pLut), Nwk_ObjId(pCand) );
1003 Vec_PtrForEachEntry( Nwk_Obj_t *, vCands2, pCand, k )
1004 Nwk_ManGraphHashEdge( p, Nwk_ObjId(pLut), Nwk_ObjId(pCand) );
1005 // print statistics about this node
1006 if ( pPars->fVeryVerbose )
1007 printf( "Node %6d : Fanins = %d. Fanouts = %3d. Cand1 = %3d. Cand2 = %3d.\n",
1008 Nwk_ObjId(pLut), Nwk_ObjFaninNum(pLut), Nwk_ObjFaninNum(pLut),
1009 Vec_PtrSize(vCands1), Vec_PtrSize(vCands2) );
1010 }
1011 Vec_PtrFree( vStart );
1012 Vec_PtrFree( vNext );
1013 Vec_PtrFree( vCands1 );
1014 Vec_PtrFree( vCands2 );
1015 if ( pPars->fVerbose )
1016 {
1017 printf( "Mergable LUTs = %6d. Total cands = %6d. ", p->nVertsMax, nCands );
1018 ABC_PRT( "Deriving graph", Abc_Clock() - clk );
1019 }
1020 // solve the graph problem
1021 clk = Abc_Clock();
1022 Nwk_ManGraphSolve( p );
1023 if ( pPars->fVerbose )
1024 {
1025 printf( "GRAPH: Nodes = %6d. Edges = %6d. Pairs = %6d. ",
1026 p->nVerts, p->nEdges, Vec_IntSize(p->vPairs)/2 );
1027 ABC_PRT( "Solving", Abc_Clock() - clk );
1028 Nwk_ManGraphReportMemoryUsage( p );
1029 }
1030 vResult = p->vPairs; p->vPairs = NULL;
1031 /*
1032 for ( i = 0; i < vResult->nSize; i += 2 )
1033 printf( "(%d,%d) ", vResult->pArray[i], vResult->pArray[i+1] );
1034 printf( "\n" );
1035 */
1036 Nwk_ManGraphFree( p );
1037 return vResult;
1038 }
1039
1040 ////////////////////////////////////////////////////////////////////////
1041 /// END OF FILE ///
1042 ////////////////////////////////////////////////////////////////////////
1043
1044
1045 ABC_NAMESPACE_IMPL_END
1046
1047