1 /*
2 * Copyright (C) 1989-1990 Yale University
3 * Copyright (C) 2015 Tim Edwards <tim@opencircuitdesign.com>
4 *
5 * This work is distributed in the hope that it will be useful; you can
6 * redistribute it and/or modify it under the terms of the
7 * GNU General Public License as published by the Free Software Foundation;
8 * either version 2 of the License,
9 * or any later version, on the following conditions:
10 *
11 * (a) YALE MAKES NO, AND EXPRESSLY DISCLAIMS
12 * ALL, REPRESENTATIONS OR WARRANTIES THAT THE MANUFACTURE, USE, PRACTICE,
13 * SALE OR
14 * OTHER DISPOSAL OF THE SOFTWARE DOES NOT OR WILL NOT INFRINGE UPON ANY
15 * PATENT OR
16 * OTHER RIGHTS NOT VESTED IN YALE.
17 *
18 * (b) YALE MAKES NO, AND EXPRESSLY DISCLAIMS ALL, REPRESENTATIONS AND
19 * WARRANTIES
20 * WHATSOEVER WITH RESPECT TO THE SOFTWARE, EITHER EXPRESS OR IMPLIED,
21 * INCLUDING,
22 * BUT NOT LIMITED TO, WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A
23 * PARTICULAR
24 * PURPOSE.
25 *
26 * (c) LICENSEE SHALL MAKE NO STATEMENTS, REPRESENTATION OR WARRANTIES
27 * WHATSOEVER TO
28 * ANY THIRD PARTIES THAT ARE INCONSISTENT WITH THE DISCLAIMERS BY YALE IN
29 * ARTICLE
30 * (a) AND (b) above.
31 *
32 * (d) IN NO EVENT SHALL YALE, OR ITS TRUSTEES, DIRECTORS, OFFICERS,
33 * EMPLOYEES AND
34 * AFFILIATES BE LIABLE FOR DAMAGES OF ANY KIND, INCLUDING ECONOMIC DAMAGE OR
35 * INJURY TO PROPERTY AND LOST PROFITS, REGARDLESS OF WHETHER YALE SHALL BE
36 * ADVISED, SHALL HAVE OTHER REASON TO KNOW, OR IN FACT SHALL KNOW OF THE
37 * POSSIBILITY OF THE FOREGOING.
38 *
39 */
40
41 /* -----------------------------------------------------------------
42 FILE: cglbroute.c
43 DESCRIPTION:coarse global routing routines.
44 CONTENTS: cglb_initial()
45 proj_tree_to_grid( )
46 set_cbucket( )
47 cglbroute()
48 free_cglb_initial()
49 reinitial_Hdensity()
50 update_switchvalue()
51 rebuild_cbucket()
52 check_cbucket()
53 print_bucket( row )
54 INT row ;
55 DATE: Mar 27, 1989
56 REVISIONS: Sat Dec 15 22:08:21 EST 1990 - modified pinloc values
57 so that it will always be positive.
58 ----------------------------------------------------------------- */
59
60 #include "standard.h"
61 #include "main.h"
62 #include "groute.h"
63 #define OVERHEAD_INIT 100
64 #define OVERHEAD_DELTA 20
65
66 typedef struct coarsedensity {
67 SHORT density ;
68 SHORT x_coord ;
69 struct coarsedensity *next ;
70 struct coarsedensity *prev ;
71 } HCAPBOX , *HCAPPTR ;
72
73 static HCAPPTR **HcapacityS ;
74 static HCAPPTR **entryptS ;
75 static int entrysizeS ;
76 static SEGBOXPTR *swLsegptrS ;
77 static INT LswitchsegS , svalueS , evalueS ;
78 static INT *crowdmaxS , glb_crowdmaxS , *node_rightS ;
79 static DOUBLE ctrackContS , factor_hereS , factor_oneS , factor_twoS ;
80
cglb_initial()81 void cglb_initial()
82 {
83
84 INT i , j , net , x , tilted_seg ;
85 PINBOXPTR ptr1 , ptr2 ;
86 SEGBOXPTR segptr ;
87
88 tilted_seg = 0 ;
89 ctrackContS = 2.25 ;
90 factor_hereS = 1.0 ;
91 factor_oneS = 0.5 ;
92 factor_twoS = 0.2 ;
93 svalueS = hznode_sepG * 4 / 10 ;
94 evalueS = hznode_sepG * 6 / 10 ;
95 node_rightS = (INT *)Ysafe_malloc( ( chan_node_noG + 1 ) * sizeof(INT) );
96 node_rightS[1] = blkleftG + ( hznode_sepG + 1 ) / 2 ;
97 for( i = 2 ; i <= chan_node_noG ; i++ ) {
98 node_rightS[i] = node_rightS[i-1] + hznode_sepG ;
99 }
100 HcapacityS = (HCAPPTR **)Ysafe_malloc( numChansG * sizeof(HCAPPTR *) );
101 for( i = 1 ; i <= numRowsG ; i++ ) {
102 HcapacityS[i] = (HCAPPTR *) Ysafe_calloc( chan_node_noG + 1 ,
103 sizeof( HCAPPTR ) ) ;
104 for( j = 1 ; j <= chan_node_noG ; j++ ) {
105 HcapacityS[i][j] = ( HCAPPTR )Ysafe_calloc(1,sizeof(HCAPBOX));
106 HcapacityS[i][j]->x_coord = j ;
107 }
108 }
109 for( net = 1 ; net <= numnetsG ; net++ ) {
110 for( segptr = netsegHeadG[net]->next ; segptr ;
111 segptr = segptr->next ) {
112 ptr1 = segptr->pin1ptr ;
113 ptr2 = segptr->pin2ptr ;
114 x = ABS( ptr1->xpos - ptr2->xpos ) ;
115 if( ptr1->row != ptr2->row ) {
116 if( add_Lcorner_feedG && x >= average_feed_sepG ) {
117 segptr->flag = FALSE ;
118 } else {
119 segptr->flag = TRUE ;
120 }
121 if( x >= average_feed_sepG ) {
122 segptr->switchvalue = swL_up ;
123 } else {
124 segptr->switchvalue = nswLINE ;
125 }
126 tilted_seg++ ;
127 } else if( ABS( ptr1->pinloc - ptr2->pinloc ) > 1 ) {
128 segptr->flag = FALSE ;
129 if( x >= average_feed_sepG ) {
130 segptr->switchvalue = swL_up ;
131 } else {
132 segptr->switchvalue = nswLINE ;
133 }
134 } else {
135 segptr->flag = TRUE ;
136 segptr->switchvalue = nswLINE ;
137 }
138 }
139 }
140 fprintf(fpoG," the number of net = %d\n", numnetsG ) ;
141 fprintf(fpoG," the number of tilted segment = %d\n", tilted_seg ) ;
142 }
143
144
proj_tree_to_grid()145 void proj_tree_to_grid( )
146 {
147
148 SEGBOXPTR segptr ;
149 PINBOXPTR ptr1 , ptr2 , netptr ;
150 INT lowV , highV , lowH , highH ;
151 INT i , h , k , net ;
152
153 for( net = 1 ; net <= numnetsG ; net++ ) {
154 for( netptr = steinerHeadG[net]->next;netptr;netptr = netptr->next ) {
155 if( netptr->flag && 1 <= netptr->row && netptr->row <= numRowsG){
156 k = set_node( netptr->xpos ) ;
157 feedpptrG[netptr->row][k]->needed++ ;
158 }
159 }
160 }
161 for( net = 1 ; net <= numnetsG ; net++ ) {
162 for( segptr = netsegHeadG[net]->next ;
163 segptr ; segptr = segptr->next ) {
164 ptr1 = segptr->pin1ptr ;
165 ptr2 = segptr->pin2ptr ;
166 lowV = ptr1->row ;
167 highV = ptr2->row ;
168 lowH = set_node( ptr1->xpos ) ;
169 highH = set_node( ptr2->xpos ) ;
170 if( segptr->switchvalue == nswLINE ) {
171 if( lowV != highV ) {
172 if( ptr1->pinloc >= NEITHER || ptr1->row == 0 ) {
173 lowV++ ;
174 }
175 if( ptr2->pinloc <= NEITHER || ptr2->row == numChansG ) {
176 highV-- ;
177 }
178 for( i = lowV ; i <= highV ; i++ ) {
179 feedpptrG[i][lowH]->needed++ ;
180 }
181 } else if( 1 <= lowV && lowV <= numRowsG ) {
182 if( lowH == highH ) {
183 HcapacityS[lowV][lowH]->density++ ;
184 } else if( ptr2->xpos >=
185 ptr1->xpos + average_feed_sepG ) {
186 for( i = lowH + 1 ; i < highH ; i++ ) {
187 HcapacityS[lowV][i]->density++ ;
188 }
189 if( node_rightS[lowH] - ptr1->xpos >= svalueS ) {
190 HcapacityS[lowV][lowH]->density++ ;
191 }
192 if( node_rightS[highH] - ptr2->xpos <= evalueS ) {
193 HcapacityS[lowV][highH]->density++ ;
194 }
195 } else if( ptr1->xpos >=
196 ptr2->xpos + average_feed_sepG ){
197 for( i = highH + 1 ; i < lowH ; i++ ) {
198 HcapacityS[lowV][i]->density++ ;
199 }
200 if( node_rightS[highH] - ptr2->xpos >= svalueS ) {
201 HcapacityS[lowV][highH]->density++ ;
202 }
203 if( node_rightS[lowH] - ptr1->xpos <= evalueS ) {
204 HcapacityS[lowV][lowH]->density++ ;
205 }
206 }
207 if( segptr->flag == FALSE ) {
208 /* segptr->pin1ptr->pinloc == BOTCELL
209 && segptr->pin2ptr->pinloc == TOPCELL */
210 feedpptrG[lowV][lowH]->needed++ ;
211 }
212 }
213 continue ;
214 } else if( segptr->switchvalue == swL_up ) {
215 h = lowH ;
216 k = highV ;
217 if( ptr1->pinloc >= NEITHER || ptr1->row == 0 ) {
218 lowV++ ;
219 }
220 if( ptr2->pinloc <= NEITHER && segptr->flag ||
221 ptr2->row == numChansG ) {
222 highV-- ;
223 }
224 if( k <= numRowsG ) {
225 if( lowH == highH ) {
226 HcapacityS[k][lowH]->density++ ;
227 } else if( lowH < highH ) {
228 for( i = lowH + 1 ; i < highH ; i++ ) {
229 HcapacityS[k][i]->density++ ;
230 }
231 if( node_rightS[lowH] - ptr1->xpos >= svalueS ) {
232 HcapacityS[k][lowH]->density++ ;
233 }
234 if( node_rightS[highH] - ptr2->xpos <= evalueS ) {
235 HcapacityS[k][highH]->density++ ;
236 }
237 } else {
238 for( i = highH + 1 ; i < lowH ; i++ ) {
239 HcapacityS[k][i]->density++ ;
240 }
241 if( node_rightS[highH] - ptr2->xpos >= svalueS ) {
242 HcapacityS[k][highH]->density++ ;
243 }
244 if( node_rightS[lowH] - ptr1->xpos <= evalueS ) {
245 HcapacityS[k][lowH]->density++ ;
246 }
247 }
248 }
249 } else { /* switchvalue == swL_down */
250 h = highH ;
251 k = lowV ;
252 if( ptr1->row == 0 || ptr1->pinloc >= NEITHER && segptr->flag ) {
253 lowV++ ;
254 }
255 if( ptr2->row == numChansG || ptr2->pinloc <= NEITHER ) {
256 highV-- ;
257 }
258 if( 1 <= k ) {
259 if( lowH == highH ) {
260 HcapacityS[k][lowH]->density++ ;
261 } else if( lowH < highH ) {
262 for( i = lowH + 1 ; i < highH ; i++ ) {
263 HcapacityS[k][i]->density++ ;
264 }
265 if( node_rightS[lowH] - ptr1->xpos >= svalueS ) {
266 HcapacityS[k][lowH]->density++ ;
267 }
268 if( node_rightS[highH] - ptr2->xpos <= evalueS ) {
269 HcapacityS[k][highH]->density++ ;
270 }
271 } else {
272 for( i = highH + 1 ; i < lowH ; i++ ) {
273 HcapacityS[k][i]->density++ ;
274 }
275 if( node_rightS[highH] - ptr2->xpos >= svalueS ) {
276 HcapacityS[k][highH]->density++ ;
277 }
278 if( node_rightS[lowH] - ptr1->xpos <= evalueS ) {
279 HcapacityS[k][lowH]->density++ ;
280 }
281 }
282 }
283 }
284 for( i = lowV ; i <= highV ; i++ ) {
285 feedpptrG[i][h]->needed++ ;
286 }
287 }
288 }
289 }
290
291
set_cbucket()292 void set_cbucket( )
293 {
294
295 HCAPPTR hcaptr , headptr ;
296 SEGBOXPTR segptr ;
297 INT j , last_j , row , max , net ;
298
299 glb_crowdmaxS = 0 ;
300 crowdmaxS = (INT *)Ysafe_calloc( numRowsG + 1, sizeof(INT) ) ;
301 for( row = 1 ; row <= numRowsG ; row++ ) {
302 max = 0 ;
303 for( j = 1 ; j <= chan_node_noG ; j++ ) {
304 if( HcapacityS[row][j]->density > max ) {
305 max = HcapacityS[row][j]->density ;
306 }
307 }
308 crowdmaxS[row] = max ;
309 if( max > glb_crowdmaxS ) {
310 glb_crowdmaxS = max ;
311 }
312 }
313
314 entryptS = (HCAPPTR **)Ysafe_malloc( ( numRowsG+1 ) * sizeof(HCAPPTR *) ) ;
315 entrysizeS = glb_crowdmaxS + OVERHEAD_INIT;
316 for( row = 1 ; row <= numRowsG ; row++ ) {
317 entryptS[row] = (HCAPPTR *)Ysafe_malloc( ( entrysizeS + 1 ) * sizeof( HCAPPTR )) ;
318 for( j = 0 ; j <= entrysizeS ; j++ ) {
319 entryptS[row][j] = (HCAPPTR)Ysafe_calloc( 1,sizeof(HCAPBOX)) ;
320 }
321 }
322
323 for( row = 1 ; row <= numRowsG ; row++ ) {
324 for( j = 1 ; j <= chan_node_noG ; j++ ) {
325 hcaptr = HcapacityS[row][j] ;
326 headptr = entryptS[row][ hcaptr->density ] ;
327 if( headptr->next != NULL ) {
328 hcaptr->next = headptr->next ;
329 hcaptr->next->prev = hcaptr ;
330 hcaptr->prev = headptr ;
331 headptr->next = hcaptr ;
332 } else {
333 headptr->next = hcaptr ;
334 hcaptr->prev = headptr ;
335 hcaptr->next = NULL ;
336 }
337 }
338 }
339 LswitchsegS = 0 ;
340 for( net = 1 ; net <= numnetsG ; net++ ) {
341 for( segptr = netsegHeadG[net]->next ; segptr ;
342 segptr = segptr->next ) {
343 if( segptr->switchvalue != nswLINE ) {
344 LswitchsegS++ ;
345 }
346 }
347 }
348 fprintf(fpoG," the number of switchable L segment = %d\n", LswitchsegS );
349 swLsegptrS = ( SEGBOXPTR *)Ysafe_malloc(
350 ( LswitchsegS + 2 * numnetsG ) * sizeof( SEGBOXPTR ) ) ;
351
352 j = 0 ;
353 for( net = 1 ; net <= numnetsG ; net++ ) {
354 for( segptr = netsegHeadG[net]->next ; segptr ;
355 segptr = segptr->next ) {
356 if( segptr->switchvalue != nswLINE ) {
357 swLsegptrS[ ++j ] = segptr ;
358 }
359 }
360 }
361 }
362
363
cglbroute()364 void cglbroute()
365 {
366
367 SEGBOXPTR segptr ;
368 PINBOXPTR ptr1 , ptr2 ;
369 HCAPPTR hcaptr , denptr , headptr ;
370 INT trys , maxtrys ;
371 INT i , h , k , nh , nk , luck ;
372 INT intersect_max , cover_allmax ;
373 INT lowH , highH , startH , endH , lowV , highV ;
374 INT vt_beg , vt_end , nvt_beg , nvt_end ;
375 INT new_SwValue , density ;
376 INT range_one_diff , range_two_diff , diff_here ;
377 INT back_one_diff , back_two_diff , next_one_diff , next_two_diff ;
378 DOUBLE penalty , ctrack_penalty , attperLseg ;
379 DOUBLE penalty_here , penalty_one , penalty_two ;
380
381
382 trys = 0 ;
383 attperLseg = 15.0 ;
384 maxtrys = attperLseg * LswitchsegS ;
385
386 while( ++trys < maxtrys ) {
387 luck = (INT)( (DOUBLE)LswitchsegS * ( (DOUBLE)RAND /
388 (DOUBLE) 0x7fffffff ) ) + 1 ;
389 segptr = swLsegptrS[ luck ] ;
390 ptr1 = segptr->pin1ptr ;
391 ptr2 = segptr->pin2ptr ;
392 lowH = set_node( ptr1->xpos ) ;
393 highH = set_node( ptr2->xpos ) ;
394 lowV = ptr1->row ;
395 highV = ptr2->row ;
396 if( lowH == highH ) {
397 startH = endH = lowH ;
398 } else if( lowH < highH ) {
399 if( node_rightS[lowH] - ptr1->xpos >= svalueS ) {
400 startH = lowH ;
401 } else {
402 startH = lowH + 1 ;
403 }
404 if( node_rightS[highH] - ptr2->xpos <= evalueS ) {
405 endH = highH ;
406 } else {
407 endH = highH - 1 ;
408 }
409 } else {
410 if( node_rightS[highH] - ptr2->xpos >= svalueS ) {
411 startH = highH ;
412 } else {
413 startH = highH + 1 ;
414 }
415 if( node_rightS[lowH] - ptr1->xpos <= evalueS ) {
416 endH = lowH ;
417 } else {
418 endH = lowH - 1 ;
419 }
420 }
421 if( segptr->switchvalue == swL_up ) {
422 h = lowH ;
423 k = highV ;
424 nh = highH ;
425 nk = lowV ;
426 new_SwValue = swL_down ;
427 if( ptr1->pinloc >= NEITHER ) {
428 vt_beg = lowV + 1 ;
429 if( segptr->flag || ptr1->row == 0 ) {
430 nvt_beg = lowV + 1 ;
431 } else {
432 nvt_beg = lowV ;
433 }
434 } else if( ptr1->row == 0 ) {
435 vt_beg = lowV + 1 ;
436 nvt_beg = lowV + 1 ;
437 } else {
438 vt_beg = lowV ;
439 nvt_beg = lowV ;
440 }
441 if( ptr2->pinloc <= NEITHER ) {
442 if( segptr->flag || ptr2->row == numChansG ) {
443 vt_end = highV - 1 ;
444 } else {
445 vt_end = highV ;
446 }
447 nvt_end = highV - 1 ;
448 } else if( ptr2->row == numChansG ) {
449 vt_end = highV - 1 ;
450 nvt_end = highV - 1 ;
451 } else {
452 vt_end = highV ;
453 nvt_end = highV ;
454 }
455
456 } else {
457 h = highH ;
458 k = lowV ;
459 nh = lowH ;
460 nk = highV ;
461 new_SwValue = swL_up ;
462 if( ptr1->pinloc >= NEITHER ) {
463 if( segptr->flag || ptr1->row == 0 ) {
464 vt_beg = lowV + 1 ;
465 } else {
466 vt_beg = lowV ;
467 }
468 nvt_beg = lowV + 1 ;
469 } else if( ptr1->row == 0 ) {
470 vt_beg = lowV + 1 ;
471 nvt_beg = lowV + 1 ;
472 } else {
473 vt_beg = lowV ;
474 nvt_beg = lowV ;
475 }
476 if( ptr2->pinloc <= NEITHER ) {
477 vt_end = highV - 1 ;
478 if( segptr->flag || ptr2->row == numChansG ) {
479 nvt_end = highV - 1 ;
480 } else {
481 nvt_end = highV ;
482 }
483 } else if( ptr2->row == numChansG ) {
484 vt_end = highV - 1 ;
485 nvt_end = highV - 1 ;
486 } else {
487 vt_end = highV ;
488 nvt_end = highV ;
489 }
490 }
491 if( 1 <= k && k <= numRowsG ) {
492 cover_allmax = TRUE ;
493 for( hcaptr = entryptS[k][ crowdmaxS[k] ]->next ;
494 hcaptr != NULL ; hcaptr = hcaptr->next ) {
495 if( !( startH <= hcaptr->x_coord &&
496 hcaptr->x_coord <= endH ) ) {
497 cover_allmax = FALSE ;
498 break ;
499 }
500 }
501 } else {
502 cover_allmax = FALSE ;
503 }
504
505 intersect_max = FALSE ;
506 if( 1 <= nk && nk <= numRowsG ) {
507 for( i = startH ; i <= endH ; i++ ) {
508 if( HcapacityS[nk][i]->density == crowdmaxS[nk] ) {
509 intersect_max = TRUE ;
510 break ;
511 }
512 }
513 }
514 penalty_here = 0.0 ;
515 penalty_one = 0.0 ;
516 penalty_two = 0.0 ;
517 for( i = vt_beg ; i <= vt_end ; i++ ) {
518 diff_here = feedpptrG[i][h]->actual - feedpptrG[i][h]->needed ;
519 if( diff_here < 0 ) {
520 penalty_here-- ;
521 }
522 if( h > 2 ) {
523 back_two_diff = feedpptrG[i][h-2]->actual
524 - feedpptrG[i][h-2]->needed ;
525 back_one_diff = feedpptrG[i][h-1]->actual
526 - feedpptrG[i][h-1]->needed ;
527 } else if( h == 2 ) {
528 back_two_diff = 0 ;
529 back_one_diff = feedpptrG[i][h-1]->actual
530 - feedpptrG[i][h-1]->needed ;
531 } else {
532 back_two_diff = 0 ;
533 back_one_diff = 0 ;
534 }
535 if( h <= chan_node_noG - 2 ) {
536 next_two_diff = feedpptrG[i][h+2]->actual
537 - feedpptrG[i][h+2]->needed ;
538 next_one_diff = feedpptrG[i][h+1]->actual
539 - feedpptrG[i][h+1]->needed ;
540 } else if( h == chan_node_noG - 1 ) {
541 next_two_diff = 0 ;
542 next_one_diff = feedpptrG[i][h+1]->actual
543 - feedpptrG[i][h+1]->needed ;
544 } else {
545 next_two_diff = 0 ;
546 next_one_diff = 0 ;
547 }
548 range_one_diff = diff_here + back_one_diff + next_one_diff ;
549 range_two_diff = range_one_diff + back_two_diff + next_two_diff;
550 if( range_one_diff < 0 ) {
551 penalty_one-- ;
552 }
553 if( range_two_diff < 0 ) {
554 penalty_two-- ;
555 }
556 feedpptrG[i][h]->needed-- ;
557 }
558 for( i = nvt_beg ; i <= nvt_end ; i++ ) {
559 feedpptrG[i][nh]->needed++ ;
560 diff_here = feedpptrG[i][nh]->actual - feedpptrG[i][nh]->needed ;
561 if( diff_here < 0 ) {
562 penalty_here++ ;
563 }
564 if( nh > 2 ) {
565 back_two_diff = feedpptrG[i][nh-2]->actual
566 - feedpptrG[i][nh-2]->needed ;
567 back_one_diff = feedpptrG[i][nh-1]->actual
568 - feedpptrG[i][nh-1]->needed ;
569 } else if( nh == 2 ) {
570 back_two_diff = 0 ;
571 back_one_diff = feedpptrG[i][nh-1]->actual
572 - feedpptrG[i][nh-1]->needed ;
573 } else {
574 back_two_diff = 0 ;
575 back_one_diff = 0 ;
576 }
577 if( nh <= chan_node_noG - 2 ) {
578 next_two_diff = feedpptrG[i][nh+2]->actual
579 - feedpptrG[i][nh+2]->needed ;
580 next_one_diff = feedpptrG[i][nh+1]->actual
581 - feedpptrG[i][nh+1]->needed ;
582 } else if( nh == chan_node_noG - 1 ) {
583 next_two_diff = 0 ;
584 next_one_diff = feedpptrG[i][nh+1]->actual
585 - feedpptrG[i][nh+1]->needed ;
586 } else {
587 next_two_diff = 0 ;
588 next_one_diff = 0 ;
589 }
590 range_one_diff = diff_here + back_one_diff + next_one_diff ;
591 range_two_diff = range_one_diff + back_two_diff + next_two_diff;
592 if( range_one_diff < 0 ) {
593 penalty_one++ ;
594 }
595 if( range_two_diff < 0 ) {
596 penalty_two++ ;
597 }
598 }
599 if( cover_allmax && intersect_max ) {
600 ctrack_penalty = crowdmaxS[nk] - crowdmaxS[k] ;
601 } else if( cover_allmax && !intersect_max ) {
602 ctrack_penalty = -1 ;
603 } else if( !cover_allmax && intersect_max ) {
604 ctrack_penalty = 1 ;
605 } else {
606 ctrack_penalty = 0 ;
607 }
608
609 penalty = ctrackContS * ctrack_penalty + factor_hereS * penalty_here
610 + factor_oneS * penalty_one + factor_twoS * penalty_two ;
611 if( penalty <= 0 ) {
612 if( 1 <= k && k <= numRowsG ) {
613 for( i = startH ; i <= endH ; i++ ) {
614 denptr = HcapacityS[k][i] ;
615 if( denptr->next != NULL ) {
616 denptr->next->prev = denptr->prev ;
617 }
618 denptr->prev->next = denptr->next ;
619 density = --denptr->density ;
620
621 headptr = entryptS[k][density] ;
622 if( headptr->next != NULL ) {
623 denptr->next = headptr->next ;
624 denptr->next->prev = denptr ;
625 denptr->prev = headptr ;
626 headptr->next = denptr ;
627 } else {
628 headptr->next = denptr ;
629 denptr->prev = headptr ;
630 denptr->next = NULL ;
631 }
632 }
633 if( cover_allmax ) {
634 crowdmaxS[k]-- ;
635 }
636 }
637 if( 1 <= nk && nk <= numRowsG ) {
638 for( i = startH ; i <= endH ; i++ ) {
639 denptr = HcapacityS[nk][i] ;
640 if( denptr->next != NULL ) {
641 denptr->next->prev = denptr->prev ;
642 }
643 denptr->prev->next = denptr->next ;
644 density = ++denptr->density ;
645
646 // Need to check bounds and reallocate if density has
647 // exceeded OVERHEAD. This should be quite rare.
648
649 if (density >= entrysizeS)
650 {
651 INT row, j;
652
653 for( row = 1 ; row <= numRowsG ; row++ ) {
654 entryptS[row] = (HCAPPTR *)Ysafe_realloc( entryptS[row],
655 ( entrysizeS + OVERHEAD_DELTA + 1 ) * sizeof( HCAPPTR )) ;
656 for( j = entrysizeS + 1; j <= entrysizeS + OVERHEAD_DELTA ; j++ ) {
657 entryptS[row][j] = (HCAPPTR)Ysafe_calloc( 1,sizeof(HCAPBOX)) ;
658 }
659 }
660 entrysizeS += OVERHEAD_DELTA;
661 }
662
663 headptr = entryptS[nk][density] ;
664 if( headptr->next != NULL ) {
665 denptr->next = headptr->next ;
666 denptr->next->prev = denptr ;
667 denptr->prev = headptr ;
668 headptr->next = denptr ;
669 } else {
670 headptr->next = denptr ;
671 denptr->prev = headptr ;
672 denptr->next = NULL ;
673 }
674 }
675 if( intersect_max ) {
676 crowdmaxS[nk]++ ;
677 }
678 }
679 segptr->switchvalue = new_SwValue ;
680 } else {
681 for( i = vt_beg ; i <= vt_end ; i++ ) {
682 feedpptrG[i][h]->needed++ ;
683 }
684 for( i = nvt_beg ; i <= nvt_end ; i++ ) {
685 feedpptrG[i][nh]->needed-- ;
686 }
687 }
688 }
689 }
690
691
free_cglb_initial()692 void free_cglb_initial()
693 {
694 INT i , j , last_j , row ;
695
696 Ysafe_free( node_rightS ) ;
697 for( i = 1 ; i <= numRowsG ; i++ ) {
698 for( j = 1 ; j <= chan_node_noG ; j++ ) {
699 Ysafe_free( HcapacityS[i][j] ) ;
700 }
701 Ysafe_free( HcapacityS[i] ) ;
702 }
703 Ysafe_free( HcapacityS ) ;
704 Ysafe_free( crowdmaxS ) ;
705 for( row = 1 ; row <= numRowsG ; row++ ) {
706 for( j = 0 ; j <= entrysizeS ; j++ ) {
707 Ysafe_free( entryptS[row][j] ) ;
708 }
709 Ysafe_free( entryptS[row] ) ;
710 }
711 Ysafe_free( entryptS ) ;
712 Ysafe_free( swLsegptrS ) ;
713 }
714
715
reinitial_Hdensity()716 void reinitial_Hdensity()
717 {
718
719 INT i , j ;
720
721 for( i = 1 ; i <= numRowsG ; i++ ) {
722 for( j = 1 ; j <= chan_node_noG ; j++ ) {
723 HcapacityS[i][j]->density = 0 ;
724 }
725 }
726 }
727
728
update_switchvalue()729 void update_switchvalue()
730 {
731
732 INT net , x , tilted_seg ;
733 PINBOXPTR ptr1 , ptr2 , netptr ;
734 SEGBOXPTR segptr ;
735
736 LswitchsegS = 0 ;
737 tilted_seg = 0 ;
738 for( net = 1 ; net <= numnetsG ; net++ ) {
739 for( netptr = steinerHeadG[net]->next;netptr; netptr = netptr->next ){
740 netptr->xpos = tearrayG[ netptr->newx ]->xpos ;
741 /* update the steiner poINT position according
742 to the reference pin position. */
743 }
744 for( segptr = netsegHeadG[net]->next ; segptr ;
745 segptr = segptr->next ) {
746 ptr1 = segptr->pin1ptr ;
747 ptr2 = segptr->pin2ptr ;
748 x = ABS( ptr1->xpos - ptr2->xpos ) ;
749 if( ptr1->row != ptr2->row ) {
750 if( add_Lcorner_feedG && x >= average_feed_sepG ) {
751 segptr->flag = FALSE ;
752 if( segptr->switchvalue == nswLINE ) {
753 segptr->switchvalue = swL_up ;
754 }
755 } else {
756 segptr->flag = TRUE ;
757 /* if( x >= average_feed_sep ) { */
758 if( x ) {
759 if( segptr->switchvalue == nswLINE ) {
760 segptr->switchvalue = swL_up ;
761 }
762 } else {
763 segptr->switchvalue = nswLINE ;
764 }
765 }
766 ++tilted_seg ;
767 } else if( ABS( ptr1->pinloc - ptr2->pinloc ) > 1 ) {
768 segptr->flag = FALSE ;
769 if( x >= average_feed_sepG ) {
770 if( segptr->switchvalue == nswLINE ) {
771 segptr->switchvalue = swL_up ;
772 }
773 } else {
774 segptr->switchvalue = nswLINE ;
775 }
776 } else {
777 segptr->flag = TRUE ;
778 segptr->switchvalue = nswLINE ;
779 }
780 if( segptr->switchvalue != nswLINE ) {
781 swLsegptrS[ ++LswitchsegS ] = segptr ;
782 }
783 }
784 }
785 fprintf(fpoG," the number of tilted segment = %d\n", tilted_seg ) ;
786 fprintf(fpoG," the number of switchable L segment = %d\n", LswitchsegS );
787 }
788
789
rebuild_cbucket()790 void rebuild_cbucket()
791 {
792 INT row , j , last_j ;
793 HCAPPTR hcaptr , headptr ;
794
795 for( row = 1 ; row <= numRowsG ; row++ ) {
796 crowdmaxS[row] = 0 ;
797 for( j = 0 ; j <= entrysizeS ; j++ ) {
798 entryptS[row][j]->next = NULL ;
799 }
800 }
801 for( row = 1 ; row <= numRowsG ; row++ ) {
802 for( j = 1 ; j <= chan_node_noG ; j++ ) {
803 hcaptr = HcapacityS[row][j] ;
804
805 // Watch for density exceeding OVERHEAD and increase
806 // array sizes accordingly.
807
808 if (hcaptr->density > entrysizeS) {
809 INT lrow, k;
810
811 for( lrow = 1 ; lrow <= numRowsG ; lrow++ ) {
812 entryptS[lrow] = (HCAPPTR *)Ysafe_realloc( entryptS[lrow],
813 ( entrysizeS + OVERHEAD_DELTA + 1 ) * sizeof( HCAPPTR )) ;
814 for( k = entrysizeS + 1; k <= entrysizeS + OVERHEAD_DELTA ; k++ ) {
815 entryptS[lrow][k] = (HCAPPTR)Ysafe_calloc( 1,sizeof(HCAPBOX)) ;
816 }
817 }
818 entrysizeS += OVERHEAD_DELTA;
819 }
820
821 headptr = entryptS[row][ hcaptr->density ] ;
822 if( headptr->next != NULL ) {
823 hcaptr->next = headptr->next ;
824 hcaptr->next->prev = hcaptr ;
825 hcaptr->prev = headptr ;
826 headptr->next = hcaptr ;
827 } else {
828 headptr->next = hcaptr ;
829 hcaptr->prev = headptr ;
830 hcaptr->next = NULL ;
831 }
832 if( hcaptr->density > crowdmaxS[row] ) {
833 crowdmaxS[row] = hcaptr->density ;
834 }
835 }
836 }
837 }
838
839
840 #ifdef DEBUG
check_cbucket()841 void check_cbucket()
842 {
843 INT row, j ;
844 HCAPPTR dptr , denptr ;
845
846 for( row = 1 ; row <= numRowsG ; row++ ) {
847 for( j = 1 ; j <= chan_node_noG ; j++ ) {
848 denptr = HcapacityS[row][j] ;
849 for( dptr = entryptS[row][denptr->density]->next ;
850 dptr ; dptr = dptr->next ) {
851 if( dptr == denptr ) {
852 break ;
853 }
854 }
855 if( dptr == NULL ) {
856 printf(" something is going wrong\n" ) ;
857 abort() ;
858 }
859 }
860 }
861 }
862
print_bucket(row)863 print_bucket( row )
864 INT row ;
865 {
866 INT j ;
867 HCAPPTR denptr ;
868 FILE *fp ;
869
870 fp = TWOPEN("bucket.dat", "a", ABORT ) ;
871 fprintf(fp, "\n ROW = %d\n", row ) ;
872 fprintf(fp, " sizeof densitybox = %d\n", sizeof(HCAPBOX) ) ;
873 fprintf(fp, " %d %d\n", HcapacityS[row][1], HcapacityS[row][2] ) ;
874 fprintf(fp," density cbin denptr nextptr prevptr\n" ) ;
875 for( j = 1 ; j <= chan_node_noG ; j++ ) {
876 denptr = HcapacityS[row][j] ;
877 fprintf(fp," %7d %5d %12x %12x %12x\n", denptr->density,
878 denptr->x_coord, denptr, denptr->next, denptr->prev ) ;
879 }
880 fprintf(fp,"\n\n" ) ;
881 for( j = crowdmaxS[row] ; j >= 0 ; j-- ) {
882 denptr = entryptS[row][j]->next ;
883 if( denptr == NULL ) continue ;
884 fprintf(fp,"\n denptr density x_coord\n" ) ;
885 for( ; denptr ; denptr = denptr->next ) {
886 fprintf(fp, " %12x %7d %7d\n",
887 denptr, denptr->density, denptr->x_coord ) ;
888 }
889 }
890 TWCLOSE(fp) ;
891 }
892 #endif
893