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

Last change on this file since 82 was 14, checked in by cecile, 15 years ago

vis2.3
File size: 40.3 KB
RevLine 
[14]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.