1 /*
2 * grouteMain.c --
3 *
4 * Top level code for the global signal router.
5 *
6 * The global router's job is to find the sequence of channel pins
7 * through which each signal must pass, and mark these pins so the
8 * channel router can connect them within each channel.
9 *
10 * Our overall approach is greedy: we compute the area of the bounding
11 * box of all terminals in a net for each net, and perform global routing
12 * of each net in order of increasing area of this bounding box. This
13 * has the effect of routing more constrained nets first, and less
14 * constrained ones later.
15 *
16 * *********************************************************************
17 * * Copyright (C) 1985, 1990 Regents of the University of California. *
18 * * Permission to use, copy, modify, and distribute this *
19 * * software and its documentation for any purpose and without *
20 * * fee is hereby granted, provided that the above copyright *
21 * * notice appear in all copies. The University of California *
22 * * makes no representations about the suitability of this *
23 * * software for any purpose. It is provided "as is" without *
24 * * express or implied warranty. Export of this software outside *
25 * * of the United States of America may require an export license. *
26 * *********************************************************************
27 */
28
29 #include <stdio.h>
30 #include <sys/types.h>
31 #include <sys/times.h>
32 #include "utils/magic.h"
33 #include "utils/geometry.h"
34 #include "utils/styles.h"
35 #include "utils/hash.h"
36 #include "utils/heap.h"
37 #include "utils/utils.h"
38 #include "tiles/tile.h"
39 #include "database/database.h"
40 #include "debug/debug.h"
41 #include "gcr/gcr.h"
42 #include "windows/windows.h"
43 #include "utils/main.h"
44 #include "dbwind/dbwind.h"
45 #include "utils/signals.h"
46 #include "router/router.h"
47 #include "grouter/grouter.h"
48 #include "utils/netlist.h"
49 #include "utils/styles.h"
50 #include "textio/textio.h"
51 #include "utils/malloc.h"
52
53 /* Global data */
54 Heap glMazeHeap; /* Heap of search points for global routing */
55 FILE *glLogFile; /* Used for debugging to remember crossings processed */
56 int glNumTries; /* Debugging too -- # calls to glProcessLoc() */
57
58 /* Forward declarations */
59 void glClientInit();
60 void glClientFree();
61
62
63 /*
64 * ----------------------------------------------------------------------------
65 *
66 * GlGlobalRoute --
67 *
68 * Build a heap of nets, ordered with smallest area first.
69 * Globally route nets on the heap, decomposing multi-pin nets using
70 * Steiner-like trees. Leave routing problems in channel structures.
71 *
72 * Results:
73 * None.
74 *
75 * Side effects:
76 * On completion crossing points for nets have been set. Channel
77 * structures are ready to be routed by the channel structure.
78 *
79 * ----------------------------------------------------------------------------
80 */
81
82 void
GlGlobalRoute(chanList,netList)83 GlGlobalRoute(chanList, netList)
84 GCRChannel *chanList; /* List of all channels in routing problem */
85 NLNetList *netList; /* Netlist built by caller */
86 {
87 HeapEntry entry;
88 Heap netHeap;
89 bool doFast;
90 int numTerms;
91 NLNet *net;
92
93 GlInit();
94 glStatsInit();
95 doFast = DebugIsSet(glDebugID, glDebFast);
96
97 /*
98 * Initialize the client-specific portion of each channel and
99 * of each net. These fields point to structures holding
100 * (respectively) density information and blocked regions
101 * during global routing.
102 */
103 glClientInit(chanList, netList);
104
105 /*
106 * Build a tile plane that represents all the channels in the
107 * routing problem. This tile plane will be used to search
108 * for nearby channels during global routing.
109 */
110 glChanBuildMap(chanList);
111 if (DebugIsSet(glDebugID, glDebChan))
112 {
113 SigInterruptPending = TRUE;
114 return;
115 }
116
117 /* Compute penalties for passing through congested zones */
118 if (DebugIsSet(glDebugID, glDebPen))
119 glPenCompute(chanList, netList);
120
121 /*
122 * Build a heap of nets sorted in order of increasing size, then
123 * successively remove the topmost entry of the heap and route its
124 * net. Make almost-Steiner tree global routes for multi-pin nets.
125 */
126 numTerms = 0;
127 NLSort(netList, &netHeap);
128 while (HeapRemoveTop(&netHeap, &entry) && !SigInterruptPending)
129 {
130 net = (NLNet *) entry.he_id;
131 if (DebugIsSet(glDebugID, glDebPen))
132 {
133 glCrossUnreserve(net);
134 glPenSetPerChan(net);
135 }
136 numTerms += glMultiSteiner(EditCellUse, net, glProcessLoc,
137 glCrossMark, (ClientData) doFast, (ClientData) 0);
138 if (DebugIsSet(glDebugID, glDebPen))
139 glPenClearPerChan(net);
140 RtrMilestonePrint();
141 }
142 HeapKill(&netHeap, (void (*)()) NULL);
143
144 glClientFree(chanList, netList);
145 glChanFreeMap();
146 glStatsDone(netList->nnl_numNets, numTerms);
147 }
148
149 /*
150 * ----------------------------------------------------------------------------
151 *
152 * glClientInit --
153 *
154 * Allocate and initialize the structures that go in the gcr_client and
155 * nnet_cdata fields of all the channels and nets respectively in chanList
156 * and netList, and leave these fields pointing to the newly allocated and
157 * initialized structures.
158 *
159 * Results:
160 * None.
161 *
162 * Side effects:
163 * Allocates memory; see above.
164 *
165 * ----------------------------------------------------------------------------
166 */
167
168 void
glClientInit(chanList,netList)169 glClientInit(chanList, netList)
170 GCRChannel *chanList;
171 NLNetList *netList;
172 {
173 GCRChannel *ch;
174 GlobChan *gc;
175 NLNet *net;
176 int nrow, ncol;
177
178 for (ch = chanList; ch; ch = ch->gcr_next)
179 {
180 gc = (GlobChan *) mallocMagic((unsigned) (sizeof (GlobChan)));
181 gc->gc_penList = (CZone *) NULL;
182 nrow = ch->gcr_width;
183 ncol = ch->gcr_length;
184 glDMAlloc(&gc->gc_prevDens[CZ_COL], ncol, nrow);
185 glDMAlloc(&gc->gc_prevDens[CZ_ROW], nrow, ncol);
186 glDMAlloc(&gc->gc_postDens[CZ_COL], ncol, nrow);
187 glDMAlloc(&gc->gc_postDens[CZ_ROW], nrow, ncol);
188 glDensInit(gc->gc_prevDens, ch);
189 glDMCopy(&gc->gc_prevDens[CZ_COL], &gc->gc_postDens[CZ_COL]);
190 glDMCopy(&gc->gc_prevDens[CZ_ROW], &gc->gc_postDens[CZ_ROW]);
191 ch->gcr_client = (ClientData) gc;
192 }
193
194 for (net = netList->nnl_nets; net; net = net->nnet_next)
195 net->nnet_cdata = (ClientData) callocMagic((unsigned) (sizeof (NetClient)));
196 }
197
198 /*
199 * ----------------------------------------------------------------------------
200 *
201 * glClientFree --
202 *
203 * Free the memory allocated by glClientInit() above (as well as any
204 * memory allocated to CZone lists pointed to by the NetClient structs
205 * in the NLNetList netList).
206 *
207 * Results:
208 * None.
209 *
210 * Side effects:
211 * Frees memory.
212 *
213 * ----------------------------------------------------------------------------
214 */
215
216 void
glClientFree(chanList,netList)217 glClientFree(chanList, netList)
218 GCRChannel *chanList;
219 NLNetList *netList;
220 {
221 GlobChan *gc;
222 CZone *cz;
223 NetClient *nclient;
224 GCRChannel *ch;
225 NLNet *net;
226
227 for (ch = chanList; ch; ch = ch->gcr_next)
228 {
229 gc = (GlobChan *) ch->gcr_client;
230 glDMFree(&gc->gc_prevDens[CZ_COL]);
231 glDMFree(&gc->gc_prevDens[CZ_ROW]);
232 glDMFree(&gc->gc_postDens[CZ_COL]);
233 glDMFree(&gc->gc_postDens[CZ_ROW]);
234 freeMagic((char *) gc);
235 ch->gcr_client = (ClientData) NULL;
236 }
237
238 for (net = netList->nnl_nets; net; net = net->nnet_next)
239 {
240 nclient = (NetClient *) net->nnet_cdata;
241 for (cz = nclient->nc_pens; cz; cz = cz->cz_next)
242 freeMagic((char *) cz);
243 net->nnet_cdata = (ClientData) NULL;
244 }
245 }
246
247 /*
248 * ----------------------------------------------------------------------------
249 *
250 * glProcessLoc --
251 *
252 * Function called for all but the first NLTermLoc in a net: finds and
253 * returns the best-cost path from any of the points in the starting
254 * point list to loc->nloc_stem.
255 *
256 * Algorithm:
257 * We use two passes. The first attempts to find the shortest
258 * distance path between the source and the destination, if
259 * such a path exists. It uses a mechanism for storing the
260 * best cost so far to each crossing point considered, so
261 * we avoid looping. If no path can be found, we simply
262 * give up; otherwise, we perform a second pass where we
263 * try to generate not only the shortest path, but the
264 * next shortest, etc, until we find one whose distance
265 * plus crossing penalty is minimized.
266 *
267 * Results:
268 * Returns the best path. The first element on the list
269 * (linked by gl_path pointers) is the destination point.
270 * If no path could be found with cost less than bestCost,
271 * returns NULL.
272 *
273 * Side effects:
274 * Allocates memory from the temporary GlPoint arena.
275 *
276 * ----------------------------------------------------------------------------
277 */
278
279 GlPoint *
glProcessLoc(startList,loc,bestCost,doFast)280 glProcessLoc(startList, loc, bestCost, doFast)
281 GlPoint *startList; /* List of starting points */
282 NLTermLoc *loc; /* Location of terminal being routed to */
283 int bestCost; /* Best cost so far; if we can't find a path in
284 * less than this cost, give up.
285 */
286 bool doFast; /* If TRUE, only wiggle crossings around within the
287 * channels on the shortest path; don't bother
288 * considering other sequences of channels. If FALSE,
289 * we keep generating longer and longer paths until
290 * the sheer length of a path exceeds our best
291 * adjusted cost to date.
292 */
293 {
294 extern bool glMazeShortest;
295 extern Tile *glMazeDestTile;
296 extern Point glMazeDestPoint;
297 extern GlPoint *glMazeFindPath();
298 extern GlPoint *glCrossAdjust();
299 int headFree, shortLength, bestLength;
300 GlPoint *lastPt, *bestPt, *adjustedPt;
301 GlPage *headPage;
302
303 glNumTries++;
304 glCrossScalePenalties();
305
306 /* Sanity checks */
307 ASSERT(GEO_SAMEPOINT(loc->nloc_pin->gcr_point, loc->nloc_stem),
308 "glProcessLoc");
309
310 /*
311 * Passed to glMazeFindPath() for use in estimating the remaining
312 * distance to the destination point. Also figure out which
313 * channel tile contains the destination, so we can handle
314 * points in it specially. If the destination point is inside
315 * a blocked area, give up immediately.
316 */
317 glMazeDestPoint = loc->nloc_stem;
318 glMazeDestTile = glChanPinToTile((Tile *) NULL, loc->nloc_pin);
319
320 /* Abort immediately if destination is obviously unreachable */
321 if (glMazeDestTile == NULL)
322 return (GlPoint *) NULL;
323
324 /*
325 * First try finding the shortest path.
326 * This goes very quickly, because we are able to chop
327 * off unpromising paths at an early stage.
328 */
329 glMazeShortest = TRUE;
330 HeapInit(&glMazeHeap, 128, FALSE, FALSE);
331 glListToHeap(startList, &loc->nloc_stem);
332 headPage = glPathCurPage;
333 headFree = glPathCurPage->glp_free;
334 bestPt = glMazeFindPath(loc, bestCost);
335 glMazeResetCost(headPage, headFree);
336 HeapKill(&glMazeHeap, (void (*)()) NULL);
337 if (bestPt == (GlPoint *) NULL)
338 {
339 glBadRoutes++;
340 return bestPt;
341 }
342 shortLength = bestPt->gl_cost;
343
344 /*
345 * Now try finding a path that minimizes the crossing penalty.
346 * We do this by continuing to generate paths in order of
347 * increasing length, then adjusting the crossing points
348 * along the path to minimize (locally) the penalty for
349 * the path, until we find a path whose unadjusted length
350 * exceeds the best cost we've been able to achieve so far.
351 * The gl_cost fields in the paths generated by glCrossAdjust
352 * incorporate the penalties as well as distance.
353 */
354 HeapInit(&glMazeHeap, 128, FALSE, FALSE);
355 glListToHeap(startList, &loc->nloc_stem);
356 if (doFast)
357 {
358 headPage = glPathCurPage;
359 headFree = glPathCurPage->glp_free;
360 }
361 else glMazeShortest = FALSE;
362 bestPt = (GlPoint *) NULL;
363 while (lastPt = glMazeFindPath(loc, bestCost))
364 {
365 adjustedPt = glCrossAdjust((GlPoint *) NULL, lastPt);
366 if (adjustedPt->gl_cost < bestCost)
367 {
368 bestCost = adjustedPt->gl_cost;
369 bestLength = lastPt->gl_cost;
370 bestPt = adjustedPt;
371 }
372 }
373 if (doFast)
374 glMazeResetCost(headPage, headFree);
375 HeapKill(&glMazeHeap, (void (*)()) NULL);
376 if (bestPt)
377 {
378 if (glLogFile)
379 {
380 fprintf(glLogFile, "%d\t%d (%.2f)\t%d (%.2f)\n",
381 shortLength, bestLength,
382 (float) bestLength / (float) shortLength * 100.0,
383 bestPt->gl_cost,
384 (float) bestPt->gl_cost / (float) shortLength * 100.0);
385 }
386 glGoodRoutes++;
387 return bestPt;
388 }
389
390 glBadRoutes++;
391 glNoRoutes++;
392 return (GlPoint *) NULL;
393 }
394