1 /*
2 * Copyright (C) 1988-1991 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: findcost.c
42 DESCRIPTION:function calculates initial cost
43 CONTENTS: findcost( )
44 DATE: Jan 29, 1988
45 REVISIONS: Oct 22, 1988 - now take square root of the penalty
46 since square gives large variance compared to linear
47 terms in cost function.
48 Dec 3, 1988 - added timing driven penalty to cost function.
49 Mar 7, 1989 - added test for totalcells loop.
50 Mar 16, 1989 - rewrote the netlist data structures.
51 Mar 20, 1989 - deleted argument to checkcost.
52 May 11, 1989 - eliminated doPartition flag
53 Feb 8, 1989 - added test for wraparound for large designs
54 using cost only. Bin penalty doesn't matter.
55 Apr 23, 1990 - added new debug code.
56 ----------------------------------------------------------------- */
57
58 #include <custom.h>
59
60 #include <yalecad/relpos.h>
61 #include <yalecad/debug.h>
62
findcost()63 int findcost()
64 {
65
66 NETBOXPTR netptr ;
67 PINBOXPTR pinptr ;
68 CELLBOXPTR ptr ;
69 BINBOXPTR bptr ;
70 GLISTPTR net_of_path ;
71 INT cell , net ;
72 INT x , y , cost ;
73 INT orient ;
74 INT length, pathcount ;
75 INT low_length, high_length ;
76 PATHPTR path ;
77
78 cost = 0 ;
79
80 /* ************** calculate global coordinates of the pins *************/
81 for( cell = 1 ; cell <= totalcellsG ; cell++ ) {
82 ptr = cellarrayG[cell] ;
83 /* avoid work if cell is not custom,soft, or pad cell */
84 if( ptr->celltype != CUSTOMCELLTYPE && ptr->celltype != SOFTCELLTYPE
85 && ptr->celltype != PADCELLTYPE ){
86 continue ;
87 }
88 orient = ptr->orient ;
89 /* go thru all pins of the cell */
90 for( pinptr = ptr->pinptr ; pinptr ; pinptr = pinptr->nextpin ) {
91
92 /* debug - calculate global position for pins */
93 /* complain if different from incremental */
94 D( "findcost",
95 REL_POS( orient,
96 x, y, /* result */
97 pinptr->txpos, pinptr->typos, /* relative */
98 ptr->xcenter, ptr->ycenter ) ; /* cell center */
99 if( x != pinptr->xpos ){
100 D( "findcost/print",fprintf( stderr,"xpos incorrect\n")) ;
101 } else if( y != pinptr->ypos ){
102 D( "findcost/print",fprintf( stderr,"ypos incorrect\n")) ;
103 }
104 ) ; /* end debug macro */
105
106
107 /* rel pos is a macro which calculates absolute pin location */
108 /* defined in relpos.h */
109 REL_POS( orient,
110 pinptr->xpos, pinptr->ypos, /* result */
111 pinptr->txpos, pinptr->typos, /* cell relative */
112 ptr->xcenter, ptr->ycenter ) ; /* cell center */
113 }
114
115 } /* end calculation of pin global coordinates */
116
117
118 /* ********* calculate net half perimeter bounding box *********** */
119 for( net = 1 ; net <= numnetsG ; net++ ) {
120 netptr = netarrayG[net] ;
121 if(!(netptr)) {
122 continue ;
123 }
124 if( netptr->skip == 1 ) {
125 continue ;
126 }
127
128 /* for debug initialize the new fields so we can see difference */
129 D( "findcost/netcalc",
130 netptr->newxmin = netptr->xmin ;
131 netptr->newymin = netptr->ymin ;
132 netptr->newxmax = netptr->xmax ;
133 netptr->newymax = netptr->ymax ;
134 ) ;
135
136 /* find first pin that we don't have skip field set */
137 /* initialize bounding box pin count to 1 */
138 for( pinptr = netptr->pins;pinptr; pinptr = pinptr->next ) {
139 if( pinptr->skip == 1 ) {
140 continue ;
141 }
142 netptr->xmin = netptr->xmax = pinptr->xpos ;
143 netptr->ymin = netptr->ymax = pinptr->ypos ;
144 netptr->Lnum = netptr->Rnum = 1 ;
145 netptr->Bnum = netptr->Tnum = 1 ;
146 pinptr = pinptr->next ;
147 break ;
148 }
149 /* Now find whether this pin impacts the bounding box */
150 /* Note when we get more than one pin on the bounding box */
151 for( ; pinptr ; pinptr = pinptr->next ) {
152 if( pinptr->skip == 1 ) {
153 continue ;
154 }
155 x = pinptr->xpos ;
156 y = pinptr->ypos ;
157
158 if( x < netptr->xmin ) {
159 netptr->xmin = x ;
160 netptr->Lnum = 1 ;
161 } else if( x == netptr->xmin ) {
162 netptr->Lnum++ ;
163 if( x == netptr->xmax ) {
164 netptr->Rnum++ ;
165 }
166 } else if( x > netptr->xmax ) {
167 netptr->xmax = x ;
168 netptr->Rnum = 1 ;
169 } else if( x == netptr->xmax ) {
170 netptr->Rnum++ ;
171 }
172 if( y < netptr->ymin ) {
173 netptr->ymin = y ;
174 netptr->Bnum = 1 ;
175 } else if( y == netptr->ymin ) {
176 netptr->Bnum++ ;
177 if( y == netptr->ymax ) {
178 netptr->Tnum++ ;
179 }
180 } else if( y > netptr->ymax ) {
181 netptr->ymax = y ;
182 netptr->Tnum = 1 ;
183 } else if( y == netptr->ymax ) {
184 netptr->Tnum++ ;
185 }
186 }
187 /* calculate cost using a vertical wire weight */
188 cost += netptr->halfPx = netptr->newhalfPx =
189 netptr->xmax - netptr->xmin ;
190 netptr->halfPy = netptr->newhalfPy =
191 netptr->ymax - netptr->ymin ;
192
193 cost = cost + (INT)( vertical_wire_weightG * (DOUBLE) netptr->halfPy ) ;
194
195 /* check to make sure calculation jives */
196 D( "findcost/netcalc",
197 if( netptr->newxmin != netptr->xmin ){
198 D( "findcost/print",fprintf( stderr,"netptr->xmin wrong\n"));
199 }
200 if( netptr->newxmax != netptr->xmax ){
201 D( "findcost/print",fprintf( stderr,"netptr->xmax wrong\n"));
202 }
203 if( netptr->newymin != netptr->ymin ){
204 D( "findcost/print",fprintf( stderr,"netptr->ymin wrong\n"));
205 }
206 if( netptr->newymax != netptr->ymax ){
207 D( "findcost/print",fprintf( stderr,"netptr->ymax wrong\n"));
208 }
209 ) ;
210
211 } /* end half perimeter bounding box calculation */
212
213
214
215 /* now calculate the penalties */
216 /* first the timing penalty */
217 timingpenalG = 0 ;
218 for( pathcount = 1 ; pathcount <= numpathsG ; pathcount++ ) {
219
220 path = patharrayG[pathcount] ;
221 ASSERTNCONT( path, "findcost", "pointer to path is NULL" ) ;
222 low_length = 0 ;
223 high_length = 0 ;
224 /* -----------------------------------------------------------------
225 For all nets k of a path i:
226 We use the minimum strength driver for each net to calculate
227 the lower bound on the length and the maximum strength driver
228 for the upper bound on the length. The user must take false
229 paths into account when specifying the driver strengths.
230 ------------------------------------------------------------------ */
231 for( net_of_path=path->nets;net_of_path;
232 net_of_path=net_of_path->next ){
233 net = net_of_path->p.net ;
234 netptr = netarrayG[net] ;
235 /* accumulate length of path */
236 length = netptr->halfPx + (INT)(vertical_path_weightG *
237 (DOUBLE) netptr->halfPy) ;
238
239 low_length = low_length + (INT)
240 (netptr->max_driver * (FLOAT) length +
241 netptr->driveFactor ) ;
242 high_length = high_length + (INT)
243 (netptr->min_driver * (FLOAT) length +
244 netptr->driveFactor ) ;
245 }
246 /* save result */
247 path->lo_path_len = path->new_lo_path_len = low_length ;
248 path->hi_path_len = path->new_hi_path_len = high_length ;
249
250 /* -----------------------------------------------------------
251 Calculate penalty - no penalty if within target window:
252 lowerbound <= length <= upperbound
253 Otherwise calculate penalties
254 ------------------------------------------------------------- */
255 if( high_length > path->upper_bound ){
256 timingpenalG += high_length - path->upper_bound ;
257 } else if( low_length < path->lower_bound ){
258 timingpenalG += path->lower_bound - low_length ;
259 }
260 }
261 /* scale timing penalty */
262 timingcostG = (INT) ( timeFactorG * (DOUBLE) timingpenalG ) ;
263
264 /* next the overlap penalty */
265 binpenalG = 0 ;
266 for( x= 0 ; x <= maxBinXG; x++ ) {
267 for( y = 0 ; y <= maxBinYG; y++ ) {
268 bptr = binptrG[x][y] ;
269 binpenalG += ABS( bptr->penalty ) ;
270 }
271 }
272 /* wrap around case */
273 if( binpenalG < 0 ){
274 binpenalG = INT_MAX ;
275 }
276 /* scale penalty */
277 penaltyG = (INT) ( lapFactorG * sqrt( (DOUBLE) binpenalG ) ) ;
278
279 return( cost ) ;
280
281 } /* end findcost */
282
283 #ifdef DEBUG
checkcost()284 checkcost()
285 {
286
287 INT incr_funccost, incr_penalty, incr_time ;
288 INT incr_overpenal, incr_timepen ;
289 INT x, y ;
290 BOOL flag ;
291
292 /* verify incremental cost equals the true cost */
293 /* save value of the current costs derived from incremental calculations */
294 DS( incr_funccost = funccostG ; ) ;
295 DS( incr_penalty = penaltyG ; ) ;
296 DS( incr_overpenal = binpenalG ; ) ;
297 DS( incr_time = timingcostG ; ) ;
298 DS( incr_timepen = timingpenalG ; ) ;
299 /* calculate current cost from scratch */
300 /* verify current cost == incremental cost */
301 funccostG = findcost() ;
302 if( funccostG != incr_funccost ){
303 M( ERRMSG,"checkcost",
304 "Incremental wire cost does not equal current cost\n" ) ;
305 }
306 if( penaltyG != incr_penalty ){
307 M( ERRMSG, "checkcost",
308 "Incremental overlap penalty does not equal current penalty\n" ) ;
309 }
310 if( binpenalG != incr_overpenal ){
311 M( ERRMSG, "checkcost",
312 "Incremental overlap penalty does not equal current penalty\n" ) ;
313 }
314 if( timingcostG != incr_time ){
315 M( ERRMSG, "checkcost",
316 "Incremental timing penalty does not equal current timing\n" ) ;
317 }
318 if( timingpenalG != incr_timepen ){
319 M( ERRMSG, "checkcost",
320 "Incremental timing penalty does not equal current timing\n" ) ;
321 }
322 D( "checkcost",
323 /* drastic test */
324 incr_penalty = penaltyG ;
325 incr_overpenal = binpenalG ;
326 flag = FALSE ;
327
328 loadbins( flag ) ;
329 for( x = 0; x<= maxBinXG; x++){
330 for( y = 0; y<= maxBinYG; y++){
331 binptrG[x][y]->nupenalty = 0 ;
332 }
333 }
334 if( penaltyG != incr_penalty ){
335 M( ERRMSG, "checkcost",
336 "Incremental overlap penalty != current penalty\n" ) ;
337 }
338 if( binpenalG != incr_overpenal ){
339 M( ERRMSG, "checkcost",
340 "Incremental overlap penalty != current penalty\n" ) ;
341 }
342 ) ;
343 } /* end checkcost */
344
345 #endif /* DEBUG */
346