1 | /* ----------------------- */ |
---|
2 | /* --- mca_rosenfeld.c --- */ |
---|
3 | /* ----------------------- */ |
---|
4 | |
---|
5 | /* |
---|
6 | * Copyright (c) 2016 Lionel Lacassagne, LIP6, UPMC, CNRS |
---|
7 | * Init : 2016/03/03 |
---|
8 | */ |
---|
9 | |
---|
10 | #include <stdio.h> |
---|
11 | #include <stdlib.h> |
---|
12 | #include <string.h> |
---|
13 | #include <math.h> |
---|
14 | #include <assert.h> |
---|
15 | #if PARMERGE |
---|
16 | #include <pthread.h> |
---|
17 | #endif |
---|
18 | |
---|
19 | #include "nrc_os_config.h" |
---|
20 | #include "config.h" |
---|
21 | #include "nrc.h" |
---|
22 | |
---|
23 | #if TARGET_OS == GIETVM |
---|
24 | #include <user_barrier.h> |
---|
25 | #include <user_lock.h> |
---|
26 | #include <giet_config.h> |
---|
27 | #else |
---|
28 | #include <stdbool.h> |
---|
29 | #endif |
---|
30 | |
---|
31 | |
---|
32 | #include "util.h" |
---|
33 | #include "ecc_common.h" |
---|
34 | #include "palette.h" |
---|
35 | #include "bmpNR.h" |
---|
36 | #include "clock.h" |
---|
37 | #include "str_ext.h" |
---|
38 | #include "ecc_features.h" |
---|
39 | |
---|
40 | // ----------- |
---|
41 | // -- local -- |
---|
42 | // ----------- |
---|
43 | |
---|
44 | #include "mca.h" |
---|
45 | |
---|
46 | extern pthread_barrier_t main_barrier; |
---|
47 | extern int display_features; |
---|
48 | |
---|
49 | CLOCK_DEC; |
---|
50 | |
---|
51 | |
---|
52 | // ----------------------------------------- |
---|
53 | static uint32 FindRoot(uint32 * T, uint32 e) |
---|
54 | // ----------------------------------------- |
---|
55 | { |
---|
56 | uint32 r; |
---|
57 | |
---|
58 | assert(e != 0); |
---|
59 | r = e; |
---|
60 | while (T[r] < r) { |
---|
61 | r = T[r]; |
---|
62 | } |
---|
63 | |
---|
64 | assert(r != 0); |
---|
65 | return r; |
---|
66 | } |
---|
67 | |
---|
68 | |
---|
69 | // ---------------------------------------------------------- |
---|
70 | static uint32 FindRoot_Dist(uint32 ** D, uint32 r, int shift) |
---|
71 | // ---------------------------------------------------------- |
---|
72 | { |
---|
73 | uint32 e; |
---|
74 | uint32 e1; |
---|
75 | uint32 e0; |
---|
76 | |
---|
77 | assert(r != 0); |
---|
78 | |
---|
79 | int mask = (1 << shift) - 1; |
---|
80 | |
---|
81 | MCA_VERBOSE3(printf("%s(%d, %d) \n", __func__, r, shift)); |
---|
82 | do { |
---|
83 | e = r; |
---|
84 | e1 = r >> shift; |
---|
85 | e0 = r & mask; |
---|
86 | r = D[e1][e0]; |
---|
87 | MCA_VERBOSE3(printf("%s: D(%d) = D[%d,%d] = %d (alpha = %d)\n", __func__, e, e1, e0, r, shift)); |
---|
88 | } while (r < e); |
---|
89 | MCA_VERBOSE3(printf("%s = %d \n\n", __func__, r)); |
---|
90 | assert(r != 0); |
---|
91 | return r; |
---|
92 | } |
---|
93 | |
---|
94 | |
---|
95 | #if !FEATURES |
---|
96 | // -------------------------------------------------------------------------------- |
---|
97 | static void SetRoot_Rosenfeld_Dist(uint32 ** D, uint32 root, uint32 eps, int shift) |
---|
98 | // -------------------------------------------------------------------------------- |
---|
99 | { |
---|
100 | int mask = (1 << shift) - 1; |
---|
101 | assert(root != 0 && eps != 0); |
---|
102 | |
---|
103 | uint32 r1 = root >> shift; |
---|
104 | uint32 r0 = root & mask; |
---|
105 | |
---|
106 | D[r1][r0] = eps; |
---|
107 | } |
---|
108 | #endif // !FEATURES |
---|
109 | |
---|
110 | |
---|
111 | #if FEATURES && !PARMERGE |
---|
112 | // ----------------------------------------------------------------------------------------------------------- |
---|
113 | static void SetRoot_Features_Rosenfeld_Dist(uint32 ** D, uint32 root, uint32 eps, int shift, RegionStats ** F) |
---|
114 | // ----------------------------------------------------------------------------------------------------------- |
---|
115 | { |
---|
116 | assert(root != 0 && eps != 0); |
---|
117 | |
---|
118 | MCA_VERBOSE3(printf("F(%d) += F(%d)\n", eps, root)); |
---|
119 | |
---|
120 | int mask = (1 << shift) - 1; |
---|
121 | |
---|
122 | uint32 r1 = root >> shift; |
---|
123 | uint32 r0 = root & mask; |
---|
124 | |
---|
125 | D[r1][r0] = eps; |
---|
126 | |
---|
127 | uint32 e1 = eps >> shift; |
---|
128 | uint32 e0 = eps & mask; |
---|
129 | |
---|
130 | // version Dist de "RegionStats_Accumulate_Stats1_From_Index" |
---|
131 | |
---|
132 | // F(eps) = F(eps) U F(root) |
---|
133 | |
---|
134 | F[e1][e0].xmin = ui16min2(F[e1][e0].xmin, F[r1][r0].xmin); |
---|
135 | F[e1][e0].xmax = ui16max2(F[e1][e0].xmax, F[r1][r0].xmax); |
---|
136 | F[e1][e0].ymin = ui16min2(F[e1][e0].ymin, F[r1][r0].ymin); |
---|
137 | F[e1][e0].ymax = ui16max2(F[e1][e0].ymax, F[r1][r0].ymax); |
---|
138 | |
---|
139 | F[e1][e0].S += F[r1][r0].S; |
---|
140 | F[e1][e0].Sx += F[r1][r0].Sx; |
---|
141 | F[e1][e0].Sy += F[r1][r0].Sy; |
---|
142 | } |
---|
143 | #endif // FEATURES && !PARMERGE |
---|
144 | |
---|
145 | |
---|
146 | #if !FEATURES && PARMERGE |
---|
147 | // ----------------------------------------------------------------------------------------------------------- |
---|
148 | static bool SetRoot_Parallel_Rosenfeld_Dist(uint32 ** D, uint32 root, uint32 eps, int shift, RegionStats ** F) |
---|
149 | // ----------------------------------------------------------------------------------------------------------- |
---|
150 | { |
---|
151 | assert(root != 0 && eps != 0); |
---|
152 | |
---|
153 | MCA_VERBOSE3(printf("F(%d) += F(%d)\n", eps, root)); |
---|
154 | |
---|
155 | int mask = (1 << shift) - 1; |
---|
156 | |
---|
157 | uint32 r1 = root >> shift; |
---|
158 | uint32 r0 = root & mask; |
---|
159 | |
---|
160 | uint32 e1 = eps >> shift; |
---|
161 | uint32 e0 = eps & mask; |
---|
162 | |
---|
163 | // Locking towards the root (first root, then eps) |
---|
164 | pthread_spin_lock(&F[r1][r0].lock); |
---|
165 | pthread_spin_lock(&F[e1][e0].lock); |
---|
166 | if (D[e1][e0] != eps || D[r1][r0] != root) { |
---|
167 | // Someone change the root of epsilon or "root", need to find the new root |
---|
168 | pthread_spin_unlock(&F[e1][e0].lock); |
---|
169 | pthread_spin_unlock(&F[r1][r0].lock); |
---|
170 | return false; |
---|
171 | } |
---|
172 | |
---|
173 | D[r1][r0] = eps; |
---|
174 | |
---|
175 | pthread_spin_unlock(&F[e1][e0].lock); |
---|
176 | pthread_spin_unlock(&F[r1][r0].lock); |
---|
177 | return true; |
---|
178 | } |
---|
179 | #endif // !FEATURES && PARMERGE |
---|
180 | |
---|
181 | |
---|
182 | #if FEATURES && PARMERGE |
---|
183 | // -------------------------------------------------------------------------------------------------------------------- |
---|
184 | static bool SetRoot_Parallel_Features_Rosenfeld_Dist(uint32 ** D, uint32 root, uint32 eps, int shift, RegionStats ** F) |
---|
185 | // -------------------------------------------------------------------------------------------------------------------- |
---|
186 | { |
---|
187 | assert(root != 0 && eps != 0); |
---|
188 | |
---|
189 | MCA_VERBOSE3(printf("F(%d) += F(%d)\n", eps, root)); |
---|
190 | |
---|
191 | int mask = (1 << shift) - 1; |
---|
192 | |
---|
193 | uint32 r1 = root >> shift; |
---|
194 | uint32 r0 = root & mask; |
---|
195 | |
---|
196 | uint32 e1 = eps >> shift; |
---|
197 | uint32 e0 = eps & mask; |
---|
198 | |
---|
199 | // Locking towards the root (first root, then eps) |
---|
200 | pthread_spin_lock(&F[r1][r0].lock); |
---|
201 | pthread_spin_lock(&F[e1][e0].lock); |
---|
202 | // FIXME: merge these conditions later, when they both appear |
---|
203 | if (D[e1][e0] != eps) { |
---|
204 | // Someone change the root of epsilon, need to find the new root |
---|
205 | printf("race cond 1\n"); |
---|
206 | pthread_spin_unlock(&F[e1][e0].lock); |
---|
207 | pthread_spin_unlock(&F[r1][r0].lock); |
---|
208 | return false; |
---|
209 | } |
---|
210 | if (D[r1][r0] != root) { |
---|
211 | // Someone change the root of "root", need to find the new root |
---|
212 | printf("race cond 2\n"); |
---|
213 | pthread_spin_unlock(&F[e1][e0].lock); |
---|
214 | pthread_spin_unlock(&F[r1][r0].lock); |
---|
215 | return false; |
---|
216 | } |
---|
217 | |
---|
218 | D[r1][r0] = eps; |
---|
219 | |
---|
220 | // F(eps) = F(eps) U F(root) |
---|
221 | F[e1][e0].xmin = ui16min2(F[e1][e0].xmin, F[r1][r0].xmin); |
---|
222 | F[e1][e0].xmax = ui16max2(F[e1][e0].xmax, F[r1][r0].xmax); |
---|
223 | F[e1][e0].ymin = ui16min2(F[e1][e0].ymin, F[r1][r0].ymin); |
---|
224 | F[e1][e0].ymax = ui16max2(F[e1][e0].ymax, F[r1][r0].ymax); |
---|
225 | |
---|
226 | F[e1][e0].S += F[r1][r0].S; |
---|
227 | F[e1][e0].Sx += F[r1][r0].Sx; |
---|
228 | F[e1][e0].Sy += F[r1][r0].Sy; |
---|
229 | |
---|
230 | pthread_spin_unlock(&F[e1][e0].lock); |
---|
231 | pthread_spin_unlock(&F[r1][r0].lock); |
---|
232 | return true; |
---|
233 | } |
---|
234 | #endif // FEATURES && PARMERGE |
---|
235 | |
---|
236 | |
---|
237 | |
---|
238 | #if FAST |
---|
239 | // -------------------------------------------------------- |
---|
240 | static uint32 QuickUnion2(uint32 * T, uint32 e1, uint32 e2) |
---|
241 | // -------------------------------------------------------- |
---|
242 | { |
---|
243 | // version QU de Union2 |
---|
244 | uint32 r1 = FindRoot(T, e1); |
---|
245 | uint32 r2 = FindRoot(T, e2); |
---|
246 | |
---|
247 | assert(e1 != 0 && e2 != 0 && r1 != 0 && r2 != 0); |
---|
248 | uint32 eps = ui32Min2(r1, r2); |
---|
249 | |
---|
250 | if (r1 > eps) { |
---|
251 | T[r1] = eps; // SetRoot sans besoin de remonter |
---|
252 | } |
---|
253 | if (r2 > eps) { |
---|
254 | T[r2] = eps; // SetRoot sans besoin de remonter |
---|
255 | } |
---|
256 | assert(e1 != 0 && e2 != 0 && r1 != 0 && r2 != 0); |
---|
257 | |
---|
258 | return eps; |
---|
259 | } |
---|
260 | #endif // FAST |
---|
261 | |
---|
262 | |
---|
263 | #if FAST |
---|
264 | // --------------------------------------------------- |
---|
265 | static uint32 use1_QU_Rosenfeld(uint32 e1, uint32 * T) |
---|
266 | // --------------------------------------------------- |
---|
267 | { |
---|
268 | return FindRoot(T, e1); |
---|
269 | } |
---|
270 | #endif // FAST |
---|
271 | |
---|
272 | |
---|
273 | #if FAST |
---|
274 | // -------------------------------------------------------------- |
---|
275 | static uint32 use2_QU_Rosenfeld(uint32 e1, uint32 e2, uint32 * T) |
---|
276 | // -------------------------------------------------------------- |
---|
277 | { |
---|
278 | return QuickUnion2(T, e1, e2); |
---|
279 | } |
---|
280 | #endif // FAST |
---|
281 | |
---|
282 | |
---|
283 | #if FAST && !FEATURES && !PARMERGE && !ARSP |
---|
284 | // --------------------------------------------------------------------------------------- |
---|
285 | static void vuse2_Rosenfeld_Dist(uint32 ed, uint32 el, uint32 * T, uint32 ** D, int alpha) |
---|
286 | // --------------------------------------------------------------------------------------- |
---|
287 | { |
---|
288 | uint32 rd = FindRoot_Dist(D, ed, alpha); |
---|
289 | |
---|
290 | uint32 rl = T[el]; // car le premier acces est local |
---|
291 | rl = FindRoot_Dist(D, rl, alpha); |
---|
292 | |
---|
293 | assert(ed != 0 && el != 0 && rd != 0 && rl != 0); |
---|
294 | if (rd == rl) { |
---|
295 | return; // evite la backdoor |
---|
296 | } |
---|
297 | |
---|
298 | // forcement positifs car appel depuis optimizedBorder |
---|
299 | // qui a fait un test |
---|
300 | if (rd < rl) { |
---|
301 | SetRoot_Rosenfeld_Dist(D, rl, rd, alpha); |
---|
302 | } |
---|
303 | else { |
---|
304 | SetRoot_Rosenfeld_Dist(D, rd, rl, alpha); |
---|
305 | } |
---|
306 | } |
---|
307 | |
---|
308 | // FAST && !FEATURES && !PARMERGE && !ARSP |
---|
309 | |
---|
310 | // ----------------------------------------------------------------------------------------------------- |
---|
311 | static void vuse3_Rosenfeld_Dist(uint32 ed1, uint32 ed2, uint32 el3, uint32 * T, uint32 ** D, int alpha) |
---|
312 | // ----------------------------------------------------------------------------------------------------- |
---|
313 | { |
---|
314 | uint32 r1 = FindRoot_Dist(D, ed1, alpha); |
---|
315 | uint32 r2 = FindRoot_Dist(D, ed2, alpha); |
---|
316 | |
---|
317 | uint32 r3 = T[el3]; // local - distant |
---|
318 | r3 = FindRoot_Dist(D, r3, alpha); |
---|
319 | |
---|
320 | assert(ed1 != 0 && ed2 != 0 && el3 != 0 && r1 != 0 && r2 != 0 && r3 != 0); |
---|
321 | |
---|
322 | if (r1 == r2 && r2 == r3) { |
---|
323 | return; |
---|
324 | } |
---|
325 | |
---|
326 | uint32 eps = ui32Min3(r1, r2, r3); // forcement positifs car appel depuis optimizedBorder qui a fait un test |
---|
327 | |
---|
328 | // On ne fait pas le test car on peut faire le SetRoot plusieurs fois sur le même élément (on n'accumule pas de stats) |
---|
329 | if (r1 > eps) { |
---|
330 | SetRoot_Rosenfeld_Dist(D, r1, eps, alpha); |
---|
331 | } |
---|
332 | if (r2 > eps) { |
---|
333 | SetRoot_Rosenfeld_Dist(D, r2, eps, alpha); |
---|
334 | } |
---|
335 | if (r3 > eps) { |
---|
336 | SetRoot_Rosenfeld_Dist(D, r3, eps, alpha); |
---|
337 | } |
---|
338 | } |
---|
339 | #endif // FAST && !FEATURES && !PARMERGE && !ARSP |
---|
340 | |
---|
341 | |
---|
342 | #if FAST && FEATURES && !PARMERGE && !ARSP |
---|
343 | // ------------------------------------------------------------------------------------------------------------------ |
---|
344 | static void vuse2_Features_Rosenfeld_Dist(uint32 ed, uint32 el, uint32 * T, uint32 ** D, int alpha, RegionStats ** F) |
---|
345 | // ------------------------------------------------------------------------------------------------------------------ |
---|
346 | { |
---|
347 | assert(ed != 0 && el != 0); |
---|
348 | |
---|
349 | uint32 rd = FindRoot_Dist(D, ed, alpha); |
---|
350 | |
---|
351 | uint32 rl = T[el]; // car le premier acces est local |
---|
352 | assert(rl != 0); |
---|
353 | rl = FindRoot_Dist(D, rl, alpha); |
---|
354 | |
---|
355 | assert(rd != 0 && rl != 0); |
---|
356 | |
---|
357 | if (rd == rl) { |
---|
358 | return; // evite la backdoor |
---|
359 | } |
---|
360 | |
---|
361 | // forcement positifs car appel depuis optimizedBorder |
---|
362 | // qui a fait un test |
---|
363 | if (rd < rl) { |
---|
364 | SetRoot_Features_Rosenfeld_Dist(D, rl, rd, alpha, F); |
---|
365 | } |
---|
366 | else { |
---|
367 | SetRoot_Features_Rosenfeld_Dist(D, rd, rl, alpha, F); |
---|
368 | } |
---|
369 | } |
---|
370 | |
---|
371 | // FAST && FEATURES && !PARMERGE && !ARSP |
---|
372 | |
---|
373 | // -------------------------------------------------------------------------------------------------------------------------------- |
---|
374 | static void vuse3_Features_Rosenfeld_Dist(uint32 ed1, uint32 ed2, uint32 el3, uint32 * T, uint32 ** D, int alpha, RegionStats ** F) |
---|
375 | // -------------------------------------------------------------------------------------------------------------------------------- |
---|
376 | { |
---|
377 | assert(ed1 != 0 && ed2 != 0 && el3 != 0); |
---|
378 | |
---|
379 | uint32 r1 = FindRoot_Dist(D, ed1, alpha); |
---|
380 | uint32 r2 = FindRoot_Dist(D, ed2, alpha); |
---|
381 | |
---|
382 | uint32 r3 = T[el3]; // local - distant |
---|
383 | assert(r3 != 0); |
---|
384 | r3 = FindRoot_Dist(D, r3, alpha); |
---|
385 | |
---|
386 | assert(r1 != 0 && r2 != 0 && r3 != 0); |
---|
387 | |
---|
388 | if (r1 == r2 && r2 == r3) { |
---|
389 | return; |
---|
390 | } |
---|
391 | |
---|
392 | uint32 eps = ui32Min3(r1, r2, r3); // forcement positifs car appel depuis optimizedBorder qui a fait un test |
---|
393 | |
---|
394 | if (r1 > eps) { |
---|
395 | SetRoot_Features_Rosenfeld_Dist(D, r1, eps, alpha, F); |
---|
396 | } |
---|
397 | if (r2 > eps && r2 != r1) { |
---|
398 | SetRoot_Features_Rosenfeld_Dist(D, r2, eps, alpha, F); |
---|
399 | } |
---|
400 | if (r3 > eps && r3 != r2 && r3 != r1) { |
---|
401 | SetRoot_Features_Rosenfeld_Dist(D, r3, eps, alpha, F); |
---|
402 | } |
---|
403 | } |
---|
404 | #endif // FAST && FEATURES && !PARMERGE && !ARSP |
---|
405 | |
---|
406 | |
---|
407 | #if FAST && !FEATURES && PARMERGE && ARSP |
---|
408 | // ---------------------------------------------------------------------------------------------------------------- |
---|
409 | static bool SetRoot_Parallel_Arsp_Rosenfeld_Dist(uint32 ** D, uint32 root, uint32 eps, int shift, RegionStats ** F) |
---|
410 | // ---------------------------------------------------------------------------------------------------------------- |
---|
411 | { |
---|
412 | assert(root != 0 && eps != 0); |
---|
413 | |
---|
414 | MCA_VERBOSE3(printf("F(%d) += F(%d)\n", eps, root)); |
---|
415 | |
---|
416 | uint32_t mask = (1 << shift) - 1; |
---|
417 | |
---|
418 | uint32_t r1 = root >> shift; |
---|
419 | uint32_t r0 = root & mask; |
---|
420 | |
---|
421 | pthread_spin_lock(&F[r1][r0].lock); |
---|
422 | if (D[r1][r0] != root) { |
---|
423 | pthread_spin_unlock(&F[r1][r0].lock); |
---|
424 | return false; |
---|
425 | } |
---|
426 | |
---|
427 | D[r1][r0] = eps; |
---|
428 | |
---|
429 | pthread_spin_unlock(&F[r1][r0].lock); |
---|
430 | return true; |
---|
431 | } |
---|
432 | |
---|
433 | // FAST && !FEATURES && PARMERGE && ARSP |
---|
434 | |
---|
435 | // ------------------------------------------------------------------------------------------------------------------------------ |
---|
436 | static inline bool FindSmallerAncestor_Link(uint32 ** D, uint32_t rl, uint32_t el, uint32_t rd, uint32_t shift, RegionStats ** F) |
---|
437 | // ------------------------------------------------------------------------------------------------------------------------------ |
---|
438 | { |
---|
439 | bool ok; |
---|
440 | uint32_t el1, el0; |
---|
441 | uint32_t mask = (1 << shift) - 1; |
---|
442 | while (rl < el && rl > rd) { |
---|
443 | el = rl; |
---|
444 | el1 = rl >> shift; |
---|
445 | el0 = rl & mask; |
---|
446 | rl = D[el1][el0]; |
---|
447 | } |
---|
448 | if (rd != rl) { |
---|
449 | if (rl == el && rl > rd) { |
---|
450 | // L'ordre s'est inversé : on fait pointer rl vers rd |
---|
451 | ok = SetRoot_Parallel_Arsp_Rosenfeld_Dist(D, rl, rd, shift, F); |
---|
452 | } |
---|
453 | else { |
---|
454 | // On fait pointer rd vers rl |
---|
455 | ok = SetRoot_Parallel_Arsp_Rosenfeld_Dist(D, rd, rl, shift, F); |
---|
456 | } |
---|
457 | } |
---|
458 | else { |
---|
459 | ok = true; |
---|
460 | } |
---|
461 | return ok; |
---|
462 | } |
---|
463 | |
---|
464 | // FAST && !FEATURES && PARMERGE && ARSP |
---|
465 | |
---|
466 | // ----------------------------------------------------------------------------------------------------------------------- |
---|
467 | static void vuse2_Parallel_Arsp_Rosenfeld_Dist(uint32 ed, uint32 el, uint32 * T, uint32 ** D, int alpha, RegionStats ** F) |
---|
468 | // ----------------------------------------------------------------------------------------------------------------------- |
---|
469 | { |
---|
470 | assert(ed != 0 && el != 0); |
---|
471 | |
---|
472 | uint32_t shift = alpha; |
---|
473 | uint32_t mask = (1 << shift) - 1; |
---|
474 | |
---|
475 | uint32_t rd = ed; |
---|
476 | uint32_t rl = el; |
---|
477 | |
---|
478 | uint32_t ed1; |
---|
479 | uint32_t el1; |
---|
480 | uint32_t ed0; |
---|
481 | uint32_t el0; |
---|
482 | |
---|
483 | bool ok; |
---|
484 | |
---|
485 | // Fusion ed - el |
---|
486 | do { |
---|
487 | do { |
---|
488 | ed = rd; |
---|
489 | el = rl; |
---|
490 | ed1 = rd >> shift; |
---|
491 | el1 = rl >> shift; |
---|
492 | ed0 = rd & mask; |
---|
493 | el0 = rl & mask; |
---|
494 | rd = D[ed1][ed0]; |
---|
495 | rl = D[el1][el0]; |
---|
496 | } while (rl < el && rd < ed); |
---|
497 | |
---|
498 | assert(rl != 0 && rd != 0); |
---|
499 | |
---|
500 | if (rd != rl) { |
---|
501 | if (rd == ed) { |
---|
502 | ok = FindSmallerAncestor_Link(D, rl, el, rd, shift, F); |
---|
503 | } |
---|
504 | else { |
---|
505 | assert(rl == el); |
---|
506 | ok = FindSmallerAncestor_Link(D, rd, ed, rl, shift, F); |
---|
507 | } |
---|
508 | } |
---|
509 | else { |
---|
510 | ok = true; |
---|
511 | } |
---|
512 | } while (!ok); |
---|
513 | } |
---|
514 | |
---|
515 | // FAST && !FEATURES && PARMERGE && ARSP |
---|
516 | |
---|
517 | // ------------------------------------------------------------------------------------------------------------------------------------- |
---|
518 | static void vuse3_Parallel_Arsp_Rosenfeld_Dist(uint32 ed1, uint32 ed2, uint32 el3, uint32 * T, uint32 ** D, int alpha, RegionStats ** F) |
---|
519 | // ------------------------------------------------------------------------------------------------------------------------------------- |
---|
520 | { |
---|
521 | assert(ed1 != 0 && ed2 != 0 && el3 != 0); |
---|
522 | |
---|
523 | uint32_t shift = alpha; |
---|
524 | uint32_t mask = (1 << shift) - 1; |
---|
525 | |
---|
526 | uint32_t r1 = ed1; |
---|
527 | uint32_t r2 = ed2; |
---|
528 | uint32_t r3 = el3; |
---|
529 | |
---|
530 | uint32_t e11; |
---|
531 | uint32_t e21; |
---|
532 | uint32_t e31; |
---|
533 | uint32_t e10; |
---|
534 | uint32_t e20; |
---|
535 | uint32_t e30; |
---|
536 | |
---|
537 | uint32_t r0; |
---|
538 | uint32_t ed0; |
---|
539 | uint32_t e00; |
---|
540 | uint32_t e01; |
---|
541 | |
---|
542 | // Pas d'init pour que valgrind détecte une erreur si bool est lu sans être affecté |
---|
543 | bool ok; |
---|
544 | |
---|
545 | // Fusion ed1 - ed2 |
---|
546 | do { |
---|
547 | do { |
---|
548 | ed1 = r1; |
---|
549 | ed2 = r2; |
---|
550 | e11 = r1 >> shift; |
---|
551 | e21 = r2 >> shift; |
---|
552 | e10 = r1 & mask; |
---|
553 | e20 = r2 & mask; |
---|
554 | r1 = D[e11][e10]; |
---|
555 | r2 = D[e21][e20]; |
---|
556 | } while (r1 < ed1 && r2 < ed2); |
---|
557 | |
---|
558 | assert(r1 != 0 && r2 != 0); |
---|
559 | |
---|
560 | if (r1 != r2) { |
---|
561 | if (r1 == ed1) { |
---|
562 | ok = FindSmallerAncestor_Link(D, r2, ed2, r1, shift, F); |
---|
563 | } |
---|
564 | else { |
---|
565 | assert(r2 == ed2); |
---|
566 | ok = FindSmallerAncestor_Link(D, r1, ed1, r2, shift, F); |
---|
567 | } |
---|
568 | } |
---|
569 | else { |
---|
570 | ok = true; |
---|
571 | } |
---|
572 | } while (!ok); |
---|
573 | |
---|
574 | // Fusion r0 = min(r1, r2) avec r3 |
---|
575 | if (r1 < r2) { |
---|
576 | r0 = r1; |
---|
577 | ed0 = r1; |
---|
578 | e00 = e10; |
---|
579 | e01 = e11; |
---|
580 | } |
---|
581 | else { |
---|
582 | r0 = r2; |
---|
583 | ed0 = r2; |
---|
584 | e00 = e20; |
---|
585 | e01 = e21; |
---|
586 | } |
---|
587 | |
---|
588 | // r0 est déjà une racine |
---|
589 | goto r0_is_root; |
---|
590 | do { |
---|
591 | do { |
---|
592 | ed0 = r0; |
---|
593 | el3 = r3; |
---|
594 | e01 = r0 >> shift; |
---|
595 | e31 = r3 >> shift; |
---|
596 | e00 = r0 & mask; |
---|
597 | e30 = r3 & mask; |
---|
598 | r0 = D[e01][e00]; |
---|
599 | r3 = D[e31][e30]; |
---|
600 | } while (r0 < ed0 && r3 < el3); |
---|
601 | |
---|
602 | assert(r0 != 0 && r3 != 0); |
---|
603 | |
---|
604 | if (r0 != r3) { |
---|
605 | if (r0 == ed0) { |
---|
606 | r0_is_root: |
---|
607 | ok = FindSmallerAncestor_Link(D, r3, el3, r0, shift, F); |
---|
608 | } |
---|
609 | else { |
---|
610 | assert(r3 == el3); |
---|
611 | ok = FindSmallerAncestor_Link(D, r0, ed0, r3, shift, F); |
---|
612 | } |
---|
613 | } |
---|
614 | else { |
---|
615 | ok = true; |
---|
616 | } |
---|
617 | } while (!ok); |
---|
618 | } |
---|
619 | #endif // FAST && !FEATURES && PARMERGE && ARSP |
---|
620 | |
---|
621 | |
---|
622 | |
---|
623 | #if FAST && PARMERGE && !ARSP // Valid for FEATURES and !FEATURES |
---|
624 | // --------------------------------------------------------------------------------------------------------------------------- |
---|
625 | static void vuse2_Parallel_Rosenfeld_Dist(uint32 ed, uint32 el, uint32 * T, uint32 ** D, int alpha, RegionStats ** F) |
---|
626 | // --------------------------------------------------------------------------------------------------------------------------- |
---|
627 | { |
---|
628 | bool ok; |
---|
629 | assert(ed != 0 && el != 0); |
---|
630 | uint32 rl = T[el]; // car le premier acces est local |
---|
631 | assert(rl != 0); |
---|
632 | |
---|
633 | uint32 rd; |
---|
634 | |
---|
635 | do { |
---|
636 | rd = FindRoot_Dist(D, ed, alpha); // no lock |
---|
637 | rl = FindRoot_Dist(D, rl, alpha); |
---|
638 | |
---|
639 | assert(rd != 0 && rl != 0); |
---|
640 | |
---|
641 | if (rd == rl) { |
---|
642 | return; // evite la backdoor |
---|
643 | } |
---|
644 | |
---|
645 | // forcement positifs car appel depuis optimizedBorder |
---|
646 | // qui a fait un test |
---|
647 | if (rd < rl) { |
---|
648 | // Features or No Features depending on config |
---|
649 | ok = SetRoot_Parallel_FNF(D, rl, rd, alpha, F); |
---|
650 | } |
---|
651 | else { |
---|
652 | ok = SetRoot_Parallel_FNF(D, rd, rl, alpha, F); |
---|
653 | } |
---|
654 | } while (!ok); |
---|
655 | } |
---|
656 | |
---|
657 | // FAST && PARMERGE && !ARSP |
---|
658 | |
---|
659 | // ----------------------------------------------------------------------------------------------------------------------------------------- |
---|
660 | static void vuse3_Parallel_Rosenfeld_Dist(uint32 ed1, uint32 ed2, uint32 el3, uint32 * T, uint32 ** D, int alpha, RegionStats ** F) |
---|
661 | // ----------------------------------------------------------------------------------------------------------------------------------------- |
---|
662 | { |
---|
663 | bool ok1, ok2, ok3; |
---|
664 | assert(ed1 != 0 && ed2 != 0 && el3 != 0); |
---|
665 | |
---|
666 | uint32 r1; |
---|
667 | uint32 r2; |
---|
668 | uint32 r3 = T[el3]; // local - distant |
---|
669 | assert(r3 != 0); |
---|
670 | |
---|
671 | do { |
---|
672 | r1 = FindRoot_Dist(D, ed1, alpha); |
---|
673 | r2 = FindRoot_Dist(D, ed2, alpha); |
---|
674 | r3 = FindRoot_Dist(D, r3, alpha); |
---|
675 | |
---|
676 | assert(r1 != 0 && r2 != 0 && r3 != 0); |
---|
677 | |
---|
678 | if (r1 == r2 && r2 == r3) { |
---|
679 | return; |
---|
680 | } |
---|
681 | |
---|
682 | uint32 eps = ui32Min3(r1, r2, r3); // forcement positifs car appel depuis optimizedBorder qui a fait un test |
---|
683 | |
---|
684 | ok1 = true; |
---|
685 | ok2 = true; |
---|
686 | ok3 = true; |
---|
687 | if (r1 > eps) { |
---|
688 | ok1 = SetRoot_Parallel_FNF(D, r1, eps, alpha, F); |
---|
689 | } |
---|
690 | if (r2 > eps && r2 != r1) { |
---|
691 | ok2 = SetRoot_Parallel_FNF(D, r2, eps, alpha, F); |
---|
692 | } |
---|
693 | if (r3 > eps && r3 != r2 && r3 != r1) { |
---|
694 | ok3 = SetRoot_Parallel_FNF(D, r3, eps, alpha, F); |
---|
695 | } |
---|
696 | } while (!(ok1 && ok2 && ok3)); |
---|
697 | } |
---|
698 | #endif // FAST && PARMERGE && !ARSP |
---|
699 | |
---|
700 | |
---|
701 | |
---|
702 | #if FAST |
---|
703 | // ------------------------------------------------------------------------------------------------------------------------ |
---|
704 | static void optimizedBorder_Rosenfeld_Dist(uint32 ** E, int i, int j, uint32 * T, uint32 ** D, int alpha, RegionStats ** F) |
---|
705 | // ------------------------------------------------------------------------------------------------------------------------ |
---|
706 | { |
---|
707 | uint32 a, b, c, x; |
---|
708 | |
---|
709 | x = E[i][j]; |
---|
710 | if (x) { |
---|
711 | b = E[i - 1][j]; |
---|
712 | if (b) { |
---|
713 | vuse2_Rosenfeld(b, x, T, D, alpha, F); // dist, local |
---|
714 | } |
---|
715 | else { |
---|
716 | c = E[i - 1][j + 1]; |
---|
717 | if (c) { |
---|
718 | a = E[i - 1][j - 1]; |
---|
719 | if (a) { |
---|
720 | vuse3_Rosenfeld(a, c, x, T, D, alpha, F); // dist, local |
---|
721 | } |
---|
722 | else { |
---|
723 | vuse2_Rosenfeld(c, x, T, D, alpha, F); // dist, local |
---|
724 | } |
---|
725 | } |
---|
726 | else { |
---|
727 | a = E[i - 1][j - 1]; |
---|
728 | if (a) { |
---|
729 | vuse2_Rosenfeld(a, x, T, D, alpha, F); // dist, local |
---|
730 | } |
---|
731 | } |
---|
732 | } |
---|
733 | } |
---|
734 | } |
---|
735 | |
---|
736 | // FAST |
---|
737 | |
---|
738 | // ---------------------------------------------------------------------------------------------------------------------------- |
---|
739 | static void optimizedBorderLeft_Rosenfeld_Dist(uint32 ** E, int i, int j, uint32 * T, uint32 ** D, int alpha, RegionStats ** F) |
---|
740 | // ---------------------------------------------------------------------------------------------------------------------------- |
---|
741 | { |
---|
742 | uint32 x = E[i][j]; |
---|
743 | if (x) { |
---|
744 | uint32 b = E[i - 1][j]; |
---|
745 | if (b) { |
---|
746 | vuse2_Rosenfeld(b, x, T, D, alpha, F); // dist, local |
---|
747 | } |
---|
748 | else { |
---|
749 | uint32 c = E[i - 1][j + 1]; |
---|
750 | if (c) { |
---|
751 | vuse2_Rosenfeld(c, x, T, D, alpha, F); // dist, local |
---|
752 | } |
---|
753 | } |
---|
754 | } |
---|
755 | } |
---|
756 | |
---|
757 | // FAST |
---|
758 | |
---|
759 | // ----------------------------------------------------------------------------------------------------------------------------- |
---|
760 | static void optimizedBorderRight_Rosenfeld_Dist(uint32 ** E, int i, int j, uint32 * T, uint32 ** D, int alpha, RegionStats ** F) |
---|
761 | // ----------------------------------------------------------------------------------------------------------------------------- |
---|
762 | { |
---|
763 | // copie de optimizedBorder_Rosenfeld |
---|
764 | // test d'existance de ex en local local |
---|
765 | |
---|
766 | uint32 b = E[i - 1][j]; |
---|
767 | uint32 x = E[i][j]; |
---|
768 | |
---|
769 | if (x) { |
---|
770 | if (b) { |
---|
771 | vuse2_Rosenfeld(b, x, T, D, alpha, F); // dist, local |
---|
772 | } |
---|
773 | else { |
---|
774 | uint32 a = E[i - 1][j - 1]; |
---|
775 | if (a) { |
---|
776 | vuse2_Rosenfeld(a, x, T, D, alpha, F); // dist, local |
---|
777 | } |
---|
778 | } |
---|
779 | } |
---|
780 | } |
---|
781 | |
---|
782 | // FAST |
---|
783 | |
---|
784 | // ------------------------------------------------------------------------------------------------------------------------------------------- |
---|
785 | static void borderMerging_Fast_Rosenfeld_Dist(uint8 ** X, int i, int width, uint32 ** E, uint32 * T, uint32 ** D, int alpha, RegionStats ** F) |
---|
786 | // ------------------------------------------------------------------------------------------------------------------------------------------- |
---|
787 | { |
---|
788 | // Prologue |
---|
789 | optimizedBorderLeft_Rosenfeld_Dist(E, i, 0, T, D, alpha, F); |
---|
790 | // Boucle principale |
---|
791 | for (int j = 1; j < width - 1; j++) { |
---|
792 | optimizedBorder_Rosenfeld_Dist(E, i, j, T, D, alpha, F); |
---|
793 | } |
---|
794 | // Epilogue |
---|
795 | optimizedBorderRight_Rosenfeld_Dist(E, i, width - 1, T, D, alpha, F); |
---|
796 | } |
---|
797 | #endif // FAST |
---|
798 | |
---|
799 | |
---|
800 | |
---|
801 | #if SLOW |
---|
802 | // ------------------------------------------------------------------------------------------------------------------------------------------- |
---|
803 | static void borderMerging_Slow_Rosenfeld_Dist(uint8 ** X, int i, int width, uint32 ** E, uint32 * T, uint32 ** D, int alpha, RegionStats ** F) |
---|
804 | // ------------------------------------------------------------------------------------------------------------------------------------------- |
---|
805 | { |
---|
806 | int j = 0; |
---|
807 | |
---|
808 | uint32 eps; |
---|
809 | uint32 e1, e2, e3, ex; |
---|
810 | uint32 r1, r2, r3, rx; |
---|
811 | |
---|
812 | // -------------- |
---|
813 | // -- prologue -- |
---|
814 | // -------------- |
---|
815 | MCA_VERBOSE3(printf("[%s] i = %d\n", __func__, i)); |
---|
816 | |
---|
817 | ex = E[i][j]; |
---|
818 | |
---|
819 | if (ex) { |
---|
820 | |
---|
821 | MCA_VERBOSE3(printf("[%s] j = %d\n", __func__, j)); |
---|
822 | |
---|
823 | e2 = E[i - 1][j]; |
---|
824 | e3 = E[i - 1][j + 1]; |
---|
825 | |
---|
826 | if (e2 || e3) { |
---|
827 | |
---|
828 | // test pour eviter acces distant |
---|
829 | r2 = e2 ? FindRoot_Dist(D, e2, alpha) : 0; |
---|
830 | r3 = e3 ? FindRoot_Dist(D, e3, alpha) : 0; |
---|
831 | |
---|
832 | rx = T[ex]; |
---|
833 | rx = FindRoot_Dist(D, rx, alpha); |
---|
834 | |
---|
835 | eps = ui32MinNonNul3(r2, r3, rx); |
---|
836 | |
---|
837 | MCA_VERBOSE3(printf("\n")); |
---|
838 | MCA_VERBOSE3(printf("e2 = %5d -> r2 = %5d\n", e2, r2)); |
---|
839 | MCA_VERBOSE3(printf("e3 = %5d -> r3 = %5d\n", e3, r3)); |
---|
840 | MCA_VERBOSE3(printf("ex = %5d -> rx = %5d\n", ex, rx)); |
---|
841 | MCA_VERBOSE3(printf("eps = %5d\n", eps)); |
---|
842 | |
---|
843 | // Quick-Union |
---|
844 | if (r2 > eps) { |
---|
845 | SetRoot_Rosenfeld(D, r2, eps, alpha, F); |
---|
846 | MCA_VERBOSE3(printf("D[%5d] <- %d\n", r2, eps)); |
---|
847 | } |
---|
848 | // Pour le cas où r2 == r3, il ne faut pas ajouter deux fois les features |
---|
849 | //if (r3 > 0) { |
---|
850 | // r3 = FindRoot_Dist(D, r3, alpha); |
---|
851 | //} |
---|
852 | //if (r3 > eps) { |
---|
853 | if (r3 > eps && r3 != r2) { |
---|
854 | SetRoot_Rosenfeld(D, r3, eps, alpha, F); |
---|
855 | MCA_VERBOSE3(printf("D[%5d] <- %d\n", r3, eps)); |
---|
856 | } |
---|
857 | //rx = FindRoot_Dist(D, rx, alpha); |
---|
858 | //if (rx > eps) { |
---|
859 | if (rx > eps && rx != r3 && rx != r2) { |
---|
860 | SetRoot_Rosenfeld(D, rx, eps, alpha, F); |
---|
861 | MCA_VERBOSE3(printf("D[%5d] <- %d\n", rx, eps)); |
---|
862 | } |
---|
863 | MCA_VERBOSE3(printf("---------------------------\n")); |
---|
864 | } |
---|
865 | } |
---|
866 | |
---|
867 | // ----------------------- |
---|
868 | // -- boucle principale -- |
---|
869 | // ----------------------- |
---|
870 | |
---|
871 | for (j = 0 + 1; j < width - 1; j++) { |
---|
872 | |
---|
873 | ex = E[i][j]; |
---|
874 | |
---|
875 | if (ex) { |
---|
876 | |
---|
877 | MCA_VERBOSE3(printf("[%s] j = %d\n", __func__, j)); |
---|
878 | |
---|
879 | e1 = E[i - 1][j - 1]; |
---|
880 | e2 = E[i - 1][j]; |
---|
881 | e3 = E[i - 1][j + 1]; |
---|
882 | |
---|
883 | if (e1 || e2 || e3) { |
---|
884 | // test pour eviter un acces distant |
---|
885 | r1 = e1 ? FindRoot_Dist(D, e1, alpha) : 0; |
---|
886 | r2 = e2 ? FindRoot_Dist(D, e2, alpha) : 0; |
---|
887 | r3 = e3 ? FindRoot_Dist(D, e3, alpha) : 0; |
---|
888 | |
---|
889 | rx = T[ex]; |
---|
890 | rx = FindRoot_Dist(D, rx, alpha); |
---|
891 | |
---|
892 | eps = ui32MinNonNul4(r1, r2, r3, rx); |
---|
893 | |
---|
894 | MCA_VERBOSE3(printf("\n")); |
---|
895 | MCA_VERBOSE3(printf("e1 = %5d -> r1 = %5d\n", e1, r1)); |
---|
896 | MCA_VERBOSE3(printf("e2 = %5d -> r2 = %5d\n", e2, r2)); |
---|
897 | MCA_VERBOSE3(printf("e3 = %5d -> r3 = %5d\n", e3, r3)); |
---|
898 | MCA_VERBOSE3(printf("ex = %5d -> rx = %5d\n", ex, rx)); |
---|
899 | MCA_VERBOSE3(printf("eps = %5d\n", eps)); |
---|
900 | |
---|
901 | |
---|
902 | // Quick-Union |
---|
903 | if (r1 > eps) { |
---|
904 | SetRoot_Rosenfeld(D, r1, eps, alpha, F); |
---|
905 | MCA_VERBOSE3(printf("D[%5d] <- %d\n", r1, eps)); |
---|
906 | } |
---|
907 | //if (r2 > 0) { |
---|
908 | // r2 = FindRoot_Dist(D, r2, alpha); |
---|
909 | //} |
---|
910 | if (r2 > eps && r2 != r1) { |
---|
911 | //if (r2 > eps) { |
---|
912 | SetRoot_Rosenfeld(D, r2, eps, alpha, F); |
---|
913 | MCA_VERBOSE3(printf("D[%5d] <- %d\n", r2, eps)); |
---|
914 | } |
---|
915 | //if (r3 > 0) { |
---|
916 | // r3 = FindRoot_Dist(D, r3, alpha); |
---|
917 | //} |
---|
918 | if (r3 > eps && r3 != r2 && r3 != r1) { |
---|
919 | //if (r3 > eps) { |
---|
920 | SetRoot_Rosenfeld(D, r3, eps, alpha, F); |
---|
921 | MCA_VERBOSE3(printf("D[%5d] <- %d\n", r3, eps)); |
---|
922 | } |
---|
923 | //rx = FindRoot_Dist(D, rx, alpha); |
---|
924 | if (rx > eps && rx != r3 && rx != r2 && rx != r1) { |
---|
925 | //if (rx > eps) { |
---|
926 | SetRoot_Rosenfeld(D, rx, eps, alpha, F); |
---|
927 | MCA_VERBOSE3(printf("D[%5d] <- %d\n", rx, eps)); |
---|
928 | } |
---|
929 | MCA_VERBOSE3(puts("---------------------------\n")); |
---|
930 | } |
---|
931 | } |
---|
932 | } |
---|
933 | |
---|
934 | // -------------- |
---|
935 | // -- epilogue -- |
---|
936 | // -------------- |
---|
937 | |
---|
938 | j = width - 1; |
---|
939 | ex = E[i][j]; |
---|
940 | |
---|
941 | if (ex) { |
---|
942 | |
---|
943 | MCA_VERBOSE3(printf("[%s] j = %d\n", __func__, j)); |
---|
944 | |
---|
945 | e1 = E[i - 1][j - 1]; |
---|
946 | e2 = E[i - 1][j]; |
---|
947 | |
---|
948 | if (e1 || e2) { |
---|
949 | |
---|
950 | // test pour eviter acces distant |
---|
951 | r1 = e1 ? FindRoot_Dist(D, e1, alpha) : 0; |
---|
952 | r2 = e2 ? FindRoot_Dist(D, e2, alpha) : 0; |
---|
953 | |
---|
954 | rx = T[ex]; |
---|
955 | rx = FindRoot_Dist(D, rx, alpha); |
---|
956 | |
---|
957 | eps = ui32MinNonNul3(r1, r2, rx); |
---|
958 | |
---|
959 | MCA_VERBOSE3(printf("\n")); |
---|
960 | MCA_VERBOSE3(printf("e1 = %5d -> r1 = %5d\n", e1, r1)); |
---|
961 | MCA_VERBOSE3(printf("e2 = %5d -> r2 = %5d\n", e2, r2)); |
---|
962 | MCA_VERBOSE3(printf("ex = %5d -> rx = %5d\n", ex, rx)); |
---|
963 | MCA_VERBOSE3(printf("eps = %5d\n", eps)); |
---|
964 | |
---|
965 | // Quick-Union |
---|
966 | if (r1 > eps) { |
---|
967 | SetRoot_Rosenfeld(D, r1, eps, alpha, F); |
---|
968 | MCA_VERBOSE3(printf("D[%5d] <- %d\n", r1, eps)); |
---|
969 | } |
---|
970 | //if (r2 > 0) { |
---|
971 | // r2 = FindRoot_Dist(D, r2, alpha); |
---|
972 | //} |
---|
973 | if (r2 > eps && r2 != r1) { |
---|
974 | //if (r2 > eps) { |
---|
975 | SetRoot_Rosenfeld(D, r2, eps, alpha, F); |
---|
976 | MCA_VERBOSE3(printf("D[%5d] <- %d\n", r2, eps)); |
---|
977 | } |
---|
978 | //rx = FindRoot_Dist(D, rx, alpha); |
---|
979 | if (rx > eps && rx != r2 && rx != r1) { |
---|
980 | //if (rx > eps) { |
---|
981 | SetRoot_Rosenfeld(D, rx, eps, alpha, F); |
---|
982 | MCA_VERBOSE3(printf("D[%5d] <- %d\n", rx, eps)); |
---|
983 | } |
---|
984 | MCA_VERBOSE3(printf("---------------------------\n")); |
---|
985 | } |
---|
986 | } |
---|
987 | } |
---|
988 | #endif // SLOW |
---|
989 | |
---|
990 | |
---|
991 | |
---|
992 | // -------------------------------------------------------------------------------------------------------------------------------------- |
---|
993 | static void borderMerging_Rosenfeld_Dist(uint8 ** X, int i, int width, uint32 ** E, uint32 * T, uint32 ** D, int alpha, RegionStats ** F) |
---|
994 | // -------------------------------------------------------------------------------------------------------------------------------------- |
---|
995 | { |
---|
996 | #if FAST |
---|
997 | borderMerging_Fast_Rosenfeld_Dist(X, i, width, E, T, D, alpha, F); |
---|
998 | #endif // FAST |
---|
999 | #if SLOW |
---|
1000 | borderMerging_Slow_Rosenfeld_Dist(X, i, width, E, T, D, alpha, F); |
---|
1001 | #endif // SLOW |
---|
1002 | } |
---|
1003 | |
---|
1004 | |
---|
1005 | // ---------------------------------------------------------------------------------------------------- |
---|
1006 | static uint32 line0Labeling_Rosenfeld(uint8 ** X, int i, int width, uint32 ** E, uint32 * T, uint32 ne) |
---|
1007 | // ---------------------------------------------------------------------------------------------------- |
---|
1008 | { |
---|
1009 | int j; |
---|
1010 | uint8 x; |
---|
1011 | uint32 e4; |
---|
1012 | uint32 r4; |
---|
1013 | |
---|
1014 | // prologue : j = 0 |
---|
1015 | x = X[i][0]; |
---|
1016 | if (x) { |
---|
1017 | E[i][0] = ++ne; |
---|
1018 | } |
---|
1019 | else { |
---|
1020 | E[i][0] = 0; |
---|
1021 | } |
---|
1022 | |
---|
1023 | // boucle et epilogue j = [1..width-1] |
---|
1024 | for (j = 1; j <= width - 1; j++) { |
---|
1025 | x = X[i][j]; |
---|
1026 | if (x) { |
---|
1027 | e4 = E[i][j - 1]; |
---|
1028 | |
---|
1029 | if (e4 == 0) { |
---|
1030 | E[i][j] = ++ne; |
---|
1031 | } |
---|
1032 | else { |
---|
1033 | E[i][j] = e4; |
---|
1034 | } |
---|
1035 | } |
---|
1036 | else { |
---|
1037 | E[i][j] = 0; |
---|
1038 | } |
---|
1039 | } |
---|
1040 | return ne; |
---|
1041 | } |
---|
1042 | |
---|
1043 | |
---|
1044 | #if SLOW |
---|
1045 | // -------------------------------------------------------------------------------------------------------- |
---|
1046 | static uint32 lineLabeling_Slow_Rosenfeld(uint8 ** X, int i, int width, uint32 ** E, uint32 * T, uint32 ne) |
---|
1047 | // -------------------------------------------------------------------------------------------------------- |
---|
1048 | { |
---|
1049 | // version lineLabeling_Rosenfeld_UF_QU_8C avec Quick-Union |
---|
1050 | |
---|
1051 | int j; |
---|
1052 | |
---|
1053 | uint8 x; |
---|
1054 | uint32 e; |
---|
1055 | uint32 e1, e2, e3, e4; |
---|
1056 | uint32 r1, r2, r3, r4; |
---|
1057 | |
---|
1058 | // -------------- |
---|
1059 | // -- prologue -- |
---|
1060 | // -------------- |
---|
1061 | |
---|
1062 | j = 0; |
---|
1063 | x = X[i][j]; |
---|
1064 | |
---|
1065 | if (x) { |
---|
1066 | |
---|
1067 | e2 = E[i - 1][j]; |
---|
1068 | e3 = E[i - 1][j + 1]; |
---|
1069 | |
---|
1070 | // nouvel element |
---|
1071 | if (e2 == 0 && e3 == 0) { |
---|
1072 | e = ++ne; |
---|
1073 | E[i][j] = e; |
---|
1074 | } |
---|
1075 | else { |
---|
1076 | // etiquettes identiques |
---|
1077 | if (e2 == e3) { |
---|
1078 | e = e2; |
---|
1079 | E[i][j] = e; |
---|
1080 | } |
---|
1081 | else { |
---|
1082 | // cas general |
---|
1083 | r2 = (e2 == 0) ? 0 : FindRoot(T, e2); |
---|
1084 | r3 = (e3 == 0) ? 0 : FindRoot(T, e3); |
---|
1085 | |
---|
1086 | e = ui32MinNonNul2(r2, r3); |
---|
1087 | |
---|
1088 | // Quick-Union |
---|
1089 | if (r2 > e) { |
---|
1090 | T[r2] = e; |
---|
1091 | } |
---|
1092 | if (r3 > e) { |
---|
1093 | T[r3] = e; |
---|
1094 | } |
---|
1095 | E[i][j] = e; |
---|
1096 | } |
---|
1097 | } |
---|
1098 | } |
---|
1099 | else { |
---|
1100 | E[i][j] = 0; |
---|
1101 | } // x |
---|
1102 | |
---|
1103 | // ----------------------- |
---|
1104 | // -- boucle principale -- |
---|
1105 | // ----------------------- |
---|
1106 | |
---|
1107 | for (j = 0 + 1; j < width - 1; j++) { |
---|
1108 | |
---|
1109 | x = X[i][j]; |
---|
1110 | |
---|
1111 | if (x) { |
---|
1112 | e1 = E[i - 1][j - 1]; |
---|
1113 | e2 = E[i - 1][j]; |
---|
1114 | e3 = E[i - 1][j + 1]; |
---|
1115 | e4 = E[i][j - 1]; |
---|
1116 | |
---|
1117 | // nouvel element |
---|
1118 | if (e1 == 0 && e2 == 0 && e3 == 0 && e4 == 0) { |
---|
1119 | e = ++ne; |
---|
1120 | E[i][j] = e; |
---|
1121 | } |
---|
1122 | else { |
---|
1123 | // etiquettes identiques |
---|
1124 | if (e1 == e2 && e1 == e3 && e1 == e4) { |
---|
1125 | e = e1; |
---|
1126 | E[i][j] = e; |
---|
1127 | } |
---|
1128 | else { |
---|
1129 | // cas general |
---|
1130 | r1 = (e1 == 0) ? 0 : FindRoot(T, e1); |
---|
1131 | r2 = (e2 == 0) ? 0 : FindRoot(T, e2); |
---|
1132 | r3 = (e3 == 0) ? 0 : FindRoot(T, e3); |
---|
1133 | r4 = (e4 == 0) ? 0 : FindRoot(T, e4); |
---|
1134 | |
---|
1135 | e = ui32MinNonNul4(r1, r2, r3, r4); |
---|
1136 | |
---|
1137 | // Quick-Union |
---|
1138 | if (r1 > e) { |
---|
1139 | T[r1] = e; |
---|
1140 | } |
---|
1141 | if (r2 > e) { |
---|
1142 | T[r2] = e; |
---|
1143 | } |
---|
1144 | if (r3 > e) { |
---|
1145 | T[r3] = e; |
---|
1146 | } |
---|
1147 | if (r4 > e) { |
---|
1148 | T[r4] = e; |
---|
1149 | } |
---|
1150 | E[i][j] = e; |
---|
1151 | } |
---|
1152 | } |
---|
1153 | } |
---|
1154 | else { |
---|
1155 | E[i][j] = 0; |
---|
1156 | } // x |
---|
1157 | } // j |
---|
1158 | |
---|
1159 | // -------------- |
---|
1160 | // -- epilogue -- |
---|
1161 | // -------------- |
---|
1162 | j = width - 1; |
---|
1163 | x = X[i][j]; |
---|
1164 | |
---|
1165 | if (x) { |
---|
1166 | e1 = E[i - 1][j - 1]; |
---|
1167 | e2 = E[i - 1][j]; |
---|
1168 | e4 = E[i][j - 1]; |
---|
1169 | |
---|
1170 | // nouvel element |
---|
1171 | if (e1 == 0 && e2 == 0 && e4 == 0) { |
---|
1172 | e = ++ne; |
---|
1173 | E[i][j] = e; |
---|
1174 | } |
---|
1175 | else { |
---|
1176 | // etiquettes identiques |
---|
1177 | if (e1 == e2 && e1 == e4) { |
---|
1178 | e = e1; |
---|
1179 | E[i][j] = e; |
---|
1180 | } |
---|
1181 | else { |
---|
1182 | // cas general |
---|
1183 | r1 = (e1 == 0) ? 0 : FindRoot(T, e1); |
---|
1184 | r2 = (e2 == 0) ? 0 : FindRoot(T, e2); |
---|
1185 | r4 = (e4 == 0) ? 0 : FindRoot(T, e4); |
---|
1186 | |
---|
1187 | e = ui32MinNonNul3(r1, r2, r4); |
---|
1188 | |
---|
1189 | // Quick-Union |
---|
1190 | if (r1 > e) { |
---|
1191 | T[r1] = e; |
---|
1192 | } |
---|
1193 | if (r2 > e) { |
---|
1194 | T[r2] = e; |
---|
1195 | } |
---|
1196 | if (r4 > e) { |
---|
1197 | T[r4] = e; |
---|
1198 | } |
---|
1199 | E[i][j] = e; |
---|
1200 | } |
---|
1201 | } |
---|
1202 | } |
---|
1203 | else { |
---|
1204 | E[i][j] = 0; |
---|
1205 | } // x |
---|
1206 | |
---|
1207 | return ne; |
---|
1208 | } |
---|
1209 | #endif // SLOW |
---|
1210 | |
---|
1211 | |
---|
1212 | #if FAST |
---|
1213 | // --------------------------------------------------------------------------------------------- |
---|
1214 | static uint32 optimizedAccessLeft_DT_Rosenfeld(uint32 ** E, int i, int j, uint32 * T, uint32 ne) |
---|
1215 | // --------------------------------------------------------------------------------------------- |
---|
1216 | { |
---|
1217 | // Decision Tree 8-connexe avec Quick-Union |
---|
1218 | uint32 b, c, e; |
---|
1219 | |
---|
1220 | b = E[i - 1][j]; |
---|
1221 | if (b) { |
---|
1222 | e = use1_QU_Rosenfeld(b, T); |
---|
1223 | } |
---|
1224 | else { |
---|
1225 | c = E[i - 1][j + 1]; |
---|
1226 | if (c) { |
---|
1227 | e = use1_QU_Rosenfeld(c, T); |
---|
1228 | } |
---|
1229 | else { |
---|
1230 | e = ++ne; |
---|
1231 | } |
---|
1232 | } |
---|
1233 | E[i][j] = e; |
---|
1234 | return ne; |
---|
1235 | } |
---|
1236 | |
---|
1237 | // FAST |
---|
1238 | |
---|
1239 | // ---------------------------------------------------------------------------------------------- |
---|
1240 | static uint32 optimizedAccessRight_DT_Rosenfeld(uint32 ** E, int i, int j, uint32 * T, uint32 ne) |
---|
1241 | // ---------------------------------------------------------------------------------------------- |
---|
1242 | { |
---|
1243 | // Decision Tree 8-connexe avec Quick-Union |
---|
1244 | uint32 a, b, d, e; |
---|
1245 | |
---|
1246 | b = E[i - 1][j]; |
---|
1247 | if (b) { |
---|
1248 | e = use1_QU_Rosenfeld(b, T); |
---|
1249 | } |
---|
1250 | else { |
---|
1251 | a = E[i - 1][j - 1]; |
---|
1252 | if (a) { |
---|
1253 | e = use1_QU_Rosenfeld(a, T); |
---|
1254 | } |
---|
1255 | else { |
---|
1256 | d = E[i][j - 1]; |
---|
1257 | if (d) { |
---|
1258 | e = use1_QU_Rosenfeld(d, T); |
---|
1259 | } |
---|
1260 | else { |
---|
1261 | e = ++ne; |
---|
1262 | } |
---|
1263 | } |
---|
1264 | } |
---|
1265 | E[i][j] = e; |
---|
1266 | return ne; |
---|
1267 | } |
---|
1268 | |
---|
1269 | // FAST |
---|
1270 | |
---|
1271 | // ----------------------------------------------------------------------------------------- |
---|
1272 | static uint32 optimizedAccess_DT_Rosenfeld(uint32 ** E, int i, int j, uint32 * T, uint32 ne) |
---|
1273 | // ----------------------------------------------------------------------------------------- |
---|
1274 | { |
---|
1275 | // Decision Tree 8-connexe avec Quick-Union |
---|
1276 | uint32 a, b, c, d, e; |
---|
1277 | |
---|
1278 | b = E[i - 1][j]; |
---|
1279 | if (b) { |
---|
1280 | e = use1_QU_Rosenfeld(b, T); |
---|
1281 | } |
---|
1282 | else { |
---|
1283 | c = E[i - 1][j + 1]; |
---|
1284 | if (c) { |
---|
1285 | a = E[i - 1][j - 1]; |
---|
1286 | if (a) { |
---|
1287 | e = use2_QU_Rosenfeld(a, c, T); |
---|
1288 | } |
---|
1289 | else { |
---|
1290 | d = E[i][j - 1]; |
---|
1291 | if (d) { |
---|
1292 | e = use2_QU_Rosenfeld(c, d, T); |
---|
1293 | } |
---|
1294 | else { |
---|
1295 | e = use1_QU_Rosenfeld(c, T); |
---|
1296 | } |
---|
1297 | } |
---|
1298 | } |
---|
1299 | else { |
---|
1300 | a = E[i - 1][j - 1]; |
---|
1301 | if (a) { |
---|
1302 | e = use1_QU_Rosenfeld(a, T); |
---|
1303 | } |
---|
1304 | else { |
---|
1305 | d = E[i][j - 1]; |
---|
1306 | if (d) { |
---|
1307 | e = use1_QU_Rosenfeld(d, T); |
---|
1308 | } |
---|
1309 | else { |
---|
1310 | e = ++ne; |
---|
1311 | } |
---|
1312 | } |
---|
1313 | } |
---|
1314 | } |
---|
1315 | E[i][j] = e; |
---|
1316 | return ne; |
---|
1317 | } |
---|
1318 | |
---|
1319 | // FAST |
---|
1320 | |
---|
1321 | // -------------------------------------------------------------------------------------------------------- |
---|
1322 | static uint32 lineLabeling_Fast_Rosenfeld(uint8 ** X, int i, int width, uint32 ** E, uint32 * T, uint32 ne) |
---|
1323 | // -------------------------------------------------------------------------------------------------------- |
---|
1324 | { |
---|
1325 | uint8 x; |
---|
1326 | // avec DT et QU |
---|
1327 | // Left Border |
---|
1328 | x = X[i][0]; |
---|
1329 | if (x) { |
---|
1330 | ne = optimizedAccessLeft_DT_Rosenfeld(E, i, 0, T, ne); |
---|
1331 | } |
---|
1332 | else { |
---|
1333 | E[i][0] = 0; |
---|
1334 | } |
---|
1335 | // Middle |
---|
1336 | for (int j = 1; j < width - 1; j++) { |
---|
1337 | uint8 x = X[i][j]; |
---|
1338 | if (x) { |
---|
1339 | ne = optimizedAccess_DT_Rosenfeld(E, i, j, T, ne); |
---|
1340 | } |
---|
1341 | else { |
---|
1342 | E[i][j] = 0; |
---|
1343 | } |
---|
1344 | } |
---|
1345 | // Right Border |
---|
1346 | x = X[i][width - 1]; |
---|
1347 | if (x) { |
---|
1348 | ne = optimizedAccessRight_DT_Rosenfeld(E, i, width - 1, T, ne); |
---|
1349 | } |
---|
1350 | else { |
---|
1351 | E[i][width - 1] = 0; |
---|
1352 | } |
---|
1353 | return ne; |
---|
1354 | } |
---|
1355 | #endif // FAST |
---|
1356 | |
---|
1357 | |
---|
1358 | // --------------------------------------------------------------------------------------------------- |
---|
1359 | static uint32 lineLabeling_Rosenfeld(uint8 ** X, int i, int width, uint32 ** E, uint32 * T, uint32 ne) |
---|
1360 | // --------------------------------------------------------------------------------------------------- |
---|
1361 | { |
---|
1362 | #if SLOW |
---|
1363 | return lineLabeling_Slow_Rosenfeld(X, i, width, E, T, ne); |
---|
1364 | #elif FAST |
---|
1365 | return lineLabeling_Fast_Rosenfeld(X, i, width, E, T, ne); |
---|
1366 | #endif |
---|
1367 | } |
---|
1368 | |
---|
1369 | |
---|
1370 | // ----------------------------------------------------------------------- |
---|
1371 | static uint32 countTable_Range_Rosenfeld(uint32 * T, uint32 e0, uint32 e1) |
---|
1372 | // ----------------------------------------------------------------------- |
---|
1373 | { |
---|
1374 | uint32 e; |
---|
1375 | uint32 nr = 0; // nombre de racines = de composantes connexes |
---|
1376 | |
---|
1377 | for (e = e0; e <= e1; e++) { |
---|
1378 | if (e == T[e]) { |
---|
1379 | nr += 1; |
---|
1380 | } |
---|
1381 | } |
---|
1382 | return nr; |
---|
1383 | } |
---|
1384 | |
---|
1385 | |
---|
1386 | // ------------------------------------------------------------------------------------------ |
---|
1387 | static void solveTable_Range_Rosenfeld(uint32 * T, uint32 e0, uint32 e1, RegionStats * Stats) |
---|
1388 | // ------------------------------------------------------------------------------------------ |
---|
1389 | { |
---|
1390 | uint32 e, r; |
---|
1391 | |
---|
1392 | for (e = e0; e <= e1; e++) { |
---|
1393 | r = T[T[e]]; |
---|
1394 | assert(r != 0); |
---|
1395 | if (r < e) { |
---|
1396 | T[e] = r; // racine de la classe d'equivalence |
---|
1397 | #if FEATURES |
---|
1398 | RegionStats_Accumulate_Stats1_From_Index(Stats, r, e); |
---|
1399 | #endif |
---|
1400 | } |
---|
1401 | } |
---|
1402 | } |
---|
1403 | |
---|
1404 | |
---|
1405 | // -------------------------------------------- |
---|
1406 | static void MCA_Label_Rosenfeld_PAR1(MCA * mca) |
---|
1407 | // -------------------------------------------- |
---|
1408 | { |
---|
1409 | if (mca->p == 0) { |
---|
1410 | MCA_VERBOSE2(printf("*** %s ***\n", __func__)); |
---|
1411 | } |
---|
1412 | |
---|
1413 | |
---|
1414 | int i0 = mca->i0; |
---|
1415 | int i1 = mca->i1; |
---|
1416 | int width = mca->width; |
---|
1417 | |
---|
1418 | uint32 e0 = mca->e0; |
---|
1419 | uint32 e1 = mca->e1; |
---|
1420 | uint32 ne_prev = mca->ne_prev; |
---|
1421 | uint32 ne = e0 - 1; |
---|
1422 | uint32 nr = 0; |
---|
1423 | |
---|
1424 | // local memory zones |
---|
1425 | uint8 ** X = mca->X; |
---|
1426 | uint32 ** E = mca->E; |
---|
1427 | uint32 * T = mca->T; |
---|
1428 | RegionStats * stats = mca->stats; |
---|
1429 | |
---|
1430 | CLOCK_THREAD_START_STEP(mca->p, 0); |
---|
1431 | |
---|
1432 | set_ui32vector_j(T, e0, ne_prev); |
---|
1433 | #if FEATURES |
---|
1434 | zero_RegionStatsVector(stats, e0, ne_prev); |
---|
1435 | #endif |
---|
1436 | |
---|
1437 | if (mca->p == 0) { |
---|
1438 | MCA_VERBOSE3(display_ui8matrix_positive(X, i0, i1, 0, width - 1, 5, "Xp"); printf("\n")); |
---|
1439 | } |
---|
1440 | |
---|
1441 | // ---------------------------- // |
---|
1442 | // -- Etiquetage d'une bande -- // |
---|
1443 | // ---------------------------- // |
---|
1444 | |
---|
1445 | ne = line0Labeling_Rosenfeld(X, i0, width, E, T, ne); |
---|
1446 | #if FEATURES |
---|
1447 | lineFeaturesComputation(E, i0, width, stats); |
---|
1448 | #endif |
---|
1449 | |
---|
1450 | for (int i = i0 + 1; i <= i1; i++) { |
---|
1451 | ne = lineLabeling_Rosenfeld(X, i, width, E, T, ne); // Slow or Fast |
---|
1452 | #if FEATURES |
---|
1453 | lineFeaturesComputation(E, i, width, stats); |
---|
1454 | #endif |
---|
1455 | } |
---|
1456 | mca->ne = ne; //plus grande etiquette de l'intervalle [e0..e1] |
---|
1457 | |
---|
1458 | if (mca->p == 0) { |
---|
1459 | MCA_VERBOSE3(printf("ne = %d\n", ne)); |
---|
1460 | MCA_VERBOSE3(display_ui32matrix_positive(E, i0, i1, 0, width - 1, 5, "Ep"); printf("\n")); |
---|
1461 | MCA_VERBOSE3(display_ui32vector_number(T, e0, ne, "%5d", "Tp_avant")); |
---|
1462 | } |
---|
1463 | |
---|
1464 | // ------------------------------------------------------ // |
---|
1465 | // -- Fermeture transitive sans pack de chaque table T -- // |
---|
1466 | // ------------------------------------------------------ // |
---|
1467 | |
---|
1468 | solveTable_Range_Rosenfeld(T, e0, ne, stats); |
---|
1469 | |
---|
1470 | if (mca->p == 0) { |
---|
1471 | MCA_VERBOSE3(nr = countTable_Range_Rosenfeld(T, e0, ne); |
---|
1472 | printf("p = %d : e = [%d..%d] -> ne = %d -> nr = %d\n", mca->p, e0, ne, (ne - e0 + 1), nr)); |
---|
1473 | MCA_VERBOSE3(display_ui32vector_number(T, e0, ne, "%5d", "Tp_apres")); |
---|
1474 | } |
---|
1475 | CLOCK_THREAD_END_STEP(mca->p, 0); |
---|
1476 | } |
---|
1477 | |
---|
1478 | |
---|
1479 | |
---|
1480 | #if PARMERGE |
---|
1481 | // ----------------------------------------------------- |
---|
1482 | static void MCA_Label_Rosenfeld_PAR2(MCA * mca) |
---|
1483 | // ----------------------------------------------------- |
---|
1484 | { |
---|
1485 | int p = mca->p; |
---|
1486 | int nb_level = mca->nb_level; |
---|
1487 | |
---|
1488 | if (mca->p == 0) { |
---|
1489 | MCA_VERBOSE2(printf("*** %s ***\n", __func__)); |
---|
1490 | } |
---|
1491 | |
---|
1492 | // ------------------------------ |
---|
1493 | // -- parallel border merging -- |
---|
1494 | // ------------------------------ |
---|
1495 | |
---|
1496 | // local variables |
---|
1497 | int i = mca->i0; |
---|
1498 | int width = mca->width; |
---|
1499 | int alpha = mca->alpha; |
---|
1500 | uint32 e0 = mca->e0; |
---|
1501 | uint32 e1 = mca->ne; |
---|
1502 | |
---|
1503 | // local memory zones |
---|
1504 | uint8 ** X = mca->X; |
---|
1505 | uint32 ** E = mca->E; |
---|
1506 | uint32 * T = mca->T; |
---|
1507 | uint32 ** D = mca->D; |
---|
1508 | RegionStats ** F = mca->F; |
---|
1509 | |
---|
1510 | CLOCK_THREAD_START_STEP(p, 1); |
---|
1511 | if (p != 0) { // thread 0 never has any merge to do |
---|
1512 | borderMerging_Rosenfeld_Dist(X, i, width, E, T, D, alpha, F); // (i) et (i-1) |
---|
1513 | } |
---|
1514 | pthread_barrier_wait(&main_barrier); |
---|
1515 | CLOCK_THREAD_END_STEP(p, 1); |
---|
1516 | |
---|
1517 | |
---|
1518 | // --------------------------------- |
---|
1519 | // -- parallel transitive closure -- |
---|
1520 | // --------------------------------- |
---|
1521 | // identique a la version sans Features |
---|
1522 | |
---|
1523 | CLOCK_THREAD_START_STEP(p, 2); |
---|
1524 | for (uint32 e = e0; e <= e1; e++) { |
---|
1525 | uint32 r = T[e]; // acces local |
---|
1526 | if (r < e) { |
---|
1527 | r = FindRoot_Dist(D, e, alpha); // acces distant |
---|
1528 | T[e] = r; |
---|
1529 | } |
---|
1530 | MCA_VERBOSE3(printf("p%d : T[%d] <- %d\n", p, e, r)); |
---|
1531 | } |
---|
1532 | CLOCK_THREAD_END_STEP(p, 2); |
---|
1533 | |
---|
1534 | // To avoid uninitialized accesses |
---|
1535 | CLOCK_THREAD_START_STEP(p, 3); |
---|
1536 | CLOCK_THREAD_END_STEP(p, 3); |
---|
1537 | } |
---|
1538 | #endif // PARMERGE |
---|
1539 | |
---|
1540 | |
---|
1541 | #if !PARMERGE |
---|
1542 | // -------------------------------------------- |
---|
1543 | static void MCA_Label_Rosenfeld_PYR2(MCA * mca) |
---|
1544 | // -------------------------------------------- |
---|
1545 | { |
---|
1546 | // input |
---|
1547 | int p = mca->p; |
---|
1548 | int nb_level = mca->nb_level; |
---|
1549 | |
---|
1550 | if (mca->p == 0) { |
---|
1551 | MCA_VERBOSE2(printf("*** %s ***\n", __func__)); |
---|
1552 | } |
---|
1553 | |
---|
1554 | // ------------------------------ |
---|
1555 | // -- pyramidal border merging -- |
---|
1556 | // ------------------------------ |
---|
1557 | |
---|
1558 | // local variables |
---|
1559 | int i = mca->i0; |
---|
1560 | int width = mca->width; |
---|
1561 | int alpha = mca->alpha; |
---|
1562 | uint32 e0 = mca->e0; |
---|
1563 | uint32 e1 = mca->ne; |
---|
1564 | |
---|
1565 | // local memory zones |
---|
1566 | uint8 ** X = mca->X; |
---|
1567 | uint32 ** E = mca->E; |
---|
1568 | uint32 * T = mca->T; |
---|
1569 | uint32 ** D = mca->D; |
---|
1570 | RegionStats ** F = mca->F; |
---|
1571 | |
---|
1572 | CLOCK_THREAD_START_STEP(p, 1); |
---|
1573 | #if PYR_BARRIERS |
---|
1574 | // Version optimisée qui fait faire un break aux processeurs qui n'ont plus |
---|
1575 | // Ã faire de merge. |
---|
1576 | // Implique de pré-calculer le nombre de threads à chaque barriÚre |
---|
1577 | if (p != 0) { // thread 0 never has any merge to do |
---|
1578 | int been_active = 0; |
---|
1579 | for (int level = 0; level < nb_level; level++) { |
---|
1580 | if ((p + (1 << level)) % (1 << (level + 1)) == 0) { |
---|
1581 | borderMerging_Rosenfeld_Dist(X, i, width, E, T, D, alpha, F); // (i) et (i-1) |
---|
1582 | been_active = 1; |
---|
1583 | } |
---|
1584 | else if (been_active) { |
---|
1585 | break; |
---|
1586 | } |
---|
1587 | pthread_barrier_wait(&mca->barriers[level]); |
---|
1588 | } |
---|
1589 | } |
---|
1590 | pthread_barrier_wait(&main_barrier); |
---|
1591 | #else |
---|
1592 | for (int level = 1; level <= nb_level; level++) { |
---|
1593 | if ((p + (1 << (level - 1))) % (1 << level) == 0) { |
---|
1594 | // thread actif |
---|
1595 | borderMerging_Rosenfeld_Dist(X, i, width, E, T, D, alpha, F); // (i) et (i-1) |
---|
1596 | } |
---|
1597 | pthread_barrier_wait(&main_barrier); |
---|
1598 | } |
---|
1599 | #endif |
---|
1600 | CLOCK_THREAD_END_STEP(p, 1); |
---|
1601 | |
---|
1602 | |
---|
1603 | // --------------------------------- |
---|
1604 | // -- parallel transitive closure -- |
---|
1605 | // --------------------------------- |
---|
1606 | |
---|
1607 | CLOCK_THREAD_START_STEP(p, 2); |
---|
1608 | for (uint32 e = e0; e <= e1; e++) { |
---|
1609 | uint32 r = T[e]; // acces local |
---|
1610 | if (r < e) { |
---|
1611 | r = FindRoot_Dist(D, e, alpha); // acces distant |
---|
1612 | T[e] = r; |
---|
1613 | } |
---|
1614 | MCA_VERBOSE3(printf("p%d : T[%d] <- %d\n", p, e, r)); |
---|
1615 | } |
---|
1616 | CLOCK_THREAD_END_STEP(p, 2); |
---|
1617 | } |
---|
1618 | #endif // !FEATURES |
---|
1619 | |
---|
1620 | |
---|
1621 | // ------------------------------------- |
---|
1622 | void MCA_Label_Rosenfeld_PAR3(MCA * mca) |
---|
1623 | // ------------------------------------- |
---|
1624 | { |
---|
1625 | // input |
---|
1626 | if (mca->p == 0) { |
---|
1627 | MCA_VERBOSE2(printf("*** %s ***\n", __func__)); |
---|
1628 | } |
---|
1629 | |
---|
1630 | int i0 = mca->i0; |
---|
1631 | int i1 = mca->i1; |
---|
1632 | int j0 = 0; |
---|
1633 | int j1 = mca->width - 1; |
---|
1634 | |
---|
1635 | uint32 ** E = mca->E; |
---|
1636 | uint32 * T = mca->T; |
---|
1637 | |
---|
1638 | CLOCK_THREAD_START_STEP(mca->p, 3); |
---|
1639 | for (int i = i0; i <= i1; i++) { |
---|
1640 | for (int j = j0; j <= j1; j++) { |
---|
1641 | uint32 e = E[i][j]; |
---|
1642 | if (e != 0) { |
---|
1643 | E[i][j] = T[e]; |
---|
1644 | } |
---|
1645 | } |
---|
1646 | } |
---|
1647 | CLOCK_THREAD_END_STEP(mca->p, 3); |
---|
1648 | } |
---|
1649 | |
---|
1650 | |
---|
1651 | |
---|
1652 | // ====================================================================== |
---|
1653 | #if TARGET_OS == GIETVM |
---|
1654 | __attribute__((constructor)) void * MCA_Label_Rosenfeld(void * arg) |
---|
1655 | #else |
---|
1656 | void * MCA_Label_Rosenfeld(void * arg) |
---|
1657 | #endif |
---|
1658 | // ====================================================================== |
---|
1659 | { |
---|
1660 | MCA * mca = (MCA *) arg; |
---|
1661 | #if TARGET_OS == GIETVM |
---|
1662 | unsigned int x, y, lpid; |
---|
1663 | giet_proc_xyp(&x, &y, &lpid); |
---|
1664 | // Mettre à jour mca->p en fonction de x, y, lpid |
---|
1665 | // pour que les allocations faites par le main soient locales, |
---|
1666 | // i.e. |
---|
1667 | mca->p = (x * Y_SIZE + y) * NB_PROCS_MAX + lpid; |
---|
1668 | // We have : |
---|
1669 | // mca->p = 4 pour (x = 0, y = 1, lpid = 0) |
---|
1670 | // mca->p = 5 pour (x = 0, y = 1, lpid = 1) |
---|
1671 | MCA_VERBOSE3(printf("mca->p = %d pour (x = %d, y = %d, lpid = %d)\n", mca->p, x, y, lpid)); |
---|
1672 | #endif |
---|
1673 | |
---|
1674 | CLOCK_THREAD_START(mca->p); |
---|
1675 | |
---|
1676 | int num_runs = mca->nr; |
---|
1677 | |
---|
1678 | // We always perform one more run than the num_runs |
---|
1679 | // value, so as to know "ne", i.e. the number of |
---|
1680 | // elements to reset in the T and F tables (labels and stats) |
---|
1681 | // After this first extra run, clock times are not accumulated |
---|
1682 | // and thus are lost. |
---|
1683 | // Note: the CLOCK_THREAD_START will still include this first run, |
---|
1684 | // and in case of multiple runs, only averaged times should be |
---|
1685 | // considered. |
---|
1686 | for (int run = 0; run < num_runs + 1; run++) { |
---|
1687 | |
---|
1688 | CLOCK_THREAD_COMPUTE_START(mca->p); |
---|
1689 | |
---|
1690 | MCA_Scatter_ImageX(mca); |
---|
1691 | pthread_barrier_wait(&main_barrier); |
---|
1692 | |
---|
1693 | MCA_Label_Rosenfeld_PAR1(mca); |
---|
1694 | pthread_barrier_wait(&main_barrier); |
---|
1695 | |
---|
1696 | #if PARMERGE |
---|
1697 | MCA_Label_Rosenfeld_PAR2(mca); |
---|
1698 | #else |
---|
1699 | MCA_Label_Rosenfeld_PYR2(mca); |
---|
1700 | #endif |
---|
1701 | pthread_barrier_wait(&main_barrier); |
---|
1702 | |
---|
1703 | MCA_Label_Rosenfeld_PAR3(mca); |
---|
1704 | pthread_barrier_wait(&main_barrier); |
---|
1705 | |
---|
1706 | MCA_Gather_ImageL(mca); |
---|
1707 | pthread_barrier_wait(&main_barrier); |
---|
1708 | |
---|
1709 | CLOCK_THREAD_COMPUTE_END(mca->p); |
---|
1710 | |
---|
1711 | if (run == 0) { |
---|
1712 | // Mise à jour du ne_prev par chaque thread |
---|
1713 | mca->ne_prev = mca->ne; |
---|
1714 | mca->ne = 0; |
---|
1715 | } |
---|
1716 | else { |
---|
1717 | // Accumulation du temps COMPUTE et de toutes les STEP |
---|
1718 | if (mca->p == 0) { |
---|
1719 | CLOCK_ACCUMULATE; |
---|
1720 | } |
---|
1721 | assert(mca->ne == mca->ne_prev); |
---|
1722 | // Reinitialisation de "ne" s'il ne s'agit pas du dernier run |
---|
1723 | if (run != num_runs) { |
---|
1724 | mca->ne = 0; |
---|
1725 | } |
---|
1726 | } |
---|
1727 | pthread_barrier_wait(&main_barrier); |
---|
1728 | } |
---|
1729 | |
---|
1730 | |
---|
1731 | #if FEATURES |
---|
1732 | if (display_features) { |
---|
1733 | if (mca->p == 0) { |
---|
1734 | int i = 1; |
---|
1735 | MCA_VERBOSE1(printf("[STATS]\n")); |
---|
1736 | for (int p = 0; p < mca->np; p++) { |
---|
1737 | MCA * mca_par = mca->mca->mcas[p]; |
---|
1738 | uint32 e0 = mca_par->e0; |
---|
1739 | uint32 ne = mca_par->ne - mca_par->e0; // number of elements |
---|
1740 | uint32 * T = mca_par->T; |
---|
1741 | RegionStats * stats = mca_par->stats; |
---|
1742 | MCA_VERBOSE1(RegionStats_DisplayStats_Sparse(T, e0, e0 + ne, stats, NULL, &i)); |
---|
1743 | } |
---|
1744 | MCA_VERBOSE1(printf("[/STATS]\n")); |
---|
1745 | } |
---|
1746 | } |
---|
1747 | #endif |
---|
1748 | |
---|
1749 | CLOCK_THREAD_END(mca->p); |
---|
1750 | |
---|
1751 | #if TARGET_OS == GIETVM |
---|
1752 | if (mca->p != 0) { |
---|
1753 | exit(0); |
---|
1754 | } |
---|
1755 | #endif |
---|
1756 | |
---|
1757 | return NULL; |
---|
1758 | } |
---|
1759 | |
---|
1760 | |
---|
1761 | // Local Variables: |
---|
1762 | // tab-width: 4 |
---|
1763 | // c-basic-offset: 4 |
---|
1764 | // c-file-offsets:((innamespace . 0)(inline-open . 0)) |
---|
1765 | // indent-tabs-mode: nil |
---|
1766 | // End: |
---|
1767 | |
---|
1768 | // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=4:softtabstop=4 |
---|
1769 | |
---|