source: vis_dev/vis-2.3/src/spfd/spfdCmd.c @ 36

Last change on this file since 36 was 14, checked in by cecile, 13 years ago

vis2.3
File size: 40.3 KB
Line 
1/**CFile***********************************************************************
2
3  FileName    [spfdCmd.c]
4
5  PackageName [spfd]
6
7  Synopsis [Interface functions for commands spfd_pilo and spfd_pdlo.]
8
9  Description [Interface functions for commands spfd_pilo and spfd_pdlo.]
10
11  SeeAlso     [spfdOpt.c]
12
13  Author      [Balakrishna Kumthekar]
14
15  Copyright [This file was created at the University of Colorado at Boulder.
16  The University of Colorado at Boulder makes no warranty about the suitability
17  of this software for any purpose.  It is presented on an AS IS basis.]
18
19******************************************************************************/
20
21#include "spfdInt.h"
22
23static char rcsid[] UNUSED = "$Id: spfdCmd.c,v 1.28 2002/09/09 01:04:28 fabio Exp $";
24
25/*---------------------------------------------------------------------------*/
26/* Constant declarations                                                     */
27/*---------------------------------------------------------------------------*/
28
29/*---------------------------------------------------------------------------*/
30/* Type declarations                                                         */
31/*---------------------------------------------------------------------------*/
32
33
34/*---------------------------------------------------------------------------*/
35/* Structure declarations                                                    */
36/*---------------------------------------------------------------------------*/
37
38
39/*---------------------------------------------------------------------------*/
40/* Variable declarations                                                     */
41/*---------------------------------------------------------------------------*/
42
43static jmp_buf timeOutEnv; /* time out */
44int spfdCreatedPart; /* Whether network BDDs were created in the package */
45int spfdVerbose; /* verbosity */
46float spfdAlpha; /* spfdAlpha * load + (1-spfdAlpha) * topDepth, is used to order
47                fanin nodes during SPFD computation */
48boolean spfdPerfSim; /* Perform simulation */
49boolean spfdNtkChanged; /* TRUE if network changes structurally or functionally */
50boolean spfdReprogNoWire; /* If TRUE, no functional changes are performed
51                         unless required by structural changes */
52int spfdWiresAdded, spfdNumWiresRem; /* Number of wires added and removed */
53int spfdSortNodes; /* Method to sort nodes */
54int spfdMethod; /* Optimization method */
55
56/*---------------------------------------------------------------------------*/
57/* Macro declarations                                                        */
58/*---------------------------------------------------------------------------*/
59
60
61/**AutomaticStart*************************************************************/
62
63/*---------------------------------------------------------------------------*/
64/* Static function prototypes                                                */
65/*---------------------------------------------------------------------------*/
66
67static int CommandSpfdNetworkOptimize(Hrc_Manager_t **hmgr, int argc, char **argv);
68static int CommandSpfdPlaceOptimize(Hrc_Manager_t **hmgr, int argc, char **argv);
69static void TimeOutHandle(void);
70static int TestIsNetworkMultipleValued(Ntk_Network_t *network);
71static int SpfdSimultaneousPlacementAndLogicOpt(Ntk_Network_t *network, char *netFile, char *archFile, char *placeFile, char *routeFile, char *netOutFile, int regionDepth);
72
73/**AutomaticEnd***************************************************************/
74
75
76/*---------------------------------------------------------------------------*/
77/* Definition of exported functions                                          */
78/*---------------------------------------------------------------------------*/
79
80/**Function********************************************************************
81
82  Synopsis    [This function initializes the spfd package.]
83
84  SideEffects [None]
85
86  SeeAlso     [Spfd_End]
87
88******************************************************************************/
89void
90Spfd_Init(void)
91{
92  Cmd_CommandAdd("spfd_pilo", CommandSpfdNetworkOptimize, 1);
93  Cmd_CommandAdd("spfd_pdlo", CommandSpfdPlaceOptimize, 1);
94
95} /* End of Spfd_Init */
96
97/**Function********************************************************************
98
99  Synopsis    [This function ends the spfd package.]
100
101  SideEffects [None]
102
103  SeeAlso     [Spfd_Init]
104
105******************************************************************************/
106void
107Spfd_End(void)
108{
109
110} /* End of Spfd_End */
111
112/*---------------------------------------------------------------------------*/
113/* Definition of internal functions                                          */
114/*---------------------------------------------------------------------------*/
115
116
117/*---------------------------------------------------------------------------*/
118/* Definition of static functions                                            */
119/*---------------------------------------------------------------------------*/
120/**Function********************************************************************
121
122   Synopsis [Implements SPFD-based placement independent logic
123   optimization command, spfd_pilo, for combinational circuits mapped
124   to LUT-based FPGAs.]
125
126   CommandName [spfd_pilo]
127
128   CommandSynopsis [Perform SPFD-based placement independent logic
129   optimization.]
130
131   CommandArguments [\[-a <\[0,1\]>\] \[-D <depth>\] \[-f
132   <file>\] \[-h\] \[-i <freq>\] \[-p <percent>\]
133   \[-r\] \[-S <n>\] \[-t <sec>\] \[-v <n>\]
134   \[-w <file>\] ]
135
136   CommandDescription [This command performs SPFD-based wire
137   removal/replacement and reprogramming of combinational circuits
138   mapped to LUT-based FPGAs to reduce the number of wires and nodes
139   in the circuit. The flexibilities in the circuit are represented by
140   SPFDs. The following references explain in detail the theory behind
141   SPFDs.
142
143   <p>S. Yamashita, H. Sawada, and A. Nagoya. A new method to express
144   functional permissibilities for LUT based FPGAs and its
145   applications. In International Conference on Computer Aided Design,
146   pages 254-261, 1996.
147
148   <p>Subarnarekha Sinha and Robert K. Brayton. Implementation and use of
149   SPFDs in optimizaing Boolean networks. In International Conference
150   on Computer Aided Design, 1998.
151
152   <p> Instead of computing the flexibilities for every node in the
153   network at once, the algorithm computes the flexibilities for one
154   cluster at a time. Working with clusters allows us to avoid the BDD
155   explosion problem and hence, handle large circuits. The SPFDs are
156   computed for the cluster and the cluster nodes are reprogrammed
157   based on the flexibility derived. Switching activity is used to
158   drive the choice of alternate function to be implemented at the
159   node. In the absence of switching activity information, the
160   function that can reduce support of the node can be chosen (not
161   implemented). Currently, an arbitrary choice is made from the
162   flexibilities provided by SPFDs. (-S 0, -S 2, and -S 4)
163
164   <p>
165   Before calling this command a network should be created for the
166   design (use flatten_hierarchy) and MDD ids for every node in the
167   network should be created (static_order -o all -n append, for
168   example). Dynamic variable ordering (dvo -e sift) can be enabled
169   to reduce BDD sizes.
170
171   <p>Command options:<p>
172
173   <dl>
174
175   <dt> -a &lt;alpha&gt;
176   <dd> A convex combination of switched
177   capacitance (switching activity * fanout count, SWC) and topological
178   depth is used to sort the fanin nodes during SPFD computation. alpha
179   is between 0 and 1.0. The cost function is alpha*SWC +
180   (1.0-alpha)*topDepth. The default value is 0.5. <p>
181
182   <dt> -D &lt;depth&gt;
183   <dd> A cluster is computed which includes nodes within the specified
184   'depth'. The default value is 1.<p>
185
186   <dt> -f &lt;file&gt;
187   <dd> File with simulation vectors.  The file
188   format is as below. The format is simple but strict and hence, few
189   checks are made.
190   <p> .i <code>c n d o e p f q g r h s i t j u k a l b m</code><br>
191    .s <br>
192    0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 ; <br>
193    0 1 1 0 0 0 0 1 0 1 1 0 1 1 1 1 0 0 0 0 1 ; <br>
194    0 0 1 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 1 ; <br>
195    0 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 0 1 0 0 1 ; <br>
196
197   <p>The .i statement specifies the primary inputs of the network. The
198   patterns start after .s key word. Each vector is a space separated list of
199   bits and ends in a semi-colon. The length of any vector should be equal
200   to the number of signals specified in the .i statement. A line starting
201   with # is a comment.  <p>
202
203   <dt> -h
204   <dd> Print usage. <p>
205
206   <dt> -i &lt;freq&gt;
207   <dd> Number of iterations after which to update node switching
208   activity. This is valid only if patterns are provided in a file
209   using -f option. The default value is every 5 iterations. <p>
210
211   <dt> -m &lt;n&gt;
212   <dd> Heuristics to optimize a selected node. <br>
213   <code>0</code>: Reduce the selected node's support. <br>
214   <code>1</code>: Reprogram the selected node.<br>
215   <code>2</code>: Reprogram the selected node's fanin nodes.
216   (default)<br>
217   <code>3</code>: Reduce the selected node's fanout wires. <p>
218   
219   <dt> -p &lt;percent&gt;
220   <dd> The percentage of vectors, specified via <code>-f</code>
221   option, used to perform simulation (to update switching activity)
222   during logic optimization. The default value is 10%. <p>
223
224   <dt> -r
225   <dd> Do not reprogram LUTs if no structural changes have been
226   performed with in the cluster, i.e., if no nodes or wires have been
227   removed do not change the local implementation of LUTs even if
228   alternate implementations are availabe from SPFD information. The
229   default is to reprogram. <p>
230
231   <dt> -S &lt;n&gt;
232   <dd> Method used to sort nodes. The nodes are then optimized in
233   that order.<br>
234   <code>0</code>: Random node is chosen. (default) <br>
235   <code>1</code>: If switching activity is available, node with
236   maximum SWC is chosen.  <br>
237   <code>2</code>: Node with maximum fanout is chosen. <br>
238   <code>3</code>: If switching activity is available, node with
239   minimum SWC is chosen. <br>
240   <code>4</code>: Node with minimum fanout is chosen. <p>
241
242   <dt> -t &lt;sec&gt;
243   <dd> Time in seconds allowed to complete the command. If the
244   computation time goes above that limit, the process is aborted.
245   The default is no limit.<p>
246   
247   <dt> -v &lt;n&gt;
248   <dd> Verbosity level. Default value is 0.<p>
249
250   <dt> -w &lt;file&gt;
251   <dd> File to output final optimized circuit. <p> ]
252   </dl>
253 
254   <p> <b>Relevant flags to be set by the set command:</b> <p>
255   <dl>
256   <dt> <b>spfd_repl_rem</b>
257   <dd> If <b>no</b>, the logic optimization performs only wire
258   removal. If <b>yes</b>, both wire replacement and removal are performed.
259   </dl>
260 
261   SideEffects [The network is changed to reflect the wires/nodes
262   removed or replaced. The internal function of the nodes is also
263   changed. The partition attached to the network is changed
264   accordingly.]
265
266******************************************************************************/
267static int
268CommandSpfdNetworkOptimize(
269  Hrc_Manager_t **hmgr,
270  int argc,
271  char **argv)
272{
273
274  Ntk_Network_t *network = NIL(Ntk_Network_t);
275  graph_t *simPart;
276  int status,percent,frequency,regionDepth;
277  int c;
278  long timeOutPeriod,initialTime,finalTime;
279  char *simFile,*writeFile;
280  char endPtr[128];
281  FILE *fp = NIL(FILE);
282 
283  /* These are the default values. */
284  spfdCreatedPart = 0; /* Do not create a new partition */
285  timeOutPeriod   = 0; 
286  simFile = NIL(char);  /* File containing simulation vectors */
287  spfdVerbose = 0; /* verbosity */
288  regionDepth = 1; /* Depth of cluster */
289  percent = 10; /* Percent of total vectors to be simulated during opt. */
290  frequency = 5; /* Perform simulation every frequency iterations */
291  spfdSortNodes = RANDOM; /* Choose a random node for optimization */
292  spfdMethod = 2;
293  spfdAlpha = 0.5; 
294  writeFile = NIL(char); /* File to output final optimized ckt. */
295  spfdNtkChanged = FALSE; 
296  spfdReprogNoWire = TRUE;
297  spfdWiresAdded = 0;
298  spfdNumWiresRem = 0;
299  spfdPerfSim = FALSE; /* Default */
300 
301  if (bdd_get_package_name() != CUDD) {
302    (void) fprintf(vis_stderr,
303                   "** spfd error: The spfd package can be used "
304                   "only with CUDD package\n");
305    (void) fprintf(vis_stderr,
306                   "** spfd error: Please link with CUDD package\n");
307    return 0;
308  }
309       
310  util_getopt_reset();
311
312  while((c = util_getopt(argc, argv, "a:D:f:hi:m:p:rS:t:v:w:")) != EOF) {
313    switch(c) {
314    case 'a':
315      spfdAlpha = (float) strtod(util_optarg,(char **)&endPtr);
316      if (!strcmp(util_optarg,endPtr)) {
317        (void) fprintf(vis_stdout,
318                       "** spfd warning: Invalid value <%s> specified for -a\n",
319                       util_optarg);
320        (void) fprintf(vis_stdout,"** spfd warning: Assuming 0.5.\n");
321        spfdAlpha = 0.5;
322      } else if (spfdAlpha > 1.0 || spfdAlpha < 0.0) {
323        (void) fprintf(vis_stdout,
324                       "** spfd warning: Value for -a <%f> not in [0,1]\n",
325                       spfdAlpha);
326        (void) fprintf(vis_stdout,"** spfd warning: Assuming 0.5.\n");
327        spfdAlpha = 0.5;
328      }
329      break;
330    case 'D':
331      regionDepth = atoi(util_optarg);
332      break;
333    case 'f': 
334      if (!util_optarg) {
335        (void) fprintf(vis_stderr,
336                       "** spfd error: Simulation file not specified.\n");
337        goto usage;
338      } else {
339        simFile = util_strsav(util_optarg);
340        if ((fp = Cmd_FileOpen(simFile,"r",NIL(char *),1)) == NIL(FILE)) {
341          (void) fprintf(vis_stderr,
342                         "** spfd error: Could not open %s for reading.\n",
343                         simFile);
344          goto endgame;
345        } else {
346          fclose(fp);
347        }
348        spfdPerfSim = TRUE;
349      }
350      break;
351    case 'h':
352      goto usage;
353    case 'i':
354      frequency = atoi(util_optarg);
355      break;
356    case 'm':
357      spfdMethod = atoi(util_optarg);
358      if (spfdMethod > 3 || spfdMethod < 0) {
359        (void) fprintf(vis_stderr, "** spfd warning: -m has invalid argument\n");
360        (void) fprintf(vis_stderr, "** spfd warning: Using 2 instead.\n");
361      }
362      break;
363    case 'p':
364      percent = atoi(util_optarg);
365      if (percent > 100 || percent < 0) {
366        (void) fprintf(vis_stderr,
367                       "** spfd warning: -p <%d> has invalid argument.\n",
368                       percent);
369        (void) fprintf(vis_stderr,
370                       "** spfd warning: Using 10%% instead.\n");
371      }
372      break;
373    case 'r':
374      spfdReprogNoWire = FALSE;
375      break;
376    case 'S':
377      spfdSortNodes = atoi(util_optarg);
378      if (spfdSortNodes > 4 || spfdSortNodes < 0) {
379        (void) fprintf(vis_stderr,
380                       "** spfd warning: -S <%d> has invalid argument.\n",
381                       spfdSortNodes);
382        (void) fprintf(vis_stderr,
383                       "** spfd warning: Using 0 (random) instead.\n");
384      }
385      break;
386    case 't':
387      timeOutPeriod = atoi(util_optarg);
388      break;
389    case 'v':
390      spfdVerbose = atoi(util_optarg);
391      break;
392    case 'w':
393      writeFile = util_strsav(util_optarg);
394      if ((fp = Cmd_FileOpen(writeFile,"w",NIL(char *),1)) == NIL(FILE)) {
395        (void) fprintf(vis_stderr,
396                       "** spfd error: Could not open %s for writing.\n",
397                       writeFile);
398        goto endgame;
399      } else {
400        fclose(fp);
401      }
402      break;
403    default:
404      goto usage;
405    }
406  }
407
408  if(Hrc_ManagerReadCurrentNode(*hmgr) == NIL(Hrc_Node_t)) {
409    (void) fprintf(vis_stderr,"** spfd error: The hierarchy manager is empty."
410                   " Read in design.\n");
411    goto endgame;
412  }
413
414  network = (Ntk_Network_t *) 
415    Hrc_NodeReadApplInfo(Hrc_ManagerReadCurrentNode(*hmgr), 
416                         NTK_HRC_NODE_APPL_KEY);
417
418  if(network == NIL(Ntk_Network_t)) {
419    (void) fprintf(vis_stderr,"** spfd error: There is no network. ");
420    (void) fprintf(vis_stderr,"Use flatten_hierarchy.\n");
421    goto endgame;
422  }
423   
424  /* Check if the current network has signals with multiple values. */
425  if (TestIsNetworkMultipleValued(network)) {
426    (void) fprintf(vis_stderr,"** spfd error: Circuit has multiple "
427                   "valued variables.\n");
428    (void) fprintf(vis_stderr,"** spfd error: The algorithm currently "
429                   "supports only Boolean valued variables.\n");
430    goto endgame;
431  }
432
433  if(Ntk_NetworkReadNumPrimaryInputs(network) !=
434     Ntk_NetworkReadNumInputs(network)) {
435    (void) fprintf(vis_stderr,"** spfd error: Pseudo inputs present "
436                   "in the network.\n");
437    (void) fprintf(vis_stderr,"** spfd error: The algorithm does not apply.\n");
438    goto endgame;
439  }
440
441  if(Ntk_NetworkReadNumLatches(network) > 0) {
442    (void) fprintf(vis_stderr,"** spfd error: Sequential circuit.\n");
443    (void) fprintf(vis_stderr,"** spfd error: The command is only for combinational circuits.\n");
444    goto endgame;
445  }
446 
447  /* Access a 'total' partition */
448  simPart = (graph_t *) Ntk_NetworkReadApplInfo(network,PART_NETWORK_APPL_KEY);
449  if (simPart == NIL(graph_t) || 
450      (Part_PartitionReadMethod(simPart) != Part_Total_c)) {
451    simPart = Part_NetworkCreatePartition(network, 
452                                          NIL(Hrc_Node_t),
453                                          "dummy", (lsList) 0, 
454                                          (lsList) 0, NIL(mdd_t),
455                                          Part_Total_c,
456                                          (lsList) 0, 
457                                          FALSE, FALSE, TRUE);
458    if (simPart == NIL(graph_t)) {
459      (void) fprintf(vis_stderr,"** spfd error: Could not create partition.\n");
460      goto endgame;
461    }
462    Ntk_NetworkAddApplInfo(network,PART_NETWORK_APPL_KEY,
463                           (Ntk_ApplInfoFreeFn)Part_PartitionFreeCallback,
464                           (void *)simPart);
465    spfdCreatedPart = 1; /* Using new partition */
466    (void) fprintf(vis_stdout,
467                   "** spfd info: A new partition created.\n");
468  }
469
470  /* Start the timer.*/
471  if (timeOutPeriod > 0){
472    (void) signal(SIGALRM, (void(*)(int))TimeOutHandle);
473    (void) alarm(timeOutPeriod);
474    if (setjmp(timeOutEnv) > 0) {
475      (void) fprintf(vis_stderr, "** spfd warning: Timeout occurred after ");
476      (void) fprintf(vis_stderr, "%ld seconds.\n", timeOutPeriod);
477      alarm(0);
478      goto endgame;
479    }
480  }
481
482  initialTime = util_cpu_time();
483
484  if (!spfdPerfSim) {
485    (void) fprintf(vis_stdout,
486                   "** spfd info: Simulation vectors not specified.\n");
487    if (spfdSortNodes == MAXSWCAP) {
488      (void) fprintf(vis_stdout,
489                     "** spfd info: Using method -S 2 instead of -S 1\n");
490      spfdSortNodes = MAXFANOUT;
491    } else if (spfdSortNodes == MINSWCAP) {
492      (void) fprintf(vis_stdout,
493                     "** spfd info: Using method -S 4 instead of -S 3\n");     
494      spfdSortNodes = MINFANOUT;
495    }
496  }
497  status = SpfdNetworkOptimize(network,simFile,percent,frequency,regionDepth);
498
499  finalTime = util_cpu_time();
500  if(status) {
501    (void) fprintf(vis_stdout, "%-20s%10ld\n", "** spfd info: analysis time =",
502                   (finalTime-initialTime)/1000);
503  }
504  else {
505    (void) fprintf(vis_stdout, "** spfd error: Optimization failed.\n");
506  }
507
508  if (writeFile) {
509    SpfdNetworkWriteBlifFile(network,writeFile);
510    FREE(writeFile);
511  }
512
513  if (simFile)
514    FREE(simFile);
515
516  if (spfdCreatedPart)
517    Ntk_NetworkFreeApplInfo(network,PART_NETWORK_APPL_KEY);
518 
519  alarm(0);
520  return 0;  /* normal exit */
521
522endgame:
523  /* Clean up */
524  if (simFile)
525    FREE(simFile);
526
527  if (writeFile)
528    FREE(writeFile);
529
530  if (spfdCreatedPart)
531    Ntk_NetworkFreeApplInfo(network,PART_NETWORK_APPL_KEY);
532 
533  return 1; /* Error exit */
534
535usage:
536
537  (void) fprintf(vis_stderr, "\nusage: Also see \'help spfd_pilo\' for more details.\n\n");
538  (void) fprintf(vis_stderr, "    -a <alpha>\t\t<alpha> should be between 0.0 and 1.0\n");
539  (void) fprintf(vis_stderr, "             \t\talpha*(SA*numFanout) + (1.0-alpha)*top_depth is used\n");
540  (void) fprintf(vis_stderr, "             \t\tto order nodes during SPFD computation.\n");
541  (void) fprintf(vis_stderr, "             \t\tSA is the switching activity of the node.\n");
542  (void) fprintf(vis_stderr, "             \t\tThe default value is 0.5.\n\n");
543  (void) fprintf(vis_stderr, "    -D <depth>\t\tCollect nodes that are within the specified depth.\n");
544  (void) fprintf(vis_stderr, "            \t\tfrom the node being optimized.\n");
545  (void) fprintf(vis_stderr, "            \t\tThe default is 1.\n\n");
546  (void) fprintf(vis_stderr, "    -f <filename>\tFile containing simulation vectors.\n");
547  (void) fprintf(vis_stderr, "               \t\tSee help for the format.\n\n"); 
548  (void) fprintf(vis_stderr, "    -h      \t\tCommand usage.\n\n");
549  (void) fprintf(vis_stderr, "    -i <freq> \t\tPerform internal simulations after \n");
550  (void) fprintf(vis_stderr, "            \t\tevery <freq> iterations.\n");
551  (void) fprintf(vis_stderr, "            \t\tDefault is 5.\n\n");
552  (void) fprintf(vis_stderr, "    -m <n> \t\tHeuristics to optimize a selected node:\n");
553  (void) fprintf(vis_stderr, "           \t\t0: Reduce the selected node's support.\n");
554  (void) fprintf(vis_stderr, "           \t\t1: Reprogram the selected node.\n");
555  (void) fprintf(vis_stderr, "           \t\t2: Reprogram the selected node's fanin nodes. (default)\n");
556  (void) fprintf(vis_stderr, "           \t\t3: Reduce the selected node's fanout wires.\n\n");
557  (void) fprintf(vis_stderr, "    -p <percent>\tPercent of total pattern vectors that\n");
558  (void) fprintf(vis_stderr, "            \t\tshould be used during internal simulations.\n");
559  (void) fprintf(vis_stderr, "            \t\tDefault is 10%%.\n\n");
560  (void) fprintf(vis_stderr, "    -r      \t\tDo not reprogram internal nodes if the network\n");
561  (void) fprintf(vis_stderr, "            \t\thas not changed structurally.\n");
562  (void) fprintf(vis_stderr, "            \t\tBy default, reprogram.\n\n");
563  (void) fprintf(vis_stderr, "    -S <value> \t\tHeuristic to select nodes for optimization.\n");
564  (void) fprintf(vis_stderr, "            \t\t0. Random node. (default) \n");
565  (void) fprintf(vis_stderr, "            \t\t1. Node with max. SA*numFanout.\n");
566  (void) fprintf(vis_stderr, "            \t\t2. Node with max. fanout.\n");
567  (void) fprintf(vis_stderr, "            \t\t3. Node with min. SA*numFanout.\n");
568  (void) fprintf(vis_stderr, "            \t\t4. Node with min. fanout.\n\n");
569  (void) fprintf(vis_stderr, "    -t <N>  \t\tTime (s) limit for the command.\n\n");
570  (void) fprintf(vis_stderr, "    -v <N>  \t\tVerbosity level.\n\n"); 
571  (void) fprintf(vis_stderr, "    -w <filename>\tFile to output final optimized circuit.\n\n");
572  (void) fprintf(vis_stderr, "set options: \n");
573  (void) fprintf(vis_stderr, "\tspfd_repl_rem <yes|no>\n");
574  (void) fprintf(vis_stderr, "\t\tReplace and remove wires simultaneously?\n");
575  return 1;    /* error exit */
576
577} /* End of CommandSpfdNetworkOptimize */
578
579
580/**Function********************************************************************
581
582   Synopsis [Implements SPFD-based simultaneous placement and logic
583   optimization command, spfd_pdlo, for combinational circuits mapped
584   to LUT-based FPGAs.]
585
586   CommandName [spfd_pdlo]
587
588   CommandSynopsis [Perform SPFD-based simultaneous placement and
589   logic optimization.]
590
591   CommandArguments [\[-D &lt;depth&gt;\] \[-h\] \[-n &lt;file&gt;\]
592   \[-r\] \[-t &lt;sec&gt;\] \[-v &lt;n&gt;\] \[-w &lt;file&gt;\]
593   net_file arch_file place_file route_file]
594
595   CommandDescription [This command performs SPFD-based combined logic
596   and placement optimization of combinational circuits mapped to
597   LUT-based FPGAs to improve circuit area and speed. The
598   flexibilities in the circuit are represented by SPFDs. The
599   following references explain in detail the theory behind SPFDs.
600
601   <p>S. Yamashita, H. Sawada, and A. Nagoya. A new method to express
602   functional permissibilities for LUT based FPGAs and its
603   applications. In International Conference on Computer Aided Design,
604   pages 254-261, 1996.
605
606   <p>Subarnarekha Sinha and Robert K. Brayton. Implementation and use of
607   SPFDs in optimizaing Boolean networks. In International Conference
608   on Computer Aided Design, 1998.
609
610   <p>The command implements a technique that tightly links the logic
611   and placement optimization steps. The algorithm is based on
612   simulated annealing. Two types of moves, directed towards global
613   reduction in the cost function (total wire length), are accepted by
614   the simulated annealing algorithm: (1) wire removal/replacement,
615   and (2) swapping of a pair of blocks in the FPGA. Feedback from
616   placement is valuable in making an informed choice of a target wire
617   during logic optimization moves. The logic optimization steps
618   performed are similar to those of spfd_pilo, except that the
619   placement information is now used instead of the fanout count.
620   More information on this technique can be found in :
621
622   <p>Balakrishna Kumthekar and Fabio Somenzi. Power and delay reduction
623   via simultaneous logic and placement optimization in FPGAs.  In Design,
624   Automation and Test in Europe, 2000.
625
626   <p>The command produces a placement file which is used by VPR for
627   routing.
628 
629   <p>This command can be used only if VIS is linked with VPR 4.22
630   (Versatile Place and Route), the FPGA place and route tool <a
631   href="http://www.eecg.toronto.edu/~vaughn/vpr/vpr.html"> VPR</a>,
632   from the University of Toronto.  Please follow the instructions
633   provided in the release notes to use VPR with VIS.  You can also
634   contact kumtheka@avanticorp.com if you need more help.
635
636   <p>Before calling this command a network should be created for the
637   design (use flatten_hierarchy) and MDD ids for every node in the
638   network should be created (static_order -o all -n append). Dynamic
639   variable ordering (dvo -e sift) can be enabled to reduce BDD sizes.
640   
641   <p>Command options:<p>
642
643   <dl>
644
645   <dt> -D &lt;depth&gt;
646   <dd> A cluster is computed which includes nodes within the specified
647   'depth'. The default value is 1.<p>
648
649   <dt> -n &lt;file&gt;
650   <dd> File to output the optimized circuit in VPR's .net format.<p>
651
652   <dt> -r
653   <dd> Do not reprogram LUTs if no structural changes have been
654   performed with in the cluster, i.e., if no nodes or wires have been
655   removed do not change the local implementation of LUTs even if
656   alternate implementations are availabe from SPFD information. The
657   default is to reprogram. <p>
658
659   <dt> -t &lt;sec&gt;
660   <dd> Time in seconds allowed to complete the command. If the
661   computation time goes above that limit, the process is is aborted.
662   The default is no limit.<p>
663   
664   <dt> -v &lt;n&gt;
665   <dd> Verbosity level.<p>
666
667   <dt> -w &lt;file&gt;
668   <dd> File to output final optimized circuit. <p>
669   </dl>
670 
671   <p> <b>The following is needed by VPR:</b> <p>
672   <dl>
673   <dt> <b>net_file</b>
674   <dd> The description of the circuit in the .net format. Logic
675   optimization uses the circuit described in .BLIF format whereas VPR
676   needs the same circuit described in .net format. VPack (which comes
677   with VPR) converts a .BLIF format into a .net format. <p>
678
679   <dt> <b>arch_file</b>
680   <dd> Architecture description file for FPGAs. More information can be
681   found in VPR's manual. <p>
682
683   <dt> <b>place_file</b>
684   <dd> File to dump placement information. <p>
685
686   <dt> <b>route_file</b>
687   <dd> File to dump routing information. <p>
688
689   <p> <b>Relevant flags to be set by the set command:</b> <p>
690   <dl>
691   <dt> <b>spfd_pdlo_logic_move_freq</b> "r1 m1 r2 m2 ..."
692   <dd> Perform m1 logic moves whenever the rate of acceptance during
693   simulated annealing is greater than or equal to r1, and so on. r1,
694   r2, r3 ... should be monotonically decreasing, else the results would
695   be unpredictable. 0 <= ri <= 1.0. For example:
696
697   <p> <code>set spfd_pdlo_logic_move_freq "0.8 0 0.5 5 0.2 10"</code><p>
698
699   In the above logic schedule, zero logic moves per temperature will
700   be performed when the rate of acceptance is above 0.8, 5 logic
701   moves between 0.8 and 0.5, 10 moves between 0.5 and 0.2. As no
702   value is specified for acceptance rate close to 0.0, by default, 1
703   logic move per temperature will be performed. In this example it
704   will be 1 logic move between 0.2 and 0.0.
705   The quotes around the schedule are necessary.<p>
706
707   <dt> <b>spfd_repl_rem</b>
708   <dd> If <b>no</b>, the logic optimization performs only wire
709   removal. If <b>yes</b>, both wire replacement and removal are performed. <p>
710
711   <dt> <b>spfd_pdlo_timing</b>
712   <dd> If set, use timing driven method to remove or replace wires on the
713   critical path. If not set, use bounding box of the wires as the
714   cost function.<p>
715
716   <dt> <b>spfd_pdlo_timing_nodeorwire</b>
717   <dd> Remove/replace all the wires belonging to the most critical
718   net. If not set, attempt to remove/replace only the most critical
719   wire. <p>
720
721   <dt> <b>spfd_pdlo_out_crit_nets_first</b>
722   <dd> Output the circuit in VPR's .net format with the nets
723   appearing in the increasing order of their slack. If not set, the
724   initial net order specified in the original circuit's .net file is
725   used. The file is specified with <code>-n</code> option. This
726   variable is valid only if <b>spfd_pdlo_timing</b> is set. <p>
727
728   <dt> <b>spfd_pdlo_remap_clb_array</b>
729   <dd> During logic optimization, due to the removal of nodes in the
730   network, the current size of FPGA might be bigger than it is
731   necessary. In such cases, if this variable is set, the size of the
732   FPGA is reduced to fit the current logic network. <p>
733
734   </dl>
735
736   <p> <b>Relevant flags that are options to VPR:</b>
737   <p> For detailed information on the following options please refer to
738   the manual that accompanies VPR source distribution.
739   <p>
740   <dl>
741   <dt><b> vpr_nodisp</b>
742   <dt><b>vpr_fix_pins</b>
743   <dt><b>vpr_nx</b>
744   <dt><b>vpr_ny</b>
745   <dt><b>vpr_fast</b>
746   <dt><b>vpr_init_t</b>
747   <dt><b>vpr_alpha_t</b>
748   <dt><b>vpr_exit_t</b>
749   <dt><b>vpr_inner_num</b>
750   <dt><b>vpr_seet</b>
751   <dt><b>vpr_place_cost_exp</b>
752   <dt><b>vpr_place_chan_width</b>
753   </dl> ]
754
755   SideEffects [The network is changed to reflect the wires/nodes
756   removed or replaced. The internal function of the nodes is also
757   changed. The partition attached to the network is changed
758   accordingly.]
759   
760******************************************************************************/
761static int
762CommandSpfdPlaceOptimize(
763  Hrc_Manager_t **hmgr,
764  int argc,
765  char **argv)
766{
767
768#ifndef USE_VPR
769  (void) fprintf(vis_stdout,"** spfd info: This command requires VPR "
770                 "(Versatile Place and Route)\n");
771  (void) fprintf(vis_stdout,"** spfd info: See \'help spfd_pdlo\' for more "
772                 "information\n");
773  (void) fprintf(vis_stdout,"** spfd info: on how to compile VIS with VPR.\n");
774  (void) fprintf(vis_stdout,"** spfd info: Exiting calmly ...\n");
775  return 0;
776#else
777 
778  Ntk_Network_t *network;
779  graph_t *simPart;
780  int status,regionDepth;
781  int c;
782  long timeOutPeriod,initialTime,finalTime;
783  char *writeFile;
784  char *netFile,*archFile,*placeFile,*routeFile;
785  char *netOutFile;
786  FILE *fp = NIL(FILE);
787
788
789  /* These are the default values. */
790  spfdCreatedPart = 0; /* Do not create a new partition */
791  timeOutPeriod   = 0; 
792  spfdVerbose = 0; /* verbosity */
793  regionDepth = 1; /* Depth of cluster */
794  writeFile = NIL(char); /* File to output final optimized ckt. */
795  spfdNtkChanged = FALSE;
796  spfdReprogNoWire = TRUE;
797  netFile = archFile = NIL(char); /* Circuit specified in VPR's .net
798                                     format and FPGA architecture file */
799  placeFile = routeFile = NIL(char); /* File to store placement and
800                                        routing information */
801  spfdWiresAdded = 0;
802  spfdNumWiresRem = 0;
803  netOutFile = NIL(char); /* File to output the optimized circuit in
804                             .net format */
805  status = FALSE;
806 
807  if (bdd_get_package_name() != CUDD) {
808    (void) fprintf(vis_stderr,
809                   "** spfd error: The spfd package can be used "
810                   "only with CUDD package\n");
811    (void) fprintf(vis_stderr,
812                   "** spfd error: Please link with CUDD package\n");
813    return 0;
814  }
815
816  util_getopt_reset();
817  while((c = util_getopt(argc, argv, "D:hn:rt:v:w:")) != EOF) {
818    switch(c) {
819    case 'D':
820      regionDepth = atoi(util_optarg);
821      break;
822    case 'h':
823      goto usage;
824    case 'n':
825      netOutFile = util_strsav(util_optarg);
826      break;     
827    case 'r':
828      spfdReprogNoWire = FALSE;
829      break;
830    case 't':
831      timeOutPeriod = atoi(util_optarg);
832      break;
833    case 'v':
834      spfdVerbose = atoi(util_optarg);
835      break;
836    case 'w':
837      writeFile = util_strsav(util_optarg);
838      if ((fp = Cmd_FileOpen(writeFile,"w",NIL(char *),1)) == NIL(FILE)) {
839        (void) fprintf(vis_stderr,
840                       "** spfd error: Could not open %s for writing.\n",
841                       writeFile);
842        goto endgame;
843      } else {
844        fclose(fp);
845      }
846      break;
847    default:
848      goto usage;
849    }
850  }
851
852  /* netFile, archFile, and placeFile are essential. The user can
853     specify /dev/null for routeFile if they don't want to store the
854     routing information */
855  if (argc < 5 || argc < util_optind+4)
856    goto usage;
857
858  /* Get the net, architecture, place and route file names */
859  netFile = argv[util_optind];
860  archFile = argv[util_optind+1];
861  placeFile = argv[util_optind+2];
862  routeFile = argv[util_optind+3];
863
864  if(Hrc_ManagerReadCurrentNode(*hmgr) == NIL(Hrc_Node_t)) {
865    (void) fprintf(vis_stderr,"** spfd error: The hierarchy manager is empty. "
866                   "Read in design.\n");
867    goto endgame;
868  }
869
870  network = (Ntk_Network_t *) 
871    Hrc_NodeReadApplInfo(Hrc_ManagerReadCurrentNode(*hmgr), 
872                         NTK_HRC_NODE_APPL_KEY);
873
874  if(network == NIL(Ntk_Network_t)) {
875    (void) fprintf(vis_stderr,"** spfd error: There is no network. ");
876    (void) fprintf(vis_stderr,"Use flatten_hierarchy.\n");
877    goto endgame;
878  }
879
880  /* Check if the current network has signals with multiple values. */
881  if (TestIsNetworkMultipleValued(network)) {
882    (void) fprintf(vis_stderr,"** spfd error: Circuit has multiple "
883                   "valued variables.\n");
884    (void) fprintf(vis_stderr,"** spfd error: The algorithm applies "
885                   "to Boolean variables only.\n");
886    goto endgame;
887  }
888
889  if(Ntk_NetworkReadNumPrimaryInputs(network) !=
890     Ntk_NetworkReadNumInputs(network)) {
891    (void) fprintf(vis_stderr,"** spfd error: Pseudo inputs present "
892                   "in the network.\n");
893    (void) fprintf(vis_stderr,"** spfd error: The algorithm does not apply.\n");
894    goto endgame;
895  }
896
897  /* Access a 'total' partition */
898  simPart = (graph_t *) Ntk_NetworkReadApplInfo(network, 
899                                                PART_NETWORK_APPL_KEY);
900  if (simPart == NIL(graph_t) || 
901      (Part_PartitionReadMethod(simPart) != Part_Total_c)) {
902    simPart = Part_NetworkCreatePartition(network, 
903                                          NIL(Hrc_Node_t),
904                                          "dummy", (lsList) 0, 
905                                          (lsList) 0, NIL(mdd_t),
906                                          Part_Total_c,
907                                          (lsList) 0, 
908                                          FALSE, FALSE, TRUE);
909    if (simPart == NIL(graph_t)) {
910      (void) fprintf(vis_stderr,"** spfd error: Could not create partition.\n");
911      goto endgame;
912    }
913    Ntk_NetworkAddApplInfo(network,PART_NETWORK_APPL_KEY,
914                           (Ntk_ApplInfoFreeFn)Part_PartitionFreeCallback,
915                           (void *)simPart);
916    spfdCreatedPart = 1; /* Using new partition */
917    (void) fprintf(vis_stdout,
918                   "** spfd info: A new partition created.\n");
919  }
920
921  /* Start the timer.*/
922  if (timeOutPeriod > 0){
923    (void) signal(SIGALRM, (void(*)(int))TimeOutHandle);
924    (void) alarm(timeOutPeriod);
925    if (setjmp(timeOutEnv) > 0) {
926      (void) fprintf(vis_stderr, "** spfd warning: Timeout occurred after ");
927      (void) fprintf(vis_stderr, "%ld seconds.\n", timeOutPeriod);
928      alarm(0);
929      goto endgame;
930    }
931  }
932
933  initialTime = util_cpu_time();
934
935  /* Call the optimization routine. */
936  status = SpfdSimultaneousPlacementAndLogicOpt(network,netFile,archFile,
937                                                placeFile,routeFile,netOutFile,
938                                                regionDepth);
939 
940  finalTime = util_cpu_time();
941  if(status) {
942    (void) fprintf(vis_stdout, "%-20s%10ld\n", "** spfd info: analysis time =",
943                   (finalTime-initialTime)/1000);
944  }
945  else {
946    (void) fprintf(vis_stdout, "** spfd error: Optimization failed.\n");
947  }
948
949  if (writeFile) {
950    SpfdNetworkWriteBlifFile(network,writeFile);
951    FREE(writeFile);
952  }
953
954  if (netOutFile) {
955    FREE(netOutFile);
956  }
957
958  if (spfdCreatedPart)
959    Ntk_NetworkFreeApplInfo(network,PART_NETWORK_APPL_KEY);
960 
961  alarm(0);
962  return 0;  /* normal exit */
963
964endgame:
965  /* Clean up */
966  if (writeFile)
967    FREE(writeFile);
968
969  if (netOutFile) {
970    FREE(netOutFile);
971  }
972 
973  if (spfdCreatedPart)
974    Ntk_NetworkFreeApplInfo(network,PART_NETWORK_APPL_KEY);
975 
976  return 1; /* Error exit */
977
978usage:
979
980  (void) fprintf(vis_stderr, "\nusage: Also see \'help spfd_pdlo\' for more details.\n\n");
981  (void) fprintf(vis_stderr, "spfd_pdlo [options] net_file arch_file place_file route_file\n\n");
982  (void) fprintf(vis_stderr, "    -D <depth>\t\tConsider region upto <depth>.\n\n");
983  (void) fprintf(vis_stderr, "    -h      \t\tCommand usage.\n\n");
984  (void) fprintf(vis_stderr, "    -n <filename>\tFile to output optimized\n");
985  (void) fprintf(vis_stderr, "            \t\tcircuit in .net format.\n\n");
986  (void) fprintf(vis_stderr, "    -r      \t\tDo not reprogram internal nodes if there are no\n");
987  (void) fprintf(vis_stderr, "            \t\tstructural changes in the network.\n\n");
988  (void) fprintf(vis_stderr, "    -t <N>  \t\tTime (s) limit for the command.\n\n"); 
989  (void) fprintf(vis_stderr, "    -v <N>  \t\tVerbosity level.\n\n");
990  (void) fprintf(vis_stderr, "    -w <filename>\tFile to output final optimized circuit.\n\n");
991  (void) fprintf(vis_stderr, "set options: \n");
992  (void) fprintf(vis_stderr, "\tspfd_pdlo_logic_move_freq \"r1 m1 r2 m2 ...\"\n");
993  (void) fprintf(vis_stderr, "\t\tPerform m1 logic moves per temperature whenever the rate\n");
994  (void) fprintf(vis_stderr, "\t\tof acceptance during simulated annealing is greater than\n");
995  (void) fprintf(vis_stderr, "\t\tor equal to r1, and so on. r1 > r2 > r3 ... \n");
996  (void) fprintf(vis_stderr, "\t\tand 0 <= ri <= 1.0.\n\n");
997  (void) fprintf(vis_stderr, "\tspfd_repl_rem <yes|no>\n");
998  (void) fprintf(vis_stderr, "\t\tPerform both wire replacement and removal?\n\n");
999  (void) fprintf(vis_stderr, "\tspfd_pdlo_timing\n");
1000  (void) fprintf(vis_stderr, "\t\tUse timing driven method.\n");
1001  (void) fprintf(vis_stderr, "\t\tIf not set, Bounding box method is used.\n\n");
1002  (void) fprintf(vis_stderr, "\tspfd_pdlo_timing_nodeorwire\n");
1003  (void) fprintf(vis_stderr, "\t\tProcess the fanouts of the most tcritical node. If not set,\n");
1004  (void) fprintf(vis_stderr, "\t\tprocess only the wires on the critical path.\n\n");
1005  (void) fprintf(vis_stderr, "\tspfd_pdlo_out_crit_nets_first\n");
1006  (void) fprintf(vis_stderr, "\t\tOutput the circuit in VPR\'s .net format with\n");
1007  (void) fprintf(vis_stderr, "\t\tnets appearing in the increasing order of their slack.\n");
1008  (void) fprintf(vis_stderr, "\t\tIf not set, the initial net order specified in the original\n");
1009  (void) fprintf(vis_stderr, "\t\tcircuit\'s .net file is used. The file specified in -n option\n");
1010  (void) fprintf(vis_stderr, "\t\tis used. This option is valid only if spfd_pdlo_timing is set.\n\n");
1011  (void) fprintf(vis_stderr, "\tspfd_pdlo_remap_clb_array\n");
1012  (void) fprintf(vis_stderr, "\t\tReduce the size of FPGA if necessary during\n");
1013  (void) fprintf(vis_stderr, "\t\tlogic optimization.\n\n");
1014  (void) fprintf(vis_stderr, "set options for VPR: Please see VPR's manual for more information.\n");
1015  (void) fprintf(vis_stderr, "    vpr_nodisp\n");
1016  (void) fprintf(vis_stderr, "    vpr_fix_pins\n");
1017  (void) fprintf(vis_stderr, "    vpr_nx\n");
1018  (void) fprintf(vis_stderr, "    vpr_ny\n");
1019  (void) fprintf(vis_stderr, "    vpr_fast\n");
1020  (void) fprintf(vis_stderr, "    vpr_init_t\n");
1021  (void) fprintf(vis_stderr, "    vpr_alpha_t \n");
1022  (void) fprintf(vis_stderr, "    vpr_exit_t\n");
1023  (void) fprintf(vis_stderr, "    vpr_inner_num\n");
1024  (void) fprintf(vis_stderr, "    vpr_seed\n");
1025  (void) fprintf(vis_stderr, "    vpr_place_cost_exp\n");
1026  (void) fprintf(vis_stderr, "    vpr_place_chan_width\n");
1027  return 1;    /* error exit */
1028#endif /* ifdef USE_VPR */
1029
1030} /* End of CommandSpfdPlaceOptimize */
1031
1032
1033/**Function********************************************************************
1034
1035  Synopsis    [Handle function for timeout.]
1036
1037  Description [This function is called when the time out occurs.]
1038
1039  SideEffects []
1040
1041******************************************************************************/
1042static void
1043TimeOutHandle(void)
1044{
1045  longjmp(timeOutEnv, 1);
1046}
1047
1048/**Function********************************************************************
1049
1050  Synopsis    [Checks whether the network has multiple valued signals.]
1051
1052  Description [Checks whether the network has multiple valued
1053  signals. Returns 1 if true, else 0.]
1054
1055  SideEffects [None]
1056
1057  SeeAlso []
1058
1059******************************************************************************/
1060static int
1061TestIsNetworkMultipleValued(Ntk_Network_t *network)
1062{
1063  Ntk_Node_t *node;
1064  lsGen gen;
1065  Var_Variable_t *var;
1066  int numValues;
1067
1068  Ntk_NetworkForEachNode(network,gen,node) {
1069    var = Ntk_NodeReadVariable(node);
1070    numValues = Var_VariableReadNumValues(var);
1071    if (numValues > 2)
1072      return 1;
1073  }
1074  return 0;
1075}
1076
1077#ifndef USE_VPR
1078/**Function********************************************************************
1079 
1080  Synopsis [Dummy function]
1081
1082  SideEffects [None]
1083
1084******************************************************************************/
1085static int 
1086SpfdSimultaneousPlacementAndLogicOpt(
1087  Ntk_Network_t *network,
1088  char *netFile,
1089  char *archFile,
1090  char *placeFile,
1091  char *routeFile,
1092  char *netOutFile,
1093  int regionDepth)
1094{
1095  return 0;
1096}
1097#endif
Note: See TracBrowser for help on using the repository browser.