1 /*
2 * Copyright (C) 1989-1992 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: upair.c
42 DESCRIPTION:pairwise flips of cells.
43 CONTENTS: upair()
44 eval_range( acellptr , bcellptr, axc , anxc , bxc , bnxc )
45 CBOXPTR acellptr , bcellptr ;
46 INT axc , anxc , bxc , bnxc ;
47 DATE: Mar 27, 1989
48 REVISIONS: Fri Mar 22 16:23:46 CST 1991 - now avoid upair
49 if there are no moveable cells.
50 Fri Sep 6 15:20:48 CDT 1991 - now place pads during
51 pairwise swaps.
52 ----------------------------------------------------------------- */
53
54 #include "standard.h"
55 #include "main.h"
56 #include <yalecad/debug.h>
57 #include <yalecad/message.h>
58 #define PICK_INT(l,u) (((l)<(u)) ? ((RAND % ((u)-(l)+1))+(l)) : (l))
59
60 /* global references */
61 extern INT **pairArrayG ;
62 extern BOOL orientation_optimizationG ;
63 extern BOOL placement_improveG ;
64
upair()65 void upair()
66 {
67
68 CBOXPTR acellptr, bcellptr ;
69 BBOXPTR ablckptr ;
70 INT a , b , ablock , aorient ;
71 INT flips , attempts , oattempts ;
72 INT axcenter,anxcenter, bnxcenter ;
73 INT aleft , aright ;
74 INT startx1, endx1;
75 INT cellleft, cellrite;
76 INT leftEdge, riteEdge;
77 INT aptr , one_cell_per_row , row ;
78 INT free_cells, cells_in_row ;
79
80 if(!(placement_improveG)){
81 return ;
82 }
83 flips = 0 ;
84 attempts = 0 ;
85 oattempts = 0 ;
86
87 /* ************** place the pads ****************** */
88 setVirtualCore( TRUE ) ;
89 placepads() ;
90 funccostG = recompute_wirecost() ;
91 timingcostG = recompute_timecost() ;
92
93 /* assume conditions are true - prove otherwise */
94 one_cell_per_row = TRUE ;
95 for( row = 1 ; row <= numRowsG ; row++ ) {
96 cells_in_row = pairArrayG[row][0] ;
97 if( cells_in_row > 1 ) {
98 /* at least one row has more than one cell */
99 /* check to see if we have moveable cells in row */
100 free_cells = 0 ;
101 for( a = 1; a <= cells_in_row; a++ ){
102 aptr = pairArrayG[row][a] ;
103 acellptr = carrayG[ aptr ] ;
104 if( acellptr->cclass >= 0 ) {
105 free_cells++ ;
106 }
107 }
108 if( free_cells >= 3 ){
109 /* need at least three cells to do meaningful work. */
110 /* otherwise we will spend more time looking for the cells */
111 one_cell_per_row = FALSE ;
112 break ;
113 }
114 }
115 }
116 if( one_cell_per_row ) {
117 return ;
118 }
119
120 while( attempts < attmaxG && oattempts < 2 * attmaxG ) {
121 ablock = PICK_INT( 1 , numRowsG ) ;
122 if( pairArrayG[ablock][0] <= 1 ) {
123 continue ;
124 }
125 aptr = PICK_INT( 1 , pairArrayG[ablock][0] ) ;
126
127 a = pairArrayG[ablock][aptr] ;
128 acellptr = carrayG[ a ] ;
129 if( acellptr->cclass < 0 ) {
130 continue ;
131 }
132 aorient = acellptr->corient ;
133
134 ablckptr = barrayG[ ablock ] ;
135 axcenter = acellptr->cxcenter ;
136
137 aleft = acellptr->tileptr->left ;
138 aright = acellptr->tileptr->right ;
139 startx1 = axcenter + aleft ;
140 endx1 = axcenter + aright ;
141
142 if( orientation_optimizationG ) {
143 goto ort ;
144 }
145
146 if( aptr > 1 ) {
147 cellleft = pairArrayG[ablock][aptr - 1] ;
148 if( carrayG[cellleft]->cclass < 0 ) {
149 cellleft = 0 ;
150 }
151 } else {
152 cellleft = 0 ;
153 }
154 if( aptr < pairArrayG[ablock][0] ) {
155 cellrite = pairArrayG[ablock][aptr + 1] ;
156 if( carrayG[cellrite]->cclass < 0 ) {
157 cellrite = 0 ;
158 }
159 } else {
160 cellrite = 0 ;
161 }
162
163 /*
164 if( intel || fences_exist ) {
165 if( cellleft != 0 ) {
166 bcellptr = carrayG[cellleft] ;
167 leftEdge = bcellptr->cxcenter + bcellptr->tileptr->left ;
168 anxcenter = leftEdge - aleft ;
169 bnxcenter = endx1 - bcellptr->tileptr->right ;
170 if( eval_range( acellptr, bcellptr, axcenter, anxcenter,
171 bcellptr->cxcenter, bnxcenter ) == 0 ) {
172 cellleft = 0 ;
173 }
174 }
175 if( cellrite != 0 ) {
176 bcellptr = carrayG[cellrite] ;
177 riteEdge = bcellptr->cxcenter + bcellptr->tileptr->right ;
178 anxcenter = riteEdge - aright ;
179 bnxcenter = startx1 - bcellptr->tileptr->left ;
180 if( eval_range( acellptr, bcellptr, axcenter, anxcenter,
181 bcellptr->cxcenter, bnxcenter ) == 0 ) {
182 cellrite = 0 ;
183 }
184 }
185 }
186 */
187
188 if( cellleft == 0 && cellrite == 0 ) {
189 continue ;
190 }
191
192 if( cellleft != 0 && cellrite != 0 ) {
193 if( PICK_INT(1 , 2) == 1 ){
194 /*
195 * Take the left neighbor first.
196 */
197 b = cellleft ;
198 bcellptr = carrayG[b] ;
199 leftEdge = bcellptr->cxcenter + bcellptr->tileptr->left ;
200 anxcenter = leftEdge - aleft ;
201 bnxcenter = endx1 - bcellptr->tileptr->right ;
202 if( ucxxp( a, b, anxcenter, bnxcenter ) ) {
203 flips++ ;
204 attempts++ ;
205 pairArrayG[ablock][aptr] = b ;
206 pairArrayG[ablock][aptr - 1] = a ;
207 } else {
208 attempts++ ;
209 b = cellrite ;
210 bcellptr = carrayG[b] ;
211 riteEdge = bcellptr->cxcenter
212 + bcellptr->tileptr->right ;
213 anxcenter = riteEdge - aright ;
214 bnxcenter = startx1 - bcellptr->tileptr->left ;
215 if( ucxxp( a, b, anxcenter, bnxcenter ) ) {
216 flips++ ;
217 pairArrayG[ablock][aptr] = b ;
218 pairArrayG[ablock][aptr + 1] = a ;
219 }
220 attempts++ ;
221 }
222 } else {
223 b = cellrite ;
224 bcellptr = carrayG[b] ;
225 riteEdge = bcellptr->cxcenter + bcellptr->tileptr->right ;
226 anxcenter = riteEdge - aright ;
227 bnxcenter = startx1 - bcellptr->tileptr->left ;
228 if( ucxxp( a, b, anxcenter, bnxcenter ) ) {
229 flips++ ;
230 attempts++ ;
231 pairArrayG[ablock][aptr] = b ;
232 pairArrayG[ablock][aptr + 1] = a ;
233 } else {
234 attempts++ ;
235 b = cellleft ;
236 bcellptr = carrayG[b] ;
237 leftEdge = bcellptr->cxcenter + bcellptr->tileptr->left;
238 anxcenter = leftEdge - aleft ;
239 bnxcenter = endx1 - bcellptr->tileptr->right ;
240 if( ucxxp( a, b, anxcenter, bnxcenter ) ) {
241 flips++ ;
242 pairArrayG[ablock][aptr] = b ;
243 pairArrayG[ablock][aptr - 1] = a ;
244 }
245 attempts++ ;
246 }
247 }
248 } else {
249 if( cellleft ) {
250 b = cellleft ;
251 bcellptr = carrayG[b] ;
252 leftEdge = bcellptr->cxcenter + bcellptr->tileptr->left ;
253 anxcenter = leftEdge - aleft ;
254 bnxcenter = endx1 - bcellptr->tileptr->right ;
255 if( ucxxp( a, b, anxcenter, bnxcenter ) ) {
256 flips++ ;
257 pairArrayG[ablock][aptr] = b ;
258 pairArrayG[ablock][aptr - 1] = a ;
259 }
260 attempts++ ;
261 } else if( cellrite != 0 &&
262 carrayG[cellrite]->cclass >= 0 &&
263 acellptr->cclass >= 0 ) {
264 b = cellrite ;
265 bcellptr = carrayG[b] ;
266 riteEdge = bcellptr->cxcenter + bcellptr->tileptr->right ;
267 anxcenter = riteEdge - aright ;
268 bnxcenter = startx1 - bcellptr->tileptr->left ;
269 if( ucxxp( a, b, anxcenter, bnxcenter ) ) {
270 flips++ ;
271 pairArrayG[ablock][aptr] = b ;
272 pairArrayG[ablock][aptr + 1] = a ;
273 }
274 attempts++ ;
275 }
276 }
277 ort:if( ablckptr->borient == 1 ) {
278 if( acellptr->orflag != 0 ) {
279 uc0( a , (aorient == 0) ? 2 : 0 ) ;
280 oattempts++ ;
281 }
282 } else {
283 if( acellptr->orflag != 0 ) {
284 uc0( a , (aorient == 1) ? 3 : 1 ) ;
285 oattempts++ ;
286 }
287 }
288 D( "upair",
289 check_cost() ;
290 ) ;
291 }
292 sprintf( YmsgG, " %3d %6.3f %9d %3d%s %-8ld\n", iterationG+1, TG, funccostG,
293 (INT)( 100.0 * (DOUBLE)(flips) / (DOUBLE)(attmaxG) ) , "%" ,
294 timingcostG ) ;
295 M( MSG, NULL, YmsgG ) ;
296 return;
297 }
298
299
eval_range(acellptr,bcellptr,axc,anxc,bxc,bnxc)300 INT eval_range( acellptr , bcellptr, axc , anxc , bxc , bnxc )
301 CBOXPTR acellptr , bcellptr ;
302 INT axc , anxc , bxc , bnxc ;
303 {
304
305 FENCEBOXPTR fence ;
306 INT a_current_penalty , a_new_penalty ;
307 INT b_current_penalty , b_new_penalty ;
308
309
310 if( (fence = acellptr->fence) == NULL ) {
311 a_current_penalty = 0 ;
312 } else {
313 a_current_penalty = 10000000 ;
314 }
315 for( fence = acellptr->fence ; fence && a_current_penalty != 0 ;
316 fence = fence->next_fence ) {
317 if( axc < fence->min_xpos ) {
318 if( fence->min_xpos - axc < a_current_penalty ) {
319 a_current_penalty = fence->min_xpos - axc ;
320 }
321 } else if( axc > fence->max_xpos ) {
322 if( axc - fence->max_xpos < a_current_penalty ) {
323 a_current_penalty = axc - fence->max_xpos ;
324 }
325 } else {
326 a_current_penalty = 0 ;
327 }
328 }
329 if( (fence = bcellptr->fence) == NULL ) {
330 b_current_penalty = 0 ;
331 } else {
332 b_current_penalty = 10000000 ;
333 }
334 for( ; fence && b_current_penalty != 0 ; fence = fence->next_fence ) {
335 if( bxc < fence->min_xpos ) {
336 if( fence->min_xpos - bxc < b_current_penalty ) {
337 b_current_penalty = fence->min_xpos - bxc ;
338 }
339 } else if( bxc > fence->max_xpos ) {
340 if( bxc - fence->max_xpos < b_current_penalty ) {
341 b_current_penalty = bxc - fence->max_xpos ;
342 }
343 } else {
344 b_current_penalty = 0 ;
345 }
346 }
347
348 if( (fence = acellptr->fence) == NULL ) {
349 a_new_penalty = 0 ;
350 } else {
351 a_new_penalty = 10000000 ;
352 }
353 for( ; fence && a_new_penalty != 0 ; fence = fence->next_fence ) {
354 if( anxc < fence->min_xpos ) {
355 if( fence->min_xpos - anxc < a_new_penalty ) {
356 a_new_penalty = fence->min_xpos - anxc ;
357 }
358 } else if( anxc > fence->max_xpos ) {
359 if( anxc - fence->max_xpos < a_new_penalty ) {
360 a_new_penalty = anxc - fence->max_xpos ;
361 }
362 } else {
363 a_new_penalty = 0 ;
364 }
365 }
366 if( (fence = bcellptr->fence) == NULL ) {
367 b_new_penalty = 0 ;
368 } else {
369 b_new_penalty = 10000000 ;
370 }
371 for( ; fence && b_new_penalty != 0 ; fence = fence->next_fence ) {
372 if( bnxc < fence->min_xpos ) {
373 if( fence->min_xpos - bnxc < b_new_penalty ) {
374 b_new_penalty = fence->min_xpos - bnxc ;
375 }
376 } else if( bnxc > fence->max_xpos ) {
377 if( bnxc - fence->max_xpos < b_new_penalty ) {
378 b_new_penalty = bnxc - fence->max_xpos ;
379 }
380 } else {
381 b_new_penalty = 0 ;
382 }
383 }
384
385 if( a_new_penalty + b_new_penalty <= a_current_penalty +
386 b_current_penalty ) {
387 return(1) ;
388 } else {
389 return(0) ;
390 }
391
392 }
393