abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
fpgaMatch.c
Go to the documentation of this file.
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 ***********************************************************************/
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 ***********************************************************************/
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 ***********************************************************************/
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 ***********************************************************************/
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 ***********************************************************************/
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 ***********************************************************************/
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 ***********************************************************************/
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 ***********************************************************************/
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 
Fpga_MappingAreaWithoutNode
static Fpga_Cut_t * Fpga_MappingAreaWithoutNode(Fpga_Man_t *p, Fpga_Node_t *pFanout, Fpga_Node_t *pNodeNo)
Fpga_MatchNodeSwitch
static int Fpga_MatchNodeSwitch(Fpga_Man_t *p, Fpga_Node_t *pNode)
Definition: fpgaMatch.c:389
Fpga_CutRef
float Fpga_CutRef(Fpga_Man_t *pMan, Fpga_Node_t *pNode, Fpga_Cut_t *pCut, int fFanouts)
Definition: fpgaCutUtils.c:384
Fpga_ManStruct_t_::pInputArrivals
float * pInputArrivals
Definition: fpgaInt.h:118
Fpga_ManStruct_t_::pInputs
Fpga_Node_t ** pInputs
Definition: fpgaInt.h:104
Fpga_ManStruct_t_::nInputs
int nInputs
Definition: fpgaInt.h:105
Fpga_TimeComputeRequiredGlobal
void Fpga_TimeComputeRequiredGlobal(Fpga_Man_t *p, int fFirstTime)
Definition: fpgaTime.c:136
Fpga_MatchNodeArea
static int Fpga_MatchNodeArea(Fpga_Man_t *p, Fpga_Node_t *pNode)
Definition: fpgaMatch.c:268
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Fpga_MatchNode
static ABC_NAMESPACE_IMPL_START int Fpga_MatchNode(Fpga_Man_t *p, Fpga_Node_t *pNode, int fDelayOriented)
DECLARATIONS ///.
Definition: fpgaMatch.c:119
Fpga_FindBestNode
float Fpga_FindBestNode(Fpga_Man_t *p, Fpga_NodeVec_t *vNodes, Fpga_Node_t **ppNode, Fpga_Cut_t **ppCutBest)
Definition: fpgaMatch.c:756
Fpga_MappingMatchesAreaArray
static int Fpga_MappingMatchesAreaArray(Fpga_Man_t *p, Fpga_NodeVec_t *vNodes)
Definition: fpgaMatch.c:236
Fpga_CutGetParameters
void Fpga_CutGetParameters(Fpga_Man_t *pMan, Fpga_Cut_t *pCut)
Definition: fpgaCutUtils.c:279
Fpga_CutStruct_t_
Definition: fpgaInt.h:232
Fpga_CutStruct_t_::aFlow
float aFlow
Definition: fpgaInt.h:245
Fpga_ManStruct_t_::pOutputs
Fpga_Node_t ** pOutputs
Definition: fpgaInt.h:106
FPGA_FLOAT_LARGE
#define FPGA_FLOAT_LARGE
Definition: fpgaInt.h:65
Fpga_CutGetSwitchDerefed
float Fpga_CutGetSwitchDerefed(Fpga_Man_t *pMan, Fpga_Node_t *pNode, Fpga_Cut_t *pCut)
DECLARATIONS ///.
Definition: fpgaSwitch.c:43
Fpga_CutRefSwitch
float Fpga_CutRefSwitch(Fpga_Man_t *pMan, Fpga_Node_t *pNode, Fpga_Cut_t *pCut, int fFanouts)
Definition: fpgaSwitch.c:63
Fpga_MappingMatches
int Fpga_MappingMatches(Fpga_Man_t *p, int fDelayOriented)
FUNCTION DEFINITIONS ///.
Definition: fpgaMatch.c:67
Fpga_FloatEqual
static int Fpga_FloatEqual(Fpga_Man_t *p, float Arg1, float Arg2)
Definition: fpgaInt.h:283
Fpga_CutStruct_t_::tArrival
float tArrival
Definition: fpgaInt.h:244
Fpga_MappingMatchesSwitch
int Fpga_MappingMatchesSwitch(Fpga_Man_t *p)
Definition: fpgaMatch.c:349
Fpga_NodeStruct_t_::pCuts
Fpga_Cut_t * pCuts
Definition: fpgaInt.h:224
Fpga_NodeVecStruct_t_
Definition: fpgaInt.h:250
Fpga_CutStruct_t_::ppLeaves
Fpga_Node_t * ppLeaves[FPGA_MAX_LEAVES+1]
Definition: fpgaInt.h:237
ProgressBarStruct
DECLARATIONS ///.
Definition: extraUtilProgress.c:32
Fpga_MappingArea
float Fpga_MappingArea(Fpga_Man_t *pMan)
Definition: fpgaUtils.c:177
Fpga_NodeVecFree
void Fpga_NodeVecFree(Fpga_NodeVec_t *p)
Definition: fpgaVec.c:68
Fpga_NodeStruct_t_::pRepr
Fpga_Node_t * pRepr
Definition: fpgaInt.h:203
ABC_NAMESPACE_IMPL_END
#define ABC_NAMESPACE_IMPL_END
Definition: abc_global.h:108
Fpga_MappingMatchesArea
int Fpga_MappingMatchesArea(Fpga_Man_t *p)
Definition: fpgaMatch.c:196
Fpga_CollectNodeTfo
Fpga_NodeVec_t * Fpga_CollectNodeTfo(Fpga_Man_t *pMan, Fpga_Node_t *pNode)
Definition: fpgaUtils.c:675
Fpga_FloatMoreThan
static int Fpga_FloatMoreThan(Fpga_Man_t *p, float Arg1, float Arg2)
Definition: fpgaInt.h:281
Counter
static int Counter
Definition: extraBddMisc.c:1877
Extra_ProgressBarStop
void Extra_ProgressBarStop(ProgressBar *p)
Definition: extraUtilProgress.c:118
Fpga_CutGetAreaDerefed
float Fpga_CutGetAreaDerefed(Fpga_Man_t *pMan, Fpga_Cut_t *pCut)
Definition: fpgaCutUtils.c:362
ABC_NAMESPACE_IMPL_START
#define ABC_NAMESPACE_IMPL_START
Definition: abc_global.h:107
Fpga_ManStruct_t_::nOutputs
int nOutputs
Definition: fpgaInt.h:107
Fpga_NodeIsAnd
int Fpga_NodeIsAnd(Fpga_Node_t *p)
Definition: fpgaCreate.c:127
Fpga_NodeStruct_t_::nRefs
int nRefs
Definition: fpgaInt.h:188
Fpga_ManStruct_t_
STRUCTURE DEFINITIONS ///.
Definition: fpgaInt.h:99
Fpga_CutDeref
float Fpga_CutDeref(Fpga_Man_t *pMan, Fpga_Node_t *pNode, Fpga_Cut_t *pCut, int fFanouts)
Definition: fpgaCutUtils.c:421
Fpga_NodeStruct_t_::aEstFanouts
float aEstFanouts
Definition: fpgaInt.h:215
Fpga_Regular
#define Fpga_Regular(p)
Definition: fpga.h:58
Extra_ProgressBarStart
ProgressBar * Extra_ProgressBarStart(FILE *pFile, int nItemsTotal)
FUNCTION DEFINITIONS ///.
Definition: extraUtilProgress.c:62
Fpga_NodeStruct_t_::Num
int Num
Definition: fpgaInt.h:185
Fpga_TimeCutComputeArrival
float Fpga_TimeCutComputeArrival(Fpga_Man_t *pMan, Fpga_Cut_t *pCut)
DECLARATIONS ///.
Definition: fpgaTime.c:44
Fpga_CutStruct_t_::nLeaves
char nLeaves
Definition: fpgaInt.h:242
Fpga_NodeStruct_t_
Definition: fpgaInt.h:180
Fpga_NodeStruct_t_::tRequired
float tRequired
Definition: fpgaInt.h:214
assert
#define assert(ex)
Definition: util_old.h:213
Extra_ProgressBarUpdate
static void Extra_ProgressBarUpdate(ProgressBar *p, int nItemsCur, char *pString)
Definition: extra.h:243
Fpga_NodeVecStruct_t_::pArray
Fpga_Node_t ** pArray
Definition: fpgaInt.h:252
Fpga_NodeStruct_t_::pCutBest
Fpga_Cut_t * pCutBest
Definition: fpgaInt.h:222
Fpga_CutStruct_t_::pNext
Fpga_Cut_t * pNext
Definition: fpgaInt.h:246
Fpga_ManStruct_t_::vAnds
Fpga_NodeVec_t * vAnds
Definition: fpgaInt.h:112
Fpga_CutDerefSwitch
float Fpga_CutDerefSwitch(Fpga_Man_t *pMan, Fpga_Node_t *pNode, Fpga_Cut_t *pCut, int fFanouts)
Definition: fpgaSwitch.c:95
Fpga_NodeVecStruct_t_::nSize
int nSize
Definition: fpgaInt.h:253