1 /*
2 * ExtTimes.c --
3 *
4 * Circuit extraction timing.
5 *
6 * *********************************************************************
7 * * Copyright (C) 1985, 1990 Regents of the University of California. *
8 * * Permission to use, copy, modify, and distribute this *
9 * * software and its documentation for any purpose and without *
10 * * fee is hereby granted, provided that the above copyright *
11 * * notice appear in all copies. The University of California *
12 * * makes no representations about the suitability of this *
13 * * software for any purpose. It is provided "as is" without *
14 * * express or implied warranty. Export of this software outside *
15 * * of the United States of America may require an export license. *
16 * *********************************************************************
17 */
18
19 #ifndef lint
20 static char rcsid[] __attribute__ ((unused)) = "$Header: /usr/cvsroot/magic-8.0/extract/ExtTimes.c,v 1.2 2009/05/13 15:03:16 tim Exp $";
21 #endif /* not lint */
22
23 #include <stdio.h>
24 #include <string.h>
25 #include <sys/types.h>
26 #include <sys/time.h>
27 #include <sys/resource.h>
28 #ifdef SYSV
29 #include <sys/param.h>
30 #include <sys/times.h>
31 #endif
32 #include <math.h> /* for sqrt() function */
33
34 #include "utils/magic.h"
35 #include "utils/utils.h"
36 #include "utils/geometry.h"
37 #include "utils/geofast.h"
38 #include "tiles/tile.h"
39 #include "utils/hash.h"
40 #include "database/database.h"
41 #include "utils/malloc.h"
42 #include "textio/textio.h"
43 #include "extract/extract.h"
44 #include "extract/extractInt.h"
45
46 /*
47 * One of the following structures gets allocated for each cell.
48 * It holds the statistics we accumulate while extracting that cell.
49 */
50 struct cellStats
51 {
52 CellDef *cs_def; /* Which cell */
53 struct timeval cs_tpaint; /* Paint-only extraction time */
54 struct timeval cs_tcell; /* Extract just this cell */
55 struct timeval cs_thier; /* Extract complete tree */
56 struct timeval cs_tincr; /* Incremental extraction time */
57 int cs_fets; /* Transistor count in this cell */
58 int cs_rects; /* Non-space tile count in this cell */
59 int cs_hfets; /* Hierarchical transistor count */
60 int cs_hrects; /* Hierarchical tile count */
61 int cs_ffets; /* Total flat transistor count */
62 int cs_frects; /* Total flat tile count */
63 long cs_area; /* Total area of cell */
64 long cs_interarea; /* Interaction areas sum */
65 long cs_cliparea; /* Interaction area, counting each
66 * overlap of interaction areas only
67 * once instead of once for each
68 * interaction area.
69 */
70 };
71
72 /* Hash table of all the above structs, keyed by CellDef */
73 HashTable cellStatsTable;
74
75 /*
76 * Cumulative statistics
77 */
78 struct cumStats
79 {
80 double cums_min; /* Smallest value */
81 double cums_max; /* Largest value */
82 double cums_sum; /* Sum of values */
83 double cums_sos; /* Sum of squares */
84 int cums_n; /* Number values */
85 };
86
87 struct cumStats cumFetsPerSecPaint;
88 struct cumStats cumRectsPerSecPaint;
89 struct cumStats cumFetsPerSecFlat;
90 struct cumStats cumRectsPerSecFlat;
91 struct cumStats cumFetsPerSecHier;
92 struct cumStats cumRectsPerSecHier;
93 struct cumStats cumIncrTime;
94 struct cumStats cumPercentClipped;
95 struct cumStats cumPercentInteraction;
96 struct cumStats cumTotalArea, cumInteractArea, cumClippedArea;
97
98 FILE *extDevNull = NULL;
99
100 /* Forward declarations */
101
102 struct cellStats *extGetStats();
103 void extTimesCellFunc();
104 void extTimesIncrFunc();
105 void extTimesSummaryFunc();
106 void extTimesParentFunc();
107 void extTimeProc();
108 void extCumInit();
109 void extCumOutput();
110 void extCumAdd();
111 void extPaintOnly(CellDef *);
112 void extHierCell(CellDef *);
113 int extCountTiles();
114
115 extern int extDefInitFunc();
116
117
118 /*
119 * ----------------------------------------------------------------------------
120 *
121 * ExtTimes --
122 *
123 * Time the extractor.
124 * All cells in the tree rooted at 'rootUse' are extracted.
125 * We report the following times for each cell (seconds of CPU
126 * time, accurate to 10 milliseconds).
127 *
128 * Time to extract just its paint.
129 * Time to extract it completely.
130 * Time to perform incremental re-extraction if just this cell changed.
131 *
132 * In addition, we report:
133 *
134 * Fets/second paint extraction speed
135 * Fets/second cell extraction speed
136 * Fets/second hierarchical extraction speed
137 * Rects/second paint extraction speed
138 * Rects/second cell extraction speed
139 * Rects/second hierarchical extraction speed
140 *
141 * Also for each cell, we report the number of transistors, number
142 * of rectangles, and rectangles per transistor.
143 *
144 * In addition, we report the following cumulative information, as
145 * means, standard deviation, min, and max:
146 *
147 * Fets/second flat extraction speed
148 * Fets/second complete extraction speed
149 * Rects/second flat extraction speed
150 * Rects/second complete extraction speed
151 * Incremental extraction time after changing one cell.
152 *
153 * Results:
154 * None.
155 *
156 * Side effects:
157 * Writes to the file 'f'.
158 *
159 * ----------------------------------------------------------------------------
160 */
161
162 void
ExtTimes(rootUse,f)163 ExtTimes(rootUse, f)
164 CellUse *rootUse;
165 FILE *f;
166 {
167 double clip, inter;
168 HashSearch hs;
169 HashEntry *he;
170
171 /* Make sure this cell is read in */
172 if (DBCellReadArea(rootUse, &rootUse->cu_def->cd_bbox, TRUE))
173 {
174 TxError("Failure to read entire subtree of cell.\n");
175 return;
176 }
177
178 /* Initialize cumulative statistics */
179 extCumInit(&cumFetsPerSecPaint);
180 extCumInit(&cumRectsPerSecPaint);
181 extCumInit(&cumFetsPerSecFlat);
182 extCumInit(&cumRectsPerSecFlat);
183 extCumInit(&cumFetsPerSecHier);
184 extCumInit(&cumRectsPerSecHier);
185 extCumInit(&cumIncrTime);
186 extCumInit(&cumPercentClipped);
187 extCumInit(&cumPercentInteraction);
188 extCumInit(&cumTotalArea);
189 extCumInit(&cumInteractArea);
190 extCumInit(&cumClippedArea);
191
192 /* Open to /dev/null */
193 extDevNull = fopen("/dev/null", "w");
194 if (extDevNull == NULL)
195 {
196 perror("/dev/null");
197 return;
198 }
199
200 /* Mark all defs as unvisited */
201 (void) DBCellSrDefs(0, extDefInitFunc, (ClientData) 0);
202
203 /* Recursively visit all defs in the tree and store in hash table */
204 HashInit(&cellStatsTable, 128, 1);
205 (void) extTimesInitFunc(rootUse);
206
207 /*
208 * Now visit every cell in the hash table and compute
209 * its individual statistics.
210 */
211 TxPrintf("Computing individual cell statistics:\n"); TxFlush();
212 HashStartSearch(&hs);
213 while (he = HashNext(&cellStatsTable, &hs))
214 extTimesCellFunc((struct cellStats *) HashGetValue(he));
215
216 /*
217 * Now visit every cell in the hash table and compute
218 * its incremental time (ancestors) and hierarchical
219 * time (children).
220 */
221 TxPrintf("Computing hierarchical and incremental statistics:\n"); TxFlush();
222 HashStartSearch(&hs);
223 while (he = HashNext(&cellStatsTable, &hs))
224 extTimesIncrFunc((struct cellStats *) HashGetValue(he));
225
226 /*
227 * Compute the summary statistics and output everything.
228 * Free each entry in the table as we go.
229 */
230 TxPrintf("Computing summary statistics:\n"); TxFlush();
231 HashStartSearch(&hs);
232 while (he = HashNext(&cellStatsTable, &hs))
233 {
234 extTimesSummaryFunc((struct cellStats *) HashGetValue(he), f);
235 freeMagic((char *) HashGetValue(he));
236 }
237
238 /* Output the summary statistics */
239 fprintf(f, "\n\nSummary statistics:\n\n");
240 fprintf(f, "%s %8s %8s %8s %8s\n",
241 " ", "min", "max", "mean", "std.dev");
242 extCumOutput("fets/sec paint ", &cumFetsPerSecPaint, f);
243 extCumOutput("fets/sec hier ", &cumFetsPerSecHier, f);
244 extCumOutput("fets/sec flat ", &cumFetsPerSecFlat, f);
245 extCumOutput("rects/sec paint", &cumRectsPerSecPaint, f);
246 extCumOutput("rects/sec hier ", &cumRectsPerSecHier, f);
247 extCumOutput("rects/sec flat ", &cumRectsPerSecFlat, f);
248 extCumOutput("tot incr time ", &cumIncrTime, f);
249 extCumOutput("% cell clipped ", &cumPercentClipped, f);
250 extCumOutput("% cell interact", &cumPercentInteraction, f);
251
252 /* Fix up average value to be weighted */
253 clip = inter = 0.0;
254 if (cumTotalArea.cums_sum > 0)
255 {
256 clip = 100.0 * cumClippedArea.cums_sum / cumTotalArea.cums_sum;
257 inter = 100.0 * cumInteractArea.cums_sum / cumTotalArea.cums_sum;
258 }
259 fprintf(f, "Mean %% clipped area = %.2f\n", clip);
260 fprintf(f, "Mean %% interaction area = %.2f\n", inter);
261
262 /* Free the hash table */
263 HashKill(&cellStatsTable);
264
265 (void) fclose(extDevNull);
266 }
267
268 /*
269 * ----------------------------------------------------------------------------
270 *
271 * extTimesInitFunc --
272 *
273 * Called to add the cellStats struct for use->cu_def to the hash table
274 * cellStatsTable if it is not already present, and to initialize this
275 * structure.
276 *
277 * Results:
278 * Returns 0 always.
279 *
280 * Side effects:
281 * See above.
282 *
283 * ----------------------------------------------------------------------------
284 */
285
286 int
extTimesInitFunc(use)287 extTimesInitFunc(use)
288 CellUse *use;
289 {
290 CellDef *def = use->cu_def;
291 struct cellStats *cs;
292 HashEntry *he;
293
294 he = HashFind(&cellStatsTable, (char *) def);
295 if (HashGetValue(he))
296 return (0);
297
298 /* Not yet visited: add it to the hash table */
299 cs = (struct cellStats *) mallocMagic(sizeof (struct cellStats));
300 cs->cs_def = def;
301 cs->cs_tpaint.tv_sec = cs->cs_tpaint.tv_usec = 0;
302 cs->cs_tcell.tv_sec = cs->cs_tcell.tv_usec = 0;
303 cs->cs_thier.tv_sec = cs->cs_thier.tv_usec = 0;
304 cs->cs_tincr.tv_sec = cs->cs_tincr.tv_usec = 0;
305 cs->cs_fets = cs->cs_rects = 0;
306 cs->cs_ffets = cs->cs_frects = 0;
307 cs->cs_hfets = cs->cs_hrects = 0;
308 cs->cs_area = cs->cs_interarea = cs->cs_cliparea = 0;
309 HashSetValue(he, (ClientData) cs);
310
311 /* Visit our children */
312 (void) DBCellEnum(def, extTimesInitFunc, (ClientData) 0);
313 return (0);
314 }
315
316 /*
317 * ----------------------------------------------------------------------------
318 *
319 * extTimesCellFunc --
320 *
321 * Called for each cellStats structure in the hash table, we extract
322 * the paint of cs->cs_def and then both the paint and subcells, timing
323 * both. Also count the number of fets in this cell and the total number
324 * of tiles. Store this information in:
325 *
326 * cs->cs_tpaint Time to extract paint only
327 * cs->cs_tcell Time to extract paint and subcells
328 * cs->cs_fets Number of fets
329 * cs->cs_rects Number of non-space tiles
330 *
331 * Results:
332 * None.
333 *
334 * Side effects:
335 * See above.
336 *
337 * ----------------------------------------------------------------------------
338 */
339
340 void
extTimesCellFunc(cs)341 extTimesCellFunc(cs)
342 struct cellStats *cs;
343 {
344 extern long extSubtreeTotalArea;
345 extern long extSubtreeInteractionArea;
346 extern long extSubtreeClippedArea;
347 TransRegion *transList, *tl;
348 CellDef *def = cs->cs_def;
349 int pNum;
350
351 TxPrintf("Processing %s\n", def->cd_name); TxFlush();
352
353 /* Count the number of transistors */
354 transList = (TransRegion *) ExtFindRegions(def, &TiPlaneRect,
355 &ExtCurStyle->exts_deviceMask, ExtCurStyle->exts_deviceConn,
356 extUnInit, extTransFirst, extTransEach);
357 ExtResetTiles(def, extUnInit);
358 for (tl = transList; tl; tl = tl->treg_next)
359 cs->cs_fets++;
360 ExtFreeLabRegions((LabRegion *) transList);
361
362 /* Count the number of tiles */
363 for (pNum = PL_TECHDEPBASE; pNum < DBNumPlanes; pNum++)
364 (void) DBSrPaintArea((Tile *) NULL, def->cd_planes[pNum], &TiPlaneRect,
365 &DBAllButSpaceBits, extCountTiles, (ClientData) cs);
366
367 /* Measure the flat extraction time */
368 extTimeProc(extPaintOnly, def, &cs->cs_tpaint);
369
370 /* Measure the total extraction time */
371 extSubtreeTotalArea = 0;
372 extSubtreeInteractionArea = 0;
373 extSubtreeClippedArea = 0;
374 extTimeProc(extHierCell, def, &cs->cs_tcell);
375 cs->cs_area = extSubtreeTotalArea;
376 cs->cs_interarea = extSubtreeInteractionArea;
377 cs->cs_cliparea = extSubtreeClippedArea;
378 }
379
380 /*
381 * extCountTiles --
382 *
383 * Count the number of tiles in a cell.
384 * Called via DBSrPaintArea by extTimesCellFunc() above.
385 *
386 * Results:
387 * Returns 0 always.
388 *
389 * Side effects:
390 * Increments cs->cs_rects.
391 */
392
393 int
extCountTiles(tile,cs)394 extCountTiles(tile, cs)
395 Tile *tile; /* UNUSED */
396 struct cellStats *cs;
397 {
398 cs->cs_rects++;
399 return (0);
400 }
401
402 /*
403 * ----------------------------------------------------------------------------
404 *
405 * extTimesIncrFunc --
406 *
407 * All cells have been visited by extTimesCellFunc above. This procedure
408 * accumulates the hierarchical information from both above and below
409 * in the tree. The cs_tcell times for all ancestors, plus this cell,
410 * are summed into cs->cs_tincr. The cs_tcell times for all children,
411 * counting each child once, are summed into cs->cs_thier. The cs_fets
412 * and cs_rects for all children, also counting each child once, are
413 * summed into cs_hfets and cs_hrects. Finally, the cs_fets and cs_rects
414 * for all children, counting each child as many times as it appears,
415 * are summed into cs_ffets and cs_frects.
416 *
417 * Results:
418 * None.
419 *
420 * Side effects:
421 * See above.
422 *
423 * ----------------------------------------------------------------------------
424 */
425
426 void
extTimesIncrFunc(cs)427 extTimesIncrFunc(cs)
428 struct cellStats *cs;
429 {
430 /*
431 * Visit all of our parents recursively.
432 * This sums the incremental times.
433 */
434 extTimesParentFunc(cs->cs_def, cs);
435
436 /* Reset all defs */
437 (void) DBCellSrDefs(0, extDefInitFunc, (ClientData) 0);
438
439 /*
440 * Visit all of our children recursively, visiting
441 * each child only once. This sums the number of fets
442 * and rectangles for cs_hfets and cs_hrects.
443 */
444 (void) extTimesHierFunc(cs->cs_def, cs);
445
446 /* Reset all defs */
447 (void) DBCellSrDefs(0, extDefInitFunc, (ClientData) 0);
448
449 /*
450 * Visit all of our children recursively, visiting each
451 * child as many times as it appears. This sums the
452 * number of fets and rectangles as cs_ffets and cs_frects.
453 */
454 (void) extTimesFlatFunc(cs->cs_def, cs);
455 }
456
457 /*
458 * ----------------------------------------------------------------------------
459 *
460 * extTimesSummaryFunc --
461 *
462 * Write the statistics contained in the cellStats structure 'cs'
463 * out to the FILE 'f'. Add them to the summary structures being
464 * maintained (cumFetsPerSecPaint, etc).
465 *
466 * Results:
467 * None.
468 *
469 * Side effects:
470 * Writes to the FILE f.
471 *
472 * ----------------------------------------------------------------------------
473 */
474
475 void
extTimesSummaryFunc(cs,f)476 extTimesSummaryFunc(cs, f)
477 struct cellStats *cs;
478 FILE *f;
479 {
480 double tpaint, tcell, thier, tincr;
481 double fetspaint, rectspaint;
482 double fetshier, rectshier;
483 double fetsflat, rectsflat;
484 double pctinter, pctclip;
485
486 pctinter = pctclip = 0.0;
487 if (cs->cs_area > 0)
488 {
489 pctinter = ((double)cs->cs_interarea) / ((double)cs->cs_area) * 100.0;
490 pctclip = ((double)cs->cs_cliparea) / ((double)cs->cs_area) * 100.0;
491 }
492
493 tpaint = cs->cs_tpaint.tv_usec;
494 tpaint = (tpaint / 1000000.) + cs->cs_tpaint.tv_sec;
495
496 tcell = cs->cs_tcell.tv_usec;
497 tcell = (tcell / 1000000.) + cs->cs_tcell.tv_sec;
498
499 thier = cs->cs_thier.tv_usec;
500 thier = (thier / 1000000.) + cs->cs_thier.tv_sec;
501
502 tincr = cs->cs_tincr.tv_usec;
503 tincr = (tincr / 1000000.) + cs->cs_tincr.tv_sec;
504
505 fetspaint = fetsflat = fetshier = 0.0;
506 rectspaint = rectsflat = rectshier = 0.0;
507
508 if (tpaint > 0.01)
509 {
510 fetspaint = cs->cs_fets / tpaint;
511 rectspaint = cs->cs_rects / tpaint;
512 }
513
514 if (thier > 0.01)
515 {
516 fetshier = cs->cs_hfets / thier;
517 rectshier = cs->cs_hrects / thier;
518 fetsflat = cs->cs_ffets / thier;
519 rectsflat = cs->cs_frects / thier;
520 }
521
522 /* Cell name */
523 fprintf(f, "\n%8s %8s %s\n", "", "", cs->cs_def->cd_name);
524
525 /* Sizes */
526 fprintf(f, "%8d %8d (paint) fets rects\n",
527 cs->cs_fets, cs->cs_rects);
528 fprintf(f, "%8d %8d (hier) fets rects\n",
529 cs->cs_hfets, cs->cs_hrects);
530 fprintf(f, "%8d %8d (flat) fets rects\n",
531 cs->cs_ffets, cs->cs_frects);
532
533 /* Times */
534 fprintf(f, "%8.2f %8.2f Tpaint, Tcell\n", tpaint, tcell);
535 fprintf(f, "%8.2f %8.2f Thier, Tincr\n", thier, tincr);
536
537 /* Speeds */
538 fprintf(f, "%8.2f %8.2f (paint) fets/sec rects/sec\n",
539 fetspaint, rectspaint);
540 fprintf(f, "%8.2f %8.2f (hier) fets/sec rects/sec\n",
541 fetshier, rectshier);
542 fprintf(f, "%8.2f %8.2f (flat) fets/sec rects/sec\n",
543 fetsflat, rectsflat);
544
545 /* Fraction of area in subtree processing */
546 fprintf(f, "%8.2f %8.2f clip %% inter %%\n",
547 pctclip, pctinter);
548
549 /* Accumulate statistics */
550 if (cs->cs_fets > 0) extCumAdd(&cumFetsPerSecPaint, fetspaint);
551 if (cs->cs_rects > 0) extCumAdd(&cumRectsPerSecPaint, rectspaint);
552 if (cs->cs_hfets > 0) extCumAdd(&cumFetsPerSecHier, fetshier);
553 if (cs->cs_hrects > 0) extCumAdd(&cumRectsPerSecHier, rectshier);
554 if (cs->cs_ffets > 0) extCumAdd(&cumFetsPerSecFlat, fetsflat);
555 if (cs->cs_frects > 0) extCumAdd(&cumRectsPerSecFlat, rectsflat);
556 if (pctclip > 0.0) extCumAdd(&cumPercentClipped, pctclip);
557 if (pctinter > 0.0) extCumAdd(&cumPercentInteraction, pctinter);
558 extCumAdd(&cumTotalArea, (double) cs->cs_area);
559 extCumAdd(&cumInteractArea, (double) cs->cs_interarea);
560 extCumAdd(&cumClippedArea, (double) cs->cs_cliparea);
561 extCumAdd(&cumIncrTime, tincr);
562 }
563
564 /*
565 * ----------------------------------------------------------------------------
566 *
567 * extTimesParentFunc --
568 *
569 * Function to visit all the parents of 'def' and add their
570 * times to that of 'cs'. We only add the times if the def
571 * being visited is unmarked, ie, its cd_client field is 0.
572 * After adding the times for a def, we mark it by setting
573 * its cd_client field to 1.
574 *
575 * Results:
576 * None.
577 *
578 * Side effects:
579 * See above.
580 *
581 * ----------------------------------------------------------------------------
582 */
583
584 void
extTimesParentFunc(def,cs)585 extTimesParentFunc(def, cs)
586 CellDef *def;
587 struct cellStats *cs;
588 {
589 struct cellStats *csForDef;
590 CellUse *parent;
591
592 if (def->cd_client)
593 return;
594
595 /* Mark this def as visited */
596 def->cd_client = (ClientData) 1;
597
598 /* Find its statistics in the table */
599 if ((csForDef = extGetStats(def)) == NULL)
600 return;
601
602 /* Add the time */
603 cs->cs_tincr.tv_sec += csForDef->cs_tcell.tv_sec;
604 cs->cs_tincr.tv_usec += csForDef->cs_tcell.tv_usec;
605 if (cs->cs_tincr.tv_usec > 1000000)
606 {
607 cs->cs_tincr.tv_usec -= 1000000;
608 cs->cs_tincr.tv_sec += 1;
609 }
610
611 /* Visit all our parents */
612 for (parent = def->cd_parents; parent; parent = parent->cu_nextuse)
613 if (parent->cu_parent)
614 extTimesParentFunc(parent->cu_parent, cs);
615 }
616
617 /*
618 * ----------------------------------------------------------------------------
619 *
620 * extTimesHierFunc --
621 *
622 * Function to visit all the children of 'def' and add their
623 * times to that of 'cs'. We only add the times if the def
624 * being visited is unmarked, ie, its cd_client field is 0.
625 * After adding the times for a def, we mark it by setting
626 * its cd_client field to 1.
627 *
628 * Results:
629 * Returns 0 always.
630 *
631 * Side effects:
632 * See above.
633 *
634 * ----------------------------------------------------------------------------
635 */
636
637 int
extTimesHierFunc(def,cs)638 extTimesHierFunc(def, cs)
639 CellDef *def;
640 struct cellStats *cs;
641 {
642 int extTimesHierUse();
643 struct cellStats *csForDef;
644
645 if (def->cd_client)
646 return (0);
647
648 /* Mark this def as visited */
649 def->cd_client = (ClientData) 1;
650
651 /* Find its statistics in the table */
652 if ((csForDef = extGetStats(def)) == NULL)
653 return (0);
654
655 /* Add the time */
656 cs->cs_thier.tv_sec += csForDef->cs_tcell.tv_sec;
657 cs->cs_thier.tv_usec += csForDef->cs_tcell.tv_usec;
658 if (cs->cs_thier.tv_usec > 1000000)
659 {
660 cs->cs_thier.tv_usec -= 1000000;
661 cs->cs_thier.tv_sec += 1;
662 }
663
664 /* Add the fets and rectangles */
665 cs->cs_hfets += csForDef->cs_fets;
666 cs->cs_hrects += csForDef->cs_rects;
667
668 /* Visit our children */
669 (void) DBCellEnum(def, extTimesHierUse, (ClientData) cs);
670 return (0);
671 }
672
673 int
extTimesHierUse(use,cs)674 extTimesHierUse(use, cs)
675 CellUse *use;
676 struct cellStats *cs;
677 {
678 return (extTimesHierFunc(use->cu_def, cs));
679 }
680
681 /*
682 * ----------------------------------------------------------------------------
683 *
684 * extTimesFlatFunc --
685 *
686 * Function to visit all the children of 'def' and add their
687 * fet and rect counts to those of 'cs'. This is a fully
688 * instantiated count, rather than a drawn count, so we count
689 * each cell as many times as it appears in an array or as
690 * a subcell.
691 *
692 * Results:
693 * Returns 0 always.
694 *
695 * Side effects:
696 * See above.
697 *
698 * ----------------------------------------------------------------------------
699 */
700
701 int
extTimesFlatFunc(def,cs)702 extTimesFlatFunc(def, cs)
703 CellDef *def;
704 struct cellStats *cs;
705 {
706 struct cellStats *csForDef;
707 int extTimesFlatUse();
708
709 /* Find this cell's statistics in the table */
710 if ((csForDef = extGetStats(def)) == NULL)
711 return (0);
712
713 /* Add the fets and rectangles */
714 cs->cs_ffets += csForDef->cs_fets;
715 cs->cs_frects += csForDef->cs_rects;
716
717 /* Visit our children */
718 (void) DBCellEnum(def, extTimesFlatUse, (ClientData) cs);
719 return (0);
720 }
721
722 int
extTimesFlatUse(use,cs)723 extTimesFlatUse(use, cs)
724 CellUse *use;
725 struct cellStats *cs;
726 {
727 struct cellStats dummyCS;
728 int nx, ny, nel;
729
730 /* Compute statistics for this cell and its children */
731 bzero((char *) &dummyCS, sizeof dummyCS);
732 (void) extTimesFlatFunc(use->cu_def, &dummyCS);
733
734 /* Scale by number of elements in this array */
735 if (use->cu_xlo < use->cu_xhi) nx = use->cu_xhi - use->cu_xlo + 1;
736 else nx = use->cu_xlo - use->cu_xhi + 1;
737 if (use->cu_ylo < use->cu_yhi) ny = use->cu_yhi - use->cu_ylo + 1;
738 else ny = use->cu_ylo - use->cu_yhi + 1;
739
740 nel = nx * ny;
741
742 /* Fets and rects */
743 cs->cs_ffets += dummyCS.cs_ffets * nel;
744 cs->cs_frects += dummyCS.cs_frects * nel;
745 return (0);
746 }
747
748 /*
749 * ----------------------------------------------------------------------------
750 *
751 * extTimeProc --
752 *
753 * Time a procedure applied to the CellDef 'def', storing the time
754 * in the timeval pointed to by 'tv'. The procedure should be of
755 * the form:
756 *
757 * (*proc)(def)
758 * CellDef *def;
759 * {
760 * }
761 *
762 * Results:
763 * None.
764 *
765 * Side effects:
766 * See above.
767 *
768 * Algorithm:
769 * If (*proc)() takes less than a second to run, we run it ten
770 * times to get a better time estimate, then divide by ten.
771 *
772 * ----------------------------------------------------------------------------
773 */
774
775 void
776 extTimeProc(proc, def, tv)
777 int (*proc)();
778 CellDef *def;
779 struct timeval *tv;
780 {
781 int secs, usecs, i;
782
783 #ifdef SYSV
784 tv->tv_sec = 0;
785 tv->tv_usec = 0;
786 #else
787 extern int getrusage();
788 struct rusage r1, r2;
789
790 (void) getrusage(RUSAGE_SELF, &r1);
791 (*proc)(def);
792 (void) getrusage(RUSAGE_SELF, &r2);
793
794 tv->tv_sec = r2.ru_utime.tv_sec - r1.ru_utime.tv_sec;
795 tv->tv_usec = r2.ru_utime.tv_usec - r1.ru_utime.tv_usec;
796 if (tv->tv_usec < 0)
797 {
798 tv->tv_usec += 1000000;
799 tv->tv_sec -= 1;
800 }
801
802 if (tv->tv_sec < 1)
803 {
804 (void) getrusage(RUSAGE_SELF, &r1);
805 for (i = 0; i < 10; i++)
806 (*proc)(def);
807 (void) getrusage(RUSAGE_SELF, &r2);
808 secs = r2.ru_utime.tv_sec - r1.ru_utime.tv_sec;
809 usecs = r2.ru_utime.tv_usec - r1.ru_utime.tv_usec;
810 usecs = (usecs + (secs * 1000000)) / 10;
811 tv->tv_sec = usecs / 1000000;
812 tv->tv_usec = usecs % 1000000;
813 }
814 #endif
815 }
816
817 /*
818 * ----------------------------------------------------------------------------
819 *
820 * extPaintOnly --
821 *
822 * Called via extTimeProc() above. Extract just the paint in a cell.
823 *
824 * Results:
825 * None.
826 *
827 * Side effects:
828 * None.
829 *
830 * ----------------------------------------------------------------------------
831 */
832
833 void
extPaintOnly(def)834 extPaintOnly(def)
835 CellDef *def;
836 {
837 NodeRegion *reg;
838
839 reg = extBasic(def, extDevNull);
840 if (reg) ExtFreeLabRegions((LabRegion *) reg);
841 ExtResetTiles(def, extUnInit);
842 }
843
844 /*
845 * ----------------------------------------------------------------------------
846 *
847 * extHierCell --
848 *
849 * Called via extTimeProc() above. Extract a cell normally, but
850 * send the extracted output to /dev/null.
851 *
852 * Results:
853 * None.
854 *
855 * Side effects:
856 * None.
857 *
858 * ----------------------------------------------------------------------------
859 */
860
861 void
extHierCell(def)862 extHierCell(def)
863 CellDef *def;
864 {
865 extCellFile(def, extDevNull, FALSE);
866 }
867
868 /*
869 * ----------------------------------------------------------------------------
870 *
871 * extCumInit --
872 *
873 * Initialize a cumulative statistics structure.
874 *
875 * Results:
876 * None.
877 *
878 * Side effects:
879 * See above.
880 *
881 * ----------------------------------------------------------------------------
882 */
883
884 void
extCumInit(cum)885 extCumInit(cum)
886 struct cumStats *cum;
887 {
888 cum->cums_min = (double) INFINITY;
889 cum->cums_max = (double) MINFINITY;
890 cum->cums_sum = 0.0;
891 cum->cums_sos = 0.0;
892 cum->cums_n = 0;
893 }
894
895 /*
896 * ----------------------------------------------------------------------------
897 *
898 * extCumOutput --
899 *
900 * Output a cumulative statistics structure.
901 *
902 * Results:
903 * None.
904 *
905 * Side effects:
906 * Writes to the FILE 'f'.
907 *
908 * ----------------------------------------------------------------------------
909 */
910
911 void
extCumOutput(str,cum,f)912 extCumOutput(str, cum, f)
913 char *str; /* Prefix string */
914 struct cumStats *cum;
915 FILE *f;
916 {
917 double mean, var;
918
919 mean = var = 0.0;
920 if (cum->cums_n != 0)
921 {
922 mean = cum->cums_sum / (double) cum->cums_n;
923 var = (cum->cums_sos / (double) cum->cums_n) - (mean * mean);
924 }
925
926 fprintf(f, "%s", str);
927 if (cum->cums_min < INFINITY)
928 fprintf(f, " %8.2f", cum->cums_min);
929 else
930 fprintf(f, " <none>");
931 if (cum->cums_max > MINFINITY)
932 fprintf(f, " %8.2f", cum->cums_max);
933 else
934 fprintf(f, " <none>");
935 fprintf(f, " %8.2f %8.2f\n", mean, sqrt(var));
936 }
937
938 /*
939 * ----------------------------------------------------------------------------
940 *
941 * extCumAdd --
942 *
943 * Add the value v to the cumulative statistics structure,
944 * updating the statistics.
945 *
946 * Results:
947 * None.
948 *
949 * Side effects:
950 * See above.
951 *
952 * ----------------------------------------------------------------------------
953 */
954
955 void
extCumAdd(cum,v)956 extCumAdd(cum, v)
957 struct cumStats *cum;
958 double v;
959 {
960 if (v < cum->cums_min) cum->cums_min = v;
961 if (v > cum->cums_max) cum->cums_max = v;
962 cum->cums_sum += v;
963 cum->cums_sos += v*v;
964 cum->cums_n++;
965 }
966
967 /*
968 * ----------------------------------------------------------------------------
969 *
970 * extGetStats --
971 *
972 * Return the cellStats record for the CellDef 'def'.
973 *
974 * Results:
975 * See above.
976 *
977 * Side effects:
978 * None.
979 *
980 * ----------------------------------------------------------------------------
981 */
982
983 struct cellStats *
extGetStats(def)984 extGetStats(def)
985 CellDef *def;
986 {
987 HashEntry *he;
988
989 he = HashLookOnly(&cellStatsTable, (char *) def);
990 if (he == (HashEntry *) NULL)
991 return ((struct cellStats *) NULL);
992
993 return ((struct cellStats *) HashGetValue(he));
994 }
995
996 /*
997 * ----------------------------------------------------------------------------
998 *
999 * ExtInterCount --
1000 *
1001 * Find all interaction areas in an entire design, and count
1002 * the fraction of the total area that is really an interaction
1003 * area. Report this for each cell in the design, and as a
1004 * fraction of the total area.
1005 *
1006 * Results:
1007 * None.
1008 *
1009 * Side effects:
1010 * Writes to the FILE 'f'.
1011 *
1012 * ----------------------------------------------------------------------------
1013 */
1014
1015 int extInterCountHalo;
1016 CellDef *extInterCountDef;
1017
1018 void
ExtInterCount(rootUse,halo,f)1019 ExtInterCount(rootUse, halo, f)
1020 CellUse *rootUse;
1021 int halo;
1022 FILE *f;
1023 {
1024 double inter;
1025
1026 /* Make sure this cell is read in */
1027 if (DBCellReadArea(rootUse, &rootUse->cu_def->cd_bbox, TRUE))
1028 {
1029 TxError("Failure to read entire subtree of cell.\n");
1030 return;
1031 }
1032
1033 /* Initialize cumulative statistics */
1034 extCumInit(&cumPercentInteraction);
1035 extCumInit(&cumTotalArea);
1036 extCumInit(&cumInteractArea);
1037
1038 /* Mark all defs as unvisited */
1039 (void) DBCellSrDefs(0, extDefInitFunc, (ClientData) 0);
1040
1041 /*
1042 * Recursively visit all defs in the tree and compute
1043 * their interaction area.
1044 */
1045 extInterCountHalo = halo;
1046 (void) extInterAreaFunc(rootUse, f);
1047
1048 /* Mark all defs as unvisited */
1049 (void) DBCellSrDefs(0, extDefInitFunc, (ClientData) 0);
1050
1051 /* Output the summary statistics */
1052 fprintf(f, "\n\nSummary statistics:\n\n");
1053 fprintf(f, "%s %8s %8s %8s %8s\n",
1054 " ", "min", "max", "mean", "std.dev");
1055 extCumOutput("% cell interact", &cumPercentInteraction, f);
1056
1057 /* Fix up average value to be weighted */
1058 inter = 0.0;
1059 if (cumTotalArea.cums_sum > 0)
1060 inter = 100.0 * cumInteractArea.cums_sum / cumTotalArea.cums_sum;
1061 fprintf(f, "Mean %% interaction area = %.2f\n", inter);
1062 }
1063
1064 int
extInterAreaFunc(use,f)1065 extInterAreaFunc(use, f)
1066 CellUse *use;
1067 FILE *f;
1068 {
1069 static Plane *interPlane = (Plane *) NULL;
1070 CellDef *def = use->cu_def;
1071 int extInterCountFunc();
1072 int area, interarea;
1073 double pctinter;
1074
1075 if (interPlane == NULL)
1076 interPlane = DBNewPlane((ClientData) TT_SPACE);
1077
1078 /* Skip if already visited */
1079 if (def->cd_client)
1080 return (0);
1081
1082 /* Mark as visited */
1083 def->cd_client = (ClientData) 1;
1084
1085 /* Compute interaction area */
1086 extInterCountDef = def;
1087 ExtFindInteractions(def, extInterCountHalo, 0, interPlane);
1088 interarea = 0;
1089 (void) DBSrPaintArea((Tile *) NULL, interPlane, &TiPlaneRect,
1090 &DBAllButSpaceBits, extInterCountFunc, (ClientData) &interarea);
1091 DBClearPaintPlane(interPlane);
1092 area = (def->cd_bbox.r_xtop - def->cd_bbox.r_xbot)
1093 * (def->cd_bbox.r_ytop - def->cd_bbox.r_ybot);
1094
1095 pctinter = 0.0;
1096 if (area > 0)
1097 pctinter = ((double) interarea) / ((double) area) * 100.0;
1098 if (pctinter > 0.0) extCumAdd(&cumPercentInteraction, pctinter);
1099 extCumAdd(&cumTotalArea, (double) area);
1100 extCumAdd(&cumInteractArea, (double) interarea);
1101
1102 fprintf(f, "%7.2f%% %s\n", pctinter, def->cd_name);
1103
1104 /* Visit our children */
1105 (void) DBCellEnum(def, extInterAreaFunc, (ClientData) f);
1106 return (0);
1107 }
1108
1109 int
extInterCountFunc(tile,pArea)1110 extInterCountFunc(tile, pArea)
1111 Tile *tile;
1112 int *pArea;
1113 {
1114 Rect r;
1115
1116 TITORECT(tile, &r);
1117 GEOCLIP(&r, &extInterCountDef->cd_bbox);
1118 *pArea += (r.r_xtop - r.r_xbot) * (r.r_ytop - r.r_ybot);
1119 return (0);
1120 }
1121