1 /* fidmat.c */
2
3 #include "../BKL.h"
4
5 #define MYDEBUG 0
6 #define MAXNDOM_FOR_EXHAUSTIVE_SEARCH 8
7
8 /*--------------------------------------------------------------------*/
9 /*
10 ---------------------------
11 structure used in this file
12 ---------------------------
13 */
14 typedef struct _cell Cell ;
15 struct _cell {
16 int domid ;
17 int deltaS ;
18 int deltaB ;
19 int deltaW ;
20 Cell *prev ;
21 Cell *next ;
22 } ;
23
24 static Cell Head, *head = &Head ;
25 static Cell Undo, *undo = &Undo ;
26
27 static float
28 BKL_fidmatPass (
29 BKL *bkl,
30 Cell cells[],
31 int tags[],
32 Graph *DomByDom,
33 int npass
34 ) ;
35
36 /*--------------------------------------------------------------------*/
37 /*
38 -------------------------------------------------------
39 improve the partition using the FidMat algorithm
40
41 created -- 95oct11, cca
42 modified -- 95dec07, cca
43 memory leak fixed, comments added, DomByDom inserted
44 -------------------------------------------------------
45 */
46 float
BKL_fidmat(BKL * bkl)47 BKL_fidmat (
48 BKL *bkl
49 ) {
50 float cost ;
51 int ndom ;
52 /*
53 ---------------
54 check the input
55 ---------------
56 */
57 if ( bkl == NULL ) {
58 fprintf(stderr, "\n fatal error in BKL_fidmat(%p)"
59 "\n bad input\n", bkl) ;
60 exit(-1) ;
61 }
62 ndom = bkl->ndom ;
63 /*
64 ---------------------------------------------
65 if ndom <= MAXNDOM_FOR_EXHAUSTIVE_SEARCH then
66 do exhaustive search
67 else
68 do fidmat sweeps
69 endif
70 ---------------------------------------------
71 */
72 if ( ndom <= MAXNDOM_FOR_EXHAUSTIVE_SEARCH ) {
73 int mdom, *domids, *tcolors ;
74 /*
75 --------------------
76 do exhaustive search
77 --------------------
78 */
79 mdom = ndom - 1 ;
80 domids = IVinit(mdom, -1) ;
81 tcolors = IVinit(mdom, -1) ;
82 IVramp(mdom, domids, 1, 1) ;
83 BKL_exhSearch(bkl, mdom, domids, tcolors) ;
84 IVfree(domids) ;
85 IVfree(tcolors) ;
86 cost = BKL_evalfcn(bkl) ;
87 } else {
88 Cell *cell, *cells ;
89 float bestcost ;
90 Graph *DomByDom ;
91 int idom ;
92 int *tags ;
93 /*
94 ---------------------------------------------------
95 initialize the cell objects and the working vectors
96 ---------------------------------------------------
97 */
98 ALLOCATE(cells, struct _cell, ndom) ;
99 tags = IVinit(ndom, -1) ;
100 for ( idom = 0, cell = cells ; idom < ndom ; idom++, cell++ ) {
101 cell->domid = idom ;
102 cell->deltaS = cell->deltaB = cell->deltaW = 0 ;
103 cell->prev = cell->next = cell ;
104 }
105 /*
106 -------------------------------------
107 create the domain-domain Graph object
108 -------------------------------------
109 */
110 DomByDom = BPG_makeGraphXbyX(bkl->bpg) ;
111 #if MYDEBUG > 1
112 fprintf(stdout, "\n\n domain-domain Graph object") ;
113 Graph_writeForHumanEye(DomByDom, stdout) ;
114 fflush(stdout) ;
115 #endif
116 /*
117 --------------------------
118 make the first fidmat pass
119 --------------------------
120 */
121 #if MYDEBUG > 0
122 fprintf(stdout, "\n\n pass %d, cost %.2f, < %d %d %d >",
123 bkl->npass, BKL_evalfcn(bkl),
124 bkl->cweights[0], bkl->cweights[1], bkl->cweights[2]) ;
125 fflush(stdout) ;
126 #endif
127 bkl->npass = 1 ;
128 bestcost = BKL_fidmatPass(bkl, cells, tags, DomByDom, bkl->npass) ;
129 #if MYDEBUG > 0
130 fprintf(stdout, "\n\n pass %d, cost %.2f, < %d %d %d >",
131 bkl->npass, bestcost,
132 bkl->cweights[0], bkl->cweights[1], bkl->cweights[2]) ;
133 fflush(stdout) ;
134 #endif
135 /*
136 ---------------------------------------------------
137 make additional passes while the partition improves
138 ---------------------------------------------------
139 */
140 while ( 1 ) {
141 bkl->npass++ ;
142 cost = BKL_fidmatPass(bkl, cells, tags, DomByDom, bkl->npass) ;
143 #if MYDEBUG > 0
144 fprintf(stdout, "\n\n pass %d, cost %.2f, < %d %d %d >",
145 bkl->npass, cost,
146 bkl->cweights[0], bkl->cweights[1], bkl->cweights[2]) ;
147 fflush(stdout) ;
148 #endif
149 if ( cost < bestcost ) {
150 bestcost = cost ;
151 } else {
152 break ;
153 }
154 }
155 /*
156 ------------------------
157 free the working storage
158 ------------------------
159 */
160 FREE(cells) ;
161 IVfree(tags) ;
162 Graph_free(DomByDom) ;
163 }
164
165 return(cost) ; }
166
167 /*--------------------------------------------------------------------*/
168 /*
169 -------------------------------------
170 make one pass of the FidMat algorithm
171
172 created -- 95oct11, cca
173 -------------------------------------
174 */
175 static float
BKL_fidmatPass(BKL * bkl,Cell cells[],int tags[],Graph * DomByDom,int npass)176 BKL_fidmatPass (
177 BKL *bkl,
178 Cell cells[],
179 int tags[],
180 Graph *DomByDom,
181 int npass
182 ) {
183 Cell *cell ;
184 float bestcost, bettercost, cost ;
185 int dom, dom2, ii, ndom, size ;
186 int *cweights, *doms ;
187 /*
188 ---------------
189 check the input
190 ---------------
191 */
192 if ( bkl == NULL || cells == NULL || tags == NULL || DomByDom == NULL ){
193 fprintf(stderr, "\n fatal error in BKL_fidmatPass(%p,%p,%p,%p,%d)"
194 "\n bad input\n", bkl, cells, tags, DomByDom, npass) ;
195 exit(-1) ;
196 }
197 ndom = bkl->ndom ;
198 cweights = bkl->cweights ;
199 /*
200 ------------------------------
201 evaluate the current partition
202 ------------------------------
203 */
204 bestcost = BKL_evalfcn(bkl) ;
205 /*
206 -----------------------------------------------------
207 fill the cells with domains adjacent to the separator
208 -----------------------------------------------------
209 */
210 head->next = head->prev = head ;
211 undo->next = undo->prev = undo ;
212 for ( dom = 0 ; dom < ndom ; dom++ ) {
213 cell = &cells[dom] ;
214 cell->domid = dom ;
215 cell->prev = cell->next = cell ;
216 if ( BKL_domAdjToSep(bkl, dom) == 1 ) {
217 /*
218 ----------------------------------------
219 domain dom is adjacent to the separator
220 evaluate its change and insert into list
221 ----------------------------------------
222 */
223 BKL_evalgain(bkl, dom, &cell->deltaS,
224 &cell->deltaB, &cell->deltaW) ;
225 #if MYDEBUG > 1
226 fprintf(stdout, "\n loading domain %d, <%d %d %d>",
227 dom, cell->deltaS, cell->deltaB, cell->deltaW) ;
228 fflush(stdout) ;
229 #endif
230 DLIST_TAIL_INSERT(head, cell) ;
231 }
232 }
233 /*
234 ---------------
235 loop over moves
236 ---------------
237 */
238 while ( head->next != head ) {
239 /*
240 -----------------------------------------------
241 find best move to make w.r.t. the cost function
242 -----------------------------------------------
243 */
244 cell = head->next ;
245 dom = cell->domid ;
246 bettercost = BKL_eval(bkl, cweights[0] + cell->deltaS,
247 cweights[1] + cell->deltaB,
248 cweights[2] + cell->deltaW) ;
249 #if MYDEBUG > 1
250 fprintf(stdout, "\n domain %d, move cost = %.1f",
251 dom, bettercost) ;
252 fflush(stdout) ;
253 #endif
254 for ( cell = cell->next ; cell != head ; cell = cell->next ) {
255 cost = BKL_eval(bkl, cweights[0] + cell->deltaS,
256 cweights[1] + cell->deltaB,
257 cweights[2] + cell->deltaW) ;
258 #if MYDEBUG > 1
259 fprintf(stdout, "\n domain %d, move cost = %.1f",
260 cell->domid, cost) ;
261 fflush(stdout) ;
262 #endif
263 if ( cost < bettercost ) {
264 #if MYDEBUG > 1
265 fprintf(stdout, ", better") ;
266 fflush(stdout) ;
267 #endif
268 dom = cell->domid ;
269 bettercost = cost ;
270 }
271 }
272 /*
273 -----------------------------
274 remove the node from the list
275 -----------------------------
276 */
277 cell = &cells[dom] ;
278 DLIST_DELETE(cell) ;
279 /*
280 ---------------
281 flip the domain
282 ---------------
283 */
284 #if MYDEBUG > 1
285 fprintf(stdout, "\n flipping domain %d, cweights <%d %d %d>",
286 dom, cweights[0] + cell->deltaS,
287 cweights[1] + cell->deltaB,
288 cweights[2] + cell->deltaW) ;
289 fflush(stdout) ;
290 #endif
291 BKL_flipDomain(bkl, dom) ;
292 cost = BKL_eval(bkl, cweights[0], cweights[1], cweights[2]) ;
293 #if MYDEBUG > 1
294 fprintf(stdout, ", cost = %.1f", cost) ;
295 fflush(stdout) ;
296 #endif
297 if ( bestcost > cost ) {
298 /*
299 ---------------------------------------------
300 better partition found, set undo list to NULL
301 ---------------------------------------------
302 */
303 bestcost = cost ;
304 DLIST_DELETE(undo) ;
305 bkl->nimprove++ ;
306 } else {
307 /*
308 ----------------------------------------------
309 partition is not better, add move to undo list
310 ----------------------------------------------
311 */
312 DLIST_HEAD_INSERT(undo, cell) ;
313 }
314 /*
315 --------------------------
316 loop over adjacent domains
317 --------------------------
318 */
319 tags[dom] = npass ;
320 Graph_adjAndSize(DomByDom, dom, &size, &doms) ;
321 for ( ii = 0 ; ii < size ; ii++ ) {
322 dom2 = doms[ii] ;
323 if ( tags[dom2] < npass && BKL_domAdjToSep(bkl, dom2) == 1 ) {
324 /*
325 ------------------------------------
326 domain dom2 has not yet been flipped
327 and is adjacent to the separator
328 ------------------------------------
329 */
330 #if MYDEBUG > 1
331 fprintf(stdout,
332 "\n domain %d, not yet flipped, adj to separator",
333 dom2) ;
334 fflush(stdout) ;
335 #endif
336 cell = &cells[dom2] ;
337 BKL_evalgain(bkl, dom2, &cell->deltaS,
338 &cell->deltaB, &cell->deltaW) ;
339 #if MYDEBUG > 1
340 fprintf(stdout, ", gain < %d %d %d >",
341 cell->deltaS, cell->deltaB, cell->deltaW) ;
342 fflush(stdout) ;
343 #endif
344 if ( cell->prev == cell ) {
345 /*
346 ---------------------------------------------
347 domain is not on the list of domains eligible
348 to move, insert on the tail of the list
349 ---------------------------------------------
350 */
351 DLIST_TAIL_INSERT(head, cell) ;
352 }
353 }
354 }
355 }
356 /*
357 -------------------------------------------------------
358 undo the flips of domains since the last best partition
359 -------------------------------------------------------
360 */
361 while ( (cell = undo->next) != undo ) {
362 #if MYDEBUG > 1
363 fprintf(stdout, "\n un-flipping domain %d", cell->domid) ;
364 fflush(stdout) ;
365 #endif
366 DLIST_DELETE(cell) ;
367 BKL_flipDomain(bkl, cell->domid) ;
368 }
369 return(bestcost) ; }
370
371 /*--------------------------------------------------------------------*/
372