GCC Code Coverage Report

Directory: src/
File: src/mngo/mngo_balancer.c
Date: 2026-09-15 07:37:49
Exec Total Coverage
Lines: 74 74 100.0%
Functions: 7 7 100.0%
Branches: 43 46 93.5%
Line Branch Exec Source
1 /*********************************************************************************/
2 /* Copyright 2009-2026 Barcelona Supercomputing Center */
3 /* */
4 /* This file is part of the DLB library. */
5 /* */
6 /* DLB is free software: you can redistribute it and/or modify */
7 /* it under the terms of the GNU Lesser General Public License as published by */
8 /* the Free Software Foundation, either version 3 of the License, or */
9 /* (at your option) any later version. */
10 /* */
11 /* DLB is distributed in the hope that it will be useful, */
12 /* but WITHOUT ANY WARRANTY; without even the implied warranty of */
13 /* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the */
14 /* GNU Lesser General Public License for more details. */
15 /* */
16 /* You should have received a copy of the GNU Lesser General Public License */
17 /* along with DLB. If not, see <https://www.gnu.org/licenses/>. */
18 /*********************************************************************************/
19
20 #include <stdbool.h>
21 #include <stddef.h>
22 #include <stdlib.h>
23
24 #include "mngo/mngo_balancer.h"
25
26 /**
27 * This file's task is to find a coherent (among all participants) ammount of
28 * cores that a process can change. For example: if one process requests 2
29 * cores, another 3 cores, but only one releases 4 cores. We must find a
30 * distribution makes the total ammount cores given equal to the total ammount
31 * received.
32 */
33
34 static size_t precompute_levels(int *restrict deltas, size_t deltas_size,
35 int *restrict count_add,
36 int *restrict count_sub, size_t count_size);
37
38 static int coherent_redistribution(bool i_am_a_giver, size_t my_abs_delta,
39 int *restrict count_add,
40 int *restrict count_sub, size_t count_size);
41
42 10 int mngo_balancer(size_t id, int *deltas, size_t size) {
43
44 10 size_t max = 0;
45
2/2
✓ Branch 0 taken 784 times.
✓ Branch 1 taken 10 times.
 794 for (size_t i = 0; i < size; i++) {
46 784 size_t abs_delta = (size_t)abs(deltas[i]);
47
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 774 times.
 784 if (max < abs_delta) max = abs_delta;
48 }
49
50 // We allocate up to max possition, because count_add[max] and
51 // count_sub[max] holds how many processes want to take or give
52 // (respectively) up-to max ammount of CPUs.
53 10 int *count_add = calloc(max + 1, sizeof(int));
54 10 int *count_sub = calloc(max + 1, sizeof(int));
55
56 // precompute_levels if the maximum among deltas is smaller than max this
57 // will provide the new max value. To avoid not needed computation during
58 // the next phase.
59 10 max = precompute_levels(deltas, size, count_add, count_sub, max);
60
61 10 size_t self_abs_delta = abs(deltas[id]);
62 10 bool i_am_a_giver = deltas[id] < 0;
63 10 int coherent_delta = coherent_redistribution(i_am_a_giver, self_abs_delta,
64 count_add, count_sub, max);
65
66 10 free(count_add);
67 10 free(count_sub);
68
69 10 return coherent_delta;
70 }
71
72 /*! \brief From a list of integer differences, compute how many give more than a
73 * value.
74 * \param[in] deltas An integer array of size deltas_size, with differences
75 * from different items.
76 * \param[in] deltas_size Size fo the deltas array.
77 * \param[out] count_add Array where count_add[N] shows how many items have
78 * positive N or bigger.
79 * \param[out] count_sub Array where count_sub[N] shows how many items have
80 * negative N or lower.
81 * \param[in] count_size Maximum size of count_add and count_sub.
82 *
83 * This function counts how many items in deltas have values of N or bigger for
84 * all N in {0, max(deltas)}.
85 */
86 12 static size_t precompute_levels(int *restrict deltas, size_t deltas_size,
87 int *restrict count_add,
88 int *restrict count_sub, size_t count_size) {
89
90 12 size_t final_count_size = 0;
91
92
2/2
✓ Branch 0 taken 792 times.
✓ Branch 1 taken 12 times.
 804 for (size_t id = 0; id < deltas_size; id++) {
93 // We have to continue when `deltas[id] == 0` to maintain the position
94 // `0` of the arrays the same as position `1`. To maintain the maximum
95 // value in the arrays properly.
96
2/2
✓ Branch 0 taken 772 times.
✓ Branch 1 taken 20 times.
 792 if (deltas[id] == 0) continue;
97
98 20 size_t abs_delta = abs(deltas[id]);
99
100 // Saturate the value of abs_delta, to avoid going out of bounds of the
101 // arrays.
102 20 size_t sat_abs_delta = abs_delta < count_size ? abs_delta : count_size;
103
104 // Update the highest value
105
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 4 times.
 20 if (sat_abs_delta > final_count_size) {
106 16 final_count_size = sat_abs_delta;
107 }
108
109 // Update the levels
110
2/2
✓ Branch 0 taken 13 times.
✓ Branch 1 taken 7 times.
 20 if (deltas[id] > 0) {
111
2/2
✓ Branch 0 taken 263 times.
✓ Branch 1 taken 13 times.
 276 for (size_t l = 0; l <= sat_abs_delta; l++) {
112 263 count_add[l]++;
113 }
114 } else {
115
2/2
✓ Branch 0 taken 192 times.
✓ Branch 1 taken 7 times.
 199 for (size_t l = 0; l <= sat_abs_delta; l++) {
116 192 count_sub[l]++;
117 }
118 }
119 }
120
121 12 return final_count_size;
122 }
123
124 static void pack_levels(size_t my_abs_delta, int *restrict levels,
125 int *restrict deltas, size_t id);
126
127 /**
128 * This function aims to redistribute CPUs across processes coherently after
129 * each process has communicated how many processes would like to give/take,
130 * without more communication.
131 *
132 * To achieve that it uses the aggregated data of how many processes want to
133 * give/take up-to a level of CPUs in the arrays `count_add` and `count_sub`.
134 *
135 * What is a level in this context:
136 * - A level is the number of CPUs a process wants to give or take.
137 *
138 * Local parameters (to decide what this process needs to do):
139 * - i_am_a_giver: true when this process wants to reduce the number of cpus
140 * - my_abs_delta: the positive value of the number of CPUs this process wants
141 * to give or get
142 *
143 * Remote parameters (to know what the others will do):
144 * - count_add: an array holding how many processes take CPUs for each level
145 * - count_sub: an array holding how many processes give CPUs for each level
146 * - max_level: the heighest valid level. group_deltas, count_add, count_sub
147 * should have allocated and valid data up to the max_level position.
148 */
149 14 static int coherent_redistribution(bool i_am_a_giver, size_t my_abs_delta,
150 int *restrict count_add,
151 int *restrict count_sub, size_t count_size) {
152
153 14 int my_coherent_delta = 0;
154
155 14 int *group_deltas = calloc(count_size + 1, sizeof(int));
156
4/4
✓ Branch 0 taken 233 times.
✓ Branch 1 taken 9 times.
✓ Branch 2 taken 228 times.
✓ Branch 3 taken 5 times.
 242 for (size_t i = 0; i <= count_size && i <= my_abs_delta; i++) {
157 228 group_deltas[i] = 1;
158 }
159
160
2/2
✓ Branch 0 taken 245 times.
✓ Branch 1 taken 14 times.
 259 for (size_t l_add = count_size; l_add >= 1; l_add--) {
161
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 238 times.
 245 if (count_add[l_add] == 0) continue; // Empty level
162
163 size_t l_sub;
164 238 bool match_found = false;
165
2/2
✓ Branch 0 taken 6304 times.
✓ Branch 1 taken 56 times.
 6360 for (l_sub = count_size; l_sub >= 1; l_sub--) {
166
2/2
✓ Branch 0 taken 6121 times.
✓ Branch 1 taken 183 times.
 6304 if (count_sub[l_sub] == 0) continue; // Empty level
167
168 // Pack with lower level if no match will be found
169
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 180 times.
 183 if (count_add[0] < count_sub[l_sub]) {
170 3 pack_levels(my_abs_delta, count_add, group_deltas, l_add);
171 3 break;
172 }
173
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 179 times.
 180 if (count_add[l_add] > count_sub[0]) {
174 1 pack_levels(my_abs_delta, count_sub, group_deltas, l_sub);
175 1 continue;
176 }
177
178 // We find a match
179
1/2
✓ Branch 0 taken 179 times.
✗ Branch 1 not taken.
 179 if (count_add[l_add] == count_sub[l_sub]) {
180 179 match_found = true;
181 179 count_add[l_add] = 0;
182 179 count_sub[l_sub] = 0;
183 179 break;
184 }
185 }
186
187
2/2
✓ Branch 0 taken 179 times.
✓ Branch 1 taken 59 times.
 238 if (match_found) {
188
2/2
✓ Branch 0 taken 90 times.
✓ Branch 1 taken 89 times.
 179 if (i_am_a_giver) {
189
1/2
✓ Branch 0 taken 90 times.
✗ Branch 1 not taken.
 90 if (l_sub <= my_abs_delta) {
190 90 my_coherent_delta -= group_deltas[l_sub];
191 90 group_deltas[l_sub] = 0;
192 }
193 } else {
194
1/2
✓ Branch 0 taken 89 times.
✗ Branch 1 not taken.
 89 if (l_add <= my_abs_delta) {
195 89 my_coherent_delta += group_deltas[l_add];
196 89 group_deltas[l_add] = 0;
197 }
198 }
199 }
200 }
201
202 14 free(group_deltas);
203
204 14 return my_coherent_delta;
205 }
206
207 6 static void pack_levels(size_t my_abs_delta, int *restrict levels,
208 int *restrict deltas, size_t level) {
209
210 /* Pack the level */
211 6 levels[level - 1] += levels[level];
212 6 levels[level] = 0;
213
214 /* If our level is within range we pack the deltas too. */
215
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 2 times.
 6 if (level <= my_abs_delta) {
216 4 deltas[level - 1] += deltas[level];
217 4 deltas[level] = 0;
218 }
219
220 /* Keep position 0 (i.e. the maximum) updated. */
221
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 2 times.
 6 if (levels[0] < levels[level - 1]) {
222 4 levels[0] = levels[level - 1];
223 }
224 6 }
225
226 /*********************************************************************************/
227 /* Functions for testing purposes */
228 /*********************************************************************************/
229
230 2 void mngo_balancer_testing__pack_levels(size_t my_abs_delta,
231 int *restrict levels,
232 int *restrict deltas, size_t level) {
233 2 return pack_levels(my_abs_delta, levels, deltas, level);
234 }
235
236 2 int mngo_balancer_testing__precompute_levels(int *restrict deltas,
237 size_t deltas_size,
238 int *restrict count_add,
239 int *restrict count_sub,
240 size_t count_size) {
241 2 return precompute_levels(deltas, deltas_size, count_add, count_sub,
242 count_size);
243 }
244
245 4 int mngo_balancer_testing__coherent_redistribution(bool i_am_a_giver,
246 size_t my_abs_delta,
247 int *restrict count_add,
248 int *restrict count_sub,
249 size_t count_size) {
250 4 return coherent_redistribution(i_am_a_giver, my_abs_delta, count_add,
251 count_sub, count_size);
252 }
253