source: soft/giet_vm/applications/rosenfeld/src-par/mca.c

Last change on this file was 826, checked in by meunier, 9 years ago
  • Mise à jour NR2 et Rosenfeld
File size: 15.8 KB
Line 
1/* ------------- */
2/* --- mca.c --- */
3/* ------------- */
4
5/*
6 * Copyright (c) 2016 Lionel Lacassagne, LIP6, UPMC, CNRS
7 * Init : 2016/03/03
8 * modif : 2016/03/07
9 */
10
11#include <stdio.h>
12#include <stdlib.h>
13#include <string.h>
14#include <math.h>
15#include <malloc.h>
16
17#include "nrc_os_config.h"
18#include "config.h"
19#include "nrc.h"
20
21#if TARGET_OS == GIETVM
22 #include <giet_config.h>
23#endif
24
25#include "util.h"
26#include "ecc_common.h"
27#include "ecc_features.h"
28#include "mca_matrix_dist.h"
29
30#include "palette.h"
31#include "bmpNR.h"
32#include "str_ext.h"
33
34
35// -- local --
36#include "mca.h"
37
38
39// -----------------------
40void MCA_Error(char * msg)
41// -----------------------
42{
43 printf("MCA ERROR: %s\n", msg);
44 exit(1);
45}
46
47
48// -------------------------------
49MCA * MCA_pConstructor_Empty(void)
50// -------------------------------
51{
52 MCA * mca;
53 mca = (MCA *) malloc(sizeof(MCA));
54
55 if (mca == NULL) {
56 MCA_Error("allocation failed in MCA_pConstructor_Empty");
57 }
58 return mca;
59}
60
61
62// ---------------------------------------
63void MCA_Set_ImageX(MCA * mca, uint8 ** X)
64// ---------------------------------------
65{
66 mca->X = X;
67}
68
69
70// --------------------------------------
71void MCA_Set_ImageL(MCA * mca, uint32 ** E)
72// --------------------------------------
73{
74 mca->E = E;
75}
76
77
78// ------------------------------------
79void MCA_Set_Width(MCA * mca, int width)
80// ------------------------------------
81{
82 mca->width = width;
83
84 mca->j0 = 0;
85 mca->j1 = width - 1;
86}
87
88
89// --------------------------------------
90void MCA_Set_Height(MCA * mca, int height)
91// --------------------------------------
92{
93 mca->height = height;
94
95 mca->i0 = 0;
96 mca->i1 = height - 1;
97}
98
99
100// ------------------------------------------------
101void MCA_Set_Size(MCA * mca, int width, int height)
102// ------------------------------------------------
103{
104 MCA_Set_Width(mca, width);
105 MCA_Set_Height(mca, height);
106}
107
108
109// -----------------------------------------------------
110void MCA_Set_Dimension(MCA * mca, int width, int height)
111// -----------------------------------------------------
112{
113 MCA_Set_Width(mca, width);
114 MCA_Set_Height(mca, height);
115}
116
117
118// -------------------------------
119void MCA_Set_NP(MCA * mca, int np)
120// -------------------------------
121{
122 mca->np = np;
123}
124
125
126// -------------------------------
127void MCA_Set_NR(MCA * mca, int nr)
128// -------------------------------
129{
130 mca->nr = nr;
131}
132
133
134
135// ------------------------------------------------------------------
136uint32 MCA_CalcMaxLabels(int connection, uint32 height, uint32 width)
137// ------------------------------------------------------------------
138{
139 uint32 nemax = 0;
140
141 if (connection == 4) {
142 nemax = ((height + 1) / 2) * ((width + 1) / 2) + (height / 2) * (width / 2); // 4C
143 }
144 if (connection == 8) {
145 nemax = ((height + 1) / 2) * ((width + 1) / 2); // 8C
146 }
147 return nemax;
148}
149
150
151// ---------------------------
152void MCA_Initialize(MCA * mca)
153// ---------------------------
154{
155 // input
156 int np = mca->np;
157 int nr = mca->nr;
158 int width = mca->width;
159 int height = mca->height;
160
161 // variables
162 int i0_par, i1_par, i1_par_previous;
163 int j0_par, j1_par;
164 int height_par, height_mod;
165
166 int pw2;
167 int32 ne_par; // quantite par bande
168 uint32 nemax_par; // la puissance de 2 >=
169 uint32 e0_par, e1_par; // indice par bande [start..end]
170 int nb_level;
171
172 MCA ** mcas;
173 MCA * mca_par;
174
175 MCA_VERBOSE1(printf("*** %s ***\n", __func__));
176 MCA_VERBOSE2(printf(" height = %d\n", height));
177 MCA_VERBOSE2(printf(" width = %d\n", width));
178
179 // array of pointers to mca workers
180 mcas = (MCA **) malloc(np * sizeof(MCA *));
181 if (mcas == NULL) {
182 MCA_Error("MCA_Initialize1");
183 }
184 mca->mcas = mcas;
185
186 // hauteur de chaque bande
187 height_par = height / np;
188 height_mod = height % np;
189
190 MCA_VERBOSE2(printf(" height_par = %d x %d + %d\n", height_par, np, height_mod));
191 MCA_VERBOSE2(printf(" ========================\n"));
192
193 i1_par_previous = 0;
194
195 // puissance de 2 de chaque bande
196 ne_par = height_par * width + 1;
197 MCA_VERBOSE2(printf(" ne_par = %d\n", ne_par));
198 pw2 = i32log2(ne_par);
199 if (ne_par > (1 << pw2)) {
200 pw2++;
201 }
202 nemax_par = 1 << pw2;
203 mca->alpha = pw2;
204
205 MCA_VERBOSE2(printf(" nemax_par = %d\n", nemax_par));
206
207 nb_level = i32log2(np);
208 if ((1 << nb_level) < np) {
209 nb_level++;
210 }
211
212#if PYR_BARRIERS
213 // ------------------------------------------
214 // -- Allocation des barriÚres pyramidales --
215 // ------------------------------------------
216
217 pthread_barrier_t * barriers = NULL;
218 if (nb_level > 0) {
219 barriers = malloc(sizeof(pthread_barrier_t) * nb_level);
220
221 // Initially all threads are active except thread 0
222 int nb_active = np - 1;
223 pthread_barrier_init(&barriers[0], NULL, nb_active);
224 for (int i = 1; i < nb_level; i++) {
225 // thread 0 never does any merge
226 for (int p = 1; p < np; p++) {
227 if ((p + (1 << (i - 1))) % (1 << i) == 0) {
228 // thread inactive at level i
229 nb_active -= 1;
230 }
231 }
232 pthread_barrier_init(&barriers[i], NULL, nb_active);
233 }
234 }
235#endif
236
237 for (int p = 0; p < np; p++) {
238
239 // ----------------- //
240 // -- constructor -- //
241 // ----------------- //
242 MCA_VERBOSE3(printf("-- p = %d ----------------\n", p));
243
244 // alloc of mca workers into array of pointers
245 mca_par = MCA_pConstructor_Empty();
246 if (mca_par == NULL) {
247 MCA_Error("MCA_Initialize2\n");
248 }
249 mcas[p] = mca_par;
250 mca_par->p = p;
251 mca_par->mca = mca; // pointer to master
252#if TARGET_OS == GIETVM
253 int x, y; // cluster coordinates
254 // We have p == 4 => x = 0; y = 1
255 x = (p / NB_PROCS_MAX) / Y_SIZE;
256 y = (p / NB_PROCS_MAX) % Y_SIZE;
257 MCA_VERBOSE3(printf("p = %d (x = %d, y = %d)\n", p, x, y));
258#endif
259
260 // ------------------------------------- //
261 // -- calcul des parametres: passe #1 -- //
262 // ------------------------------------- //
263
264 // hauteur de chaque bande
265 if (p == 0) {
266 i0_par = 0;
267 }
268 else {
269 i0_par = i1_par_previous + 1;
270 }
271 if (height_mod) {
272 i1_par = i0_par + height_par;
273 height_mod = height_mod - 1;
274 }
275 else {
276 i1_par = i0_par + height_par - 1;
277 }
278 i1_par_previous = i1_par;
279
280 MCA_VERBOSE3(printf("i0_par = %d\n", i0_par));
281 MCA_VERBOSE3(printf("i1_par = %d\n", i1_par));
282
283 // etiquettes
284 if (p == 0) {
285 e0_par = 1;
286 e1_par = nemax_par - 1;
287 }
288 else {
289 e0_par = p * nemax_par;
290 e1_par = e0_par + nemax_par - 1;
291 }
292
293 MCA_VERBOSE3(printf("e0_par = %d\n", e0_par));
294 MCA_VERBOSE3(printf("e1_par = %d\n", e1_par));
295
296 mca_par->width = width;
297 mca_par->height = height_par;
298 mca_par->i0 = i0_par;
299 mca_par->i1 = i1_par;
300 mca_par->j0 = 0;
301 mca_par->j1 = width - 1;
302 mca_par->e0 = e0_par;
303 mca_par->e1 = e1_par;
304 // à la premiÚre itération, on remet à 0 toute la table T
305 mca_par->ne_prev = e1_par;
306 mca_par->alpha = pw2;
307 mca_par->np = np;
308 mca_par->nr = nr;
309 // Pour les barriÚres pyramidales
310 mca_par->nb_level = nb_level;
311#if PYR_BARRIERS
312 mca_par->barriers = barriers;
313#else
314 mca_par->barriers = NULL;
315#endif
316 mca_par->F = NULL; // default init
317 mca_par->stats = NULL; // default init
318
319 // ---------------- //
320 // -- allocation -- //
321 // ---------------- //
322#if TARGET_OS == GIETVM
323 mca_par->X = remote_ui8matrix(i0_par, i1_par, 0, width - 1, x, y);
324 mca_par->E = remote_dist_ui32matrix(i0_par, i1_par, 0, width - 1, x, y); // distributed matrix with border
325
326 mca_par->T = remote_ui32vector(e0_par, e1_par, x, y);
327 mca_par->stats = remote_RegionStatsVector(e0_par, e1_par, x, y);
328
329 mca_par->D = (uint32 **) remote_vvector(0, np - 1, x, y);
330 mca_par->F = (RegionStats **) remote_vvector(0, np - 1, x, y);
331#else // !GIETVM
332 mca_par->X = ui8matrix (i0_par, i1_par, 0, width - 1);
333 mca_par->E = dist_ui32matrix(i0_par, i1_par, 0, width - 1); // distributed matrix with border
334
335 mca_par->T = ui32vector(e0_par, e1_par);
336 mca_par->stats = RegionStatsVector(e0_par, e1_par);
337
338 mca_par->D = (uint32 **) vvector(0, np - 1);
339 mca_par->F = (RegionStats **) vvector(0, np - 1);
340#endif
341 MCA_VERBOSE3(printf("X = %p\n", mca_par->X));
342 MCA_VERBOSE3(printf("E = %p\n", mca_par->E));
343 MCA_VERBOSE3(printf("T = %p\n", mca_par->T));
344 MCA_VERBOSE3(printf("D = %p\n", mca_par->D));
345 } // p
346
347
348 for (int p = 0; p < np; p++) {
349 MCA * mca_par = mcas[p];
350
351 uint32 * T = mca_par->T;
352 uint32 e0 = mca_par->e0;
353 uint32 e1 = mca_par->e1;
354
355 MCA_VERBOSE3(printf("p = %d T[%d..%d]\n", p, e0, e1));
356 set_ui32vector_j(T, e0, e1);
357 }
358
359 MCA_VERBOSE3(printf("display des tables d'EQ\n"));
360 for (int p = 0; p < np; p++) {
361 MCA * mca_par = mcas[p];
362
363 uint32 * T = mca_par->T;
364 uint32 e0 = mca_par->e0;
365 uint32 e1 = mca_par->e1;
366
367 MCA_VERBOSE3(printf("p = %d T[%d..%d]\n", p, e0, e1));
368 MCA_VERBOSE3(display_ui32vector_number(T, e0, e0 + 10, "%5d", "T"));
369 MCA_VERBOSE3(printf("\n"));
370 }
371
372 // ------------------------------------------------------------- //
373 // -- calcul des parametres: passe #2 = parametres distribues -- //
374 // ------------------------------------------------------------- //
375
376 // table d'indirection distribuee D
377 MCA_VERBOSE3(printf("nemax_par = %d\n", nemax_par));
378 for (int p = 0; p < np; p++) {
379 MCA * mca_p = mcas[p];
380 uint32 ** D = mca_p->D;
381 RegionStats ** F = mca_p->F;
382
383 for (int k = 0; k < np; k++) {
384 MCA * mca_k = mcas[k];
385 uint32 * T = mca_k->T;
386 D[k] = T + k * nemax_par; // il faut soustraire le "MSB"
387 RegionStats * stat = mca_k->stats;
388 F[k] = stat + k * nemax_par; // il faut soustraire le "MSB"
389 } // k
390 } // p
391
392 MCA_VERBOSE3(printf("table d'indirection distribuee D\n"));
393
394 for (int p = 0; p < np; p++) {
395 MCA_VERBOSE3(printf("== p = %d ==========\n", p));
396
397 MCA * mca_p = mcas[p];
398 uint32 ** D = mca_p->D;
399
400 for (int k = 0; k < np; k++) {
401 MCA * mca_k = mcas[k];
402 uint32 * T = mca_k->T;
403
404 uint32 e0 = mca_k->e0;
405 uint32 e1 = mca_k->e1;
406 MCA_VERBOSE3(display_ui32vector_number(T, e0, e0 + 9, "%5d", "T"));
407 MCA_VERBOSE3(display_ui32vector(D[k], 0, 9, "%5d", "D\n"));
408 }
409 MCA_VERBOSE3(printf("\n"));
410 }
411
412 for (int p = 0; p < np; p++) {
413 if (p > 0) {
414 //printf("i0_(%d) = %d i1_{%d} = %d\n", p, mcas[p]->i0, p-1, mcas[p-1]->i1);
415 mcas[p]->E[mcas[p]->i0 - 1] = mcas[p - 1]->E[mcas[p - 1]->i1];
416
417 /*printf("E[%2d] = E[%2d] = %p\n", mcas[p ]->i0 - 1,
418 mcas[p - 1]->i1,
419 mcas[p - 1]->E[mcas[p - 1]->i1]);*/
420 }
421 if (p < np - 1) {
422 //printf("i1_(%d) = %d i0_{%d} = %d\n", p, mcas[p]->i1, p+1, mcas[p-1]->i0);
423 mcas[p]->E[mcas[p]->i1 + 1] = mcas[p + 1]->E[mcas[p + 1]->i0];
424
425 /*printf("E[%2d] = E[%2d] = %p\n", mcas[p ]->i1 + 1,
426 mcas[p + 1]->i0,
427 mcas[p + 1]->E[mcas[p + 1]->i1]);*/
428 }
429 }
430}
431
432
433// -----------------------------------
434void MCA_Display_Parameters(MCA * mca)
435// -----------------------------------
436{
437 int np = mca->np;
438
439 MCA ** mcas = mca->mcas;
440 MCA * mca_par;
441 (void) mca_par;
442
443 MCA_VERBOSE1(printf("*** %s ***\n", __func__));
444
445 MCA_VERBOSE2(printf(" height = %d\n", mca->height));
446 MCA_VERBOSE2(printf(" width = %d\n", mca->width));
447 MCA_VERBOSE2(printf(" np = %d\n", mca->np));
448
449 for (int p = 0; p < np; p++) {
450 mca_par = mcas[p];
451
452 MCA_VERBOSE3(printf("Display MCA[%d]\n", p));
453 MCA_VERBOSE3(printf("p = %d\n", mca_par->p));
454 MCA_VERBOSE3(printf("i0 = %8d i1 = %8d\n", mca_par->i0, mca_par->i1));
455 MCA_VERBOSE3(printf("j0 = %8d j1 = %8d\n", mca_par->j0, mca_par->j1));
456 MCA_VERBOSE3(printf("e0 = %8d e1 = %8d\n", mca_par->e0, mca_par->e1));
457 }
458}
459
460
461// -------------------------
462void MCA_Finalize(MCA * mca)
463// -------------------------
464{
465 int np = mca->np;
466
467 MCA ** mcas = mca->mcas;
468 MCA * mca_par;
469
470 int i0, i1;
471 int j0, j1;
472 uint32 e0, e1;
473
474 MCA_VERBOSE1(printf("*** %s ***\n", __func__));
475
476#if PYR_BARRIERS
477 free(mcas[0]->barriers);
478#endif
479
480 for (int p = 0; p < np; p++) {
481 mca_par = mcas[p];
482
483 i0 = mca_par->i0;
484 i1 = mca_par->i1;
485 j0 = mca_par->j0;
486 j1 = mca_par->j1;
487 e0 = mca_par->e0;
488 e1 = mca_par->e1;
489
490 // ---------- //
491 // -- free -- //
492 // ---------- //
493
494 free_ui8matrix (mca_par->X, i0, i1, j0, j1);
495 free_dist_ui32matrix(mca_par->E, i0, i1, j0, j1);
496
497 free_ui32vector(mca_par->T, e0, e1);
498 free_RegionStatsVector(mca_par->stats, e0, e1);
499
500 free_vvector((void **) mca_par->D, 0, np - 1);
501 free_vvector((void **) mca_par->F, 0, np - 1);
502 free(mca_par);
503 }
504 free(mcas);
505 free(mca);
506}
507
508
509// -------------------------------
510void MCA_Scatter_ImageX(MCA * mca)
511// -------------------------------
512{
513 // diffusion de l'image binaire source
514
515 int np = mca->np;
516 uint8 ** X = mca->mca->X;
517
518 if (mca->p == 0) {
519 MCA_VERBOSE1(printf("*** %s ***\n", __func__));
520 }
521
522 int i0 = mca->i0;
523 int i1 = mca->i1;
524 int width = mca->width;
525
526 uint8 ** X_par = mca->X;
527 uint32 ** E_par = mca->E;
528
529 //printf("copie de [%d..%d]x[%d..%d]\n", i0, i1, 0, width - 1);
530 for (int i = i0; i <= i1; i++) {
531 for (int j = 0; j <= width - 1; j++) {
532 X_par[i][j] = X[i][j];
533 E_par[i][j] = 0; // inutile normalement car ecriture de 0
534 }
535 }
536}
537
538
539// ------------------------------
540void MCA_Gather_ImageL(MCA * mca)
541// ------------------------------
542{
543 // recuperation de l'image d'etiquettes
544 int np = mca->np;
545 uint32 ** E = mca->mca->E;
546
547 if (mca->p == 0) {
548 MCA_VERBOSE1(printf("*** %s ***\n", __func__));
549 }
550
551 int i0 = mca->i0;
552 int i1 = mca->i1;
553 int width = mca->width;
554
555 uint32 ** E_par = mca->E;
556
557 for (int i = i0; i <= i1; i++) {
558 for (int j = 0; j <= width - 1; j++) {
559 E[i][j] = E_par[i][j];
560 }
561 }
562}
563
564
565// Local Variables:
566// tab-width: 4
567// c-basic-offset: 4
568// c-file-offsets:((innamespace . 0)(inline-open . 0))
569// indent-tabs-mode: nil
570// End:
571
572// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=4:softtabstop=4
573
574
Note: See TracBrowser for help on using the repository browser.