1 /*
2 * Copyright (C) 1989-1990 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: crossbus.c
42 DESCRIPTION:cross bus code.
43 CONTENTS: handle_crossbuses()
44 check_violations()
45 reduce_violations()
46 DATE: Mar 27, 1989
47 REVISIONS:
48 ----------------------------------------------------------------- */
49
50 #include "standard.h"
51 #include "main.h"
52 #include "groute.h"
53 #include "pads.h"
54
55 /* global definitions */
56 extern INT left_row_boundaryG ;
57 extern INT row_extentG ;
58 extern BOOL exclude_noncrossbus_padsG ;
59
handle_crossbuses()60 void handle_crossbuses()
61 {
62
63 PINBOXPTR netptr ;
64 FENCEBOXPTR fence , fence2, save_fence , prev_fence ;
65 INT cell , net , process , row_area , area ;
66 INT length , max_x , min_x , max_y , min_y , count , cross_bus ;
67 INT block , x , y , avg_length , left , right ;
68 INT large_pos , large_neg , ro_height , tmp , i ;
69 INT distance , j , save_j , side ;
70 INT *left_pins , *rite_pins , *top_pins , *bot_pins , bound ;
71
72 left_pins = (INT *) Ysafe_malloc( (1 + numtermsG) * sizeof( INT ) ) ;
73 rite_pins = (INT *) Ysafe_malloc( (1 + numtermsG) * sizeof( INT ) ) ;
74 top_pins = (INT *) Ysafe_malloc( (1 + numtermsG) * sizeof( INT ) ) ;
75 bot_pins = (INT *) Ysafe_malloc( (1 + numtermsG) * sizeof( INT ) ) ;
76
77 large_pos = 10000000 ;
78 large_neg = -10000000 ;
79 if( rowHeightG % 2 == 1 ) {
80 ro_height = rowHeightG + 1 ;
81 } else {
82 ro_height = rowHeightG ;
83 }
84
85 for( net = 1 ; net <= numnetsG ; net++ ) {
86 length = 0 ;
87 count = 0 ;
88 process = 0 ;
89 left_pins[0] = 0 ;
90 rite_pins[0] = 0 ;
91 top_pins[0] = 0 ;
92 bot_pins[0] = 0 ;
93 min_x = large_pos ;
94 min_y = large_pos ;
95 max_x = large_neg ;
96 max_y = large_neg ;
97 for( netptr = netarrayG[net]->pins;netptr ; netptr = netptr->next ) {
98 if( netptr->cell > numcellsG ) {
99 process = 1 ;
100 x = carrayG[ netptr->cell ]->cxcenter ;
101 y = carrayG[ netptr->cell ]->cycenter ;
102 if( carrayG[ netptr->cell ]->padptr ){
103 side = carrayG[ netptr->cell ]->padptr->padside ;
104 } else {
105 side = 0 ;
106 }
107 if( side == 1 /* L */ ) {
108 left_pins[ ++left_pins[0] ] = netptr->cell ;
109 } else if( side == 2 /* T */ ) {
110 top_pins[ ++top_pins[0] ] = netptr->cell ;
111 } else if( side == 3 /* R */ ) {
112 rite_pins[ ++rite_pins[0] ] = netptr->cell ;
113 } else if( side == 4 /* B */ ) {
114 bot_pins[ ++bot_pins[0] ] = netptr->cell ;
115 }
116 if( x < min_x ) {
117 min_x = x ;
118 }
119 if( x > max_x ) {
120 max_x = x ;
121 }
122 if( y < min_y ) {
123 min_y = y ;
124 }
125 if( y > max_y ) {
126 max_y = y ;
127 }
128 } else {
129 count++ ;
130 length += carrayG[netptr->cell]->clength ;
131 }
132 } /* close of first pass thru all pins for this net */
133 if( !process ) {
134 continue ;
135 }
136
137 if( count == 0 ) {
138 continue ;
139 }
140 avg_length = length / count ;
141 if( avg_length < (INT) mean_widthG ) {
142 avg_length = (INT) mean_widthG ;
143 }
144 if( avg_length % 2 == 1 ) {
145 avg_length++ ;
146 }
147
148 if( left_pins[0] > 0 && rite_pins[0] > 0 ) {
149 for( i = 1 ; i <= left_pins[0] ; i++ ) {
150 distance = 10000000 ;
151 for( j = 1 ; j <= rite_pins[0] ; j++ ) {
152 if( ABS( carrayG[ left_pins[i] ]->cycenter -
153 carrayG[ rite_pins[j] ]->cycenter) < distance ) {
154 distance = ABS( carrayG[ left_pins[i] ]->cycenter -
155 carrayG[ rite_pins[j] ]->cycenter) ;
156 save_j = j ;
157 }
158 }
159 if( distance <= 5 * ro_height ) {
160 min_y = carrayG[ left_pins[i] ]->cycenter ;
161 max_y = carrayG[ rite_pins[save_j] ]->cycenter ;
162 if( min_y > max_y ) {
163 tmp = min_y ;
164 min_y = max_y ;
165 max_y = tmp ;
166 }
167 bound = 3 * (1 + (count - 1)/2) * ro_height ;
168 /* while( max_y - min_y < 9 * ro_height ) */
169 while( max_y - min_y < bound ) {
170 min_y -= ro_height / 2 ;
171 max_y += ro_height / 2 ;
172 }
173 min_x = carrayG[ left_pins[i] ]->cxcenter ;
174 max_x = carrayG[ rite_pins[save_j] ]->cxcenter ;
175
176 for( netptr = netarrayG[net]->pins ;netptr;
177 netptr = netptr->next ) {
178 if( netptr->cell > numcellsG ) {
179 continue ;
180 }
181 fence = carrayG[netptr->cell]->fence ;
182 carrayG[netptr->cell]->fence = (FENCEBOXPTR)
183 Ysafe_malloc( sizeof(FENCEBOX) ) ;
184 carrayG[netptr->cell]->fence->next_fence = fence ;
185 carrayG[netptr->cell]->fence->min_block = min_y ;
186 carrayG[netptr->cell]->fence->max_block = max_y ;
187 carrayG[netptr->cell]->fence->min_xpos = min_x ;
188 carrayG[netptr->cell]->fence->max_xpos = max_x ;
189 }
190 }
191 }
192 } else if( top_pins[0] > 0 && bot_pins[0] > 0 ) {
193 for( i = 1 ; i <= bot_pins[0] ; i++ ) {
194 distance = 10000000 ;
195 for( j = 1 ; j <= top_pins[0] ; j++ ) {
196 if( ABS( carrayG[ bot_pins[i] ]->cxcenter -
197 carrayG[ top_pins[j] ]->cxcenter) < distance ) {
198 distance = ABS( carrayG[ bot_pins[i] ]->cxcenter -
199 carrayG[ top_pins[j] ]->cxcenter) ;
200 save_j = j ;
201 }
202 }
203 if( distance <= 4 * avg_length ) {
204 min_x = carrayG[ bot_pins[i] ]->cxcenter ;
205 max_x = carrayG[ top_pins[save_j] ]->cxcenter ;
206 if( min_x > max_x ) {
207 tmp = min_x ;
208 min_x = max_x ;
209 max_x = tmp ;
210 }
211 bound = 2 * (2 + (count - 1)/2) * avg_length ;
212 /* while( max_x - min_x < 6 * avg_length ) */
213 while( max_x - min_x < bound ) {
214 min_x -= avg_length / 2 ;
215 max_x += avg_length / 2 ;
216 }
217 min_y = carrayG[ bot_pins[i] ]->cycenter ;
218 max_y = carrayG[ top_pins[save_j] ]->cycenter ;
219
220 netptr = netarrayG[net]->pins ;
221 for( ; netptr ; netptr = netptr->next ) {
222 if( netptr->cell > numcellsG ) {
223 continue ;
224 }
225 fence = carrayG[netptr->cell]->fence ;
226 carrayG[netptr->cell]->fence = (FENCEBOXPTR)
227 Ysafe_malloc( sizeof(FENCEBOX) ) ;
228 carrayG[netptr->cell]->fence->next_fence = fence ;
229 carrayG[netptr->cell]->fence->min_block = min_y ;
230 carrayG[netptr->cell]->fence->max_block = max_y ;
231 carrayG[netptr->cell]->fence->min_xpos = min_x ;
232 carrayG[netptr->cell]->fence->max_xpos = max_x ;
233 }
234 }
235 }
236 } else {
237 if( min_x < left_row_boundaryG ) {
238 min_x = left_row_boundaryG ;
239 }
240 if( min_x > left_row_boundaryG + row_extentG ) {
241 min_x = left_row_boundaryG + row_extentG ;
242 }
243 if( max_x < left_row_boundaryG ) {
244 max_x = left_row_boundaryG ;
245 }
246 if( max_x > left_row_boundaryG + row_extentG ) {
247 max_x = left_row_boundaryG + row_extentG ;
248 }
249 if( min_y < barrayG[1]->bycenter ) {
250 min_y = barrayG[1]->bycenter ;
251 }
252 if( min_y > barrayG[numRowsG]->bycenter ) {
253 min_y = barrayG[numRowsG]->bycenter ;
254 }
255 if( max_y < barrayG[1]->bycenter ) {
256 max_y = barrayG[1]->bycenter ;
257 }
258 if( max_y > barrayG[numRowsG]->bycenter ) {
259 max_y = barrayG[numRowsG]->bycenter ;
260 }
261 min_x -= (3 + (count * 3)) * avg_length ;
262 max_x += (3 + (count * 3)) * avg_length ;
263 min_y -= (3 + (count * 3)) * rowHeightG ;
264 max_y += (3 + (count * 3)) * rowHeightG ;
265
266 netptr = netarrayG[net]->pins ;
267 for( ; netptr ; netptr = netptr->next ) {
268 if( netptr->cell > numcellsG ) {
269 continue ;
270 }
271 fence = carrayG[netptr->cell]->fence ;
272 carrayG[netptr->cell]->fence = (FENCEBOXPTR)
273 Ysafe_malloc( sizeof(FENCEBOX) ) ;
274 carrayG[netptr->cell]->fence->next_fence = fence ;
275 carrayG[netptr->cell]->fence->min_block = min_y ;
276 carrayG[netptr->cell]->fence->max_block = max_y ;
277 carrayG[netptr->cell]->fence->min_xpos = min_x ;
278 carrayG[netptr->cell]->fence->max_xpos = max_x ;
279 }
280 }
281 }
282
283 for( cell = 1 ; cell <= numcellsG ; cell++ ) {
284 fence = carrayG[cell]->fence ;
285 if( !fence ) {
286 continue ;
287 }
288 for( ; fence ; fence = fence->next_fence ) {
289 for( block = 1 ; block <= numRowsG ; block++ ) {
290 if( barrayG[block]->bycenter >= fence->min_block ) {
291 fence->min_block = block ;
292 break ;
293 }
294 }
295 for( block = numRowsG ; block >= 1 ; block-- ) {
296 if( barrayG[block]->bycenter <= fence->max_block ) {
297 fence->max_block = block ;
298 break ;
299 }
300 }
301 }
302 fence = carrayG[cell]->fence ;
303 for( ; fence ; fence = fence->next_fence ) {
304 if( fence->min_xpos < left_row_boundaryG ) {
305 fence->min_xpos = left_row_boundaryG ;
306 }
307 if( fence->max_xpos > left_row_boundaryG + row_extentG ) {
308 fence->max_xpos = left_row_boundaryG + row_extentG ;
309 }
310 }
311 fence = carrayG[cell]->fence ;
312 cross_bus = 0 ;
313 for( ; fence ; fence = fence->next_fence ) {
314 if( (fence->min_xpos <= left_row_boundaryG &&
315 fence->max_xpos >= left_row_boundaryG + row_extentG) ||
316 (fence->min_block <= 1 &&
317 fence->max_block >= numRowsG)){
318 cross_bus = 1 ;
319 break ;
320 }
321 }
322 if( cross_bus ) {
323 fence = carrayG[cell]->fence ;
324 prev_fence = NULL ;
325 for( ; fence ; ) {
326 if( (fence->min_xpos <= left_row_boundaryG &&
327 fence->max_xpos >= left_row_boundaryG +
328 row_extentG) || (fence->min_block <= 1 &&
329 fence->max_block >= numRowsG )){
330 prev_fence = fence ;
331 fence = fence->next_fence ;
332 continue ;
333 }
334 if( prev_fence == NULL ) {
335 carrayG[cell]->fence = fence->next_fence ;
336 Ysafe_free( fence ) ;
337 fence = carrayG[cell]->fence ;
338 } else {
339 prev_fence->next_fence = fence->next_fence ;
340 Ysafe_free( fence ) ;
341 fence = prev_fence->next_fence ;
342 }
343 }
344
345 /* intersecting crossbuses of the same orienation and merge'm */
346 fence = carrayG[cell]->fence ;
347 for( ; fence ; fence = fence->next_fence ) {
348 if( fence->min_block <= 1 && fence->max_block >= numRowsG ){
349 fence2 = fence->next_fence ;
350 prev_fence = fence ;
351 for( ; fence2 ; ) {
352 if( fence2->min_block <= 1 &&
353 fence2->max_block >= numRowsG ){
354 if( fence->min_xpos > fence2->max_xpos ||
355 fence2->min_xpos > fence->max_xpos ) {
356 prev_fence = fence2 ;
357 fence2 = fence2->next_fence ;
358 continue ;
359 }
360 if( fence->min_xpos > fence2->min_xpos ) {
361 fence->min_xpos = fence2->min_xpos ;
362 }
363 if( fence->max_xpos < fence2->max_xpos ) {
364 fence->max_xpos = fence2->max_xpos ;
365 }
366 prev_fence->next_fence = fence2->next_fence ;
367 Ysafe_free( fence2 ) ;
368 fence2 = prev_fence->next_fence ;
369 } else {
370 prev_fence = fence2 ;
371 fence2 = fence2->next_fence ;
372 }
373 }
374 }
375 }
376 fence = carrayG[cell]->fence ;
377 for( ; fence ; fence = fence->next_fence ) {
378 if( fence->min_xpos <= left_row_boundaryG &&
379 fence->max_xpos >= left_row_boundaryG + row_extentG ){
380 fence2 = fence->next_fence ;
381 prev_fence = fence ;
382 for( ; fence2 ; ) {
383 if( fence2->min_xpos <= left_row_boundaryG &&
384 fence2->max_xpos >=
385 left_row_boundaryG + row_extentG ){
386 if( fence->min_block > fence2->max_block ||
387 fence2->min_block > fence->max_block ) {
388 prev_fence = fence2 ;
389 fence2 = fence2->next_fence ;
390 continue ;
391 }
392 if( fence->min_block > fence2->min_block ) {
393 fence->min_block = fence2->min_block ;
394 }
395 if( fence->max_block < fence2->max_block ) {
396 fence->max_block = fence2->max_block ;
397 }
398 prev_fence->next_fence = fence2->next_fence ;
399 Ysafe_free( fence2 ) ;
400 fence2 = prev_fence->next_fence ;
401 } else {
402 prev_fence = fence2 ;
403 fence2 = fence2->next_fence ;
404 }
405 }
406 }
407 }
408 } else { /* keep only largest fence */
409 fence = carrayG[cell]->fence ;
410 row_area = 0 ;
411 for( ; fence ; fence = fence->next_fence ) {
412 left = fence->min_xpos ;
413 if( left < left_row_boundaryG ) {
414 left = left_row_boundaryG ;
415 }
416 right = fence->max_xpos ;
417 if( right > left_row_boundaryG + row_extentG ) {
418 right = left_row_boundaryG + row_extentG ;
419 }
420 area = (right - left) * (fence->max_block -
421 fence->min_block) ;
422 if( area > row_area ) {
423 row_area = area ;
424 save_fence = fence ;
425 }
426 }
427 fence = carrayG[cell]->fence ;
428 prev_fence = NULL ;
429 for( ; fence ; ) {
430 if( fence == save_fence ) {
431 prev_fence = fence ;
432 fence = fence->next_fence ;
433 continue ;
434 }
435 if( prev_fence == NULL ) {
436 carrayG[cell]->fence = fence->next_fence ;
437 Ysafe_free( fence ) ;
438 fence = carrayG[cell]->fence ;
439 } else {
440 prev_fence->next_fence = fence->next_fence ;
441 Ysafe_free( fence ) ;
442 fence = prev_fence->next_fence ;
443 }
444 }
445 if( exclude_noncrossbus_padsG ) {
446 Ysafe_free( carrayG[cell]->fence ) ;
447 carrayG[cell]->fence = NULL ;
448 }
449 }
450 }
451
452 count = 0 ;
453 for( cell = 1 ; cell <= numcellsG ; cell++ ) {
454 fence = carrayG[cell]->fence ;
455 if( fence ) {
456 count++ ;
457 } else {
458 continue ;
459 }
460 /*
461 printf("Constrained Cell #%d:\n ", cell ) ;
462 for( ; fence ; fence = fence->next_fence ) {
463 printf(" X: %5d, %5d R:%3d, %3d\n", fence->min_xpos ,
464 fence->max_xpos ,
465 fence->min_block ,
466 fence->max_block ) ;
467 }
468 printf("\n");
469 */
470 }
471 fprintf(fpoG,"Percentage of constrained cells:%f\n",
472 (DOUBLE) count / (DOUBLE) numcellsG ) ;
473 fflush(stdout);
474 Ysafe_free( left_pins ) ;
475 Ysafe_free( rite_pins ) ;
476 Ysafe_free( top_pins ) ;
477 Ysafe_free( bot_pins ) ;
478
479 return ;
480 }
481
482
483
484
check_violations()485 void check_violations()
486 {
487
488 FENCEBOXPTR fence ;
489 INT cell , total_r , total_l , x , error , row_error ;
490 INT max_x , min_x , row , min_block , max_block ;
491 INT r_error ;
492
493 total_r = 0 ;
494 total_l = 0 ;
495 for( cell = 1 ; cell <= numcellsG ; cell++ ) {
496 fence = carrayG[cell]->fence ;
497 if( !fence ) {
498 continue ;
499 }
500 x = carrayG[cell]->cxcenter ;
501 row = carrayG[cell]->cblock ;
502 error = 10000000 ;
503 row_error = 10000000 ;
504 for( ; fence && (!(error == 0 && row_error == 0)) ;
505 fence = fence->next_fence ) {
506 max_x = fence->max_xpos ;
507 min_x = fence->min_xpos ;
508 min_block = fence->min_block ;
509 max_block = fence->max_block ;
510 if( x > max_x ) {
511 if( x - max_x < error ) {
512 error = x - max_x ;
513 r_error = 1 ;
514 if( row > max_block ) {
515 if( row - max_block < row_error ) {
516 row_error = row - max_block ;
517 }
518 } else if( row < min_block ) {
519 if( min_block - row < row_error ) {
520 row_error = min_block - row;
521 }
522 } else {
523 row_error = 0 ;
524 }
525 }
526 } else if( x < min_x ) {
527 if( min_x - x < error ) {
528 error = min_x - x ;
529 r_error = 0 ;
530 if( row > max_block ) {
531 if( row - max_block < row_error ) {
532 row_error = row - max_block ;
533 }
534 } else if( row < min_block ) {
535 if( min_block - row < row_error ) {
536 row_error = min_block - row;
537 }
538 } else {
539 row_error = 0 ;
540 }
541 }
542 } else {
543 error = 0 ;
544 if( row > max_block ) {
545 if( row - max_block < row_error ) {
546 row_error = row - max_block ;
547 }
548 } else if( row < min_block ) {
549 if( min_block - row < row_error ) {
550 row_error = min_block - row;
551 }
552 } else {
553 row_error = 0 ;
554 }
555 }
556 }
557 if( !( error == 0 && row_error == 0) ) {
558 if( error > (INT) mean_widthG ) {
559 if( r_error == 1 ) {
560 total_r += error ;
561 /*
562 fprintf(fpoG,"Right Violation for cell #%d ", cell );
563 fprintf(fpoG,"X ERROR by %d\n", error ) ;
564 */
565 } else {
566 total_l += error ;
567 /*
568 fprintf(fpoG,"Left Violation for cell #%d ", cell );
569 fprintf(fpoG,"X ERROR by %d\n", error ) ;
570 */
571 }
572 /*
573 fprintf(fpoG,"Row Error by %d rows\n", row_error ) ;
574 */
575 }
576 }
577 }
578 fprintf(fpoG,"Total placement violations to the left:%d\n", total_l );
579 fprintf(fpoG,"Total placement violations to the rite:%d\n", total_r );
580
581 return ;
582 }
583
584
585
586
reduce_violations()587 int reduce_violations()
588 {
589
590 FENCEBOXPTR fence , save_fence ;
591 INT cell , x , error , work , l_error , r_error , row ;
592 INT max_x , min_x , i ;
593
594 work = 0 ;
595 for( row = 1 ; row <= numRowsG ; row++ ) {
596 for( i = 1 ; i <= pairArrayG[row][0] ; i++ ) {
597 cell = pairArrayG[row][i] ;
598 fence = carrayG[cell]->fence ;
599 if( !fence ) {
600 continue ;
601 }
602 x = carrayG[cell]->cxcenter ;
603 l_error = 10000000 ;
604 error = 10000000 ;
605 r_error = 10000000 ;
606 for( ; fence && error != 0 ; fence = fence->next_fence ) {
607 max_x = fence->max_xpos ;
608 min_x = fence->min_xpos ;
609 if( error == 0 ) {
610 } else if( x > max_x || x < min_x ) {
611 if( x > max_x ) {
612 if( x - max_x < error ) {
613 r_error = x - max_x ;
614 save_fence = fence ;
615 }
616 } else {
617 if( min_x - x < error ) {
618 l_error = min_x - x ;
619 save_fence = fence ;
620 }
621 }
622 } else {
623 error = 0 ;
624 }
625 }
626 if( error != 0 ) {
627 work++ ;
628 if( l_error < r_error ) {
629 /* we should shift the cell to the right */
630 carrayG[ pairArrayG[row][i] ]->cxcenter =
631 save_fence->min_xpos + 3 * (INT)(mean_widthG) ;
632 } else {
633 /* we should shift the cell to the left */
634 carrayG[ pairArrayG[row][i] ]->cxcenter =
635 save_fence->max_xpos - 3 * (INT)(mean_widthG) ;
636 }
637 }
638 }
639 }
640 return( work ) ;
641 }
642