SCM

SCM Repository

[matrix] Annotation of /pkg/src/Metis/mbalance2.c
ViewVC logotype

Annotation of /pkg/src/Metis/mbalance2.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 10 - (view) (download) (as text)

1 : bates 10 /*
2 :     * Copyright 1997, Regents of the University of Minnesota
3 :     *
4 :     * mbalance2.c
5 :     *
6 :     * This file contains code that is used to forcefully balance either
7 :     * bisections or k-sections
8 :     *
9 :     * Started 7/29/97
10 :     * George
11 :     *
12 :     * $Id: mbalance2.c,v 1.1 2003/12/31 21:32:30 bates Exp $
13 :     *
14 :     */
15 :    
16 :     #include <metis.h>
17 :    
18 :    
19 :     /*************************************************************************
20 :     * This function is the entry point of the bisection balancing algorithms.
21 :     **************************************************************************/
22 :     void MocBalance2Way2(CtrlType *ctrl, GraphType *graph, float *tpwgts, float *ubvec)
23 :     {
24 :     int i;
25 :     float tvec[MAXNCON];
26 :    
27 :     Compute2WayHLoadImbalanceVec(graph->ncon, graph->npwgts, tpwgts, tvec);
28 :     if (!AreAllBelow(graph->ncon, tvec, ubvec))
29 :     MocGeneral2WayBalance2(ctrl, graph, tpwgts, ubvec);
30 :     }
31 :    
32 :    
33 :    
34 :     /*************************************************************************
35 :     * This function performs an edge-based FM refinement
36 :     **************************************************************************/
37 :     void MocGeneral2WayBalance2(CtrlType *ctrl, GraphType *graph, float *tpwgts, float *ubvec)
38 :     {
39 :     int i, ii, j, k, l, kwgt, nvtxs, ncon, nbnd, nswaps, from, to, pass, me, limit, tmp, cnum;
40 :     idxtype *xadj, *adjncy, *adjwgt, *where, *id, *ed, *bndptr, *bndind;
41 :     idxtype *moved, *swaps, *perm, *qnum;
42 :     float *nvwgt, *npwgts, origbal[MAXNCON], minbal[MAXNCON], newbal[MAXNCON];
43 :     PQueueType parts[MAXNCON][2];
44 :     int higain, oldgain, mincut, newcut, mincutorder;
45 :     float *maxwgt, *minwgt, tvec[MAXNCON];
46 :    
47 :    
48 :     nvtxs = graph->nvtxs;
49 :     ncon = graph->ncon;
50 :     xadj = graph->xadj;
51 :     nvwgt = graph->nvwgt;
52 :     adjncy = graph->adjncy;
53 :     adjwgt = graph->adjwgt;
54 :     where = graph->where;
55 :     id = graph->id;
56 :     ed = graph->ed;
57 :     npwgts = graph->npwgts;
58 :     bndptr = graph->bndptr;
59 :     bndind = graph->bndind;
60 :    
61 :     moved = idxwspacemalloc(ctrl, nvtxs);
62 :     swaps = idxwspacemalloc(ctrl, nvtxs);
63 :     perm = idxwspacemalloc(ctrl, nvtxs);
64 :     qnum = idxwspacemalloc(ctrl, nvtxs);
65 :    
66 :     limit = amin(amax(0.01*nvtxs, 15), 100);
67 :    
68 :     /* Setup the weight intervals of the two subdomains */
69 :     minwgt = fwspacemalloc(ctrl, 2*ncon);
70 :     maxwgt = fwspacemalloc(ctrl, 2*ncon);
71 :    
72 :     for (i=0; i<2; i++) {
73 :     for (j=0; j<ncon; j++) {
74 :     maxwgt[i*ncon+j] = tpwgts[i]*ubvec[j];
75 :     minwgt[i*ncon+j] = tpwgts[i]*(1.0/ubvec[j]);
76 :     }
77 :     }
78 :    
79 :    
80 :     /* Initialize the queues */
81 :     for (i=0; i<ncon; i++) {
82 :     PQueueInit(ctrl, &parts[i][0], nvtxs, PLUS_GAINSPAN+1);
83 :     PQueueInit(ctrl, &parts[i][1], nvtxs, PLUS_GAINSPAN+1);
84 :     }
85 :     for (i=0; i<nvtxs; i++)
86 :     qnum[i] = samax(ncon, nvwgt+i*ncon);
87 :    
88 :     Compute2WayHLoadImbalanceVec(ncon, npwgts, tpwgts, origbal);
89 :     for (i=0; i<ncon; i++)
90 :     minbal[i] = origbal[i];
91 :    
92 :     newcut = mincut = graph->mincut;
93 :     mincutorder = -1;
94 :    
95 :     if (ctrl->dbglvl&DBG_REFINE) {
96 :     printf("Parts: [");
97 :     for (l=0; l<ncon; l++)
98 :     printf("(%.3f, %.3f) ", npwgts[l], npwgts[ncon+l]);
99 :     printf("] T[%.3f %.3f], Nv-Nb[%5d, %5d]. ICut: %6d, LB: ", tpwgts[0], tpwgts[1],
100 :     graph->nvtxs, graph->nbnd, graph->mincut);
101 :     for (i=0; i<ncon; i++)
102 :     printf("%.3f ", origbal[i]);
103 :     printf("[B]\n");
104 :     }
105 :    
106 :     idxset(nvtxs, -1, moved);
107 :    
108 :     ASSERT(ComputeCut(graph, where) == graph->mincut);
109 :     ASSERT(CheckBnd(graph));
110 :    
111 :     /* Insert all nodes in the priority queues */
112 :     nbnd = graph->nbnd;
113 :     RandomPermute(nvtxs, perm, 1);
114 :     for (ii=0; ii<nvtxs; ii++) {
115 :     i = perm[ii];
116 :     PQueueInsert(&parts[qnum[i]][where[i]], i, ed[i]-id[i]);
117 :     }
118 :    
119 :    
120 :     for (nswaps=0; nswaps<nvtxs; nswaps++) {
121 :     if (AreAllBelow(ncon, minbal, ubvec))
122 :     break;
123 :    
124 :     SelectQueue3(ncon, npwgts, tpwgts, &from, &cnum, parts, maxwgt);
125 :     to = (from+1)%2;
126 :    
127 :     if (from == -1 || (higain = PQueueGetMax(&parts[cnum][from])) == -1)
128 :     break;
129 :    
130 :     saxpy(ncon, 1.0, nvwgt+higain*ncon, 1, npwgts+to*ncon, 1);
131 :     saxpy(ncon, -1.0, nvwgt+higain*ncon, 1, npwgts+from*ncon, 1);
132 :     newcut -= (ed[higain]-id[higain]);
133 :     Compute2WayHLoadImbalanceVec(ncon, npwgts, tpwgts, newbal);
134 :    
135 :     if (IsBetter2wayBalance(ncon, newbal, minbal, ubvec) ||
136 :     (IsBetter2wayBalance(ncon, newbal, origbal, ubvec) && newcut < mincut)) {
137 :     mincut = newcut;
138 :     for (i=0; i<ncon; i++)
139 :     minbal[i] = newbal[i];
140 :     mincutorder = nswaps;
141 :     }
142 :     else if (nswaps-mincutorder > limit) { /* We hit the limit, undo last move */
143 :     newcut += (ed[higain]-id[higain]);
144 :     saxpy(ncon, 1.0, nvwgt+higain*ncon, 1, npwgts+from*ncon, 1);
145 :     saxpy(ncon, -1.0, nvwgt+higain*ncon, 1, npwgts+to*ncon, 1);
146 :     break;
147 :     }
148 :    
149 :     where[higain] = to;
150 :     moved[higain] = nswaps;
151 :     swaps[nswaps] = higain;
152 :    
153 :     if (ctrl->dbglvl&DBG_MOVEINFO) {
154 :     printf("Moved %6d from %d(%d). Gain: %5d, Cut: %5d, NPwgts: ", higain, from, cnum, ed[higain]-id[higain], newcut);
155 :     for (i=0; i<ncon; i++)
156 :     printf("(%.3f, %.3f) ", npwgts[i], npwgts[ncon+i]);
157 :    
158 :     Compute2WayHLoadImbalanceVec(ncon, npwgts, tpwgts, tvec);
159 :     printf(", LB: ");
160 :     for (i=0; i<ncon; i++)
161 :     printf("%.3f ", tvec[i]);
162 :     if (mincutorder == nswaps)
163 :     printf(" *\n");
164 :     else
165 :     printf("\n");
166 :     }
167 :    
168 :    
169 :     /**************************************************************
170 :     * Update the id[i]/ed[i] values of the affected nodes
171 :     ***************************************************************/
172 :     SWAP(id[higain], ed[higain], tmp);
173 :     if (ed[higain] == 0 && bndptr[higain] != -1 && xadj[higain] < xadj[higain+1])
174 :     BNDDelete(nbnd, bndind, bndptr, higain);
175 :     if (ed[higain] > 0 && bndptr[higain] == -1)
176 :     BNDInsert(nbnd, bndind, bndptr, higain);
177 :    
178 :     for (j=xadj[higain]; j<xadj[higain+1]; j++) {
179 :     k = adjncy[j];
180 :     oldgain = ed[k]-id[k];
181 :    
182 :     kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
183 :     INC_DEC(id[k], ed[k], kwgt);
184 :    
185 :     /* Update the queue position */
186 :     if (moved[k] == -1)
187 :     PQueueUpdate(&parts[qnum[k]][where[k]], k, oldgain, ed[k]-id[k]);
188 :    
189 :     /* Update its boundary information */
190 :     if (ed[k] == 0 && bndptr[k] != -1)
191 :     BNDDelete(nbnd, bndind, bndptr, k);
192 :     else if (ed[k] > 0 && bndptr[k] == -1)
193 :     BNDInsert(nbnd, bndind, bndptr, k);
194 :     }
195 :    
196 :     }
197 :    
198 :    
199 :    
200 :     /****************************************************************
201 :     * Roll back computations
202 :     *****************************************************************/
203 :     for (i=0; i<nswaps; i++)
204 :     moved[swaps[i]] = -1; /* reset moved array */
205 :     for (nswaps--; nswaps>mincutorder; nswaps--) {
206 :     higain = swaps[nswaps];
207 :    
208 :     to = where[higain] = (where[higain]+1)%2;
209 :     SWAP(id[higain], ed[higain], tmp);
210 :     if (ed[higain] == 0 && bndptr[higain] != -1 && xadj[higain] < xadj[higain+1])
211 :     BNDDelete(nbnd, bndind, bndptr, higain);
212 :     else if (ed[higain] > 0 && bndptr[higain] == -1)
213 :     BNDInsert(nbnd, bndind, bndptr, higain);
214 :    
215 :     saxpy(ncon, 1.0, nvwgt+higain*ncon, 1, npwgts+to*ncon, 1);
216 :     saxpy(ncon, -1.0, nvwgt+higain*ncon, 1, npwgts+((to+1)%2)*ncon, 1);
217 :     for (j=xadj[higain]; j<xadj[higain+1]; j++) {
218 :     k = adjncy[j];
219 :    
220 :     kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
221 :     INC_DEC(id[k], ed[k], kwgt);
222 :    
223 :     if (bndptr[k] != -1 && ed[k] == 0)
224 :     BNDDelete(nbnd, bndind, bndptr, k);
225 :     if (bndptr[k] == -1 && ed[k] > 0)
226 :     BNDInsert(nbnd, bndind, bndptr, k);
227 :     }
228 :     }
229 :    
230 :     if (ctrl->dbglvl&DBG_REFINE) {
231 :     printf("\tMincut: %6d at %5d, NBND: %6d, NPwgts: [", mincut, mincutorder, nbnd);
232 :     for (i=0; i<ncon; i++)
233 :     printf("(%.3f, %.3f) ", npwgts[i], npwgts[ncon+i]);
234 :     printf("], LB: ");
235 :     Compute2WayHLoadImbalanceVec(ncon, npwgts, tpwgts, tvec);
236 :     for (i=0; i<ncon; i++)
237 :     printf("%.3f ", tvec[i]);
238 :     printf("\n");
239 :     }
240 :    
241 :     graph->mincut = mincut;
242 :     graph->nbnd = nbnd;
243 :    
244 :    
245 :     for (i=0; i<ncon; i++) {
246 :     PQueueFree(ctrl, &parts[i][0]);
247 :     PQueueFree(ctrl, &parts[i][1]);
248 :     }
249 :    
250 :     idxwspacefree(ctrl, nvtxs);
251 :     idxwspacefree(ctrl, nvtxs);
252 :     idxwspacefree(ctrl, nvtxs);
253 :     idxwspacefree(ctrl, nvtxs);
254 :     fwspacefree(ctrl, 2*ncon);
255 :     fwspacefree(ctrl, 2*ncon);
256 :    
257 :     }
258 :    
259 :    
260 :    
261 :    
262 :     /*************************************************************************
263 :     * This function selects the partition number and the queue from which
264 :     * we will move vertices out
265 :     **************************************************************************/
266 :     void SelectQueue3(int ncon, float *npwgts, float *tpwgts, int *from, int *cnum,
267 :     PQueueType queues[MAXNCON][2], float *maxwgt)
268 :     {
269 :     int i, j, maxgain=0;
270 :     float maxdiff=0.0, diff;
271 :    
272 :     *from = -1;
273 :     *cnum = -1;
274 :    
275 :     /* First determine the side and the queue, irrespective of the presence of nodes */
276 :     for (j=0; j<2; j++) {
277 :     for (i=0; i<ncon; i++) {
278 :     diff = npwgts[j*ncon+i]-maxwgt[j*ncon+i];
279 :     if (diff >= maxdiff) {
280 :     maxdiff = diff;
281 :     *from = j;
282 :     *cnum = i;
283 :     }
284 :     }
285 :     }
286 :    
287 :     /* DELETE
288 :     j = *from;
289 :     for (i=0; i<ncon; i++)
290 :     printf("[%5d %5d %.4f %.4f] ", i, PQueueGetSize(&queues[i][j]), npwgts[j*ncon+i], maxwgt[j*ncon+i]);
291 :     printf("***[%5d %5d]\n", *cnum, *from);
292 :     */
293 :    
294 :     /* If the desired queue is empty, select a node from that side anyway */
295 :     if (*from != -1 && PQueueGetSize(&queues[*cnum][*from]) == 0) {
296 :     for (i=0; i<ncon; i++) {
297 :     if (PQueueGetSize(&queues[i][*from]) > 0) {
298 :     maxdiff = (npwgts[(*from)*ncon+i] - maxwgt[(*from)*ncon+i]);
299 :     *cnum = i;
300 :     break;
301 :     }
302 :     }
303 :    
304 :     for (i++; i<ncon; i++) {
305 :     diff = npwgts[(*from)*ncon+i] - maxwgt[(*from)*ncon+i];
306 :     if (diff > maxdiff && PQueueGetSize(&queues[i][*from]) > 0) {
307 :     maxdiff = diff;
308 :     *cnum = i;
309 :     }
310 :     }
311 :     }
312 :    
313 :     /* If the constraints ar OK, select a high gain vertex */
314 :     if (*from == -1) {
315 :     maxgain = -100000;
316 :     for (j=0; j<2; j++) {
317 :     for (i=0; i<ncon; i++) {
318 :     if (PQueueGetSize(&queues[i][j]) > 0 && PQueueGetKey(&queues[i][j]) > maxgain) {
319 :     maxgain = PQueueGetKey(&queues[i][0]);
320 :     *from = j;
321 :     *cnum = i;
322 :     }
323 :     }
324 :     }
325 :    
326 :     /* printf("(%2d %2d) %3d\n", *from, *cnum, maxgain); */
327 :     }
328 :     }

root@r-forge.r-project.org
ViewVC Help
Powered by ViewVC 1.0.0  
Thanks to:
Vienna University of Economics and Business Powered By FusionForge