1 /*
2 * Copyright (C) 1989-1991 Yale University
3 * Copyright (C) 2013 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: coarseglb.c
43 DESCRIPTION:coarse global router code.
44 CONTENTS: coarseglb()
45 assign_row_to_pin()
46 set_up_grid( )
47 initialize_feed_need()
48 feed_config( )
49 set_node( x )
50 INT x ;
51 compute_feed_diff( iteration )
52 INT iteration ;
53 space_for_feed( )
54 update_feed_config( iteration )
55 INT iteration ;
56 no_of_feedthru_cells()
57 addin_feedcell()
58 final_feed_config( )
59 free_cglb_data()
60 DATE: Mar 27, 1989
61 REVISIONS: Aug 27, 1990 - modified shift so it only shifts if not
62 enough room for pads.
63 ----------------------------------------------------------------- */
64
65 #include "standard.h"
66 #include "groute.h"
67 #include "main.h"
68 #include "feeds.h"
69 #include "parser.h"
70 #include "pads.h"
71 #include "readpar.h"
72
73 /* static definitions */
74 static INT *accumulate_feedS , *feed_diffS , *diff_in_rowfeedS ;
75 static INT *feed_shortS , half_hzsepS , right_Pads_left_edgeS ;
76 INT set_node(INT x );
77
78 /* local functions */
79 static int space_for_feed(void);
80 void set_up_grid( );
81 void initialize_feed_need();
82 void feed_config( );
83 void compute_feed_diff( INT iteration );
84 void update_feed_config( INT iteration );
85 INT no_of_feedthru_cells();
86 void addin_feedcell();
87 void final_feed_config();
88 void free_cglb_data();
89
90 /* global definitions */
91 INT longest_row_lengthG ;
92
93 /* global references */
94 extern INT add_Lcorner_feedG ;
95 extern INT extra_cellsG ;
96 extern INT actual_feed_thru_cells_addedG ;
97 extern BOOL no_feed_at_endG ;
98 extern BOOL ignore_feedsG ;
99
coarseglb()100 void coarseglb()
101 {
102
103 INT shift ;
104 INT iteration = 0 ;
105
106 void assign_row_to_pin() ;
107 if( case_unequiv_pinG ) {
108 unequiv_pin_pre_processing() ;
109 }
110 set_up_grid( ) ; /* set up the bin for coarse global routing */
111 buildimp( ) ; /* link up all the implicit feed through pins */
112 feedest( ) ; /* estimate the number of feed needed in a row */
113 printf(" building the steiner trees\n" ) ;
114 steiner( ) ; /* make steiner tree for all pins in the same net */
115 feed_config( ) ; /* compute the needed and actual available feed
116 through pins in each bins */
117 cglb_initial( ) ; /* set up some parameter values */
118 proj_tree_to_grid( ) ;
119 set_cbucket( ) ;
120
121 if( SGGRG ) {
122 seagate_input() ;
123 return ; /* finished with this func. if SGR is to be used */
124 }
125 #define EVEN_ROW
126 #ifdef EVEN_ROW
127 cglbroute() ;
128 compute_feed_diff(1) ;
129 rowevener() ;
130 printf(" rebuilding the steiner tree\n" ) ;
131 redo_steiner() ;
132 initialize_feed_need() ;
133 reinitial_Hdensity() ;
134 update_switchvalue() ;
135 proj_tree_to_grid() ;
136 rebuild_cbucket() ;
137 #endif
138
139 printf( "\n----start doing coarse global routing ------ \n") ;
140 while(1) {
141 printf(" ITERATION %2d\n", ++iteration ) ;
142 cglbroute() ;
143 compute_feed_diff( iteration ) ;
144 shift = space_for_feed( ) ;
145 if( shift ) {
146 update_feed_config(iteration) ;
147 reinitial_Hdensity() ;
148 update_switchvalue() ;
149 proj_tree_to_grid() ;
150 rebuild_cbucket() ;
151 } else {
152 break ;
153 }
154 }
155 free_cglb_initial( ) ;
156 fdthrusG = no_of_feedthru_cells( ) ;
157 fixwolf() ;
158 addin_feedcell() ;
159 final_feed_config( ) ;
160 free_cglb_data( ) ;
161
162 }
163
164
assign_row_to_pin()165 void assign_row_to_pin()
166 {
167
168 CBOXPTR cellptr ;
169 PINBOXPTR pinptr ;
170 INT i , block ;
171
172 for( i = 1 ; i <= numcellsG ; i++ ) {
173 cellptr = carrayG[i] ;
174 block = cellptr->cblock ;
175 for( pinptr = cellptr->pins; pinptr ; pinptr = pinptr->nextpin ){
176 pinptr->row = block ;
177 }
178 }
179 }
180
181
182
set_up_grid()183 void set_up_grid( )
184 {
185
186 INT i , j , x , row_rite ;
187 INT left, right, bottom, top ;
188 INT row , cell , last_cell , class ;
189 INT curr_row_rite , max_desire, prev_row_rite , padside ;
190 TIBOXPTR tptr ;
191
192 numChansG = numRowsG + 1 ;
193 accumulate_feedS = (INT *)Ysafe_malloc( numChansG * sizeof(INT) ) ;
194 /* set up the grid points in each rows for coarse routing */
195
196 if( average_pin_sepG <= 3.25 * average_pin_sepG ) {
197 hznode_sepG = 2.3 * average_feed_sepG ;
198 } else {
199 hznode_sepG = 7.5 * average_pin_sepG ;
200 }
201 /* horizontal node separation */
202 half_hzsepS = hznode_sepG / 2 ;
203 blk_most_leftG = barrayG[1]->bxcenter + barrayG[1]->bleft ;
204 for( row = 2 ; row <= numRowsG ; row++ ) {
205 if( barrayG[row]->bxcenter + barrayG[row]->bleft < blk_most_leftG ) {
206 blk_most_leftG = barrayG[row]->bxcenter + barrayG[row]->bleft ;
207 }
208 }
209
210 blk_most_riteG = 0 ;
211 for( row = 1 ; row <= numRowsG ; row++ ) {
212 last_cell = pairArrayG[row][ pairArrayG[row][0] ] ;
213 row_rite = carrayG[ last_cell ]->cxcenter
214 + carrayG[ last_cell ]->tileptr->right ;
215 if( row_rite > blk_most_riteG ) {
216 blk_most_riteG = row_rite ;
217 }
218 }
219 max_desire = barrayG[1]->desire ;
220 for( row = 2 ; row <= numRowsG ; row++ ) {
221 if( max_desire < barrayG[row]->desire ) {
222 max_desire = barrayG[row]->desire ;
223 }
224 }
225 if( blk_most_riteG - blk_most_leftG >= max_desire ) {
226 chan_node_noG = ( blk_most_riteG - blk_most_leftG) / hznode_sepG + 1 ;
227 chan_node_noG += chan_node_noG ;
228 } else {
229 chan_node_noG = max_desire / hznode_sepG + 1 ;
230 chan_node_noG += chan_node_noG ;
231 }
232 /* chan_node_noG is the number of horizontal edges in each row.
233 Make one more node in case the row length is longer
234 because of feedthrough cells add in */
235
236 feedpptrG = (FEED_DATA **)Ysafe_malloc(
237 numChansG * sizeof(FEED_DATA *) );
238 for( i = 1 ; i <= numRowsG ; i++ ) {
239 feedpptrG[i] = (FEED_DATA *) Ysafe_malloc(
240 ( chan_node_noG + 1 ) * sizeof( FEED_DATA ) ) ;
241 for( j = 1 ; j <= chan_node_noG ; j++ ) {
242 feedpptrG[i][j] = (FEED_DATA)Ysafe_calloc( 1,sizeof(FEED_DBOX) ) ;
243 }
244 }
245 diff_in_rowfeedS = (INT *)Ysafe_malloc( numChansG * sizeof(INT) ) ;
246 feed_diffS = (INT *)Ysafe_calloc( chan_node_noG + 1, sizeof( INT )) ;
247 fdcel_addedG = (INT *)Ysafe_calloc( numChansG, sizeof( INT ) ) ;
248 feed_shortS = (INT *)Ysafe_calloc( numChansG, sizeof( INT ) ) ;
249 fdcel_needG = (INT **)Ysafe_calloc( numChansG, sizeof(INT *) );
250 for( i = 1 ; i <= numRowsG ; i++ ) {
251 fdcel_needG[i] = (INT *)Ysafe_calloc( chan_node_noG+1, sizeof(INT) ) ;
252 }
253
254 /* in order to take care of the circuits with
255 macros we need to do the following */
256 row_rite_classG = (INT *) Ysafe_malloc( numChansG * sizeof(INT) ) ;
257 right_most_in_classG = (INT *)Ysafe_malloc( numChansG * sizeof(INT) ) ;
258 class = 0 ;
259 prev_row_rite = -1 ;
260 row_rite_classG[1] = class ;
261 for( row = 1 ; row <= numRowsG ; row++ ) {
262 curr_row_rite = barrayG[row]->bxcenter
263 + barrayG[row]->bleft + barrayG[row]->desire ;
264 if( curr_row_rite == prev_row_rite ) {
265 row_rite_classG[row] = class ;
266 } else {
267 row_rite_classG[row] = ++class ;
268 prev_row_rite = curr_row_rite ;
269 }
270 }
271 right_Pads_left_edgeS = INFINITY ;
272 for( cell = numcellsG + 1 ; cell <= lastpadG ; cell++ ) {
273 padside = carrayG[cell]->padptr->padside ;
274 if( padside == R ) {
275 tptr = carrayG[cell]->tileptr ;
276 left = tptr->left ;
277 right = tptr->right ;
278 bottom = tptr->bottom ;
279 top = tptr->top ;
280 YtranslateT( &left, &bottom, &right, &top, (INT)carrayG[cell]->corient ) ;
281 x = carrayG[cell]->cxcenter + left ;
282 if( x < right_Pads_left_edgeS ) {
283 right_Pads_left_edgeS = x ;
284 }
285 }
286 }
287 }
288
initialize_feed_need()289 void initialize_feed_need()
290 {
291
292 INT i , row ;
293 FEED_DATA *feedptr ;
294
295 for( row = 1 ; row <= numRowsG ; row++ ) {
296 fdcel_addedG[row] = 0 ;
297 feedptr = feedpptrG[row] ;
298 for( i = 1 ; i <= chan_node_noG ; i++ ) {
299 feedptr[i]->needed = 0 ;
300 feedptr[i]->actual = 0 ;
301 }
302 }
303 feed_config() ;
304 }
305
306
feed_config()307 void feed_config( )
308 {
309
310 INT row , cell , cxcenter , k ;
311 CBOXPTR cellptr ;
312 IPBOXPTR imptr ;
313
314 for( cell = 1 ; cell <= numcellsG ; cell++ ) {
315 cellptr = carrayG[ cell ] ;
316 cxcenter = cellptr->cxcenter ;
317 row = cellptr->cblock ;
318 for( imptr = cellptr->imptr ; imptr ; imptr = imptr->next ) {
319 if( cellptr->corient <= 1 ) {
320 imptr->xpos = cxcenter + imptr->txpos ;
321 } else {
322 if( cellptr->clength % 2 == 0 ) {
323 imptr->xpos = cxcenter - imptr->txpos ;
324 } else {
325 imptr->xpos = cxcenter - imptr->txpos - 1 ;
326 }
327 }
328 k = set_node( imptr->xpos ) ;
329 feedpptrG[row][k]->actual++ ;
330 }
331 }
332 }
333
334
set_node(INT x)335 INT set_node(INT x )
336 {
337
338 DOUBLE h ;
339
340 h = (DOUBLE)( x - blk_most_leftG ) / (DOUBLE)hznode_sepG + 1.5 ;
341 if( h < 1 ) {
342 return( 1 ) ;
343 } else if( h > chan_node_noG ) {
344 return( chan_node_noG ) ;
345 } else {
346 return( (INT)h ) ;
347 }
348 }
349
350
compute_feed_diff(INT iteration)351 void compute_feed_diff( INT iteration )
352 {
353
354 INT i , j , k , range , left_node , rite_node ;
355
356 if( ignore_feedsG || try_not_to_add_explicit_feedsG ) {
357 range = chan_node_noG ;
358 } else if( iteration <= 1 ) {
359 if( add_Lcorner_feedG ) {
360 range = 5 + iteration ;
361 } else {
362 range = iteration ;
363 }
364 } else {
365 range = chan_node_noG ;
366 }
367 for( i = 1 ; i <= numRowsG ; i++ ) {
368 feed_shortS[i] = 0 ;
369 for( j = 1 ; j <= chan_node_noG ; j++ ) {
370 feed_diffS[j] = feedpptrG[i][j]->actual - feedpptrG[i][j]->needed ;
371 feed_shortS[i] -= feed_diffS[j] ;
372 }
373 for( j = 1 ; j <= chan_node_noG ; j++ ) {
374 if( feed_diffS[j] < 0 ) {
375 left_node = rite_node = j ;
376 for( k = 1 ; k <= range ; k++ ) {
377 if( left_node > 1 ) {
378 if( feed_diffS[--left_node] > 0 ) {
379 if( feed_diffS[left_node] + feed_diffS[j] < 0 ) {
380 feed_diffS[j] += feed_diffS[left_node] ;
381 feed_diffS[left_node] = 0 ;
382 } else {
383 feed_diffS[left_node] += feed_diffS[j] ;
384 feed_diffS[j] = 0 ;
385 break ;
386 }
387 }
388 }
389 if( rite_node < chan_node_noG ) {
390 if( feed_diffS[++rite_node] > 0 ) {
391 if( feed_diffS[rite_node] + feed_diffS[j] < 0 ) {
392 feed_diffS[j] += feed_diffS[rite_node] ;
393 feed_diffS[rite_node] = 0 ;
394 } else {
395 feed_diffS[rite_node] += feed_diffS[j] ;
396 feed_diffS[j] = 0 ;
397 break ;
398 }
399 }
400 }
401 }
402 }
403 if( feed_diffS[j] < 0 ) {
404 fdcel_needG[i][j] = - feed_diffS[j] ;
405 } else {
406 fdcel_needG[i][j] = 0 ;
407 }
408 }
409 }
410 }
411
412
space_for_feed(void)413 static int space_for_feed(void)
414 {
415
416 PINBOXPTR pinptr ;
417 CBOXPTR cellptr ;
418 INT row , i , Flag , shiftFlag , *Aray ;
419 INT nodex , node , shift , patch_shift ;
420 INT locFdWidth = fdWidthG;
421
422 // if ( ignore_feedsG ) locFdWidth = 0;
423
424 shiftFlag = 0 ;
425 for( row = 1 ; row <= numRowsG ; row++ ) {
426 Flag = 1 ;
427 Aray = pairArrayG[row] ;
428 accumulate_feedS[row] = 0 ;
429 for( node = 1 ; node <= chan_node_noG ; node++ ) {
430 if( fdcel_needG[row][node] != 0 ) {
431 Flag = 0 ;
432 /* the first position need to add feed thru cell */
433 break ;
434 }
435 }
436 if( Flag ) {
437 continue ; /* no need to add actual feed thru cells */
438 }
439 shiftFlag = 1 ;
440 nodex = blk_most_leftG + ( node - 1 ) * hznode_sepG ;
441 cellptr = carrayG[ pairArrayG[row][ pairArrayG[row][0] ] ] ;
442 if( Aray[0] == 1 ) {
443 patch_shift = locFdWidth * feed_shortS[row] ;
444 cellptr->cxcenter += patch_shift ;
445 for( pinptr = cellptr->pins;pinptr; pinptr = pinptr->nextpin ) {
446 pinptr->xpos += patch_shift ;
447 }
448 fdcel_addedG[row] += feed_shortS[row] ;
449 continue ;
450 }
451 if( nodex >= cellptr->cxcenter ) {
452 if( feed_shortS[row] > 0 ) {
453 patch_shift = locFdWidth * feed_shortS[row] ;
454 cellptr->cxcenter += patch_shift ;
455 for( pinptr = cellptr->pins;pinptr;pinptr=pinptr->nextpin ) {
456 pinptr->xpos += patch_shift ;
457 }
458 fdcel_addedG[row] += feed_shortS[row] ;
459 }
460 continue ;
461 }
462 for( i = 1 ; i <= Aray[0] ; i++ ) {
463 cellptr = carrayG[ Aray[i] ] ;
464 if( cellptr->cxcenter > nodex && cellptr->cclass != -2 ) {
465 break ;
466 }
467 }
468 nodex += hznode_sepG ;
469 for( ; node <= chan_node_noG ; node++ , nodex += hznode_sepG ) {
470 accumulate_feedS[row] += fdcel_needG[row][node] ;
471 shift = accumulate_feedS[row] * locFdWidth ;
472 for( ; i <= Aray[0] ; i++ ) {
473 cellptr = carrayG[ Aray[i] ] ;
474 if( cellptr->cclass == -3 ) {
475 break ;
476 } else if( cellptr->cxcenter < nodex ) {
477 cellptr->cxcenter += shift ;
478 for( pinptr=cellptr->pins;pinptr;pinptr=pinptr->nextpin ){
479 pinptr->xpos += shift ;
480 }
481 } else {
482 break ;
483 }
484 }
485 if( i > Aray[0] ) {
486 break ;
487 }
488 }
489 for( ; i <= Aray[0] ; i++ ) {
490 carrayG[ Aray[i] ]->cxcenter += shift ;
491 for( pinptr = carrayG[ Aray[i] ]->pins ;pinptr;
492 pinptr = pinptr->nextpin ) {
493 pinptr->xpos += shift ;
494 }
495 }
496 if( feed_shortS[row] > accumulate_feedS[row] ) {
497 patch_shift = locFdWidth *
498 ( feed_shortS[row] - accumulate_feedS[row] ) ;
499 if( carrayG[ Aray[ Aray[0] ] ]->cclass == -3 ) {
500 for( i = Aray[0] - 1 ; i >= 1 ; i-- ) {
501 if( carrayG[ Aray[i] ]->cclass != -3 ) {
502 i++ ;
503 break ;
504 }
505 }
506 } else {
507 i = Aray[0] ;
508 }
509 for( ; i <= Aray[0] ; i++ ) {
510 cellptr = carrayG[ Aray[i] ] ;
511 cellptr->cxcenter += patch_shift ;
512 for( pinptr = cellptr->pins;pinptr;pinptr=pinptr->nextpin ) {
513 pinptr->xpos += patch_shift ;
514 }
515 }
516
517 fdcel_addedG[row] += feed_shortS[row] ;
518 } else {
519 fdcel_addedG[row] += accumulate_feedS[row] ;
520 }
521 }
522
523 /* added by Carl 12/7/91 */
524 for( row = 1 ; row <= numRowsG ; row++ ) {
525 if( fdcel_addedG[row] < 0 ) {
526 fdcel_addedG[row] = 0 ;
527 }
528 }
529 /* added by Carl 12/7/91 */
530
531 return( shiftFlag ) ;
532 }
533
534
update_feed_config(INT iteration)535 void update_feed_config( INT iteration )
536 {
537
538 INT cell , padside , shift ;
539 INT *Aray , i , k , row , row_left , row_rite ;
540 INT last , orient , curr_rite , next_left , lastcell_rite ;
541 INT feedx , last_feedx , first_cell_left ;
542 CBOXPTR cellptr , nextptr , currptr ;
543 PINBOXPTR pin ;
544 FEED_DATA *feedptr ;
545 IPBOXPTR imptr ;
546
547 INT locFdWidth = fdWidthG;
548
549 // if ( ignore_feedsG ) locFdWidth = 0;
550
551 /*********************************************************************
552 * if we need to add in feed through cells , we first create a *
553 * gap space between adjacent cells where real feed through cells *
554 * will be placed later on. Thus the new available number of feed *
555 * through cells in each bins will be equal to the number of implicit *
556 * feed through pins in this bin plus the gap space in this bin *
557 * divide by the width of feed through cells. *
558 **********************************************************************/
559 for( row = 1 ; row <= numRowsG ; row++ ) {
560 Aray = pairArrayG[row] ;
561 feedptr = feedpptrG[row] ;
562 for( k = 1 ; k <= chan_node_noG ; k++ ) {
563 feedptr[k]->actual = 0 ;
564 feedptr[k]->needed = 0 ;
565 }
566 currptr = carrayG[ Aray[1] ] ;
567 first_cell_left = currptr->cxcenter + currptr->tileptr->left ;
568 row_left = barrayG[row]->bxcenter + barrayG[row]->bleft ;
569 if( row_left != first_cell_left ) {
570 feedx = row_left + locFdWidth / 2 ;
571 for( ; feedx < first_cell_left ; feedx += locFdWidth ) {
572 k = set_node( feedx ) ;
573 feedptr[k]->actual++ ;
574 }
575 }
576 last = Aray[0] - 1 ;
577 for( i = 1 ; i <= last ; i++ ) {
578 nextptr = carrayG[ Aray[i+1] ] ;
579 orient = currptr->corient ;
580 for( imptr = currptr->imptr ; imptr ; imptr = imptr->next ) {
581 if( orient <= 1 ) {
582 imptr->xpos = currptr->cxcenter + imptr->txpos ;
583 } else {
584 if( currptr->clength % 2 == 0 ) {
585 imptr->xpos = currptr->cxcenter - imptr->txpos ;
586 } else {
587 imptr->xpos = currptr->cxcenter - imptr->txpos - 1 ;
588 }
589 }
590 k = set_node( imptr->xpos ) ;
591 feedptr[k]->actual++ ;
592 }
593 curr_rite = currptr->cxcenter + currptr->tileptr->right ;
594 next_left = nextptr->cxcenter + nextptr->tileptr->left ;
595 if( curr_rite != next_left ) {
596 for( feedx = curr_rite + locFdWidth / 2 ;
597 feedx < next_left ; feedx += locFdWidth ) {
598 k = set_node( feedx ) ;
599 feedptr[k]->actual++ ;
600 }
601 }
602 currptr = nextptr ;
603 }
604 orient = currptr->corient ;
605 for( imptr = currptr->imptr ; imptr ; imptr = imptr->next ) {
606 if( orient <= 1 ) {
607 imptr->xpos = currptr->cxcenter + imptr->txpos ;
608 } else {
609 if( currptr->clength % 2 == 0 ) {
610 imptr->xpos = currptr->cxcenter - imptr->txpos ;
611 } else {
612 imptr->xpos = currptr->cxcenter - imptr->txpos - 1 ;
613 }
614 }
615 k = set_node( imptr->xpos ) ;
616 feedptr[k]->actual++ ;
617 }
618 }
619 blk_most_riteG = 0 ;
620 for( row = 1 ; row <= numRowsG ; row++ ) {
621 cellptr = carrayG[ pairArrayG[row][ pairArrayG[row][0] ] ] ;
622 row_rite = cellptr->cxcenter + cellptr->tileptr->right ;
623 if( row_rite > blk_most_riteG ) {
624 blk_most_riteG = row_rite ;
625 }
626 }
627
628 decide_right_most_in_class() ;
629
630 if( iteration >= 2 && !no_feed_at_endG ) {
631 for( row = 1 ; row <= numRowsG ; row++ ) {
632 cellptr = carrayG[ pairArrayG[row][ pairArrayG[row][0] ] ] ;
633 lastcell_rite = cellptr->cxcenter + cellptr->tileptr->right ;
634 feedx = lastcell_rite + locFdWidth / 2 ;
635 last_feedx = right_most_in_classG[ row_rite_classG[row] ]
636 - ( locFdWidth + 1 ) / 2 ;
637 feedptr = feedpptrG[row] ;
638 for( ; feedx <= last_feedx ; feedx += locFdWidth ) {
639 k = set_node( feedx ) ;
640 feedptr[k]->actual++ ;
641 }
642 }
643 }
644 if( rowsG == 0 && blk_most_riteG >= right_Pads_left_edgeS ) {
645 shift = blk_most_riteG - right_Pads_left_edgeS + 30 ;
646 right_Pads_left_edgeS += shift ;
647
648 for( cell = numcellsG + 1 ; cell <= lastpadG ; cell++ ) {
649 padside = carrayG[cell]->padptr->padside ;
650 if( padside == R || padside == MR ||
651 padside == MUR || padside == MLR ) {
652 carrayG[cell]->cxcenter += shift ;
653
654 for( pin = carrayG[cell]->pins; pin ; pin = pin->nextpin ){
655 pin->xpos += shift ;
656 }
657 }
658 }
659 }
660 }
661
662
no_of_feedthru_cells()663 INT no_of_feedthru_cells()
664 {
665
666 INT i , row , n , difference , lastcell_rite , total_feedthrus ;
667 CBOXPTR cellptr ;
668 FEED_DATA *feedptr ;
669
670 INT locFdWidth = fdWidthG;
671
672 // if (ignore_feedsG) locFdWidth = 0;
673
674 total_feedthrus = 0 ;
675
676 for( row = 1 ; row <= numRowsG ; row++ ) {
677 difference = 0 ;
678 feedptr = feedpptrG[row] ;
679 for( i = 1 ; i <= chan_node_noG ; i++ ) {
680 difference += feedptr[i]->actual - feedptr[i]->needed ;
681 }
682 if( difference < 0 ) {
683 diff_in_rowfeedS[row] = -difference ;
684 if( no_feed_at_endG ) {
685 printf(" not enough feed were added in\n" ) ;
686 exit(0) ;
687 }
688 } else {
689 diff_in_rowfeedS[row] = 0 ;
690 }
691 cellptr = carrayG[ pairArrayG[row][ pairArrayG[row][0] ] ] ;
692 lastcell_rite = cellptr->cxcenter + cellptr->tileptr->right ;
693 if( locFdWidth == 0 || cellptr->cclass == -3 ) {
694 n = 0 ;
695 } else {
696 n = ( right_most_in_classG[ row_rite_classG[row] ]
697 - lastcell_rite ) / locFdWidth ;
698 }
699 total_feedthrus += ( fdcel_addedG[row] + diff_in_rowfeedS[row] + n ) ;
700 }
701 return( total_feedthrus ) ;
702 }
703
704
addin_feedcell()705 void addin_feedcell()
706 {
707
708 INT row , i , k , r , last , feednum , row_left ;
709 INT curr_rite , next_left , half_fdWidthG , feedx , last_feedx ;
710 INT *Aray , *nAray , last_rite_edge , first_cell_left ;
711 CBOXPTR current , nextone , lastptr ;
712
713 INT locFdWidth = fdWidthG;
714
715 // if ( ignore_feedsG ) locFdWidth = 0;
716
717
718 half_fdWidthG = locFdWidth / 2 ;
719 feednum = 0 ;
720 /*
721 fp = TWOPEN( "rowlen.dat" , "a", ABORT ) ;
722 fprintf(fp,"\n the row length after coarse global routing are\n" ) ;
723 fprintf(fp," row row_length desire over/under fdthrus\n" ) ;
724 */
725 for( row = 1 ; row <= numRowsG ; row++ ) {
726 Aray = pairArrayG[row] ;
727 lastptr = carrayG[ Aray[ Aray[0] ] ] ;
728 last_rite_edge = lastptr->cxcenter + lastptr->tileptr->right ;
729
730 if( !no_feed_at_endG ) {
731 r = ( right_most_in_classG[ row_rite_classG[row] ]
732 - last_rite_edge ) / locFdWidth + 1 ;
733 } else {
734 r = 0 ;
735 }
736 /*
737 n = fdcel_addedG[row] + diff_in_rowfeedS[row] ;
738 fprintf(fp," %3d %10d %6d %10d %6d\n", row, last_rite_edge -
739 barrayG[row]->bxcenter - barrayG[row]->bleft ,
740 barrayG[row]->desire, last_rite_edge - barrayG[row]->desire -
741 barrayG[row]->bxcenter - barrayG[row]->bleft , n ) ;
742 */
743 if( fdcel_addedG[row] == 0 ) {
744 if( r > 1 ) {
745 Aray = (INT *)Ysafe_realloc( Aray ,
746 (2 * ( r + Aray[0] + diff_in_rowfeedS[row] + 1 ) +
747 (extra_cellsG / numRowsG) * 4) * sizeof(INT) ) ;
748 feedx = last_rite_edge + half_fdWidthG ;
749 last_feedx = right_most_in_classG[ row_rite_classG[row] ]
750 - ( locFdWidth + 1 ) / 2 ;
751 for( ; feedx <= last_feedx ; feedx += locFdWidth ) {
752 addfeed( row , feedx , ++feednum ) ;
753 Aray[ ++Aray[0] ] = numcellsG + numtermsG + feednum ;
754 }
755 last_feedx += diff_in_rowfeedS[row] * locFdWidth ;
756 for( ; feedx <= last_feedx ; feedx += locFdWidth ) {
757 addfeed( row , feedx , ++feednum ) ;
758 Aray[ ++Aray[0] ] = numcellsG + numtermsG + feednum ;
759 k = set_node( feedx ) ;
760 feedpptrG[row][k]->actual++ ;
761 }
762 }
763 pairArrayG[row] = Aray ;
764 continue ;
765 }
766
767 nAray = (INT *)Ysafe_malloc( (2 * ( Aray[0] + fdcel_addedG[row] +
768 diff_in_rowfeedS[row] + r + 1 )
769 + (extra_cellsG / numRowsG ) * 4 ) * sizeof( INT ) ) ;
770 nAray[0] = 0 ;
771
772 current = carrayG[ Aray[1] ] ;
773 first_cell_left = current->cxcenter + current->tileptr->left ;
774 row_left = barrayG[row]->bxcenter + barrayG[row]->bleft ;
775 if( row_left != first_cell_left ) {
776 feedx = row_left + locFdWidth / 2 ;
777 for( ; feedx < first_cell_left ; feedx += locFdWidth ) {
778 addfeed( row , feedx , ++feednum ) ;
779 nAray[ ++nAray[0] ] = numcellsG + numtermsG + feednum ;
780 }
781 }
782 last = Aray[0] - 1 ;
783 for( i = 1 ; i <= last ; i++ ) {
784 nAray[ ++nAray[0] ] = Aray[i] ;
785 nextone = carrayG[ Aray[i+1] ] ;
786 curr_rite = current->cxcenter + current->tileptr->right ;
787 next_left = nextone->cxcenter + nextone->tileptr->left ;
788 if( curr_rite < next_left ) {
789 feedx = curr_rite + half_fdWidthG ;
790 for( ; feedx < next_left ; feedx += locFdWidth ) {
791 addfeed( row , feedx , ++feednum ) ;
792 nAray[ ++nAray[0] ] = numcellsG + numtermsG + feednum ;
793 }
794 }
795 current = nextone ;
796 }
797 nAray[ ++nAray[0] ] = Aray[ Aray[0] ] ;
798
799 if( !no_feed_at_endG ) {
800 feedx = last_rite_edge + half_fdWidthG ;
801 last_feedx = right_most_in_classG[ row_rite_classG[row] ]
802 - ( locFdWidth + 1 ) / 2;
803 for( ; feedx <= last_feedx ; feedx += locFdWidth ) {
804 addfeed( row , feedx , ++feednum ) ;
805 nAray[ ++nAray[0] ] = numcellsG + numtermsG + feednum ;
806 }
807 last_feedx += diff_in_rowfeedS[row] * locFdWidth ;
808 for( ; feedx <= last_feedx ; feedx += locFdWidth ) {
809 addfeed( row , feedx , ++feednum ) ;
810 nAray[ ++nAray[0] ] = numcellsG + numtermsG + feednum ;
811 k = set_node( feedx ) ;
812 feedpptrG[row][k]->actual++ ;
813 }
814 }
815
816 pairArrayG[row] = nAray ;
817 Ysafe_free( Aray ) ;
818 }
819 actual_feed_thru_cells_addedG = feednum ;
820
821 /* Added by Tim, 8/26/2013 */
822 expand_heat_index();
823
824 /*
825 TWCLOSE(fp) ;
826 */
827 }
828
829
final_feed_config()830 void final_feed_config( )
831 {
832
833 IPBOXPTR imptr ;
834 FEED_DATA *feedptr ;
835 CBOXPTR first_cptr , last_cptr ;
836 INT i , row , longest_row , max_length , k , length , *Aray ;
837 INT delta_row_len ;
838
839 for( row = 1 ; row <= numRowsG ; row++ ) {
840 Aray = pairArrayG[row] ;
841 for( i = 1 ; i <= Aray[0] ; i++ ) {
842 for( imptr = carrayG[ Aray[i] ]->imptr ; imptr ;
843 imptr = imptr->next ) {
844 k = set_node( imptr->xpos ) ;
845 if( feedpptrG[row][k]->firstimp ) {
846 feedpptrG[row][k]->lastimp = imptr ;
847 } else {
848 feedpptrG[row][k]->firstimp = imptr ;
849 feedpptrG[row][k]->lastimp = imptr ;
850 }
851 }
852 }
853 }
854 total_feed_in_the_rowG = (INT *)Ysafe_malloc( numChansG * sizeof(INT) ) ;
855 for( row = 1 ; row <= numRowsG ; row++ ) {
856 k = 0 ;
857 feedptr = feedpptrG[row] ;
858 for( i = 1 ; i <= chan_node_noG ; i++ ) {
859 k += feedptr[i]->actual ;
860 }
861 total_feed_in_the_rowG[row] = k ;
862 }
863
864 fprintf(fpoG,"After Feeds are Added:\n");
865 fprintf(fpoG,"BLOCK TOTAL CELL LENGTHS OVER/UNDER TARGET\n");
866 max_length = 0 ;
867 for( i = 1 ; i <= numRowsG ; i++ ) {
868 Aray = pairArrayG[i] ;
869 first_cptr = carrayG[ Aray[1] ] ;
870 last_cptr = carrayG[ Aray[ Aray[0] ] ] ;
871 length = last_cptr->cxcenter + last_cptr->tileptr->right -
872 first_cptr->cxcenter - first_cptr->tileptr->left ;
873 delta_row_len = length - barrayG[i]->desire ;
874 fprintf( fpoG, "%3d %7d %6d\n", i,
875 length , delta_row_len );
876 if( max_length < length ) {
877 longest_row = i ;
878 max_length = length ;
879 }
880 }
881 fprintf( fpoG, "\nLONGEST Row is:%d Its length is:%d\n",
882 longest_row , max_length ) ;
883 longest_row_lengthG = max_length ;
884 printf("\n longest Row is:%d Its length is:%d\n",
885 longest_row , max_length ) ;
886 }
887
888
free_cglb_data()889 void free_cglb_data()
890 {
891
892 INT i , net ;
893 PINBOXPTR netptr ;
894 ADJASEGPTR adjptr , saveptr ;
895
896
897 for( i = 1 ; i <= numRowsG ; i++ ) {
898 Ysafe_free( fdcel_needG[i] ) ;
899 }
900 Ysafe_free( fdcel_needG ) ;
901 Ysafe_free( fdcel_addedG ) ;
902 Ysafe_free( feed_diffS ) ;
903 Ysafe_free( feed_shortS ) ;
904 Ysafe_free( row_rite_classG) ;
905 Ysafe_free( right_most_in_classG) ;
906 Ysafe_free( accumulate_feedS ) ;
907 Ysafe_free( diff_in_rowfeedS ) ;
908
909 for( net = 1 ; net <= numnetsG ; net++ ) {
910 for( netptr = netarrayG[net]->pins ; netptr ;netptr = netptr->next ) {
911 for( adjptr = netptr->adjptr->next ; adjptr ;
912 adjptr = saveptr ) {
913 saveptr = adjptr->next ;
914 Ysafe_free( adjptr ) ;
915 }
916 netptr->adjptr->next = NULL ;
917 }
918 for( netptr = steinerHeadG[net]->next;netptr;netptr = netptr->next ) {
919 for( adjptr = netptr->adjptr->next ; adjptr ;
920 adjptr = saveptr ) {
921 saveptr = adjptr->next ;
922 Ysafe_free( adjptr ) ;
923 }
924 netptr->adjptr->next = NULL ;
925 }
926 }
927 }
928