4 * This file contains various utility functions for the MOC portion of the
10 * $Id: mcutil.c 13901 2013-03-24 16:17:03Z karypis $
17 /*************************************************************************/
18 /*! This function compares two vectors x & y and returns true
19 if \forall i, x[i] <= y[i].
21 /**************************************************************************/
22 int rvecle(idx_t n
, real_t
*x
, real_t
*y
)
24 for (n
--; n
>=0; n
--) {
33 /*************************************************************************/
34 /*! This function compares two vectors x & y and returns true
35 if \forall i, x[i] >= y[i].
37 /**************************************************************************/
38 int rvecge(idx_t n
, real_t
*x
, real_t
*y
)
40 for (n
--; n
>=0; n
--) {
49 /*************************************************************************/
50 /*! This function compares vectors x1+x2 against y and returns true
51 if \forall i, x1[i]+x2[i] <= y[i].
53 /**************************************************************************/
54 int rvecsumle(idx_t n
, real_t
*x1
, real_t
*x2
, real_t
*y
)
56 for (n
--; n
>=0; n
--) {
57 if (x1
[n
]+x2
[n
] > y
[n
])
65 /*************************************************************************/
66 /*! This function returns max_i(x[i]-y[i]) */
67 /**************************************************************************/
68 real_t
rvecmaxdiff(idx_t n
, real_t
*x
, real_t
*y
)
83 /*************************************************************************/
84 /*! This function returns true if \forall i, x[i] <= z[i]. */
85 /**************************************************************************/
86 int ivecle(idx_t n
, idx_t
*x
, idx_t
*z
)
88 for (n
--; n
>=0; n
--) {
97 /*************************************************************************/
98 /*! This function returns true if \forall i, x[i] >= z[i]. */
99 /**************************************************************************/
100 int ivecge(idx_t n
, idx_t
*x
, idx_t
*z
)
102 for (n
--; n
>=0; n
--) {
111 /*************************************************************************/
112 /*! This function returns true if \forall i, a*x[i]+y[i] <= z[i]. */
113 /**************************************************************************/
114 int ivecaxpylez(idx_t n
, idx_t a
, idx_t
*x
, idx_t
*y
, idx_t
*z
)
116 for (n
--; n
>=0; n
--) {
117 if (a
*x
[n
]+y
[n
] > z
[n
])
125 /*************************************************************************/
126 /*! This function returns true if \forall i, a*x[i]+y[i] >= z[i]. */
127 /**************************************************************************/
128 int ivecaxpygez(idx_t n
, idx_t a
, idx_t
*x
, idx_t
*y
, idx_t
*z
)
130 for (n
--; n
>=0; n
--) {
131 if (a
*x
[n
]+y
[n
] < z
[n
])
139 /*************************************************************************/
140 /*! This function checks if v+u2 provides a better balance in the weight
142 /*************************************************************************/
143 int BetterVBalance(idx_t ncon
, real_t
*invtvwgt
, idx_t
*v_vwgt
, idx_t
*u1_vwgt
,
147 real_t sum1
=0.0, sum2
=0.0, diff1
=0.0, diff2
=0.0;
149 for (i
=0; i
<ncon
; i
++) {
150 sum1
+= (v_vwgt
[i
]+u1_vwgt
[i
])*invtvwgt
[i
];
151 sum2
+= (v_vwgt
[i
]+u2_vwgt
[i
])*invtvwgt
[i
];
156 for (i
=0; i
<ncon
; i
++) {
157 diff1
+= rabs(sum1
- (v_vwgt
[i
]+u1_vwgt
[i
])*invtvwgt
[i
]);
158 diff2
+= rabs(sum2
- (v_vwgt
[i
]+u2_vwgt
[i
])*invtvwgt
[i
]);
161 return (diff1
- diff2
>= 0);
165 /*************************************************************************/
166 /*! This function takes two ubfactor-centered load imbalance vectors x & y,
167 and returns true if y is better balanced than x. */
168 /*************************************************************************/
169 int BetterBalance2Way(idx_t n
, real_t
*x
, real_t
*y
)
171 real_t nrm1
=0.0, nrm2
=0.0;
173 for (--n
; n
>=0; n
--) {
174 if (x
[n
] > 0) nrm1
+= x
[n
]*x
[n
];
175 if (y
[n
] > 0) nrm2
+= y
[n
]*y
[n
];
181 /*************************************************************************/
182 /*! Given a vertex and two weights, this function returns 1, if the second
183 partition will be more balanced than the first after the weighted
184 additional of that vertex.
185 The balance determination takes into account the ideal target weights
186 of the two partitions.
188 /*************************************************************************/
189 int BetterBalanceKWay(idx_t ncon
, idx_t
*vwgt
, real_t
*ubvec
,
190 idx_t a1
, idx_t
*pt1
, real_t
*bm1
,
191 idx_t a2
, idx_t
*pt2
, real_t
*bm2
)
194 real_t tmp
, nrm1
=0.0, nrm2
=0.0, max1
=0.0, max2
=0.0;
196 for (i
=0; i
<ncon
; i
++) {
197 tmp
= bm1
[i
]*(pt1
[i
]+a1
*vwgt
[i
]) - ubvec
[i
];
198 //printf("BB: %d %+.4f ", (int)i, (float)tmp);
200 max1
= (tmp
> max1
? tmp
: max1
);
202 tmp
= bm2
[i
]*(pt2
[i
]+a2
*vwgt
[i
]) - ubvec
[i
];
203 //printf("%+.4f ", (float)tmp);
205 max2
= (tmp
> max2
? tmp
: max2
);
207 //printf("%4d %4d %4d %4d %4d %4d %4d %.2f\n",
209 // (int)a1, (int)pt1[i], (int)tpt1[i],
210 // (int)a2, (int)pt2[i], (int)tpt2[i], ubvec[i]);
212 //printf(" %.3f %.3f %.3f %.3f\n", (float)max1, (float)nrm1, (float)max2, (float)nrm2);
217 if (max2
== max1
&& nrm2
< nrm1
)
224 /*************************************************************************/
225 /*! Computes the maximum load imbalance of a partitioning solution over
226 all the constraints. */
227 /**************************************************************************/
228 real_t
ComputeLoadImbalance(graph_t
*graph
, idx_t nparts
, real_t
*pijbm
)
230 idx_t i
, j
, ncon
, *pwgts
;
234 pwgts
= graph
->pwgts
;
237 for (i
=0; i
<ncon
; i
++) {
238 for (j
=0; j
<nparts
; j
++) {
239 cur
= pwgts
[j
*ncon
+i
]*pijbm
[j
*ncon
+i
];
249 /*************************************************************************/
250 /*! Computes the maximum load imbalance difference of a partitioning
251 solution over all the constraints.
252 The difference is defined with respect to the allowed maximum
253 unbalance for the respective constraint.
255 /**************************************************************************/
256 real_t
ComputeLoadImbalanceDiff(graph_t
*graph
, idx_t nparts
, real_t
*pijbm
,
259 idx_t i
, j
, ncon
, *pwgts
;
263 pwgts
= graph
->pwgts
;
266 for (i
=0; i
<ncon
; i
++) {
267 for (j
=0; j
<nparts
; j
++) {
268 cur
= pwgts
[j
*ncon
+i
]*pijbm
[j
*ncon
+i
] - ubvec
[i
];
278 /*************************************************************************/
279 /*! Computes the difference between load imbalance of each constraint across
280 the partitions minus the desired upper bound on the load imabalnce.
281 It also returns the maximum load imbalance across the partitions &
283 /**************************************************************************/
284 real_t
ComputeLoadImbalanceDiffVec(graph_t
*graph
, idx_t nparts
, real_t
*pijbm
,
285 real_t
*ubfactors
, real_t
*diffvec
)
287 idx_t i
, j
, ncon
, *pwgts
;
291 pwgts
= graph
->pwgts
;
293 for (max
=-1.0, i
=0; i
<ncon
; i
++) {
294 diffvec
[i
] = pwgts
[i
]*pijbm
[i
] - ubfactors
[i
];
295 for (j
=1; j
<nparts
; j
++) {
296 cur
= pwgts
[j
*ncon
+i
]*pijbm
[j
*ncon
+i
] - ubfactors
[i
];
297 if (cur
> diffvec
[i
])
300 if (max
< diffvec
[i
])
308 /*************************************************************************/
309 /*! Computes the load imbalance of each constraint across the partitions. */
310 /**************************************************************************/
311 void ComputeLoadImbalanceVec(graph_t
*graph
, idx_t nparts
, real_t
*pijbm
,
314 idx_t i
, j
, ncon
, *pwgts
;
318 pwgts
= graph
->pwgts
;
320 for (i
=0; i
<ncon
; i
++) {
321 lbvec
[i
] = pwgts
[i
]*pijbm
[i
];
322 for (j
=1; j
<nparts
; j
++) {
323 cur
= pwgts
[j
*ncon
+i
]*pijbm
[j
*ncon
+i
];