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