1 /*
2 * Copyright (C) 1988-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: acceptt.c
42 DESCRIPTION:accept routine used in simulated annealing
43 CONTENTS: acceptt( INT )
44 DATE: Jan 30, 1988
45 REVISIONS:
46 ----------------------------------------------------------------- */
47
48 #include <yalecad/base.h>
49 #include <yalecad/debug.h>
50 #include "main.h"
51 #include "standard.h"
52
53 #define MASK 0x3ff
54
55 static DOUBLE table1S[1024] , table2S[1024] , table3S[1024] ;
56
init_table()57 void init_table()
58 {
59 INT i2 ;
60 table1S[0] = 1.0 ;
61 table2S[0] = 1.0 ;
62 table3S[0] = 1.0 ;
63 for( i2 = 1 ; i2 <= 1023 ; i2++ ) {
64 table1S[ i2 ] = exp( -(DOUBLE) i2 / 8.0 ) ;
65 table2S[ i2 ] = exp( -(DOUBLE) i2 / 8192.0 ) ;
66 table3S[ i2 ] = exp( -(DOUBLE) i2 / 8388608.0 ) ;
67 }
68 }
69
70 #ifdef DEBUG_CODE
71 static FILE *fpS = NULL ;
acceptt(d_wire,d_time,d_penal)72 BOOL acceptt( d_wire, d_time, d_penal )
73 INT d_wire, d_time, d_penal ;
74 {
75 BOOL truth ;
76 INT time ;
77 extern INT aG ;
78
79 time = d_time ;
80 truth = acceptt2( d_wire, d_time, d_penal ) ;
81 if(!fpS){
82 fpS = fopen( "newcost.dat", "w" ) ;
83 }
84 fprintf( fpS, "delta_cost:%10d w:%10d t:%10d p:%10d accept:%d cell:%d\n",
85 d_costG, d_wire, time, d_penal, truth, aG ) ;
86 fflush( fpS ) ;
87 return( truth ) ;
88
89 }
90 #endif /* DEBUG_CODE */
91
92 /* -----------------------------------------------------------------
93 Acceptance function for the annealing algorithm. We expect all
94 deltas to be of the form (old_cost - new_cost). If new_cost is
95 less than the old_cost, the quantity will be positive and always
96 acceptted. The variable d_costG lets the statistic accumulation
97 code know of the change.
98 ----------------------------------------------------------------- */
acceptt(d_wire,d_time,d_penal)99 BOOL acceptt( d_wire, d_time, d_penal )
100 INT d_wire, d_time, d_penal ;
101 {
102
103 DOUBLE fred ;
104 register unsigned fract ;
105
106 /* d_time = (INT) ( 10.0 * timeFactorG * (DOUBLE) d_time ) ; */
107 d_time = (INT) ( timeFactorG * (DOUBLE) d_time ) ;
108 d_costG = d_wire + d_time + d_penal ;
109 if( d_costG >= 0 ){
110 return( TRUE ) ;
111 } else {
112 fred = ((DOUBLE) d_costG ) / TG ;
113 }
114
115 /* Now we are left with the uphill moves */
116 if( fred < -80.0 ) {
117 return( FALSE ) ;
118 } else if( fred > -0.0001 ) {
119 if( 1.0 + fred > ( (DOUBLE) RAND / (DOUBLE)0x7fffffff ) ) {
120 return( TRUE ) ;
121 } else {
122 return( FALSE ) ;
123 }
124 } else {
125 fract = (INT)( -fred * 8388608.0 ) ;
126 if( (table1S[ (fract >> 20) & MASK ] *
127 table2S[ (fract >> 10) & MASK] *
128 table3S[ fract & MASK ]) >
129 ( (DOUBLE) RAND / (DOUBLE)0x7fffffff ) ) {
130 return( TRUE ) ;
131 } else {
132 return( FALSE ) ;
133 }
134 }
135 } /* end acceptt() */
136
137
138 /* -----------------------------------------------------------------
139 Greedy acceptance function for the annealing algorithm. We expect
140 all deltas to be of the form (old_cost - new_cost). If new_cost is
141 less than the old_cost, the quantity will be positive and always
142 acceptted.
143 ----------------------------------------------------------------- */
accept_greedy(d_wire,d_time,d_penal)144 BOOL accept_greedy( d_wire, d_time, d_penal )
145 INT d_wire, d_time, d_penal ;
146 {
147
148 if( d_time == 0 ){
149 /* in the case the delta time is zero, use wirelength */
150 d_costG = d_wire + d_penal ;
151 if( d_costG >= 0 ){
152 return( TRUE ) ;
153 } else {
154 return( FALSE ) ;
155 }
156 } else {
157 /* If we have a timing constraint, use it */
158 d_costG = d_time + d_penal ;
159 if( d_costG >= 0 ){
160 return( TRUE ) ;
161 } else {
162 return( FALSE ) ;
163 }
164 }
165 } /* end accept_greedy() */
166