1 /*
2 * Copyright (C) 1988-1991 Yale University
3 * Copyright (C) 2014 Ruben Undheim <ruben.undheim@gmail.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: placepads.c
43 DESCRIPTION:This file contains the place pads routines.
44 CONTENTS:
45 placepads()
46 find_core()
47 setVirtualCore( flag )
48 BOOL flag ;
49 find_core_boundry( left, right, bottom, top )
50 INT *left, *right, *bottom, *top ;
51 get_global_pos( cell, l, b, r, t )
52 INT cell, *l, *r, *b, *t ;
53 DATE: Aug 12, 1988
54 REVISIONS: Oct 24, 1988 - added virtual core switch to control pad
55 placement.
56 Jan 17, 1988 - add find_core_boundary for channel graph
57 generation code - outgeo.c .
58 Jan 20, 1989 - fixed problem when pad has no pin connected
59 to it. Made sure softcells are using correct fields
60 and coordinates are translated.
61 Feb. 15, 1989 - added get_global_pos so that amount of
62 duplicated code is reduced.
63 Apr 30, 1989 - added bound to padcenter for non-virtual
64 core placement. Modified putChildren to place
65 padgroups with sidespace restriction.
66 Oct 20, 1989 - Now pads are output with global routing
67 density.
68 Feb 7, 1990 - Updated placepad core coordinates to
69 reflect new routing scheme.
70 Sun Jan 20 21:34:36 PST 1991 - ported to AIX.
71 Wed Feb 13 23:55:50 EST 1991 - now call placepads program.
72 Sat Feb 23 00:17:28 EST 1991 - added placepads algorithm.
73 Sun May 5 14:30:08 EDT 1991 - after setVirtual switch
74 is turned on update the block variables.
75 Thu Sep 19 16:33:58 EDT 1991 - fixed problem with sidespace
76 options when only a fraction of the pins to pads have
77 connections to the core.
78 ----------------------------------------------------------------- */
79
80 #include <custom.h>
81 #include <pads.h>
82 #include <dens.h>
83 #include <yalecad/debug.h>
84 #include <yalecad/file.h>
85 #include <yalecad/string.h>
86 #include <yalecad/set.h>
87
88 #include "config-build.h"
89
90 #define PLACEPADPROG "placepads"
91 #define PLACEPADPATH "../placepads"
92 #define PADKEYWORD "pad"
93
94 /* ***************** STATIC FUNCTION DEFINITIONS ******************* */
95 static void find_optimum_locations( P1(void) ) ;
96 static void place_pad( P2(PADBOXPTR pad,INT bestside ) ) ;
97 static void place_children( P5(PADBOXPTR pad,INT side,DOUBLE lb,DOUBLE ub,BOOL sr) ) ;
98 static INT find_cost_for_a_side(P5(PADBOXPTR pad,INT side,DOUBLE lb,DOUBLE ub,
99 BOOL spacing_restricted ) ) ;
100 static void find_core( P1(void) ) ;
101
102 void call_place_pads();
103 void output_nets( FILE *fp, int numnets );
104
105 /* ***************** STATIC VARIABLE DEFINITIONS ******************* */
106 static INT sumposS ; /* sum of the modified opt. pin pos. of pad pins */
107 static INT sumtieS ; /* sum of all the opt. pin pos. of pad pins */
108 static INT pin_countS ; /* number of pins found with valid connections */
109 static BOOL virtualCoreS = FALSE ;
110 static YSETPTR pad_net_setS = NIL(YSETPTR) ;
111 static BOOL external_pad_programS = FALSE ;
112
113
114
115
116 /*-------------------------------------------------------------------
117 placepads() now call placepads program or uses internal algorithm.
118 If you convert from placepads program remember to change numterms
119 field to endsuper.
120 ____________________________________________________________________*/
121
placepads()122 void placepads()
123 {
124
125 if( padspacingG == EXACT_PADS ){
126 /* no work to do */
127 return ;
128 }
129
130 find_core(); /* GET THE UPDATED CORE'S DIMENSION */
131
132 if( external_pad_programG ){
133 call_place_pads() ;
134 funccostG = findcost() ;
135 return ;
136 }
137
138 /* otherwise do the internal routines */
139 D( "placepads/initially",
140 print_pads( "pads initially\n", padarrayG, totalpadsG ) ;
141 ) ;
142
143 find_optimum_locations() ;
144 D( "placepads/after_find_opt",
145 print_pads( "pads after_cost\n", sortarrayG, totalpadsG ) ;
146 ) ;
147
148 sort_pads();
149 D( "placepads/after_sort",
150 print_pads( "pads after sort\n", placearrayG, numpadsG );
151 ) ;
152
153 align_pads();
154 D( "placepads/after_align",
155 print_pads( "pads after align\n", placearrayG, numpadsG ) ;
156 ) ;
157
158 orient_pads();
159 D( "placepads/after_orient",
160 print_pads( "pads after orient\n", placearrayG, numpadsG ) ;
161 ) ;
162
163 dimension_pads();
164 D( "placepads/after_dim",
165 print_pads( "pads after dimension\n", placearrayG, numpadsG ) ;
166 ) ;
167
168 funccostG = findcost() ;
169
170 } /* end placepads */
171 /* ***************************************************************** */
172
find_optimum_locations()173 static void find_optimum_locations()
174 {
175 INT i ; /* pad counter */
176 INT side ; /* loop thru valid sides */
177 INT cost ; /* current cost */
178 INT bestpos ; /* best modified position for pad */
179 INT besttie ; /* best position for pad for tiebreak */
180 INT bestcost ; /* best cost for pad or padgroup */
181 INT bestside ; /* best side to place pad or padgroup */
182 PADBOXPTR pad ; /* current pad */
183
184 /** FIND OPTIMUM PLACE FOR PADS ACCORDING TO THE RESTRICTIONS **/
185 for( i = 1; i <= totalpadsG; i++ ){
186
187 /**** LEAVES AND SUBROOTS NEED TO BE PLACED ON THE SAME
188 **** SIDE AS THEIR PARENT ROOT, HENCE WE PLACE THE ROOT
189 **** FIRST, AND THEN PLACE ALL ITS CHILDREN **/
190
191 pad = padarrayG[i] ;
192 if( pad->padtype == PADGROUPTYPE && pad->hierarchy == ROOT ){
193 /* the case of a padgroup root */
194 bestcost = INT_MAX ;
195 for (side = 1; side <= 4; side++ ) {
196 if( pad->valid_side[ALL] || pad->valid_side[side] ){
197 cost = find_cost_for_a_side( pad,side,
198 (DOUBLE) pad->lowerbound, (DOUBLE) pad->upperbound,
199 pad->fixed ) ;
200 if( cost < bestcost) {
201 bestcost = cost;
202 bestside = side ;
203 }
204 }
205 }
206 place_children( pad, bestside, (DOUBLE) pad->lowerbound,
207 (DOUBLE) pad->upperbound, pad->fixed ) ;
208
209 } else if( pad->padtype == PADCELLTYPE && pad->hierarchy == NONE ) {
210 /* the case of a pad that is not in a padgroup */
211 bestcost = INT_MAX ;
212 for (side = 1; side <= 4; side++ ) {
213 if( pad->valid_side[ALL] || pad->valid_side[side] ){
214 cost = find_cost_for_a_side( pad,side,
215 (DOUBLE) pad->lowerbound, (DOUBLE) pad->upperbound,
216 pad->fixed ) ;
217 if( cost < bestcost) {
218 bestcost = cost;
219 bestside = side ;
220 bestpos = sumposS ;
221 besttie = sumtieS ;
222 }
223 }
224 }
225 /* now use the best positions for the position */
226 sumposS = bestpos ;
227 sumtieS = besttie ;
228 place_pad( pad, bestside ) ;
229
230 } /* end simple pad case */
231 }
232 } /* end find_optimum */
233
234 /* ***************************************************************** */
find_cost_for_a_side(pad,side,lb,ub,spacing_restricted)235 static INT find_cost_for_a_side(pad,side,lb,ub,spacing_restricted)
236 PADBOXPTR pad;
237 INT side ;
238 DOUBLE lb, ub ;
239 BOOL spacing_restricted ;
240 {
241 INT i ; /* children counter */
242 INT pos ; /* current pos. of current core pin constrained*/
243 INT dist ; /* current distance from core pin to pad */
244 INT cost ; /* sum of the opt pad pins to closest core pin */
245 INT dist2 ; /* under restrictions dist from core pin to pad */
246 INT lowpos ; /* convert lower bound to a position */
247 INT uppos ; /* convert upper bound to a position */
248 INT bestpos ; /* best constrained pos for pad to core for 1 net */
249 INT besttie ; /* best position for pad to core for 1 net */
250 INT bestdist ; /* best distance for pad to core for 1 net */
251 INT tiebreak ; /* best place to put pad pin unconstrained */
252 BOOL pinFound ; /* true if we find a match on current net */
253 PINBOXPTR pinptr; /* current pin */
254 PINBOXPTR netterm;/* loop thru pins of a net */
255 PADBOXPTR child; /* go thru the children of the padgroup */
256
257
258 /**** FOR NORMAL PADS AND LEAVES, JUST CALCULATE THE COST */
259 /*** AND POSITION. THE LEAF CASE IS THE RETURN CONDITION OF */
260 /*** THE RECURSION ON THE ROOT PADS ***/
261
262 if( pad->hierarchy == LEAF || pad->hierarchy == SUBROOT ){
263 if( !(pad->valid_side[ALL]) && !(pad->valid_side[side]) ){
264 /* this is not a valid side return a huge cost */
265 return( PINFINITY ) ;
266 }
267 }
268 /* At this point are guaranteed to have a valid side */
269 cost = 0 ;
270 sumposS = 0 ;
271 sumtieS = 0 ;
272
273 /* determine spacing restrictions */
274 calc_constraints( pad, side, &lb, &ub, &spacing_restricted,
275 &lowpos, &uppos ) ;
276
277 if( pad->hierarchy == LEAF || pad->hierarchy == NONE ){
278
279
280 /**** FOR ALL PINS BELONGING TO THE SAME NET AS PINS ON THE
281 PAD, FIND THE PIN CLOSEST TO THE SIDE IN padside. ****/
282
283 /**** ASSUME NO PIN WAS FOUND ***/
284 pin_countS = 0 ;
285
286 for ( pinptr = cellarrayG[pad->cellnum]->pinptr ;pinptr; pinptr = pinptr->nextpin) {
287 bestdist = INT_MAX ;
288 /*** GO TO FIRST TERMS OF THE NET TO MAKE SURE ALL
289 TERMINALS ARE INCLUDED ***/
290 pinFound = FALSE ;
291 netterm = netarrayG[pinptr->net]->pins;
292 for( ;netterm ;netterm = netterm->next ) {
293
294 /**** CALCULATE THE DISTANCE FROM CORE.
295 **** pos IS THE POSITION OF THE PAD ON THIS SIDE
296 **** WHICH RESULTS IN THE SHORTEST DISTANCE TO THE PIN.
297 **** ONLY PINS ON CELLS ARE IN THIS CONTEST **/
298
299
300 if( netterm->cell <= endsuperG ) {
301 switch (side) {
302 case L:
303 pos = netterm->ypos;
304 dist = netterm->xpos - coreG[X][MINI];
305 break;
306 case T:
307 pos = netterm->xpos;
308 dist = coreG[Y][MAXI] - netterm->ypos;
309 break;
310 case R:
311 pos = netterm->ypos;
312 dist = coreG[X][MAXI] - netterm->xpos;
313 break;
314 case B:
315 pos = netterm->xpos;
316 dist = netterm->ypos - coreG[Y][MINI];
317 break;
318 } /* end switch on side */
319
320 tiebreak = pos ; /* save original spot */
321 if( spacing_restricted ){
322 /* the pad placement on the side has been */
323 /* restricted in some way */
324 if( lowpos <= pos && pos <= uppos ){
325 /* everythings cool do no extra distance */
326 dist2 = 0 ;
327 } else if( lowpos > pos ){
328 dist2 = ABS( lowpos - pos ) ;
329 pos = lowpos ;
330 } else if( pos > uppos ){
331 dist2 = ABS( pos - uppos ) ;
332 pos = uppos ;
333 }
334 /* modify the distance by it Manhattan length */
335 /* to the pad in the orthogonal direction */
336 /* since this pad is fixed at a point */
337 /* could modify this to be more accurate since we want matching padpin*/
338 dist += dist2 ;
339 }
340 }
341 if (dist < bestdist) {
342 bestdist = dist; /*** UPDATE THE BEST DISTANCE */
343 bestpos = pos; /*** AND BEST POSITION */
344 besttie = tiebreak; /* save the original position */
345 pinFound = TRUE ; /* pin on this net was found */
346 }
347 } /* end looking at this net */
348
349 if( pinFound ){
350 /*** SUM UP THE BEST POSITION OF ALL PINS */
351 sumposS += bestpos ;
352 sumtieS += besttie ;
353
354 /*** KEEP TRACK OF THE TOTAL COST FOR THIS SIDE */
355 cost += bestdist;
356 pin_countS++ ;
357 }
358 } /* end for loop on pins of the pad */
359
360 /*** IF NO PIN IS FOUND TO MATCH WITH PAD ARBITRARILY ***/
361 /*** SET best position to random number for THIS PAD ***/
362 if( pin_countS == 0 ){
363 if( spacing_restricted ){
364 /* average between constraints */
365 sumposS = (lowpos + uppos) / 2 ;
366 } else {
367 /*
368 Randomly pick a cost to break ties in the
369 case that this pad could go on any side. Small
370 value will not effect padgroups
371 */
372 cost = PICK_INT( 0, 3 ) ;
373 switch (side) {
374 case L:
375 sumposS = PICK_INT( coreG[Y][MINI],coreG[Y][MAXI] ) ;
376 break;
377 case T:
378 sumposS = PICK_INT( coreG[X][MINI],coreG[X][MAXI] ) ;
379 break;
380 case R:
381 sumposS = PICK_INT( coreG[Y][MINI],coreG[Y][MAXI] ) ;
382 break;
383 case B:
384 sumposS = PICK_INT( coreG[X][MINI],coreG[X][MAXI] ) ;
385 break;
386 default:
387 break;
388 }
389 }
390 sumtieS = sumposS ;
391 } /* end pin_countS == 0 */
392
393 return( cost ) ;
394
395 } else {
396
397 /***
398 IF THE PAD IS A SUPERPAD, THEN SEARCH THROUGH ALL ***
399 ITS CHILDREN AND SUM THE COST AND IDEAL POSITION ***
400 RECURSIVELY. Use the spacing restrictions derived above.
401 ***/
402
403
404 for( i = 1 ;i <= pad->children[HOWMANY]; i++ ){
405 child = padarrayG[pad->children[i]];
406 cost += find_cost_for_a_side( child, side,
407 lb, ub, spacing_restricted ) ;
408 }
409 return( cost );
410 }
411 } /* end find_cost_for_a_side */
412 /* ***************************************************************** */
413
414 /**** SET POSITION OF THE PAD. POS IS THE SUM OF THE OPTIMAL POSITION
415 **** FOR ALL TERMINALS OF THE PAD. WE DIVIDE BY THE NUMBER OF TERMINAL
416 **** TO GET THE AVERAGE. Place_pad must be performed immediately
417 **** after a find_cost_for_a_side since sumposS and sumtieS
418 **** are set in those routines. Otherwise set sumposS and sumtieS
419 **** to their proper values.
420 ***/
place_pad(pad,bestside)421 static void place_pad( pad, bestside )
422 PADBOXPTR pad ;
423 INT bestside ;
424 {
425
426 if( pin_countS == 0 ){
427 /*** SET PAD TO RANDOM POSITION DETERMINED IN find_cost_for_side*/
428 pad->position = sumposS ;
429 pad->tiebreak = sumtieS ;
430 } else {
431 pad->position = sumposS / pin_countS ;
432 pad->tiebreak = sumtieS / pin_countS ;
433 }
434 /* now bound pad center to current core boundary for normal case */
435 pad->padside = bestside ;
436 #ifdef LATER
437 switch( bestside ){
438 case L:
439 case R:
440 pad->position = MAX( pad->position, coreG[Y][MINI] ) ;
441 pad->position = MIN( pad->position, coreG[Y][MAXI] ) ;
442 break;
443 case T:
444 case B:
445 pad->position = MAX( pad->position, coreG[X][MINI] ) ;
446 pad->position = MIN( pad->position, coreG[X][MAXI] ) ;
447 } /* end bound of pad position */
448 #endif
449
450 } /* end place_pad */
451 /* ***************************************************************** */
452
453
454
455 /**** RECURSIVELY SET THE PADSIDE OF ALL CHILDREN OF THE ROOT PAD TO THE
456 **** PADSIDE OF THE PARENT. GIVEN THAT SIDE, SET THE OPTIMAL CXCENTER */
place_children(pad,side,lb,ub,spacing_restricted)457 static void place_children( pad, side, lb, ub, spacing_restricted )
458 PADBOXPTR pad ;
459 INT side ;
460 DOUBLE lb, ub ;
461 BOOL spacing_restricted ;
462 {
463 INT i ; /* pad counter */
464 INT pos ; /* position of last placed pad */
465 INT min_pos ; /* min position of the last padgroup */
466 INT max_pos ; /* max position of the last padgroup */
467 DOUBLE lowbound ; /* lower bound for pad or pad group */
468 DOUBLE hibound ; /* upper bound for pad or pad group */
469 PADBOXPTR child; /* go thru the children of the padgroup */
470
471 /* DETERMINE SPACING RESTRICTIONS */
472 if( spacing_restricted ){
473 /* this is the case that the spacing has been restricted */
474 if( pad->fixed ){
475 /* if the padgroup bounds have been fixed, */
476 /* force position to be within bound */
477 /* assume we are ok and then correct it */
478 lowbound = pad->lowerbound ;
479 if( lowbound < lb ){
480 lowbound = lb ;
481 }
482 if( lowbound > ub ){
483 lowbound = ub ;
484 }
485 hibound = pad->upperbound ;
486 if( hibound < lb ){
487 hibound = lb ;
488 }
489 if( hibound > ub ){
490 hibound = ub ;
491 }
492 } else {
493 /* this pad is not fixed use the given ub and lb */
494 lowbound = lb ; hibound = ub ;
495 }
496 } else {
497 if( pad->fixed ){
498 /* the padgroup bounds have not been fixed */
499 /* just take the pad's restricted position */
500 lowbound = pad->lowerbound;
501 hibound = pad->upperbound;
502 spacing_restricted = TRUE ;
503 }
504 }
505 /* **** END spacing restriction calculations *** */
506
507 if( pad->hierarchy == LEAF ){
508 find_cost_for_a_side( pad, side,
509 lowbound, hibound, spacing_restricted ) ;
510 place_pad( pad, side ) ;
511 return ;
512 } else {
513 pos = 0 ;
514 min_pos = INT_MAX ;
515 max_pos = INT_MIN ;
516 for( i = 1; i <= pad->children[HOWMANY]; i++ ){
517 child = padarrayG[pad->children[i]];
518 place_children( child, side, lowbound, hibound, spacing_restricted ) ;
519 pos += child->position ;
520 min_pos = MIN( child->position, min_pos ) ;
521 max_pos = MAX( child->position, max_pos ) ;
522 }
523 if( pad->children[HOWMANY] ){
524 pad->position = pos /= pad->children[HOWMANY] ;
525 } else {
526 pad->position = pos ;
527 }
528 /* for tiebreak use the bounds of the padgroup and average them. */
529 /* set the side of the pad */
530 pad->padside = side ;
531 pad->tiebreak = (min_pos + max_pos ) / 2 ;
532 return ;
533 }
534 } /* end place_children */
535 /* ***************************************************************** */
536
537 /* ***************************************************************** */
538 #ifdef DEBUG
print_pads(message,array,howmany)539 void print_pads( message, array, howmany )
540 char *message ;
541 PADBOXPTR *array ;
542 INT howmany ;
543 {
544 INT i ;
545 PADBOXPTR ptr ;
546 CELLBOXPTR cptr ;
547
548 fprintf( stderr, "\n%s\n", message ) ;
549
550 /* now print them out */
551 for( i = 1 ; i <= howmany; i++ ){
552 ptr = array[i] ;
553 cptr = cellarrayG[ptr->cellnum] ;
554 fprintf( stderr,
555 "pad:%s x:%d y:%d type:%d side:%d pos:%d tie:%d orient:%d\n",
556 cptr->cname, cptr->xcenter, cptr->ycenter, ptr->hierarchy,
557 ptr->padside, ptr->position, ptr->tiebreak, cptr->orient ) ;
558 }
559 fprintf( stderr, "\n" ) ;
560
561 dimension_pads() ;
562 G( process_graphics() ) ;
563
564 } /* end print_pads */
565
566 #endif /* DEBUG */
567 /* ***************************************************************** */
568
569
570 /* turn virtual core on and off */
setVirtualCore(BOOL flag)571 void setVirtualCore( BOOL flag )
572 {
573 virtualCoreS = flag ;
574 } /* end set Virtual core */
575
576 /* function finds and returns core boundary region including cells */
577 /* which overlap the core region */
find_core_boundary(INT * left,INT * right,INT * bottom,INT * top)578 void find_core_boundary( INT *left, INT *right, INT *bottom, INT *top )
579 {
580 BOOL rememberFlag ;
581
582 /* call routine to find core boundary based on virtual core */
583 rememberFlag = virtualCoreS ;/* so we can put flag back */
584 virtualCoreS = TRUE ;
585 find_core() ;
586
587 /* set flag back to whatever it was */
588 virtualCoreS = rememberFlag ;
589
590 /* now return values */
591 *left = coreG[X][MINI] ;
592 *right = coreG[X][MAXI] ;
593 *bottom = coreG[Y][MINI] ;
594 *top = coreG[Y][MAXI] ;
595
596 } /* end find_core_boundary */
597
598
599 /* given a cell it returns bounding box of cell in global coordinates */
get_global_pos(cell,l,b,r,t)600 void get_global_pos( cell, l, b, r, t )
601 INT cell ;
602 INT *l, *r, *b, *t ;
603 {
604 INT orient ;
605 BOUNBOXPTR bounptr ;
606 CELLBOXPTR ptr ;
607
608 ptr = cellarrayG[cell] ;
609 orient = ptr->orient ;
610 bounptr = ptr->bounBox[orient] ;
611 *l = bounptr->l ;
612 *r = bounptr->r ;
613 *b = bounptr->b ;
614 *t = bounptr->t ;
615
616 /* now add xcenter ycenter to get global position */
617 *l += ptr->xcenter ;
618 *r += ptr->xcenter ;
619 *b += ptr->ycenter ;
620 *t += ptr->ycenter ;
621 } /* end get_global_pos */
622
623
624 /* given a cell it returns bounding box of cell including routing area */
get_routing_boundary(cell,ret_l,ret_b,ret_r,ret_t)625 void get_routing_boundary( cell, ret_l, ret_b, ret_r, ret_t )
626 INT cell ;
627 INT *ret_l, *ret_r, *ret_b, *ret_t ; /* return quantities */
628 {
629 INT minx, maxx ;
630 INT miny, maxy ;
631 CELLBOXPTR ptr ;
632 RTILEBOXPTR tileptr ;
633
634
635 get_global_pos( cell, ret_l, ret_b, ret_r, ret_t ) ;
636
637 if( !(routingTilesG) ){
638 /* return cell boundary if no routing tiles */
639 return ;
640 }
641
642 /* otherwise find bounding box of routing tiles */
643 minx = INT_MAX ;
644 miny = INT_MAX ;
645 maxx = INT_MIN ;
646 maxy = INT_MIN ;
647 for( tileptr = routingTilesG[cell];tileptr;tileptr=tileptr->next ){
648 minx = MIN( minx, tileptr->x1 ) ;
649 maxx = MAX( maxx, tileptr->x2 ) ;
650 miny = MIN( miny, tileptr->y1 ) ;
651 maxy = MAX( maxy, tileptr->y2 ) ;
652 }
653
654 /* now add xcenter ycenter to get global position */
655 ptr = cellarrayG[cell] ;
656 *ret_l = MIN( minx + ptr->xcenter, *ret_l ) ;
657 *ret_r = MAX( maxx + ptr->xcenter, *ret_r ) ;
658 *ret_b = MIN( miny + ptr->ycenter, *ret_b ) ;
659 *ret_t = MAX( maxy + ptr->ycenter, *ret_t ) ;
660 return ;
661 } /* end get_routing_boundary */
662
663
get_pad_routing(cell)664 static INT get_pad_routing( cell )
665 INT cell ;
666 {
667
668 CELLBOXPTR cptr ; /* pad cell in question */
669 RTILEBOXPTR tptr ; /* look at all the routing tiles */
670 INT last_core_cell ; /* calc last core cell index */
671 INT new ; /* new position with routing */
672 INT old ; /* old position with no routing */
673
674 last_core_cell = ( (INT) routingTilesG[HOWMANY] ) - 4 ;
675
676 /* find bounding box of routing tiles */
677 cptr = cellarrayG[endpadgrpsG + cell] ;
678 tptr = routingTilesG[last_core_cell + cell] ;
679 new = 0 ;
680 switch( cell ){
681 case L:
682 for( ; tptr ; tptr = tptr->next ){
683 new = MAX( new, tptr->x2 ) ;
684 }
685 old = cptr->tiles->right ;
686 break ;
687 case T:
688 for( ; tptr ; tptr = tptr->next ){
689 new = MIN( new, tptr->y1 ) ;
690 }
691 old = cptr->tiles->bottom ;
692 break ;
693 case R:
694 for( ; tptr ; tptr = tptr->next ){
695 new = MIN( new, tptr->x1 ) ;
696 }
697 old = cptr->tiles->left ;
698 break ;
699 case B:
700 for( ; tptr ; tptr = tptr->next ){
701 new = MAX( new, tptr->y2 ) ;
702 }
703 old = cptr->tiles->top ;
704 break ;
705 } /* end switch */
706
707 if( new ){
708 return( ABS( new - old ) ) ;
709 }
710 return( 0 ) ;
711 } /* end get_pad_routing */
712
find_core()713 static void find_core()
714 {
715 INT ominx, ominy ;
716 INT omaxx, omaxy ;
717 INT l, r, b, t ;
718 INT i ;
719
720 if( virtualCoreS ){
721 /* initialize xmin, ymax, etc. */
722 coreG[X][MINI] = INT_MAX ;
723 coreG[Y][MINI] = INT_MAX ;
724 coreG[X][MAXI] = INT_MIN ;
725 coreG[Y][MAXI] = INT_MIN ;
726
727 /* reset bounding boxes for all cells for get_global_pos */
728 regenorient(1, numcellsG) ;
729
730 /* find virtual boundary of core */
731 for( i=1;i<=numcellsG;i++ ){
732
733 if( cellarrayG[i]->celltype == STDCELLTYPE && doPartitionG ){
734 /* ignore standard cell types */
735 continue ;
736 }
737
738 if( doPartitionG ){
739 get_global_pos( i, &l, &b, &r, &t ) ;
740 } else {
741 get_routing_boundary( i, &l, &b, &r, &t ) ;
742 }
743 coreG[X][MINI] = MIN( coreG[X][MINI], l ) ;
744 coreG[X][MAXI] = MAX( coreG[X][MAXI], r ) ;
745 coreG[Y][MINI] = MIN( coreG[Y][MINI], b ) ;
746 coreG[Y][MAXI] = MAX( coreG[Y][MAXI], t ) ;
747
748 }
749 if( doPartitionG ){
750 coreG[X][MINI] = MIN( coreG[X][MINI], blocklG ) ;
751 coreG[X][MAXI] = MAX( coreG[X][MAXI], blockrG ) ;
752 coreG[Y][MINI] = MIN( coreG[Y][MINI], blockbG ) ;
753 coreG[Y][MAXI] = MAX( coreG[Y][MAXI], blocktG ) ;
754 }
755 /* set block parameters once virtual core is set */
756 blocklG = coreG[X][MINI] ;
757 blockrG = coreG[X][MAXI] ;
758 blockbG = coreG[Y][MINI] ;
759 blocktG = coreG[Y][MAXI] ;
760 } else {
761 coreG[X][MINI] = blocklG ;
762 coreG[X][MAXI] = blockrG ;
763 coreG[Y][MINI] = blockbG ;
764 coreG[Y][MAXI] = blocktG ;
765 }
766
767 /* now guarantee space between core and pads */
768 /* if global router info not available */
769 if( !(routingTilesG) ){
770 coreG[X][MINI] -= track_spacingXG ;
771 coreG[Y][MINI] -= track_spacingYG ;
772 coreG[X][MAXI] += track_spacingXG ;
773 coreG[Y][MAXI] += track_spacingYG ;
774 } else if(!(doPartitionG)){
775 /* find delta in pad spacing */
776 coreG[X][MINI] -= get_pad_routing( L ) ;
777 coreG[Y][MAXI] += get_pad_routing( T ) ;
778 coreG[X][MAXI] += get_pad_routing( R ) ;
779 coreG[Y][MINI] -= get_pad_routing( B ) ;
780 }
781
782 /* if the grid is given force to grid positions */
783 if( gridCellsG ){
784 ominx = coreG[X][MINI] ;
785 ominy = coreG[Y][MINI] ;
786 omaxx = coreG[X][MAXI] ;
787 omaxy = coreG[Y][MAXI] ;
788 YforceGrid( &coreG[X][MINI], &coreG[Y][MINI] ) ;
789 YforceGrid( &coreG[X][MAXI], &coreG[Y][MAXI] ) ;
790
791 /* make sure gridded data is outside of core to avoid overlap */
792 if( ominx < coreG[X][MINI] ){
793 coreG[X][MINI] -= track_spacingXG ;
794 }
795 if( ominy < coreG[Y][MINI] ){
796 coreG[Y][MINI] -= track_spacingYG ;
797 }
798 if( omaxx > coreG[X][MAXI] ){
799 coreG[X][MAXI] += track_spacingXG ;
800 }
801 if( omaxy > coreG[Y][MAXI] ){
802 coreG[Y][MAXI] += track_spacingYG ;
803 }
804 }
805 perdimG[X] = coreG[X][MAXI] - coreG[X][MINI] ;
806 perdimG[Y] = coreG[Y][MAXI] - coreG[Y][MINI] ;
807
808
809 } /* end find_core */
810
811
812 /* ***********************EXTERNAL ROUTINES ************************** */
call_place_pads()813 void call_place_pads()
814 {
815 FILE *fp ;
816 INT pad ;
817 INT line ;
818 INT numnets ;
819 INT numtokens ;
820 INT closegraphics() ;
821 INT find_numnets() ;
822 BOOL abort ;
823 char **tokens ;
824 char *bufferptr ;
825 char *pathname, *Yrelpath() ;
826 char *twdir, *Ygetenv() ;
827 char filename[LRECL] ;
828 char buffer[LRECL] ;
829 CELLBOXPTR cellptr ;
830
831 /* build the input file for the placepads program */
832 sprintf( filename, "%s.pads", cktNameG );
833 fp = TWOPEN( filename, "w", ABORT ) ;
834 numnets = find_numnets() ;
835 fprintf( fp, "core %d %d %d %d\n",
836 coreG[X][MINI], coreG[Y][MINI], coreG[X][MAXI], coreG[Y][MAXI] ) ;
837 fprintf( fp, "pads %d numnets %d\n", numpadsG+numpadgroupsG, numnets);
838 output_pads( fp ) ;
839 output_nets( fp, numnets ) ;
840 TWCLOSE( fp ) ;
841
842 /* now call the placepad program */
843 /* find the path of placepads relative to main program */
844 pathname = Yrelpath( argv0G, PLACEPADPATH ) ;
845 if( !(YfileExists(pathname))){
846 /* Check if TWDIR overridden */
847 if((twdir = getenv("TWDIR"))) {
848 M(MSG,NULL, "Directory overridden with 'TWDIR' environment variable\n" ) ;
849 }
850 else {
851 twdir = TWFLOWDIR;
852 }
853 sprintf( filename, "%s/bin/%s", twdir, PLACEPADPROG ) ;
854 pathname = Ystrclone( filename ) ;
855 }
856 switch( padspacingG ){
857 case ABUT_PADS:
858 sprintf( YmsgG, "%s -asn %s", pathname, cktNameG ) ;
859 break ;
860 case UNIFORM_PADS:
861 sprintf( YmsgG, "%s -usn %s", pathname, cktNameG ) ;
862 break ;
863 case VARIABLE_PADS:
864 sprintf( YmsgG, "%s -osn %s", pathname, cktNameG ) ;
865 break ;
866 }
867 M( MSG, NULL, YmsgG ) ;
868 M( MSG, NULL, "\n" ) ;
869
870 /* Ysystem will kill program if catastrophe occurred */
871 Ysystem( PLACEPADPROG, ABORT, YmsgG, closegraphics ) ;
872 Ysafe_free( pathname ) ; /* free name created in Yrelpath */
873 /* ############# end of placepads execution ############# */
874
875 /* **************** READ RESULTS of placepads ************/
876 /* open pad placement file for reading */
877 M( MSG, NULL, "Reading results of placing pads...\n" ) ;
878 sprintf(filename, "%s.pout" , cktNameG ) ;
879 fp = TWOPEN( filename , "r", ABORT ) ;
880
881 /* parse file */
882 line = 0 ;
883 abort = FALSE ;
884 pad = endsuperG ;
885 while( bufferptr=fgets(buffer,LRECL,fp )){
886 /* parse file */
887 line ++ ; /* increment line number */
888 tokens = Ystrparser( bufferptr, ": \t\n", &numtokens );
889
890 if( numtokens == 0 ){
891 /* skip over empty lines */
892 continue ;
893 } else if( strcmp( tokens[0], PADKEYWORD ) == STRINGEQ){
894 /* look at first field for keyword */
895 /* ie. pad <string> x y orient padside */
896 if( numtokens != 6 ){
897 sprintf( YmsgG, "Syntax error on line:%d\n", line ) ;
898 M(ERRMSG, "placepads", YmsgG ) ;
899 abort = TRUE ;
900 continue ;
901 }
902 pad++ ;
903 ASSERTNBREAK( pad > 0 && pad <= endpadsG, "placepads",
904 "pad out of bounds\n" ) ;
905 cellptr = cellarrayG[pad] ;
906 cellptr->xcenter = atoi(tokens[2] ) ;
907 cellptr->ycenter = atoi(tokens[3] ) ;
908 cellptr->orient = atoi(tokens[4] ) ;
909 cellptr->padptr->padside = atoi(tokens[5] ) ;
910
911 } else {
912 sprintf( YmsgG, "Syntax error on line:%d\n", line ) ;
913 M(ERRMSG, "placepads", YmsgG ) ;
914 abort = TRUE ;
915 continue ;
916 }
917 }
918 TWCLOSE( fp ) ;
919
920 if( abort ){
921 M(ERRMSG, "placepads", "Problem with placing pads.Must abort\n") ;
922 closegraphics() ;
923 YexitPgm( PGMFAIL ) ;
924 }
925 /* ************ END READ RESULTS of placepads ************/
926
927 } /* end call_place_pads */
928
find_numnets()929 INT find_numnets()
930 {
931 INT pad ;
932 INT numnets ;
933 CELLBOXPTR ptr ;
934 PINBOXPTR pin ;
935
936 if(!(pad_net_setS) ){
937 pad_net_setS = Yset_init( 1, numnetsG ) ;
938 }
939 Yset_empty( pad_net_setS ) ;
940 numnets = 0 ;
941 for( pad = endsuperG; pad <= endpadsG; pad++ ){
942 ptr = cellarrayG[ pad ] ;
943 for( pin = ptr->pinptr; pin ; pin = pin->nextpin ){
944 if( netarrayG[ pin->net ]->numpins <= 1 ){
945 continue ;
946 }
947 if( Yset_add( pad_net_setS, pin->net ) ){
948 /* Yset_add returns TRUE if a new member of set */
949 numnets++ ;
950 }
951 }
952 }
953 return( numnets ) ;
954 } /* end find_numnets */
955
output_nets(FILE * fp,int numnets)956 void output_nets( FILE *fp, int numnets )
957 {
958 INT net ;
959 INT pincount ;
960 PINBOXPTR pin ;
961 NETBOXPTR netptr ;
962 YSETLISTPTR list ;
963
964 for( list = Yset_enumerate(pad_net_setS) ;list; list = list->next ){
965 net = list->node ;
966 netptr = netarrayG[ net ] ;
967 fprintf( fp, "net %s ", netptr->nname ) ;
968 pincount = 0 ;
969 for( pin = netptr->pins; pin ; pin = pin->next ){
970 if( pin->cell > endsuperG ){
971 /* skip over the pad connections */
972 continue ;
973 }
974 fprintf( fp, "%d %d ", pin->xpos, pin->ypos ) ;
975 if( ++pincount > 5 ){
976 pincount = 0 ;
977 fprintf( fp, "\n" ) ;
978 }
979 }
980 if( pincount != 0 ){
981 fprintf( fp, "\n" ) ;
982 }
983 }
984 } /* end output_nets */
985