1 /*
2 * Copyright (C) 1988-1992 Yale University
3 *
4 * This work is distributed in the hope that it will be useful; you can
5 * redistribute it and/or modify it under the terms of the
6 * GNU General Public License as published by the Free Software Foundation;
7 * either version 2 of the License,
8 * or any later version, on the following conditions:
9 *
10 * (a) YALE MAKES NO, AND EXPRESSLY DISCLAIMS
11 * ALL, REPRESENTATIONS OR WARRANTIES THAT THE MANUFACTURE, USE, PRACTICE,
12 * SALE OR
13 * OTHER DISPOSAL OF THE SOFTWARE DOES NOT OR WILL NOT INFRINGE UPON ANY
14 * PATENT OR
15 * OTHER RIGHTS NOT VESTED IN YALE.
16 *
17 * (b) YALE MAKES NO, AND EXPRESSLY DISCLAIMS ALL, REPRESENTATIONS AND
18 * WARRANTIES
19 * WHATSOEVER WITH RESPECT TO THE SOFTWARE, EITHER EXPRESS OR IMPLIED,
20 * INCLUDING,
21 * BUT NOT LIMITED TO, WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A
22 * PARTICULAR
23 * PURPOSE.
24 *
25 * (c) LICENSEE SHALL MAKE NO STATEMENTS, REPRESENTATION OR WARRANTIES
26 * WHATSOEVER TO
27 * ANY THIRD PARTIES THAT ARE INCONSISTENT WITH THE DISCLAIMERS BY YALE IN
28 * ARTICLE
29 * (a) AND (b) above.
30 *
31 * (d) IN NO EVENT SHALL YALE, OR ITS TRUSTEES, DIRECTORS, OFFICERS,
32 * EMPLOYEES AND
33 * AFFILIATES BE LIABLE FOR DAMAGES OF ANY KIND, INCLUDING ECONOMIC DAMAGE OR
34 * INJURY TO PROPERTY AND LOST PROFITS, REGARDLESS OF WHETHER YALE SHALL BE
35 * ADVISED, SHALL HAVE OTHER REASON TO KNOW, OR IN FACT SHALL KNOW OF THE
36 * POSSIBILITY OF THE FOREGOING.
37 *
38 */
39
40 /* -----------------------------------------------------------------
41 FILE: paths.c
42 DESCRIPTION:output length of paths
43 CONTENTS: print_paths.
44 INT calc_incr_time( cell )
45 INT cell ;
46 update_time( cell )
47 INT cell ;
48 INT calc_incr_time2( cella, cellb )
49 INT cella, cellb ;
50 update_time2()
51 init_path_set()
52 add2path_set( path )
53 INT path ;
54 PSETPTR enum_path_set()
55 clear_path_set()
56 init_net_set()
57 add2net_set( net )
58 INT net ;
59 BOOL member_net_set( net )
60 clear_net_set()
61 INT dcalc_full_penalty(newtimepenal)
62 INT dcalc_path_len(path_num)
63 INT path_num ;
64 DATE: Oct 22, 1988
65 REVISIONS: Dec 3, 1988 - completed timing driven code.
66 Jan 29, 1989 - added \n's for pretty output.
67 Mar 11, 1989 - added statistics to print_paths.
68 - added wirelength to print_paths.
69 Mar 13, 1989 - now output penalty in print_paths.
70 Thu Dec 20 00:23:46 EST 1990 - removed += operator.
71 Fri Jan 18 18:33:25 PST 1991 - updated output format.
72 Thu Apr 18 01:52:21 EDT 1991 - added OOS for out of spec
73 for easier searching.
74 Sun Apr 21 21:25:12 EDT 1991 - added ignore keyword for
75 analyze nets. Renamed for library stat function.
76 Mon Aug 12 17:01:03 CDT 1991 - changed timing ASSERTIONS
77 to D( ) constructs to speed execution time during
78 debug mode.
79 Fri Nov 8 01:08:41 EST 1991 - rewrote pad output file
80 for easier understanding.
81 ----------------------------------------------------------------- */
82
83 /* #define ZERO_CHECK */
84
85 #include "standard.h"
86 #include "main.h"
87 #include <yalecad/debug.h>
88 #include "readnets.h"
89 #include <yalecad/message.h>
90 #include <yalecad/stat.h>
91
92 /* global variables */
93 extern DOUBLE avg_timeG ;/* average random time penalty */
94 extern DOUBLE avg_funcG ;/* average random wirelength penalty */
95
96 /* forward declarations */
97 INT dcalc_min_path_len() ;
98 INT dcalc_max_path_len() ;
99 INT dcalc_path_len(INT, INT);
100
101 void add2path_set( INT path );
102 void clear_path_set();
103 BOOL member_net_set( int net );
104
105 static INT errorboundS = 0 ;
106
print_paths()107 void print_paths( )
108 {
109
110 char filename[LRECL] ;
111 INT i, pathLength ;
112 INT length ;
113 INT above, really_above, really_below, below, in ;
114 INT check, way_above, way_below ;
115 INT really_way_above, really_way_below ;
116 INT *stat ;
117 INT xspan, yspan ;
118 PATHPTR pptr, get_path_list() ;
119 GLISTPTR net ;
120 DBOXPTR nptr ;
121 PINBOXPTR netptr ;
122 FILE *fp ;
123 DOUBLE mean ;
124 DOUBLE paths ;
125 INT num_paths ;
126 INT penaltyS ;
127
128 i = 0 ;
129 above = 0 ;
130 really_above = 0 ;
131 way_above = 0 ;
132 really_way_above = 0 ;
133 below = 0 ;
134 really_below = 0 ;
135 way_below = 0 ;
136 really_way_below = 0 ;
137 in = 0 ;
138 penaltyS = 0 ;
139 /* get total number of paths in timing analysis */
140 num_paths = get_total_paths() ;
141 /* allocate the an array for calculating statistics */
142 if( num_paths ){
143 stat = (INT *) Ysafe_malloc( num_paths * sizeof(INT) ) ;
144 }
145 sprintf(filename, "%s.pth" , cktNameG ) ;
146 fp = TWOPEN( filename , "w", ABORT ) ;
147 /* first the lengths of the nets */
148 fprintf( fp, "The paths:\n" ) ;
149 fprintf( fp, "##############################################\n" ) ;
150 for( pptr=get_path_list() ;pptr;pptr=pptr->next ){
151 pathLength = 0 ;
152 xspan = 0 ;
153 yspan = 0 ;
154 /* get pathLength for path */
155 fprintf( fp, "\npath %3d:\n",++i ) ;
156 for( net = pptr->nets ; net ; net = net->next ){
157 nptr = netarrayG[net->p.net] ;
158 fprintf( fp, "\t\t%s\n", nptr->name ) ;
159 length = (INT)(horizontal_path_weightG * (DOUBLE) nptr->halfPx) +
160 (INT)(vertical_path_weightG * (DOUBLE) nptr->halfPy) ;
161 pathLength += length ;
162 xspan += nptr->halfPx ;
163 yspan += nptr->halfPy ;
164 }
165 fprintf( fp, "\tpriority:%d lower_bound:%d upper_bound:%d\n",
166 pptr->priority, pptr->lower_bound, pptr->upper_bound ) ;
167 fprintf( fp,"\tweighted length:%d\n", pathLength ) ;
168 fprintf( fp, "\txspan:%d yspan:%d length:%d ", xspan, yspan,
169 xspan+yspan ) ;
170 if( pptr->priority ){
171 ASSERT( pathLength == pptr->path_len,"print_paths",
172 "pathLength does not equal incremental value " ) ;
173 }
174
175 check = FALSE ;
176 for( net = pptr->nets ; net ; net = net->next ){
177 netptr = netarrayG[net->p.net]->pins ;
178 for( ; netptr ; netptr = netptr->next ) {
179 if( netptr->cell > numcellsG ) {
180 check = TRUE ;
181 break ;
182 }
183 }
184 }
185 if( pathLength < pptr->lower_bound ){
186 penaltyS += pptr->lower_bound - pathLength ;
187 fprintf( fp, "*" ) ;
188 if( check ) {
189 fprintf( fp, " pad" ) ;
190 }
191 if( pathLength < (INT)( 0.90 * (DOUBLE) pptr->lower_bound) ){
192 below++ ;
193
194 if( !check ) {
195 really_below++ ;
196 }
197 }
198 if( pathLength < (INT)( 0.80 * (DOUBLE) pptr->lower_bound) ){
199 way_below++ ;
200 fprintf( fp, " OOS" ) ;
201 if( !check ) {
202 really_way_below++ ;
203 }
204 }
205 } else if( pathLength > pptr->upper_bound ){
206 penaltyS += pathLength - pptr->upper_bound ;
207 fprintf( fp, "*" ) ;
208 check = FALSE ;
209 for( net = pptr->nets ; net ; net = net->next ){
210 netptr = netarrayG[net->p.net]->pins ;
211 for( ; netptr ; netptr = netptr->next ) {
212 if( netptr->cell > numcellsG ) {
213 check = TRUE ;
214 break ;
215 }
216 }
217 }
218 if( check ) {
219 fprintf( fp, " pad" ) ;
220 }
221 if( pathLength > (INT)( 1.10 * (DOUBLE) pptr->upper_bound) ){
222 above++ ;
223
224 if( !check ) {
225 really_above++ ;
226 }
227 }
228 if( pathLength > (INT)( 1.20 * (DOUBLE) pptr->upper_bound) ){
229 way_above++ ;
230 fprintf( fp, " OOS" ) ;
231 if( !check ) {
232 really_way_above++ ;
233 }
234 }
235 } else {
236 in++ ;
237 }
238 fprintf( fp, "\n" ) ;
239 /* add pathlength to stat array */
240 stat[i-1] = pathLength ;
241
242 }
243 /* first the lengths of the nets */
244 fprintf( fp, "\nThe nets:\n" ) ;
245 fprintf( fp, "##############################################\n" ) ;
246 for( i=1;i<=numnetsG;i++ ){
247 nptr = netarrayG[i] ;
248 fprintf( fp, "net %3d:%s xspan:%d yspan:%d length:%d numpins:%d",
249 i, nptr->name, nptr->halfPx, nptr->halfPy,
250 (INT)(horizontal_path_weightG * (DOUBLE) nptr->halfPx) +
251 (INT)(vertical_path_weightG * (DOUBLE) nptr->halfPy),
252 nptr->numpins ) ;
253 if( nptr->ignore ){
254 fprintf( fp, " ignored\n" ) ;
255 } else {
256 fprintf( fp, "\n" ) ;
257 }
258 }
259 /* avoid a divide by zero */
260 if( num_paths ){
261 paths = (DOUBLE) num_paths ;
262 fprintf( fp, "\nSummary:\n" ) ;
263 fprintf( fp, "Total wirelength :%5d\n", funccostG ) ;
264 fprintf( fp, "Total time penalty :%5d\n", penaltyS ) ;
265 fprintf( fp, "Number of paths :%5d\n", num_paths ) ;
266 fprintf( fp, "Number of active paths :%5d\n", numpathsG ) ;
267 fprintf( fp, "Number of paths 10%% below spec :%5d - %4.2f%%\n",
268 below, 100.0 * (DOUBLE) below / paths ) ;
269 fprintf( fp, "Number of paths 10%% above spec :%5d - %4.2f%%\n",
270 above, 100.0 * (DOUBLE) above / paths ) ;
271 fprintf( fp, "Number of paths within spec :%5d - %4.2f%%\n",
272 in, 100.0 * (DOUBLE) in / paths ) ;
273 fprintf( fp, "# of non-pad paths out of spec :%5d\n", really_above +
274 really_below ) ;
275 fprintf( fp, "Number of paths 20%% below spec :%5d - %4.2f%%\n",
276 way_below, 100.0 * (DOUBLE) way_below / paths ) ;
277 fprintf( fp, "Number of paths 20%% above spec :%5d - %4.2f%%\n",
278 way_above, 100.0 * (DOUBLE) way_above / paths ) ;
279 fprintf( fp, "# of non-pad paths out of spec :%5d\n",
280 really_way_above + really_way_below ) ;
281 fprintf( fp, "Min length :%4.2le\n",
282 Ystat_min( stat, num_paths, sizeof(INT) ) ) ;
283 fprintf( fp, "Max length :%4.2le\n",
284 Ystat_max( stat, num_paths, sizeof(INT) ) ) ;
285 mean = Ystat_mean( stat, num_paths, sizeof(INT) ) ;
286 fprintf( fp, "Mean length :%4.2le\n", mean ) ;
287 fprintf( fp, "Standard Dev. length :%4.2le\n",
288 sqrt( Ystat_var( stat, num_paths, sizeof(INT),mean) ) ) ;
289 Ysafe_free( stat ) ;
290 }
291 TWCLOSE( fp ) ;
292
293 } /* end print_paths */
294
295 /* -----------------------------------------------------------------
296 The update path routines
297 The incremental routines speed execution by looking at only those
298 paths connected to the cells that are to be moved. In addition,
299 only those nets which are modified by the move are updated. This
300 gives us an incremental length which we add to old half perimeter
301 to give us total lenght of this net. The penalty is based on this
302 length. We calculate an incremental penalty based on the change
303 in the penalty.
304 ----------------------------------------------------------------- */
305 /* calculate the timing cost incrementally */
calc_incr_time(cell)306 INT calc_incr_time( cell )
307 INT cell ;
308 {
309 INT newpenal ; /* proposed move's timing penalty delta */
310 INT oldpenal ; /* the old penalty of the nets that move */
311 INT path_num ; /* name of path */
312 INT net ; /* net of path */
313 INT length ; /* path length incremental */
314 GLISTPTR pptr ; /* pointer to paths of a cell */
315 GLISTPTR net_of_path ;
316 PATHPTR path ;
317 DBOXPTR dimptr ;
318
319 newpenal = 0 ;
320 oldpenal = 0 ;
321 /* for all paths of the cell that has moved */
322 for( pptr = carrayG[cell]->paths; pptr ; pptr = pptr->next ) {
323
324 length = 0 ;
325 path_num = pptr->p.path ;
326 ASSERTNCONT( path_num > 0 && path_num <= numpathsG,
327 "calc_incr_time", "path is out of bounds" ) ;
328 path = patharrayG[path_num] ;
329 /* for all nets k of a path i */
330 for( net_of_path=path->nets;net_of_path;
331 net_of_path=net_of_path->next ){
332 net = net_of_path->p.net ;
333
334 dimptr = netarrayG[net] ;
335
336 /* accumulate length of path */
337 if( member_net_set( net ) ){
338 /* this half - perimeter has changed use update */
339 /* calculate total change on path */
340 length = length + (INT)
341 (horizontal_path_weightG * (DOUBLE) dimptr->newhalfPx ) ;
342 length = length - (INT)
343 (horizontal_path_weightG * (DOUBLE) dimptr->halfPx ) ;
344 length = length + (INT)
345 (vertical_path_weightG * (DOUBLE) dimptr->newhalfPy ) ;
346 length = length - (INT)
347 (vertical_path_weightG * (DOUBLE) dimptr->halfPy ) ;
348 } /* else this half - perimeter has not changed use old */
349 }
350 /* save total result - change to total length */
351 path->new_path_len = length += path->path_len ;
352
353 D( "twsc/check_timing",
354 ASSERT( dcalc_path_len(path_num,length),"update_time",
355 "length mismatch" ) ;
356 ) ;
357
358 /* calculate change in timing penalty */
359 /* no penalty if within target window */
360 /* lowerbound <= length <= upperbound */
361 if( length > path->upper_bound ){
362 newpenal += length - path->upper_bound ;
363 } else if( length < path->lower_bound ){
364 newpenal += path->lower_bound - length ;
365 }
366 /* now the old penalty */
367 if( path->path_len > path->upper_bound ){
368 oldpenal += path->path_len - path->upper_bound ;
369 } else if( path->path_len < path->lower_bound ){
370 oldpenal += path->lower_bound - path->path_len ;
371 }
372 } /* end loop on the paths of a cell */
373 /* return the change in penalty */
374 return( newpenal - oldpenal ) ;
375
376 } /* end function calc_incr_time */
377
378
update_time(cell)379 void update_time( cell )
380 INT cell ;
381 {
382
383 INT path_num ; /* name of path */
384 GLISTPTR pptr ; /* pointer to paths of a cell */
385 PATHPTR path ;
386
387 /* for all paths of the cell that has moved */
388 for( pptr = carrayG[cell]->paths; pptr ; pptr = pptr->next ) {
389
390 path_num = pptr->p.path ;
391 ASSERTNCONT( path_num > 0 && path_num <= numpathsG,
392 "update_time", "path is out of bounds" ) ;
393 path = patharrayG[path_num] ;
394 /* keep result */
395 path->path_len = path->new_path_len ;
396 }
397
398 } /* end function update_time */
399
400 /* calculate the timing cost incrementally for two cells */
calc_incr_time2(cella,cellb)401 INT calc_incr_time2( cella, cellb )
402 INT cella ;
403 INT cellb ;
404 {
405 INT newpenal ; /* proposed move's timing penalty delta */
406 INT oldpenal ; /* the old penalty of the nets that move */
407 INT path_num ; /* name of path */
408 INT net ; /* net of path */
409 INT length ; /* path length incremental */
410 GLISTPTR pptr ; /* pointer to paths of a cell */
411 GLISTPTR net_of_path ;
412 PATHPTR path ;
413 PSETPTR pathlist, enum_path_set() ;
414 DBOXPTR dimptr ;
415
416 newpenal = 0 ;
417 oldpenal = 0 ;
418 clear_path_set() ;
419
420 /* use add2path_set to get union of paths from cella and cellb */
421 for( pptr = carrayG[cella]->paths; pptr ; pptr = pptr->next ) {
422 add2path_set( pptr->p.path ) ;
423 }
424 for( pptr = carrayG[cellb]->paths; pptr ; pptr = pptr->next ) {
425 add2path_set( pptr->p.path ) ;
426 }
427
428
429 /* now use UNIQUE list of the union of the two cell's paths */
430 for( pathlist=enum_path_set(); pathlist; pathlist=pathlist->next){
431
432 length = 0 ;
433 path_num = pathlist->path ;
434 ASSERTNCONT( path_num > 0 && path_num <= numpathsG,
435 "calc_incr_time2", "path is out of bounds" ) ;
436 path = patharrayG[path_num] ;
437
438 /* for all nets k of a path i */
439 for( net_of_path=path->nets;net_of_path;
440 net_of_path=net_of_path->next ){
441 net = net_of_path->p.net ;
442
443 dimptr = netarrayG[net] ;
444
445 /* accumulate length of path */
446 if( member_net_set( net ) ){
447 /* this half - perimeter has changed use update */
448 /* calculate total change on path */
449 length = length + (INT)
450 (horizontal_path_weightG * (DOUBLE) dimptr->newhalfPx ) ;
451 length = length - (INT)
452 (horizontal_path_weightG * (DOUBLE) dimptr->halfPx ) ;
453 length = length + (INT)
454 (vertical_path_weightG * (DOUBLE) dimptr->newhalfPy ) ;
455 length = length - (INT)
456 (vertical_path_weightG * (DOUBLE) dimptr->halfPy ) ;
457 } /* else this half - perimeter has not changed use old */
458 }
459 /* save total result - change to total length */
460 path->new_path_len = length += path->path_len ;
461
462 D( "twsc/check_timing",
463 ASSERT( dcalc_path_len(path_num,length),"update_time",
464 "length mismatch" ) ;
465 ) ;
466
467 /* calculate change in timing penalty */
468 /* no penalty if within target window */
469 /* lowerbound <= length <= upperbound */
470 if( length > path->upper_bound ){
471 newpenal += length - path->upper_bound ;
472 } else if( length < path->lower_bound ){
473 newpenal += path->lower_bound - length ;
474 }
475 /* now the old penalty */
476 if( path->path_len > path->upper_bound ){
477 oldpenal += path->path_len - path->upper_bound ;
478 } else if( path->path_len < path->lower_bound ){
479 oldpenal += path->lower_bound - path->path_len ;
480 }
481 } /* end loop on paths */
482 /* return the change in penalty */
483 return( newpenal - oldpenal ) ;
484
485 } /* end function calc_incr_time2 */
486
update_time2()487 void update_time2()
488 {
489 PATHPTR path ;
490 PSETPTR pathlist, enum_path_set() ;
491
492 /* now use UNIQUE list of the union of the two cell's paths */
493 for( pathlist=enum_path_set(); pathlist; pathlist=pathlist->next){
494
495 ASSERTNCONT( pathlist->path > 0 && pathlist->path <= numpathsG,
496 "update_time2", "path is out of bounds" ) ;
497 path = patharrayG[pathlist->path] ;
498 /* keep result */
499 path->path_len = path->new_path_len ;
500 }
501
502 } /* end function update_time */
503 /* -----------------------------------------------------------------
504 The set required in the update path routines needs the following
505 operations done efficiently :
506 membership - O(1)
507 add to set if unique - O(1)
508 clear set - O(1)
509 set enumeration - O( paths in set )
510 Below is a space hungry O( numpaths ) but time efficient implementation
511 We combine two data structures to accomplish this goal. We use array
512 for testing membership and uniqueness but use list for enumeration.
513 By incrementing count we can reinitialize easily.
514 Note: PSETBOX, PSETPTR definitions are in custom.h
515 ----------------------------------------------------------------- */
516 static PSETPTR path_set_listS ; /* list is beginning of set as a list */
517 static PSETPTR *path_set_arrayS ; /* set is an array of path set boxes */
518 static INT path_set_countS ; /* current set count */
519
520 /* initialize set */
init_path_set()521 void init_path_set()
522 {
523 INT i ;
524
525 path_set_arrayS=(PSETPTR *)Ysafe_malloc((numpathsG+1)*sizeof(PSETPTR));
526 for( i=0;i<=numpathsG;i++ ){
527 path_set_arrayS[i] = (PSETPTR) Ysafe_calloc( 1, sizeof(PSETBOX) ) ;
528 }
529 path_set_countS = 1 ;
530 path_set_listS = NULL ;
531 } /* end initset */
532
533 /* add a path to the set if not already in set */
add2path_set(INT path)534 void add2path_set( INT path )
535 {
536 PSETPTR temp, cpath ;
537
538 if( path >= 1 && path <= numpathsG ){
539 cpath = path_set_arrayS[path] ;
540 /* something is a member in set is counts match */
541 if( cpath->member != path_set_countS ){
542 /* new path to be added */
543 /* connect to the single linked list */
544 if( temp = path_set_listS ){
545 /* hook to old list */
546 path_set_listS = cpath ;
547 cpath->next = temp ;
548 } else {
549 path_set_listS = cpath ;
550 /* terminate new list */
551 cpath->next = NULL ;
552 }
553 cpath->path = path ; /* store data */
554 cpath->member = path_set_countS ; /* store membership */
555 }
556
557 } else {
558 M( ERRMSG, "ADD2SET","value of path is out of bounds of set\n" ) ;
559 }
560 } /* end add2path_set */
561
enum_path_set()562 PSETPTR enum_path_set()
563 {
564 return( path_set_listS ) ;
565 }
566
clear_path_set()567 void clear_path_set()
568 {
569 path_set_countS ++ ;
570 path_set_listS = NULL ;
571 } /* end clear_path_set */
572
573 /* -----------------------------------------------------------------
574 Below is a second set of set routines required in the update path
575 routines which operate on nets instead of paths. The following
576 operations need to be done efficiently :
577 membership - O(1)
578 add to set if unique - O(1)
579 clear set - O(1)
580 Since we don't need to enumerate set we only need array to implement
581 this set.
582 ----------------------------------------------------------------- */
583 static INT *net_set_array ; /* set is an array of net set boxes */
584 static INT net_set_count ; /* current set count */
585
586 /* initialize set */
init_net_set()587 void init_net_set()
588 {
589 net_set_array = (INT *) Ysafe_calloc((numnetsG+1), sizeof(INT) );
590 net_set_count = 1 ;
591 } /* end initset */
592
593 /* add a net to the set if not already in set */
add2net_set(net)594 void add2net_set( net )
595 INT net ;
596 {
597 if( net >= 1 || net <= numnetsG ){
598 /* current count make array member a valid member of set */
599 net_set_array[net] = net_set_count ;
600
601 } else {
602 M( ERRMSG, "ADD2SET", "value of path is out of bounds of set" ) ;
603 }
604 } /* end add2net_set */
605
member_net_set(int net)606 BOOL member_net_set( int net )
607 /* test for membership */
608 {
609 if( net_set_array[net] == net_set_count ){
610 return( TRUE ) ;
611 } else {
612 return( FALSE ) ;
613 }
614 } /* end member_net_set */
615
clear_net_set()616 void clear_net_set()
617 {
618 /* to clear set we only need to increment net_set_count */
619 /* we can use this set up to 2 Gig times without any problem */
620 net_set_count ++ ;
621 } /* end clear_path_set */
622
623 #ifdef DEBUG
624 /* *************** DEBUG FUNCTIONS *************************** */
625 /* debug function to make sure calculation is correct */
dcalc_full_penalty(newtimepenal)626 INT dcalc_full_penalty( newtimepenal )
627 INT newtimepenal ;
628 {
629 INT timingpenal ;
630 INT pathcount ;
631 INT length ; /* path length incremental */
632 INT net ; /* net of path */
633 GLISTPTR net_of_path ;
634 PATHPTR path ;
635 DBOXPTR dimptr ;
636
637 /* now calculate the penalties */
638 /* first the timing penalty */
639 timingpenal = 0 ;
640 for( pathcount = 1 ; pathcount <= numpathsG ; pathcount++ ) {
641
642 path = patharrayG[pathcount] ;
643 ASSERTNCONT( path, "dcalc_full_penalty",
644 "pointer to path is NULL" ) ;
645 /* for all nets k of a path i */
646 length = 0 ;
647 for( net_of_path=path->nets;net_of_path;
648 net_of_path=net_of_path->next ){
649 net = net_of_path->p.net ;
650 dimptr = netarrayG[net] ;
651
652 /* accumulate length of path */
653 if( member_net_set( net ) ){
654 /* this half - perimeter has changed use update */
655 /* calculate total change on path */
656 length = length + (INT)
657 (horizontal_path_weightG * (DOUBLE) dimptr->newhalfPx ) ;
658 length = length + (INT)
659 (vertical_path_weightG * (DOUBLE) dimptr->newhalfPy) ;
660 } else {
661 /* old length */
662 length = length + (INT)
663 (horizontal_path_weightG * (DOUBLE) dimptr->halfPx) ;
664 length = length + (INT)
665 (vertical_path_weightG * (DOUBLE) dimptr->halfPy ) ;
666 }
667 }
668 /* calculate penalty */
669 /* no penalty if within target window */
670 /* lowerbound <= length <= upperbound */
671 if( length > path->upper_bound ){
672 timingpenal += length - path->upper_bound ;
673 } else if( length < path->lower_bound ){
674 timingpenal += path->lower_bound - length ;
675 }
676 }
677 if( ABS( timingpenal - newtimepenal ) > errorboundS ){
678 errorboundS = ABS( timingpenal - newtimepenal ) ;
679 return( FALSE ) ;
680 } else {
681 return( TRUE ) ;
682 }
683 }
684
dcalc_path_len(path_num,verify_length)685 INT dcalc_path_len(path_num,verify_length)
686 INT path_num ;
687 INT verify_length ;
688 {
689
690 INT net ; /* net of path */
691 INT length ; /* path length incremental */
692 GLISTPTR net_of_path ;
693 PATHPTR path ;
694 DBOXPTR dimptr ;
695
696 path = patharrayG[path_num] ;
697 /* for all nets k of a path i */
698 length = 0 ;
699 for( net_of_path=path->nets;net_of_path;
700 net_of_path=net_of_path->next ){
701 net = net_of_path->p.net ;
702 dimptr = netarrayG[net] ;
703
704 /* accumulate length of path */
705 if( member_net_set( net ) ){
706 /* this half - perimeter has changed use update */
707 /* calculate total change on path */
708 length = length + (INT)
709 (horizontal_path_weightG * (DOUBLE) dimptr->newhalfPx);
710 length = length + (INT)
711 (vertical_path_weightG * (DOUBLE) dimptr->newhalfPy) ;
712 } else {
713 /* old length */
714 length = length + (INT)
715 (horizontal_path_weightG * (DOUBLE) dimptr->halfPx ) ;
716 length = length + (INT)
717 (vertical_path_weightG * (DOUBLE) dimptr->halfPy ) ;
718 }
719 }
720 if( ABS( length - verify_length ) > errorboundS ){
721 errorboundS = ABS( length - verify_length ) ;
722 return( FALSE ) ;
723 } else {
724 return( TRUE ) ;
725 }
726 }
727
728
dpath_len(net_num,old_not_new)729 INT dpath_len( net_num, old_not_new )
730 INT net_num ;
731 BOOL old_not_new ;
732 {
733
734 INT net ; /* net of path */
735 INT length ; /* path length incremental */
736 INT timingpenal ;
737 GLISTPTR net_of_path ;
738 PATHPTR path ;
739 GLISTPTR pptr ; /* pointer to paths of a cell */
740 DBOXPTR dimptr ;
741
742 timingpenal = 0 ;
743 for( pptr = netarrayG[net_num]->paths; pptr ; pptr = pptr->next ) {
744
745 path = patharrayG[pptr->p.path] ;
746 /* for all nets k of a path i */
747 length = 0 ;
748 for( net_of_path=path->nets;net_of_path;
749 net_of_path=net_of_path->next ){
750 net = net_of_path->p.net ;
751 dimptr = netarrayG[net] ;
752
753 /* accumulate length of path */
754 if( old_not_new ){
755 /* old length */
756 length = length + (INT)
757 (horizontal_path_weightG * (DOUBLE) dimptr->halfPx ) ;
758 length = length + (INT)
759 (vertical_path_weightG * (DOUBLE) dimptr->halfPy ) ;
760 } else {
761 /* this half - perimeter has changed use update */
762 /* calculate total change on path */
763 length = length + (INT)
764 (horizontal_path_weightG * (DOUBLE) dimptr->newhalfPx);
765 length = length + (INT)
766 (vertical_path_weightG * (DOUBLE) dimptr->newhalfPy) ;
767
768 }
769 }
770 /* calculate penalty */
771 /* no penalty if within target window */
772 /* lowerbound <= length <= upperbound */
773 if( length > path->upper_bound ){
774 timingpenal += length - path->upper_bound ;
775 } else if( length < path->lower_bound ){
776 timingpenal += path->lower_bound - length ;
777 }
778 } /* end for( pptr = netarrayyG[net_num]->paths... */
779 return( timingpenal ) ;
780
781 } /* end INT dpath_len() */
782
dprint_error()783 INT dprint_error()
784 {
785 sprintf( YmsgG,
786 "\n\nWe found that the timing error was bound by :%d\n\n",
787 errorboundS ) ;
788 M( MSG, "dprint_error", YmsgG ) ;
789 return( 0 ) ;
790 } /* end dprint_error() */
791
dverify_nets()792 void dverify_nets()
793 {
794
795 INT net ; /* net of path */
796 INT per ;
797 DBOXPTR dimptr ;
798
799 for( net=1; net <= numnetsG; net++ ){
800 dimptr = netarrayG[net] ;
801 per = dimptr->xmax - dimptr->xmin ;
802 ASSERTNCONT( per == dimptr->halfPx, "dverify_nets", "problem") ;
803 per = dimptr->ymax - dimptr->ymin ;
804 ASSERTNCONT( per == dimptr->halfPy, "dverify_nets", "problem") ;
805 }
806 } /* end dverify_nets */
807
dprint_paths(cell)808 void dprint_paths( cell )
809 {
810 INT path_num ; /* name of path */
811 INT net ; /* net of path */
812 GLISTPTR pptr ; /* pointer to paths of a cell */
813 GLISTPTR net_of_path ;
814 PATHPTR path ;
815 DBOXPTR dimptr ;
816
817 /* for all paths of the cell that has moved */
818 for( pptr = carrayG[cell]->paths; pptr ; pptr = pptr->next ) {
819
820 path_num = pptr->p.path ;
821 path = patharrayG[path_num] ;
822 fprintf( stderr, "path:%d, cur_len:%d new_len:%d\n",
823 path_num, path->path_len, path->new_path_len ) ;
824 /* for all nets k of a path i */
825 for( net_of_path=path->nets;net_of_path;net_of_path=net_of_path->next ){
826 net = net_of_path->p.net ;
827
828 dimptr = netarrayG[net] ;
829 fprintf( stderr, " net:%4d Px:%6d nPx:%6d Py:%6d nPy:%6d ",
830 net, dimptr->halfPx, dimptr->newhalfPx, dimptr->halfPy,
831 dimptr->newhalfPy ) ;
832
833 /* accumulate length of path */
834 if( member_net_set( net ) ){
835 fprintf( stderr, "*" ) ;
836 }
837 fprintf( stderr, "\n" ) ;
838 } /* end for( net_of_path... */
839 } /* end for( pptr... */
840 } /* end dprint_paths() */
841
dprint_net_set()842 void dprint_net_set()
843 {
844 INT net ;
845
846 fprintf( stderr, "Current net set:\n" ) ;
847 for( net = 1; net <= numnetsG; net++ ){
848 if( member_net_set( net ) ){
849 fprintf( stderr, "%d ", net ) ;
850 }
851 }
852 fprintf( stderr, "\n" ) ;
853 } /* end dprint_net_set() */
854
855 #endif /* DEBUG */
856
857
858
859 #define TIMEDAMPFACTOR 1.0 /* damping factor on time penalty */
860
calc_time_factor()861 DOUBLE calc_time_factor()
862 {
863 /* **** timing penalty controller **** */
864
865 #ifdef ZERO_CHECK
866 timeFactorG = 0.0 ;
867 #else
868 if( avg_timeG == 0.0 ) {
869 timeFactorG = 3.0 ;
870 } else {
871 timeFactorG = 3.0 * (DOUBLE) avg_funcG / (DOUBLE) avg_timeG ;
872 }
873 #endif
874 return( timeFactorG ) ;
875
876 } /* end function calc_time_penalty */
877
878
879
calc_init_timeFactor()880 void calc_init_timeFactor()
881 {
882
883 #ifdef ZERO_CHECK
884 timeFactorG = 0.0 ;
885 #else
886 timeFactorG = 4.0 ;
887 #endif
888 fprintf(fpoG,"\n\nTIMING FACTOR (COMPUTED) : %f\n", timeFactorG ) ;
889
890 } /* end calc_init_timeFactor */
891