1 /*
2 * Copyright (C) 1988-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: usite2.c
42 DESCRIPTION:two cell flip and/or orientation change
43 CONTENTS: BOOL usite2( )
44 DATE: Jan 30, 1988
45 REVISIONS: Feb 5, 1988 - changed old_apos, new_apos, old_bpos,
46 new_bpos to global variables. Old method remains
47 commented out.
48 Aug 25, 1988 - calls to ufixpin and usoftpin changed.
49 Oct 21, 1988 - changed to sqrt for overlap penalty.
50 Nov 25, 1988 - added timing driven code.
51 May 3, 1989 - added unet2 for two cell swaps.
52 ----------------------------------------------------------------- */
53
54 #include <custom.h>
55 #include <yalecad/debug.h>
56
57 static INT acellS, bcellS, mod_cellS ;
58 static CELLBOXPTR acellptrS , bcellptrS ;
59
usite2()60 BOOL usite2( /* old_apos, new_apos, old_bpos, new_bpos */ )
61 /* MOVEBOXPTR *old_apos, *new_apos, *old_bpos, *new_bpos ; */
62 {
63
64 PINBOXPTR anewtermptr , bnewtermptr ;
65 MOVEBOXPTR pos ; /* temp pointer for easier access */
66 BINBOXPTR modptr ;
67
68 INT cost , newpenalty, newbinpenal, newtimepenalty, newtimepenal ;
69 INT oldBinX, oldBinY, limit, *oldCellList ;
70 INT modBinX, modBinY, *modCellList ;
71 INT i ;
72 INT wire_chg ;
73 DOUBLE delta_wire ;
74
75 /* -----------------------------------------------------------------
76 global information is stored in element zero of position arrays
77 new position records have been initialized in uloop().
78 */
79 acellS = new_apos0G->cell ;
80 acellptrS = cellarrayG[acellS] ;
81 anewtermptr = acellptrS->pinptr ;
82
83 bcellS = new_bpos0G->cell ;
84 bcellptrS = cellarrayG[bcellS] ;
85 bnewtermptr = bcellptrS->pinptr ;
86
87 clear_net_set() ; /* reset set to mark nets that have changed position */
88
89 /* remove overlap so that pairwise exchange has better chance at low T*/
90 mod_cellS = 0 ;
91 /* mod_cell_positions() ; */
92
93 /* save state of penalty */
94 newbinpenal = binpenalG ;
95
96 /* adjust overlap penalty */
97 newbinpenal += overlap2( /* old_apos, new_apos, old_bpos, new_bpos */ ) ;
98
99 /* scale newpenalty for feedback circuit */
100 newpenalty = (INT) ( lapFactorG * sqrt( (DOUBLE) newbinpenal ) ) ;
101
102 upin_test( anewtermptr, new_apos0G ) ;
103 upin_test( bnewtermptr, new_bpos0G ) ;
104
105 cost = funccostG ;
106
107 cost += unet2( anewtermptr, bnewtermptr ) ;
108
109 wire_chg = cost - funccostG ;
110
111 newtimepenal = timingpenalG ;
112 newtimepenal += calc_incr_time2( acellS, bcellS ) ;
113
114 ASSERT( newtimepenal == dcalc_full_penalty(),"usite2","Timing woes\n" ) ;
115
116 /* scale new timing penalty */
117 newtimepenalty = (INT) ( timeFactorG * (DOUBLE) newtimepenal ) ;
118
119 if( acceptt( penaltyG - newpenalty - wire_chg +
120 timingcostG - newtimepenalty )){
121
122 upin_accept( anewtermptr ) ;
123 upin_accept( bnewtermptr ) ;
124
125 update_overlap2( /* old_aposG, old_bposG */ ) ;
126
127 update_time2( acellS, bcellS ) ;
128
129 /* update new position and orientation of a cell */
130 acellptrS->xcenter = new_apos0G->xcenter ;
131 acellptrS->ycenter = new_apos0G->ycenter ;
132 acellptrS->orient = new_apos0G->orient ;
133
134 bcellptrS->xcenter = new_bpos0G->xcenter ;
135 bcellptrS->ycenter = new_bpos0G->ycenter ;
136 bcellptrS->orient = new_bpos0G->orient ;
137
138 /* ************ BEGIN UPDATE OF BIN CELL LIST ************** */
139 if( !(mod_cellS) ){
140 /* a and b are swapped - assert old_apos0 has b new position */
141 /* and newcellList has new a position calculated in uloop.c */
142 oldBinX = SETBINX(old_apos0G->xcenter) ;
143 oldBinY = SETBINY(old_apos0G->ycenter) ;
144 oldCellList = binptrG[oldBinX][oldBinY]->cells ;
145
146 /* do nothing if cell a remains in same bin */
147 if( oldCellList != newCellListG ){
148
149 /* swap a for b in oldcellList */
150 /* find a 's position in array */
151 limit = oldCellList[0] ;
152 for( i=1;i<=limit;i++ ){
153 if( oldCellList[i] == acellS ){
154 oldCellList[i] = bcellS ;
155 break ;
156 }
157 } /* assert i now has correct value of b */
158 ASSERT( oldCellList[i] == bcellS,"usite2",
159 "Problem in oldbin cell lists\n" ) ;
160
161 /* swap b for a in newcellList */
162 /* find a 's position in array */
163 limit = newCellListG[0] ;
164 for( i=1;i<=limit;i++ ){
165 if( newCellListG[i] == bcellS ){
166 newCellListG[i] = acellS ;
167 break ;
168 }
169 } /* assert i now has correct value of a */
170 ASSERT( newCellListG[i] == acellS,"usite2",
171 "Problem in newbin cell lists\n" ) ;
172 }
173
174 } else if( mod_cellS == acellS ){
175 /* a's bin is modified by the moving cells apart */
176 oldBinX = SETBINX(old_apos0G->xcenter) ;
177 oldBinY = SETBINY(old_apos0G->ycenter) ;
178 oldCellList = binptrG[oldBinX][oldBinY]->cells ;
179 modBinX = SETBINX(new_apos0G->xcenter) ;
180 modBinY = SETBINY(new_apos0G->ycenter) ;
181 modptr = binptrG[modBinX][modBinY] ;
182 modCellList = modptr->cells ;
183
184 /* add b to oldCellList - find a 's position in array */
185 limit = oldCellList[0] ;
186 for( i=1;i<=limit;i++ ){
187 if( oldCellList[i] == acellS ){
188 oldCellList[i] = bcellS ;
189 break ;
190 }
191 }
192 /* assert i now has correct value of b */
193 ASSERT( oldCellList[i] == bcellS, "usite2",
194 "Problem in oldbin cell lists\n");
195
196 /* delete b in newCellList */
197 limit = newCellListG[0] ;
198 for( i=1;i<=limit;i++ ){
199 if( newCellListG[i] == bcellS ){
200 break ;
201 }
202 }
203 ASSERT( newCellListG[i] == bcellS, "usite2",
204 "Problem in newbin cell lists\n" ) ;
205
206 if( i != limit ){
207 newCellListG[i] = newCellListG[ limit ] ;
208 }
209 newCellListG[0]-- ;
210
211 /* now add a to modified bin */
212 limit = ++modCellList[0] ;
213 if( limit >= modptr->space ){
214 modptr->space += EXPCELLPERBIN ;
215 modCellList = (INT *) Ysafe_realloc( modCellList,
216 modptr->space * sizeof(INT) ) ;
217 }
218 modCellList[limit] = acellS ;
219
220 } else if( mod_cellS == bcellS ){
221 /* b's bin is modified by the moving cells apart */
222 oldBinX = SETBINX(old_apos0G->xcenter) ;
223 oldBinY = SETBINY(old_apos0G->ycenter) ;
224 oldCellList = binptrG[oldBinX][oldBinY]->cells ;
225 modBinX = SETBINX(new_bpos0G->xcenter) ;
226 modBinY = SETBINY(new_bpos0G->ycenter) ;
227 modptr = binptrG[modBinX][modBinY] ;
228 modCellList = modptr->cells ;
229
230 /* add a to newCellList - find b 's position in array */
231 /* this delete's b's old position */
232 limit = newCellListG[0] ;
233 for( i=1;i<=limit;i++ ){
234 if( newCellListG[i] == bcellS ){
235 newCellListG[i] = acellS ;
236 break ;
237 }
238 }
239 /* assert i now has correct value of a */
240 ASSERT( newCellListG[i] == acellS, "usite2",
241 "Problem in newbin cell lists\n" ) ;
242
243 /* delete a in oldCellList */
244 limit = oldCellList[0] ;
245 for( i=1;i<=limit;i++ ){
246 if( oldCellList[i] == acellS ){
247 break ;
248 }
249 }
250 ASSERT( oldCellList[i] == acellS, "usite2",
251 "Problem in oldbin cell lists\n" ) ;
252
253 if( i != limit ){
254 oldCellList[i] = oldCellList[ limit ] ;
255 }
256 oldCellList[0]-- ;
257
258 /* now add b to modified bin */
259 limit = ++modCellList[0] ;
260 if( limit >= modptr->space ){
261 modptr->space += EXPCELLPERBIN ;
262 modCellList = (INT *) Ysafe_realloc( modCellList,
263 modptr->space * sizeof(INT) ) ;
264 }
265 modCellList[limit] = bcellS ;
266
267 } /* ********** END UPDATE OF BIN CELL LIST ************** */
268
269 /* check that everything is ok */
270 ASSERT( checkbinList(), "usite2",
271 "We have a problem at checkbinList()\n") ;
272
273 funccostG = cost ;
274 penaltyG = newpenalty ;
275 binpenalG = newbinpenal ;
276 timingcostG = newtimepenalty ;
277 timingpenalG = newtimepenal ;
278
279 return (ACCEPT) ;
280 } else {
281 return (REJECT) ;
282 }
283 }
284