1 /*
2 * Copyright (C) 1989-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: penalties.c
42 DESCRIPTION:calculation of the penalty coefficients
43 CONTENTS:
44 DATE: Mar 1, 1989
45 REVISIONS: May 16, 1989 - removed most doPartitionG conditions.
46 Apr 23, 1990 - modified for new graph routines and
47 modified timing constant update to use a constant
48 derived at high temperatures.
49 Mon Feb 4 02:16:26 EST 1991 - added overlap penalty
50 override for testing purposes.
51 Thu Feb 7 00:20:00 EST 1991 - reworked graph data.
52 Thu Apr 18 01:40:16 EDT 1991 - refit overlap parameters.
53 ----------------------------------------------------------------- */
54
55 #include <custom.h>
56 #include <temp.h>
57 #include <yalecad/debug.h>
58 #include <yalecad/file.h>
59 #define DEBUGLAPFACTOR
60
61 #define DAMPFACTOR 0.015 /* damping factor on overlap penalty */
62 #define COREDAMPFACTOR 0.10 /* damping factor on core oversize */
63 #define CORECAP 1.30 /* maximum penalty for core error */
64 #define COREMIN 1.00 /* min error for core at end */
65 #define LAPMIN 1.00 /* min penalty factor for binpenalty */
66 #define LAPCAPFACTOR 100.00 /* lap penalty max is 100x funccost */
67 #define TIMEFACTOR 3.00 /* ration of time to funccost */
68 #define STARTCORE 0.10 /* start core for placement case */
69 #define ENDCORE 0.05 /* end core for placement case */
70 #define STARTOVERLAP 0.70 /* start overlap for placement case */
71 #define ENDOVERLAP 0.15 /* end overlap for placement case */
72 #define INITFACTOR 1.00 /* initial penalty factors */
73 #define INITNETPENAL 1000.00 /* dummy value to avoid / 0 */
74
75
76
77 /* -----------------------------------------------------------------
78 Initial weight of various penalties to wirelength cost Penalties
79 are INITRELXXXX% of the wirelength part. This is not critical
80 since negative feedback will correct our possible mistake.
81 -------------------------------------------------------------- */
82 #define INITRELLAP 0.40 /* overlap relative to funccost */
83
84 static DOUBLE coreAreaS ; /* the area of the core */
85 static DOUBLE start_core_errorS ;/* the start and stop target */
86 static DOUBLE end_core_errorS ; /* ratios for the various */
87 static DOUBLE start_overlapS ; /* penalties. */
88 static DOUBLE end_overlapS ;
89 static BOOL firstLapS = TRUE; /* 1st time calc_init_lapFactor called */
90 static BOOL firstTimeS = TRUE;/* 1st time calc_init_timeFactor called*/
91
92 /* -----------------------------------------------------------------
93 Use negative feedback to control relative ratio between penalties
94 */
95
96 /* **** overlap penalty controller **** */
calc_lap_factor(percentDone)97 DOUBLE calc_lap_factor( percentDone )
98 DOUBLE percentDone ;
99 {
100
101 DOUBLE diff_lap, target_bin_penalty, bin_deviation ;
102 DOUBLE sqrtCoreArea, sqrtBinPenal, lapCap ;
103 INT iter ;
104 char filename[LRECL] ;
105 FILE *fp ;
106
107 #define A 0.84379
108 #define B -1.7294E-4
109 #define C -2.3867E-5
110 /* - - - - - - - - - - - - - -- - - - - - - - - - - - - - - - - -
111 Initialize beginning average to one so that in beginning
112 controller can change alot to adjust to conditions. Later the
113 average will diminish the result.
114 - - - - - - - - - - - - - -- - - - - - - - - - - - - - - - - - */
115 # define NUMSAMPLE 15
116 # define RECIP_SAMPLE 0.06666666
117 static DOUBLE avg_devS[NUMSAMPLE] = { 0.0 } ;
118 static INT avgCountS = 0 ;
119 DOUBLE running_avg ;
120 INT i ;
121
122
123 /* **** overlap penalty controller **** */
124 /* no damping at the start so that controller can react quickly */
125
126 /* calculate target penalty for overlap penalty. */
127 sqrtCoreArea = sqrt( coreAreaS ) ;
128 iter = iterationG + 2 ;
129 diff_lap = A + B*iter + C*iter*iter ;
130 if( percentDone > 2.0 ){
131 diff_lap = 0.01 ;
132 }
133 target_bin_penalty = diff_lap * sqrt( coreAreaS ) ;
134 sqrtBinPenal = sqrt( (DOUBLE) binpenalG ) ;
135
136 /* bin_deviation is percent error relative to target */
137 bin_deviation =
138 (sqrtBinPenal - target_bin_penalty) / target_bin_penalty ;
139
140 Yplot_heading( 0, "graph_lap", "iter","binpenal","sqrtbin",
141 "coreArea","sqrtCore", "percent","sqrtpercent",
142 "target", "lapFactor", "bin_dev", NULL ) ;
143 Yplot( 0, "graph_lap", "%d", iterationG, "%4.4le %4.4le %4.4le %4.4le",
144 (DOUBLE) binpenalG, sqrtBinPenal, coreAreaS, sqrtCoreArea ) ;
145
146 /* save running average of deviations */
147 avg_devS[avgCountS++ % NUMSAMPLE] = bin_deviation ;
148 running_avg = 0.0 ;
149 for( i = 0; i < NUMSAMPLE; i++ ){
150 running_avg += avg_devS[i] ;
151 }
152 running_avg *= RECIP_SAMPLE ;
153
154 if( avgCountS >= NUMSAMPLE ){
155 /* use running average to bound maximum change in lapFactor */
156 if( running_avg > 0.0 ){
157 /* bound between 0 and running average */
158 bin_deviation = MAX( bin_deviation, 0.0 ) ;
159 bin_deviation = MIN( bin_deviation, running_avg ) ;
160 } else {
161 /* bound between 0 and - running average */
162 bin_deviation = MIN( bin_deviation, 0.0 ) ;
163 bin_deviation = MAX( bin_deviation, running_avg ) ;
164 }
165 }
166
167 lapFactorG *= (1.0 + bin_deviation) ;
168 Yplot( "graph_lap", "%d", iterationG,
169 "%4.4le %4.4le %4.4le %4.4le %4.4le",
170 (DOUBLE) binpenalG / coreAreaS,
171 sqrtBinPenal / sqrtCoreArea,
172 target_bin_penalty, lapFactorG, bin_deviation ) ;
173 Yplot_flush( "graph_lap" ) ;
174
175 lapFactorG = (lapFactorG > LAPMIN) ? lapFactorG : LAPMIN ;
176 lapCap = LAPCAPFACTOR * (DOUBLE) funccostG / sqrtBinPenal ;
177 lapFactorG = (lapFactorG < lapCap) ? lapFactorG : lapCap ;
178
179 /* this is an override mechanism to setting parameters */
180 sprintf( filename, "%s.lap", cktNameG ) ;
181 if( fp = TWOPEN( filename, "r", NOABORT )){
182 HPI( fp, &lapFactorG ) ;
183 TWCLOSE( fp ) ;
184 }
185 return( lapFactorG ) ;
186
187 } /* ********* end overlap penalty controller ******** */
188
calc_time_factor(percentDone)189 DOUBLE calc_time_factor( percentDone )
190 DOUBLE percentDone ;
191 {
192 /* **** timing penalty controller **** */
193 /* don't change it from initial value */
194 return( timeFactorG ) ;
195 /* ********* end timing penalty controller ******** */
196
197 } /* end function calc_time_penalty */
198
199
200 /* -----------------------------------------------------------------
201 Calculate the new core area as a function of time. Reconfigure
202 the core according to this new target compensating overlap penalty
203 to account for change in cell areas. Calculate cell areas with
204 routing areas = TRUE. Core_deviation varies as the negative of
205 the error measurement. That is why target_core_error and core_error
206 in core_deviation calculation are reversed.
207 */
calc_core_factor(percentDone)208 DOUBLE calc_core_factor( percentDone )
209 DOUBLE percentDone ;
210 {
211 INT binArea, cellArea ;
212 DOUBLE diff_core, target_core_error, core_deviation ;
213 DOUBLE core_error ;
214
215 binArea = get_bin_area() ;
216 cellArea = calc_cellareas( TRUE ) ;
217 diff_core = start_core_errorS - end_core_errorS ;
218 core_error = (DOUBLE) (binArea - cellArea) / (DOUBLE) cellArea ;
219 target_core_error = (start_core_errorS - diff_core * percentDone ) ;
220 core_deviation =
221 COREDAMPFACTOR * (DOUBLE) (target_core_error - core_error) ;
222 coreFactorG *= 1.0 + core_deviation ;
223 coreFactorG = (coreFactorG > COREMIN ) ? coreFactorG : COREMIN ;
224 coreFactorG = (coreFactorG < CORECAP) ? coreFactorG : CORECAP ;
225 coreAreaS = coreFactorG * (DOUBLE) cellArea ;
226 /* reconfigure area and place pads */
227 reconfigure( maxBinXG-1,maxBinYG-1, coreAreaS ) ;
228 return( coreFactorG ) ;
229 } /* end calc_core_factor */
230
231
232
233 /* *****************************************************************
234 INITIAL LAP FACTOR CALCULATION
235 Currently, just set lapFactor initially to 40% of wirelength. This
236 could use move investigation in the future.
237 */
calc_init_lapFactor(totFunc,totPen)238 DOUBLE calc_init_lapFactor( totFunc, totPen )
239 DOUBLE totFunc ;
240 DOUBLE totPen ;
241 {
242 DOUBLE factor ;
243 #ifdef DEBUGLAPFACTOR
244 extern DOUBLE saveLapFactorG ;
245 #endif
246
247 /* first iteration, we set all factors to 1 */
248 /* since every move is acceptted */
249 if( firstLapS ){
250 firstLapS = FALSE ;
251 start_overlapS = INITFACTOR ; end_overlapS = INITFACTOR ;
252 return( INITFACTOR ) ;
253 }
254 if( totPen > EPSILON ){
255 factor = INITRELLAP * totFunc / totPen ;
256 }
257
258 /* -----------------------------------------------------------
259 The penalty controller forces overlap to go from :
260 start_overlap*binArea to end_overlap*binArea
261 ----------------------------------------------------------- */
262
263 #ifdef DEBUGLAPFACTOR
264 start_overlapS = STARTOVERLAP ; end_overlapS = saveLapFactorG ;
265 #else
266 start_overlapS = STARTOVERLAP ; end_overlapS = ENDOVERLAP ;
267 #endif
268 OUT2("\n\nOVERLAP FACTOR (COMPUTED) : %f\n", lapFactorG ) ;
269 OUT3("start_overlap: %4.2le end_overlap: %4.2le\n\n",
270 start_overlapS, end_overlapS ) ;
271
272 return( factor ) ;
273
274 } /* end calc_init_lapFactor */
275
276
277 /* *****************************************************************
278 INITIAL TIME FACTOR CALCULATION
279 Currently, just set timeFactor initially to 40% of wirelength. This
280 could use move investigation in the future.
281 */
calc_init_timeFactor(avgdFunc,avgdTime)282 DOUBLE calc_init_timeFactor( avgdFunc, avgdTime )
283 DOUBLE avgdFunc ;
284 DOUBLE avgdTime ;
285 {
286 if( firstTimeS ){
287 firstTimeS = FALSE ;
288 return( INITFACTOR ) ;
289 } else {
290 if( avgdTime > EPSILON ){
291 return( TIMEFACTOR * avgdFunc / avgdTime ) ;
292 } else {
293 return( 0.0 ) ;
294 }
295 }
296
297 } /* end calc_init_timeFactor */
298
calc_init_coreFactor()299 DOUBLE calc_init_coreFactor( )
300 {
301
302 /* --------------------------------------------------------------
303 The penalty controller forces corearea to go from :
304 start_core_error*cellArea to end_core_error*cellArea
305 initialize coreFactor to binArea / cellarea.
306 ----------------------------------------------------------- */
307 coreFactorG = (DOUBLE) get_bin_area() /
308 (DOUBLE) calc_cellareas(TRUE ) ;
309
310 start_core_errorS = STARTCORE ; end_core_errorS = ENDCORE ;
311
312 OUT3("start_core: %4.2le end_overcore: %4.2le\n\n",
313 start_core_errorS, end_core_errorS ) ;
314 return( coreFactorG ) ;
315 } /* end calc_init_coreFactor */
316