1 /*
2 * Copyright (C) 1991-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: wireratio.c
42 DESCRIPTION:This file contains routines for analyzing random to
43 optimal wire ratio.
44 CONTENTS: wireratio
45 DATE: Tue Jan 15 20:54:36 PST 1991
46 REVISIONS: Fri Jan 25 18:15:36 PST 1991 - added numpins to equations
47 untested at this time.
48 Mon Feb 4 02:27:16 EST 1991 - working SVD fit algorithm
49 that also checks for small cases.
50 Thu Feb 7 00:22:56 EST 1991 - last solution for small
51 cases didn't resize memory properly.
52 Wed May 1 19:18:55 EDT 1991 - added switchbox field
53 so we can ignore these areas during wire estimation.
54 ----------------------------------------------------------------- */
55
56 #include <custom.h>
57 #include <dens.h>
58 #include <yalecad/debug.h>
59 #include <yalecad/file.h>
60 #include <gsl/gsl_vector.h>
61 #include <gsl/gsl_matrix.h>
62 #include <gsl/gsl_linalg.h>
63
gsl_matrix_disp(mptr,rows,cols)64 static void gsl_matrix_disp( mptr, rows, cols )
65 gsl_matrix *mptr ;
66 int rows, cols;
67 {
68 INT i, j ;
69
70 for( i=0; i < rows; i++ ){
71 for( j=0; j < cols; j++ ){
72 fprintf( stderr, "% 4.4le ", gsl_matrix_get(mptr, i, j)) ;
73 }
74 fprintf( stderr, "\n" ) ;
75 }
76 fprintf( stderr, "\n" ) ;
77 } /* end gsl_matrix_disp */
78
gsl_vector_disp(vptr,rows)79 static void gsl_vector_disp( vptr, rows )
80 gsl_vector *vptr ;
81 int rows;
82 {
83 INT i;
84
85 for( i=0; i < rows; i++ ){
86 fprintf( stderr, "% 4.4le ", gsl_vector_get(vptr, i)) ;
87 }
88 fprintf( stderr, "\n" ) ;
89 } /* end gsl_vector_disp */
90
set_pins(A,center,loc,tile_side,sidepins,count)91 static void set_pins( A, center, loc, tile_side, sidepins, count )
92 gsl_matrix *A ; /* the matrix holding x y positions */
93 INT center ;
94 INT loc ;
95 INT tile_side ;
96 INT *sidepins ;
97 INT count ;
98 {
99 INT side ; /* the matching side for a given tile */
100
101 if( sidepins ){
102 side = find_tile_side( center, loc, tile_side ) ;
103 if( side ){
104 gsl_matrix_set(A, count, 5, (DOUBLE) sidepins[side]);
105 } else {
106 M( ERRMSG, "adapt_wire_estimator",
107 "Trouble finding pinside - defaulting to 0.\n" ) ;
108 gsl_matrix_set(A, count, 5, 0.0);
109 }
110 } else {
111 /* no pins for cell */
112 gsl_matrix_set(A, count, 5, 0.0);
113 }
114 } /* end set_pins */
115
adapt_wire_estimator()116 void adapt_wire_estimator()
117 {
118 INT i ; /* coefficient counter */
119 INT cell ; /* cell counter */
120 INT count ; /* count number of tiles */
121 INT xc, yc ; /* cell center */
122 INT *sidepins ; /* array holding #pins for side */
123 INT l, r, b, t ; /* the global position of the rtiles */
124 INT solved ; /* status of gsl_linalg_SV_solve */
125 INT *find_pin_sides() ; /* find number of pins on all sides */
126 char filename[LRECL] ; /* output the results of the SVD fit */
127 FILE *fp ; /* write out the results */
128 gsl_matrix *A ; /* the matrix holding x y positions */
129 gsl_vector *B ; /* the resulting global routing space*/
130 gsl_vector *Xret ; /* the solution to At*A*x = At*B */
131 DOUBLE x, y ; /* cell placement */
132 DOUBLE lf, rf, bf, tf ; /* the global position of the rtiles */
133 DOUBLE xlength, ylength;/* length of side */
134 DOUBLE xrouting, yrouting;/* routing space */
135 CELLBOXPTR cptr ; /* current pointer to cell */
136 RTILEBOXPTR rptr ; /* traverse tiles */
137
138 gsl_matrix *U ;
139 gsl_matrix *V ;
140 gsl_vector *S ;
141 gsl_vector *work ;
142
143 if(!(routingTilesG)){
144 return ;
145 }
146 /* first count the number of routing tiles */
147 count = 0 ;
148 for( cell = 1 ; cell <= numcellsG; cell++ ){
149 for( rptr=routingTilesG[cell];rptr;rptr=rptr->next ){
150 if( rptr->switchbox ){
151 /* switchbox densities are not accurate discard */
152 continue ;
153 }
154 count++ ;
155 }
156 }
157 if( count < 6 ){
158 /* now we can size the matrices */
159 A = gsl_matrix_alloc(6, 6);
160 B = gsl_vector_alloc(6);
161 } else {
162 /* now we can size the matrices */
163 A = gsl_matrix_alloc(count, 6);
164 B = gsl_vector_alloc(count);
165 }
166
167 /* initialize the pin counting routines */
168 init_wire_est() ;
169
170 /* we eventually want to solve AtA x = At B */
171
172 /* now fill in the data in the matrices. */
173 xlength = (DOUBLE) (blockrG - blocklG) ;
174 ylength = (DOUBLE) (blocktG - blockbG) ;
175 count = 0 ;
176 for( cell = 1 ; cell <= numcellsG; cell++ ){
177 cptr = cellarrayG[ cell ] ;
178 xc = cptr->xcenter ;
179 yc = cptr->ycenter ;
180 sidepins = find_pin_sides( cell ) ;
181 for( rptr=routingTilesG[cell];rptr;rptr=rptr->next ){
182 if( rptr->switchbox ){
183 /* switchbox densities are not accurate discard */
184 continue ;
185 }
186 gsl_matrix_set(A, count, 0, 1.0); /* for finding const */
187 l = xc + rptr->x1 ;
188 r = xc + rptr->x2 ;
189 b = yc + rptr->y1 ;
190 t = yc + rptr->y2 ;
191 xrouting = (DOUBLE)(r - l) ;
192 yrouting = (DOUBLE)(t - b) ;
193 lf = ( (DOUBLE)(l - blocklG ) ) / xlength ;
194 if( lf < 0.0 ) lf = 0.0 ;
195 rf = ( (DOUBLE)(r - blocklG ) ) / xlength ;
196 bf = ( (DOUBLE)(b - blockbG ) ) / ylength ;
197 if( bf < 0.0 ) bf = 0.0 ;
198 tf = ( (DOUBLE)(t - blockbG ) ) / ylength ;
199 switch( rptr->side ){
200 case TILEL:
201 /* calculate x and y */
202 x = rf ;
203 y = (bf + tf) / 2.0 ;
204 set_pins( A, (b+t)/2, r, TILEL, sidepins, count ) ;
205 gsl_matrix_set(A, count, 1, x);
206 gsl_matrix_set(A, count, 2, x * x);
207 gsl_matrix_set(A, count, 3, y);
208 gsl_matrix_set(A, count, 4, y * y);
209 gsl_vector_set(B, count, xrouting);
210 break ;
211 case TILET:
212 /* calculate x and y */
213 x = (lf + rf) / 2.0 ;
214 y = bf ;
215 set_pins( A, (l+r)/2, b, TILET, sidepins, count ) ;
216 gsl_matrix_set(A, count, 1, x);
217 gsl_matrix_set(A, count, 2, x * x);
218 gsl_matrix_set(A, count, 3, y);
219 gsl_matrix_set(A, count, 4, y * y);
220 gsl_vector_set(B, count, yrouting);
221 break ;
222 case TILER:
223 /* calculate x and y */
224 x = lf ;
225 y = (bf + tf) / 2.0 ;
226 set_pins( A, (b+t)/2, l, TILER, sidepins, count ) ;
227 gsl_matrix_set(A, count, 1, x);
228 gsl_matrix_set(A, count, 2, x * x);
229 gsl_matrix_set(A, count, 3, y);
230 gsl_matrix_set(A, count, 4, y * y);
231 gsl_vector_set(B, count, xrouting);
232 break ;
233 case TILEB:
234 /* calculate x and y */
235 x = (lf + rf) / 2.0 ;
236 y = tf ;
237 set_pins( A, (l+r)/2, t, TILEB, sidepins, count ) ;
238 gsl_matrix_set(A, count, 1, x);
239 gsl_matrix_set(A, count, 2, x * x);
240 gsl_matrix_set(A, count, 3, y);
241 gsl_matrix_set(A, count, 4, y * y);
242 gsl_vector_set(B, count, yrouting);
243 break ;
244 } /* end switch */
245 count++ ;
246 }
247 if( sidepins ){
248 Yvector_free( sidepins, 1, sizeof(INT) ) ;
249 }
250
251 } /* end loop on cells */
252
253 /* now make sure we have at least 6 rows */
254 if( count < 1 ){
255 M( ERRMSG, "adapt_wire_estimator",
256 "Too few cells for TimberWolfMC. Must abort\n" ) ;
257 YexitPgm(PGMFAIL) ;
258
259 } else if( count < 6 ){
260 /* pad with zeros */
261 for( ; count < 6; count++ ){
262 for( i = 0; i < 6; i++ ){
263 gsl_matrix_set(A, count, i, gsl_matrix_get(A, 0, i));
264 }
265 gsl_vector_set(B, count, gsl_vector_get(B, 0));
266 }
267 }
268
269 D( "TWMC/awe/init",
270 fprintf( stderr,"\nA:\n" ) ;
271 gsl_matrix_disp( A, count < 6 ? 6 : count, 6 ) ;
272 fprintf( stderr,"\nB:\n" ) ;
273 gsl_vector_disp( B, count < 6 ? 6 : count ) ;
274 ) ;
275
276 /* now solve using SVD */
277 U = gsl_matrix_alloc((count < 6) ? 6 : count, 6);
278 V = gsl_matrix_alloc(6, 6);
279 S = gsl_vector_alloc(6);
280 work = gsl_vector_alloc(6);
281 gsl_matrix_memcpy(U, A);
282 gsl_linalg_SV_decomp(U, V, S, work);
283 solved = gsl_linalg_SV_solve(U, V, S, B, Xret);
284
285 if( solved ){
286 sprintf( filename, "%s.mest", cktNameG ) ;
287 fp = TWOPEN( filename, "w", ABORT ) ;
288 fprintf( fpoG, "\nThe results of the SVD fit are:\n" ) ;
289 for( i = 0; i < 6; i++ ){
290 HPO( fp, gsl_vector_get(Xret, i));
291 HPO( fpoG, gsl_vector_get(Xret, i));
292 }
293 TWCLOSE( fp ) ;
294 }
295
296 gsl_matrix_free(U);
297 gsl_matrix_free(V);
298 gsl_vector_free(S);
299 gsl_vector_free(work);
300
301 D( "TWMC/awe/answer",
302 gsl_vector *AX ; /* multiply the answer */
303 gsl_vector *R ;
304 gsl_matrix *Q ;
305 INT c ;
306 DOUBLE d ;
307 DOUBLE dx ;
308
309 AX = gsl_vector_alloc(count < 6 ? count : 6);
310 R = gsl_vector_alloc(count < 6 ? count : 6);
311
312 /* Compute AX = A * Xret */
313 for ( c = 0; c < (count < 6) ? 6 : count; c++ ) {
314 d = 0.0;
315 dx = gsl_vector_get(Xret, c);
316 for ( i = 0; i < 6; i++ ) {
317 d += gsl_matrix_get(A, c, i) * dx;
318 gsl_set_vector(AX, c, d);
319 }
320
321 /* Compute R = AX - B */
322 gsl_vector_memcpy(R, AX);
323 gsl_vector_sub( R, B );
324
325 Q = gsl_matrix_alloc( count, 7 );
326 for( c = 0; c < count; c++ ){
327 gsl_matrix_set(Q, c, 0, gsl_matrix_get(A, c, 1)) ; /* x */
328 gsl_matrix_set(Q, c, 1, gsl_matrix_get(A, c, 3)) ; /* y */
329 gsl_matrix_set(Q, c, 2, gsl_matrix_get(A, c, 5)) ; /* pins */
330 gsl_matrix_set(Q, c, 3, gsl_vector_get(B, c)) ; /* B */
331 gsl_matrix_set(Q, c, 4, gsl_matrix_get(AX, c, 0)) ; /* AX */
332 gsl_matrix_set(Q, c, 5, gsl_matrix_get(R, c, 0)) ; /* B - AX */
333 gsl_matrix_set(Q, c, 6, gsl_matrix_get(Q, c, 5) /
334 gsl_matrix_get(Q, c, 3)) ; /* error */
335 }
336 fprintf( stderr, "\n x, y, B, pins, AB, B - AX, error:\n");
337 gsl_matrix_disp( Q, count, 7 ) ;
338 gsl_matrix_free(Q);
339 gsl_vector_free(R);
340 gsl_vector_free(AX);
341 ) ;
342
343 /* now done free the matrices */
344 gsl_matrix_free( A );
345 gsl_vector_free( B );
346 gsl_vector_free( Xret );
347
348 } /* end adapt_wire_estimator */
349