1 /**CFile****************************************************************
2
3 FileName [fpgaMatch.c]
4
5 PackageName [MVSIS 1.3: Multi-valued logic synthesis system.]
6
7 Synopsis [Technology mapping for variable-size-LUT FPGAs.]
8
9 Author [MVSIS Group]
10
11 Affiliation [UC Berkeley]
12
13 Date [Ver. 2.0. Started - August 18, 2004.]
14
15 Revision [$Id: fpgaMatch.c,v 1.7 2004/09/30 21:18:10 satrajit Exp $]
16
17 ***********************************************************************/
18
19 #include "fpgaInt.h"
20
21 ABC_NAMESPACE_IMPL_START
22
23
24 ////////////////////////////////////////////////////////////////////////
25 /// DECLARATIONS ///
26 ////////////////////////////////////////////////////////////////////////
27
28 static int Fpga_MatchNode( Fpga_Man_t * p, Fpga_Node_t * pNode, int fDelayOriented );
29 static int Fpga_MatchNodeArea( Fpga_Man_t * p, Fpga_Node_t * pNode );
30 static int Fpga_MatchNodeSwitch( Fpga_Man_t * p, Fpga_Node_t * pNode );
31
32 static Fpga_Cut_t * Fpga_MappingAreaWithoutNode( Fpga_Man_t * p, Fpga_Node_t * pFanout, Fpga_Node_t * pNodeNo );
33 static int Fpga_MappingMatchesAreaArray( Fpga_Man_t * p, Fpga_NodeVec_t * vNodes );
34
35 ////////////////////////////////////////////////////////////////////////
36 /// FUNCTION DEFINITIONS ///
37 ////////////////////////////////////////////////////////////////////////
38
39 /**Function*************************************************************
40
41 Synopsis [Finds the best delay assignment of LUTs.]
42
43 Description [This procedure iterates through all the nodes
44 of the object graph reachable from the POs and assigns the best
45 match to each of them. If the flag fDelayOriented is set to 1, it
46 tries to minimize the arrival time and uses the area flow as a
47 tie-breaker. If the flag is set to 0, it considers all the cuts,
48 whose arrival times matches the required time at the node, and
49 minimizes the area flow using the arrival time as a tie-breaker.
50
51 Before this procedure is called, the required times should be set
52 and the fanout counts should be computed. In the first iteration,
53 the required times are set to very large number (by NodeCreate)
54 and the fanout counts are set to the number of fanouts in the AIG.
55 In the following iterations, the required times are set by the
56 backward traversal, while the fanouts are estimated approximately.
57
58 If the arrival times of the PI nodes are given, they should be
59 assigned to the PIs after the cuts are computed and before this
60 procedure is called for the first time.]
61
62 SideEffects []
63
64 SeeAlso []
65
66 ***********************************************************************/
Fpga_MappingMatches(Fpga_Man_t * p,int fDelayOriented)67 int Fpga_MappingMatches( Fpga_Man_t * p, int fDelayOriented )
68 {
69 ProgressBar * pProgress;
70 Fpga_Node_t * pNode;
71 int i, nNodes;
72
73 // assign the arrival times of the PIs
74 for ( i = 0; i < p->nInputs; i++ )
75 p->pInputs[i]->pCutBest->tArrival = p->pInputArrivals[i];
76
77 // match LUTs with nodes in the topological order
78 nNodes = p->vAnds->nSize;
79 pProgress = Extra_ProgressBarStart( stdout, nNodes );
80 for ( i = 0; i < nNodes; i++ )
81 {
82 pNode = p->vAnds->pArray[i];
83 if ( !Fpga_NodeIsAnd( pNode ) )
84 continue;
85 // skip a secondary node
86 if ( pNode->pRepr )
87 continue;
88 // match the node
89 Fpga_MatchNode( p, pNode, fDelayOriented );
90 Extra_ProgressBarUpdate( pProgress, i, "Matches ..." );
91 }
92 Extra_ProgressBarStop( pProgress );
93 /*
94 if ( !fDelayOriented )
95 {
96 float Area = 0.0;
97 for ( i = 0; i < p->nOutputs; i++ )
98 {
99 printf( "%5.2f ", Fpga_Regular(p->pOutputs[i])->pCutBest->aFlow );
100 Area += Fpga_Regular(p->pOutputs[i])->pCutBest->aFlow;
101 }
102 printf( "\nTotal = %5.2f\n", Area );
103 }
104 */
105 return 1;
106 }
107
108 /**Function*************************************************************
109
110 Synopsis [Computes the best matching for one node.]
111
112 Description []
113
114 SideEffects []
115
116 SeeAlso []
117
118 ***********************************************************************/
Fpga_MatchNode(Fpga_Man_t * p,Fpga_Node_t * pNode,int fDelayOriented)119 int Fpga_MatchNode( Fpga_Man_t * p, Fpga_Node_t * pNode, int fDelayOriented )
120 {
121 Fpga_Cut_t * pCut, * pCutBestOld;
122 clock_t clk;
123 // make sure that at least one cut other than the trivial is present
124 if ( pNode->pCuts->pNext == NULL )
125 {
126 printf( "\nError: A node in the mapping graph does not have feasible cuts.\n" );
127 return 0;
128 }
129
130 // estimate the fanouts of the node
131 if ( pNode->aEstFanouts < 0 )
132 pNode->aEstFanouts = (float)pNode->nRefs;
133 else
134 pNode->aEstFanouts = (float)((2.0 * pNode->aEstFanouts + pNode->nRefs) / 3.0);
135 // pNode->aEstFanouts = (float)pNode->nRefs;
136
137 pCutBestOld = pNode->pCutBest;
138 pNode->pCutBest = NULL;
139 for ( pCut = pNode->pCuts->pNext; pCut; pCut = pCut->pNext )
140 {
141 // compute the arrival time of the cut and its area flow
142 clk = clock();
143 Fpga_CutGetParameters( p, pCut );
144 //p->time2 += clock() - clk;
145 // drop the cut if it does not meet the required times
146 if ( Fpga_FloatMoreThan(p, pCut->tArrival, pNode->tRequired) )
147 continue;
148 // if no cut is assigned, use the current one
149 if ( pNode->pCutBest == NULL )
150 {
151 pNode->pCutBest = pCut;
152 continue;
153 }
154 // choose the best cut using one of the two criteria:
155 // (1) delay oriented mapping (first traversal), delay first, area-flow as a tie-breaker
156 // (2) area recovery (subsequent traversals), area-flow first, delay as a tie-breaker
157 if ( (fDelayOriented &&
158 (Fpga_FloatMoreThan(p, pNode->pCutBest->tArrival, pCut->tArrival) ||
159 (Fpga_FloatEqual(p, pNode->pCutBest->tArrival, pCut->tArrival) && Fpga_FloatMoreThan(p, pNode->pCutBest->aFlow, pCut->aFlow)) )) ||
160 (!fDelayOriented &&
161 (Fpga_FloatMoreThan(p, pNode->pCutBest->aFlow, pCut->aFlow) ||
162 (Fpga_FloatEqual(p, pNode->pCutBest->aFlow, pCut->aFlow) && Fpga_FloatMoreThan(p, pNode->pCutBest->tArrival, pCut->tArrival)))) )
163 {
164 pNode->pCutBest = pCut;
165 }
166 }
167
168 // make sure the match is found
169 if ( pNode->pCutBest == NULL )
170 {
171 if ( pCutBestOld == NULL )
172 {
173 // printf( "\nError: Could not match a node in the object graph.\n" );
174 return 0;
175 }
176 pNode->pCutBest = pCutBestOld;
177 }
178 return 1;
179 }
180
181
182
183
184
185 /**Function*************************************************************
186
187 Synopsis [Finds the best area assignment of LUTs.]
188
189 Description []
190
191 SideEffects []
192
193 SeeAlso []
194
195 ***********************************************************************/
Fpga_MappingMatchesArea(Fpga_Man_t * p)196 int Fpga_MappingMatchesArea( Fpga_Man_t * p )
197 {
198 ProgressBar * pProgress;
199 Fpga_Node_t * pNode;
200 int i, nNodes;
201
202 // assign the arrival times of the PIs
203 for ( i = 0; i < p->nInputs; i++ )
204 p->pInputs[i]->pCutBest->tArrival = p->pInputArrivals[i];
205
206 // match LUTs with nodes in the topological order
207 nNodes = p->vAnds->nSize;
208 pProgress = Extra_ProgressBarStart( stdout, nNodes );
209 for ( i = 0; i < nNodes; i++ )
210 {
211 pNode = p->vAnds->pArray[i];
212 if ( !Fpga_NodeIsAnd( pNode ) )
213 continue;
214 // skip a secondary node
215 if ( pNode->pRepr )
216 continue;
217 // match the node
218 Fpga_MatchNodeArea( p, pNode );
219 Extra_ProgressBarUpdate( pProgress, i, "Matches ..." );
220 }
221 Extra_ProgressBarStop( pProgress );
222 return 1;
223 }
224
225 /**Function*************************************************************
226
227 Synopsis [Finds the best area assignment of LUTs.]
228
229 Description []
230
231 SideEffects []
232
233 SeeAlso []
234
235 ***********************************************************************/
Fpga_MappingMatchesAreaArray(Fpga_Man_t * p,Fpga_NodeVec_t * vNodes)236 int Fpga_MappingMatchesAreaArray( Fpga_Man_t * p, Fpga_NodeVec_t * vNodes )
237 {
238 Fpga_Node_t * pNode;
239 int i;
240
241 // match LUTs with nodes in the topological order
242 for ( i = 0; i < vNodes->nSize; i++ )
243 {
244 pNode = vNodes->pArray[i];
245 if ( !Fpga_NodeIsAnd( pNode ) )
246 continue;
247 // skip a secondary node
248 if ( pNode->pRepr )
249 continue;
250 // match the node
251 if ( !Fpga_MatchNodeArea( p, pNode ) )
252 return 0;
253 }
254 return 1;
255 }
256
257 /**Function*************************************************************
258
259 Synopsis [Computes the best matching for one node.]
260
261 Description []
262
263 SideEffects []
264
265 SeeAlso []
266
267 ***********************************************************************/
Fpga_MatchNodeArea(Fpga_Man_t * p,Fpga_Node_t * pNode)268 int Fpga_MatchNodeArea( Fpga_Man_t * p, Fpga_Node_t * pNode )
269 {
270 Fpga_Cut_t * pCut, * pCutBestOld;
271 float aAreaCutBest;
272 clock_t clk;
273 // make sure that at least one cut other than the trivial is present
274 if ( pNode->pCuts->pNext == NULL )
275 {
276 printf( "\nError: A node in the mapping graph does not have feasible cuts.\n" );
277 return 0;
278 }
279
280 // remember the old cut
281 pCutBestOld = pNode->pCutBest;
282 // deref the old cut
283 if ( pNode->nRefs )
284 aAreaCutBest = Fpga_CutDeref( p, pNode, pNode->pCutBest, 0 );
285
286 // search for a better cut
287 pNode->pCutBest = NULL;
288 for ( pCut = pNode->pCuts->pNext; pCut; pCut = pCut->pNext )
289 {
290 // compute the arrival time of the cut and its area flow
291 clk = clock();
292 pCut->tArrival = Fpga_TimeCutComputeArrival( p, pCut );
293 //p->time2 += clock() - clk;
294 // drop the cut if it does not meet the required times
295 if ( Fpga_FloatMoreThan( p, pCut->tArrival, pNode->tRequired ) )
296 continue;
297 // get the area of this cut
298 pCut->aFlow = Fpga_CutGetAreaDerefed( p, pCut );
299 // if no cut is assigned, use the current one
300 if ( pNode->pCutBest == NULL )
301 {
302 pNode->pCutBest = pCut;
303 continue;
304 }
305 // choose the best cut as follows: exact area first, delay as a tie-breaker
306 if ( Fpga_FloatMoreThan(p, pNode->pCutBest->aFlow, pCut->aFlow) ||
307 (Fpga_FloatEqual(p, pNode->pCutBest->aFlow, pCut->aFlow) && Fpga_FloatMoreThan(p, pNode->pCutBest->tArrival, pCut->tArrival)) )
308 {
309 pNode->pCutBest = pCut;
310 }
311 }
312
313 // make sure the match is found
314 if ( pNode->pCutBest == NULL )
315 {
316 pNode->pCutBest = pCutBestOld;
317 // insert the new cut
318 if ( pNode->nRefs )
319 pNode->pCutBest->aFlow = Fpga_CutRef( p, pNode, pNode->pCutBest, 0 );
320 // printf( "\nError: Could not match a node in the object graph.\n" );
321 return 0;
322 }
323
324 // insert the new cut
325 // make sure the area selected is not worse then the original area
326 if ( pNode->nRefs )
327 {
328 pNode->pCutBest->aFlow = Fpga_CutRef( p, pNode, pNode->pCutBest, 0 );
329 // assert( pNode->pCutBest->aFlow <= aAreaCutBest );
330 // assert( pNode->tRequired < FPGA_FLOAT_LARGE );
331 }
332 return 1;
333 }
334
335
336
337
338 /**Function*************************************************************
339
340 Synopsis [Finds the best area assignment of LUTs.]
341
342 Description []
343
344 SideEffects []
345
346 SeeAlso []
347
348 ***********************************************************************/
Fpga_MappingMatchesSwitch(Fpga_Man_t * p)349 int Fpga_MappingMatchesSwitch( Fpga_Man_t * p )
350 {
351 ProgressBar * pProgress;
352 Fpga_Node_t * pNode;
353 int i, nNodes;
354
355 // assign the arrival times of the PIs
356 for ( i = 0; i < p->nInputs; i++ )
357 p->pInputs[i]->pCutBest->tArrival = p->pInputArrivals[i];
358
359 // match LUTs with nodes in the topological order
360 nNodes = p->vAnds->nSize;
361 pProgress = Extra_ProgressBarStart( stdout, nNodes );
362 for ( i = 0; i < nNodes; i++ )
363 {
364 pNode = p->vAnds->pArray[i];
365 if ( !Fpga_NodeIsAnd( pNode ) )
366 continue;
367 // skip a secondary node
368 if ( pNode->pRepr )
369 continue;
370 // match the node
371 Fpga_MatchNodeSwitch( p, pNode );
372 Extra_ProgressBarUpdate( pProgress, i, "Matches ..." );
373 }
374 Extra_ProgressBarStop( pProgress );
375 return 1;
376 }
377
378 /**Function*************************************************************
379
380 Synopsis [Computes the best matching for one node.]
381
382 Description []
383
384 SideEffects []
385
386 SeeAlso []
387
388 ***********************************************************************/
Fpga_MatchNodeSwitch(Fpga_Man_t * p,Fpga_Node_t * pNode)389 int Fpga_MatchNodeSwitch( Fpga_Man_t * p, Fpga_Node_t * pNode )
390 {
391 Fpga_Cut_t * pCut, * pCutBestOld;
392 float aAreaCutBest = FPGA_FLOAT_LARGE;
393 clock_t clk;
394 // make sure that at least one cut other than the trivial is present
395 if ( pNode->pCuts->pNext == NULL )
396 {
397 printf( "\nError: A node in the mapping graph does not have feasible cuts.\n" );
398 return 0;
399 }
400
401 // remember the old cut
402 pCutBestOld = pNode->pCutBest;
403 // deref the old cut
404 if ( pNode->nRefs )
405 aAreaCutBest = Fpga_CutDerefSwitch( p, pNode, pNode->pCutBest, 0 );
406
407 // search for a better cut
408 pNode->pCutBest = NULL;
409 for ( pCut = pNode->pCuts->pNext; pCut; pCut = pCut->pNext )
410 {
411 // compute the arrival time of the cut and its area flow
412 clk = clock();
413 pCut->tArrival = Fpga_TimeCutComputeArrival( p, pCut );
414 //p->time2 += clock() - clk;
415 // drop the cut if it does not meet the required times
416 if ( Fpga_FloatMoreThan( p, pCut->tArrival, pNode->tRequired ) )
417 continue;
418 // get the area of this cut
419 pCut->aFlow = Fpga_CutGetSwitchDerefed( p, pNode, pCut );
420 // if no cut is assigned, use the current one
421 if ( pNode->pCutBest == NULL )
422 {
423 pNode->pCutBest = pCut;
424 continue;
425 }
426 // choose the best cut as follows: exact area first, delay as a tie-breaker
427 if ( Fpga_FloatMoreThan(p, pNode->pCutBest->aFlow, pCut->aFlow) ||
428 (Fpga_FloatEqual(p, pNode->pCutBest->aFlow, pCut->aFlow) && Fpga_FloatMoreThan(p, pNode->pCutBest->tArrival, pCut->tArrival)) )
429 {
430 pNode->pCutBest = pCut;
431 }
432 }
433
434 // make sure the match is found
435 if ( pNode->pCutBest == NULL )
436 {
437 pNode->pCutBest = pCutBestOld;
438 // insert the new cut
439 if ( pNode->nRefs )
440 pNode->pCutBest->aFlow = Fpga_CutRefSwitch( p, pNode, pNode->pCutBest, 0 );
441 // printf( "\nError: Could not match a node in the object graph.\n" );
442 return 0;
443 }
444
445 // insert the new cut
446 // make sure the area selected is not worse then the original area
447 if ( pNode->nRefs )
448 {
449 pNode->pCutBest->aFlow = Fpga_CutRefSwitch( p, pNode, pNode->pCutBest, 0 );
450 assert( pNode->pCutBest->aFlow <= aAreaCutBest + 0.001 );
451 // assert( pNode->tRequired < FPGA_FLOAT_LARGE );
452 }
453 return 1;
454 }
455
456
457 #if 0
458 /**function*************************************************************
459
460 synopsis [References the cut.]
461
462 description [This procedure is similar to the procedure NodeReclaim.]
463
464 sideeffects []
465
466 seealso []
467
468 ***********************************************************************/
469 void Fpga_Experiment( Fpga_Man_t * p )
470 {
471 int Counter[10] = {0};
472 Fpga_Node_t * pNode;
473 int i;
474
475 for ( i = 0; i < p->nOutputs; i++ )
476 {
477 pNode = Fpga_Regular(p->pOutputs[i]);
478 pNode->vFanouts = NULL;
479 }
480
481 for ( i = 0; i < p->vAnds->nSize; i++ )
482 {
483 pNode = p->vAnds->pArray[i];
484 if ( !Fpga_NodeIsAnd( pNode ) )
485 continue;
486 if ( pNode->vFanouts == NULL )
487 continue;
488 if ( pNode->vFanouts->nSize >= 10 )
489 continue;
490 Counter[pNode->vFanouts->nSize]++;
491 }
492
493 printf( "Fanout stats: " );
494 for ( i = 0; i < 10; i++ )
495 printf( " %d=%d", i, Counter[i] );
496 printf( "\n" );
497 printf( "Area before = %4.2f.\n", Fpga_MappingArea(p) );
498
499 for ( i = 0; i < p->vAnds->nSize; i++ )
500 {
501 Fpga_NodeVec_t * vNodesTfo;
502 float AreaBefore;
503
504 pNode = p->vAnds->pArray[i];
505 if ( !Fpga_NodeIsAnd( pNode ) )
506 continue;
507 if ( pNode->vFanouts == NULL )
508 continue;
509 if ( pNode->vFanouts->nSize != 1 && pNode->vFanouts->nSize != 2 && pNode->vFanouts->nSize != 3 )
510 continue;
511
512 // assert( pNode->nRefs > 0 );
513 if ( pNode->nRefs == 0 )
514 continue;
515
516 AreaBefore = pNode->pCutBest->aFlow;
517 pNode->pCutBest->aFlow = FPGA_FLOAT_LARGE;
518
519 Fpga_TimeComputeRequiredGlobal( p, 0 );
520
521 vNodesTfo = Fpga_CollectNodeTfo( p, pNode );
522 if ( Fpga_MappingMatchesAreaArray( p, vNodesTfo ) == 0 )
523 printf( "attempt failed\n" );
524 else
525 printf( "attempt succeeded\n" );
526 Fpga_NodeVecFree( vNodesTfo );
527
528 pNode->pCutBest->aFlow = AreaBefore;
529 // break;
530 }
531 printf( "Area after = %4.2f.\n", Fpga_MappingArea(p) );
532 // printf( "AREA GAIN = %4.2f (%.2f %%)\n", GainTotal, 100.0 * GainTotal / Fpga_MappingArea(p) );
533 }
534
535
536
537 /**function*************************************************************
538
539 synopsis [References the cut.]
540
541 description [This procedure is similar to the procedure NodeReclaim.]
542
543 sideeffects []
544
545 seealso []
546
547 ***********************************************************************/
548 void Fpga_Experiment2( Fpga_Man_t * p )
549 {
550 int Counter[10] = {0};
551 Fpga_Cut_t * ppCutsNew[10];
552 Fpga_Cut_t * ppCutsOld[10];
553 Fpga_Node_t * pFanout, * pNode;
554 float Gain, Loss, GainTotal, Area1, Area2;
555 int i, k;
556
557 for ( i = 0; i < p->nOutputs; i++ )
558 {
559 pNode = Fpga_Regular(p->pOutputs[i]);
560 pNode->vFanouts = NULL;
561 }
562
563 for ( i = 0; i < p->vAnds->nSize; i++ )
564 {
565 pNode = p->vAnds->pArray[i];
566 if ( !Fpga_NodeIsAnd( pNode ) )
567 continue;
568 if ( pNode->vFanouts == NULL )
569 continue;
570 if ( pNode->vFanouts->nSize >= 10 )
571 continue;
572 Counter[pNode->vFanouts->nSize]++;
573 }
574
575 printf( "Fanout stats: " );
576 for ( i = 0; i < 10; i++ )
577 printf( " %d=%d", i, Counter[i] );
578 printf( "\n" );
579 printf( "Area before = %4.2f.\n", Fpga_MappingArea(p) );
580
581 GainTotal = 0;
582 for ( i = 0; i < p->vAnds->nSize; i++ )
583 {
584 pNode = p->vAnds->pArray[i];
585 if ( !Fpga_NodeIsAnd( pNode ) )
586 continue;
587 if ( pNode->vFanouts == NULL )
588 continue;
589 if ( pNode->vFanouts->nSize != 2 )//&& pNode->vFanouts->nSize != 2 && pNode->vFanouts->nSize != 3 )
590 continue;
591
592 assert( pNode->nRefs > 0 );
593
594 // for all fanouts, find the best cut without this node
595 for ( k = 0; k < pNode->vFanouts->nSize; k++ )
596 {
597 pFanout = pNode->vFanouts->pArray[k];
598 ppCutsOld[k] = pFanout->pCutBest;
599 ppCutsNew[k] = Fpga_MappingAreaWithoutNode( p, pFanout, pNode );
600 if ( ppCutsNew[k] == NULL )
601 break;
602 }
603 if ( k != pNode->vFanouts->nSize )
604 {
605 printf( "Node %4d: Skipped.\n", pNode->Num );
606 continue;
607 }
608
609
610 // compute the area after replacing all the cuts
611 Gain = 0;
612 for ( k = 0; k < pNode->vFanouts->nSize; k++ )
613 {
614 pFanout = pNode->vFanouts->pArray[k];
615 // deref old cut
616 Area1 = Fpga_MatchAreaDeref( p, ppCutsOld[k] );
617 // assign new cut
618 pFanout->pCutBest = ppCutsNew[k];
619 // ref new cut
620 Area2 = Fpga_MatchAreaRef( p, ppCutsNew[k] );
621 // compute the gain
622 Gain += Area1 - Area2;
623 }
624
625 printf( "%d ", pNode->nRefs );
626
627 // undo the whole thing
628 Loss = 0;
629 for ( k = 0; k < pNode->vFanouts->nSize; k++ )
630 {
631 pFanout = pNode->vFanouts->pArray[k];
632 // deref old cut
633 Area1 = Fpga_MatchAreaDeref( p, ppCutsNew[k] );
634 // assign new cut
635 pFanout->pCutBest = ppCutsOld[k];
636 // ref new cut
637 Area2 = Fpga_MatchAreaRef( p, ppCutsOld[k] );
638 // compute the gain
639 Loss += Area2 - Area1;
640 }
641 assert( Gain == Loss );
642
643
644 printf( "Node %4d: Fanouts = %d. Cut area = %4.2f. Gain = %4.2f.\n",
645 pNode->Num, pNode->nRefs, pNode->pCutBest->aFlow, Gain );
646
647 if ( Gain > 0 )
648 GainTotal += Gain;
649 }
650 printf( "Area after = %4.2f.\n", Fpga_MappingArea(p) );
651 printf( "AREA GAIN = %4.2f (%.2f %%)\n", GainTotal, 100.0 * GainTotal / Fpga_MappingArea(p) );
652 }
653
654
655 /**function*************************************************************
656
657 synopsis [Computes the loss of area when node is not allowed.]
658
659 description [Returning FPGA_FLOAT_LARGE means it does not exist.]
660
661 sideeffects []
662
663 seealso []
664
665 ***********************************************************************/
666 Fpga_Cut_t * Fpga_MappingAreaWithoutNode( Fpga_Man_t * p, Fpga_Node_t * pNode, Fpga_Node_t * pNodeNo )
667 {
668 Fpga_Cut_t * pCut, * pCutBestOld, * pCutRes;
669 float aAreaCutBest;
670 int i;
671 clock_t clk;
672 // make sure that at least one cut other than the trivial is present
673 if ( pNode->pCuts->pNext == NULL )
674 {
675 printf( "\nError: A node in the mapping graph does not have feasible cuts.\n" );
676 return 0;
677 }
678
679 assert( pNode->nRefs > 0 );
680
681 // remember the old cut
682 pCutBestOld = pNode->pCutBest;
683 // deref the old cut
684 aAreaCutBest = Fpga_MatchAreaDeref( p, pNode->pCutBest );
685
686 // search for a better cut
687 pNode->pCutBest = NULL;
688 for ( pCut = pNode->pCuts->pNext; pCut; pCut = pCut->pNext )
689 {
690 // compute the arrival time of the cut and its area flow
691 clk = clock();
692 Fpga_MatchCutGetArrTime( p, pCut );
693 //p->time2 += clock() - clk;
694 // drop the cut if it does not meet the required times
695 if ( pCut->tArrival > pNode->tRequired )
696 continue;
697
698 // skip the cut if it contains the no-node
699 for ( i = 0; i < pCut->nLeaves; i++ )
700 if ( pCut->ppLeaves[i] == pNodeNo )
701 break;
702 if ( i != pCut->nLeaves )
703 continue;
704
705 // get the area of this cut
706 pCut->aFlow = Fpga_MatchAreaCount( p, pCut );
707 // if no cut is assigned, use the current one
708 if ( pNode->pCutBest == NULL )
709 {
710 pNode->pCutBest = pCut;
711 continue;
712 }
713 // choose the best cut as follows: exact area first, delay as a tie-breaker
714 if ( pNode->pCutBest->aFlow > pCut->aFlow ||
715 pNode->pCutBest->aFlow == pCut->aFlow && pNode->pCutBest->tArrival > pCut->tArrival )
716 {
717 pNode->pCutBest = pCut;
718 }
719 }
720
721 // make sure the match is found
722 if ( pNode->pCutBest == NULL )
723 {
724 pNode->pCutBest = pCutBestOld;
725 // insert the new cut
726 pNode->pCutBest->aFlow = Fpga_MatchAreaRef( p, pNode->pCutBest );
727 return NULL;
728 }
729
730 pCutRes = pNode->pCutBest;
731 pNode->pCutBest = pCutBestOld;
732
733 // insert the new cut
734 pNode->pCutBest->aFlow = Fpga_MatchAreaRef( p, pNode->pCutBest );
735
736 // make sure the area selected is not worse then the original area
737 assert( pNode->pCutBest->aFlow == aAreaCutBest );
738 assert( pNode->tRequired < FPGA_FLOAT_LARGE );
739 return pCutRes;
740 }
741
742 #endif
743
744
745 /**function*************************************************************
746
747 synopsis [Performs area minimization using a heuristic algorithm.]
748
749 description []
750
751 sideeffects []
752
753 seealso []
754
755 ***********************************************************************/
Fpga_FindBestNode(Fpga_Man_t * p,Fpga_NodeVec_t * vNodes,Fpga_Node_t ** ppNode,Fpga_Cut_t ** ppCutBest)756 float Fpga_FindBestNode( Fpga_Man_t * p, Fpga_NodeVec_t * vNodes, Fpga_Node_t ** ppNode, Fpga_Cut_t ** ppCutBest )
757 {
758 Fpga_Node_t * pNode;
759 Fpga_Cut_t * pCut;
760 float Gain, CutArea1, CutArea2, CutArea3;
761 int i;
762
763 Gain = 0;
764 for ( i = 0; i < vNodes->nSize; i++ )
765 {
766 pNode = vNodes->pArray[i];
767 // deref the current cut
768 CutArea1 = Fpga_CutDeref( p, pNode, pNode->pCutBest, 0 );
769
770 // ref all the cuts
771 for ( pCut = pNode->pCuts->pNext; pCut; pCut = pCut->pNext )
772 {
773 if ( pCut == pNode->pCutBest )
774 continue;
775 if ( pCut->tArrival > pNode->tRequired )
776 continue;
777
778 CutArea2 = Fpga_CutGetAreaDerefed( p, pCut );
779 if ( Gain < CutArea1 - CutArea2 )
780 {
781 *ppNode = pNode;
782 *ppCutBest = pCut;
783 Gain = CutArea1 - CutArea2;
784 }
785 }
786 // ref the old cut
787 CutArea3 = Fpga_CutRef( p, pNode, pNode->pCutBest, 0 );
788 assert( CutArea1 == CutArea3 );
789 }
790 if ( Gain == 0 )
791 printf( "Returning no gain.\n" );
792
793 return Gain;
794 }
795
796 ////////////////////////////////////////////////////////////////////////
797 /// END OF FILE ///
798 ////////////////////////////////////////////////////////////////////////
799 ABC_NAMESPACE_IMPL_END
800
801