Ignore:
Timestamp:
Jun 1, 2016, 10:25:43 AM (8 years ago)
Author:
meunier
Message:

In rosenfeld:

  • Updated nrio0, nrio1, nrio2, nrio1f, nrio2f, nrio1x, nrbool1, nrbool2 and nralloc1 in the nrc2 lib in order to use macro-typed functions
  • Updated the simulation script to include performance evaluation with random images, and a script to generate graphs
  • Updated the clock.h to use 64-bit integers, which potentially breaks the printing on the giet
Location:
soft/giet_vm/applications/rosenfeld/src-par
Files:
3 edited

Legend:

Unmodified
Added
Removed

  • soft/giet_vm/applications/rosenfeld/src-par/mca.c

    r821 r822  
    4242{
    4343    printf("MCA ERROR: %s\n", msg);
    44     printf("now exiting to system...\n");
    4544    exit(1);
    4645}
    … …  
    164163    MCA *  mca_par;
    165164   
    166     printf("*** %s ***\n", __func__);
    167     MCA_VERBOSE1(printf("   height = %d\n", height));
    168     MCA_VERBOSE1(printf("   width  = %d\n", width));
     165    MCA_VERBOSE1(printf("*** %s ***\n", __func__));
     166    MCA_VERBOSE2(printf("   height = %d\n", height));
     167    MCA_VERBOSE2(printf("   width  = %d\n", width));
    169168   
    170169    // array of pointers to mca workers
    … …  
    179178    height_mod = height % np;
    180179
    181     MCA_VERBOSE1(printf("   height_par = %d x %d + %d\n", height_par, np, height_mod));
    182     MCA_VERBOSE1(printf("   ========================\n"));
     180    MCA_VERBOSE2(printf("   height_par = %d x %d + %d\n", height_par, np, height_mod));
     181    MCA_VERBOSE2(printf("   ========================\n"));
    183182   
    184183    i1_par_previous = 0;
    … …  
    186185    // puissance de 2 de chaque bande
    187186    ne_par = height_par * width + 1;
    188     MCA_VERBOSE1(printf("   ne_par    = %d\n", ne_par));
     187    MCA_VERBOSE2(printf("   ne_par    = %d\n", ne_par));
    189188    pw2 = i32log2(ne_par);
    190189    if (ne_par > (1 << pw2)) {
    … …  
    192191    }
    193192    nemax_par = 1 << pw2;
    194 
    195     MCA_VERBOSE1(printf("   nemax_par = %d\n", nemax_par));
     193    mca->alpha = pw2;
     194
     195    MCA_VERBOSE2(printf("   nemax_par = %d\n", nemax_par));
    196196
    197197    nb_level = i32log2(np);
    … …  
    230230        // -- constructor -- //
    231231        // ----------------- //
    232         MCA_VERBOSE2(printf("-- p = %d ----------------\n", p));
     232        MCA_VERBOSE3(printf("-- p = %d ----------------\n", p));
    233233   
    234234        // alloc of mca workers into array of pointers
    … …  
    245245        x = (p / NB_PROCS_MAX) / Y_SIZE;
    246246        y = (p / NB_PROCS_MAX) % Y_SIZE;
    247         MCA_VERBOSE2(printf("p = %d (x = %d, y = %d)\n", p, x, y));
     247        MCA_VERBOSE3(printf("p = %d (x = %d, y = %d)\n", p, x, y));
    248248#endif
    249249       
    … …  
    268268        i1_par_previous = i1_par;
    269269       
    270         MCA_VERBOSE2(printf("i0_par = %d\n", i0_par));
    271         MCA_VERBOSE2(printf("i1_par = %d\n", i1_par));
     270        MCA_VERBOSE3(printf("i0_par = %d\n", i0_par));
     271        MCA_VERBOSE3(printf("i1_par = %d\n", i1_par));
    272272       
    273273        // etiquettes
    … …  
    281281        }
    282282   
    283         MCA_VERBOSE2(printf("e0_par = %d\n", e0_par));
    284         MCA_VERBOSE2(printf("e1_par = %d\n", e1_par));
     283        MCA_VERBOSE3(printf("e0_par = %d\n", e0_par));
     284        MCA_VERBOSE3(printf("e1_par = %d\n", e1_par));
    285285
    286286        mca_par->width  = width;
    … …  
    313313        if (p == 0) {
    314314            mca_par->T = remote_ui32vector(e0_par - 1, e1_par, x, y); // car e0 = 1, on a besoin que T[0] = 0 pour FindRoot
    315 #if FEATURES
    316315            mca_par->stats = remote_RegionStatsVector(e0_par - 1, e1_par, x, y);
    317 #endif
    318316        }
    319317        else {
    320318            mca_par->T = remote_ui32vector(e0_par, e1_par, x, y);
    321 #if FEATURES
    322319            mca_par->stats = remote_RegionStatsVector(e0_par, e1_par, x, y);
    323 #endif
    324320        }
    325321       
    326322        mca_par->D = (uint32 **) remote_vvector(0, np - 1, x, y);
    327 #if FEATURES
    328323        mca_par->F = (RegionStats **) remote_vvector(0, np - 1, x, y);
    329 #endif
    330324#else // !GIETVM
    331325        mca_par->X = ui8matrix (i0_par, i1_par, 0, width - 1);
    … …  
    334328        if (p == 0) {
    335329            mca_par->T = ui32vector(e0_par - 1, e1_par); // car e0 = 1, on a besoin que T[0] = 0 pour FindRoot
    336 #if FEATURES
    337330            mca_par->stats = RegionStatsVector(e0_par - 1, e1_par);
    338 
    339 #endif
    340331        }
    341332        else {
    342333            mca_par->T = ui32vector(e0_par, e1_par);
    343 #if FEATURES
    344334            mca_par->stats = RegionStatsVector(e0_par, e1_par);
    345 #endif
    346335        }
    347336       
    348337        mca_par->D = (uint32 **) vvector(0, np - 1);
    349 #if FEATURES
    350338        mca_par->F = (RegionStats **) vvector(0, np - 1);
    351 #endif
    352339#endif   
    353         MCA_VERBOSE2(printf("X = %p\n", mca_par->X));
    354         MCA_VERBOSE2(printf("E = %p\n", mca_par->E));
    355         MCA_VERBOSE2(printf("T = %p\n", mca_par->T));
    356         MCA_VERBOSE2(printf("D = %p\n", mca_par->D));
     340        MCA_VERBOSE3(printf("X = %p\n", mca_par->X));
     341        MCA_VERBOSE3(printf("E = %p\n", mca_par->E));
     342        MCA_VERBOSE3(printf("T = %p\n", mca_par->T));
     343        MCA_VERBOSE3(printf("D = %p\n", mca_par->D));
    357344    } // p
    358345   
    … …  
    365352        uint32 e1 = mca_par->e1;
    366353   
    367         MCA_VERBOSE2(printf("p = %d T[%d..%d]\n", p, e0, e1));
     354        MCA_VERBOSE3(printf("p = %d T[%d..%d]\n", p, e0, e1));
    368355        if (p == 0) {
    369356            set_ui32vector_j(T, e0 - 1, e1); // car e0 = 1, on a besoin que T[0] = 0 pour FindRoot
    … …  
    372359            set_ui32vector_j(T, e0, e1);
    373360        }
    374         MCA_VERBOSE2(printf("\n"));
    375     }
    376    
    377     MCA_VERBOSE2(printf("display des tables d'EQ\n"));
     361        MCA_VERBOSE3(printf("\n"));
     362    }
     363   
     364    MCA_VERBOSE3(printf("display des tables d'EQ\n"));
    378365    for (int p = 0; p < np; p++) {
    379366        MCA * mca_par = mcas[p];
    … …  
    383370        uint32 e1 = mca_par->e1;
    384371       
    385         MCA_VERBOSE2(printf("p = %d T[%d..%d]\n", p, e0, e1));
    386         if (p == 0) {
    387             MCA_VERBOSE2(display_ui32vector_number(T, e0 - 1, e0 + 10, "%5d", "T"));
    388         }
    389         else {
    390             MCA_VERBOSE2(display_ui32vector_number(T, e0, e0 + 10, "%5d", "T"));
    391         }
    392         MCA_VERBOSE2(printf("\n"));
     372        MCA_VERBOSE3(printf("p = %d T[%d..%d]\n", p, e0, e1));
     373        if (p == 0) {
     374            MCA_VERBOSE3(display_ui32vector_number(T, e0 - 1, e0 + 10, "%5d", "T"));
     375        }
     376        else {
     377            MCA_VERBOSE3(display_ui32vector_number(T, e0, e0 + 10, "%5d", "T"));
     378        }
     379        MCA_VERBOSE3(printf("\n"));
    393380    }
    394381    //exit(-1);
    … …  
    399386   
    400387    // table d'indirection distribuee D
    401     MCA_VERBOSE2(printf("nemax_par = %d\n", nemax_par));
     388    MCA_VERBOSE3(printf("nemax_par = %d\n", nemax_par));
    402389    for (int p = 0; p < np; p++) {
    403390        MCA * mca_p = mcas[p];
    … …  
    409396            uint32 * T = mca_k->T;
    410397            D[k] = T + k * nemax_par; // il faut soustraire le "MSB"
    411 #if FEATURES
    412398            RegionStats * stat = mca_k->stats;
    413399            F[k] = stat + k * nemax_par; // il faut soustraire le "MSB"
    414 #endif
    415400        } // k
    416401    } // p
    417402   
    418     MCA_VERBOSE2(printf("table d'indirection distribuee D\n"));
    419    
    420     for (int p = 0; p < np; p++) {
    421         MCA_VERBOSE2(printf("== p = %d ==========\n", p));
     403    MCA_VERBOSE3(printf("table d'indirection distribuee D\n"));
     404   
     405    for (int p = 0; p < np; p++) {
     406        MCA_VERBOSE3(printf("== p = %d ==========\n", p));
    422407       
    423408        MCA * mca_p = mcas[p];
    … …  
    430415            uint32 e0 = mca_k->e0;
    431416            uint32 e1 = mca_k->e1;
    432             MCA_VERBOSE2(display_ui32vector_number(T, e0, e0 + 9, "%5d", "T"));
    433             MCA_VERBOSE2(display_ui32vector(D[k], 0, 9, "%5d", "D\n"));
    434         }
    435         MCA_VERBOSE2(printf("\n"));
    436     }
    437    
    438     /**/
    439     //exit(-1);
    440    
    441     //printf("[MCA_Initialize] positionnement des pointeurs de lignes (i0-1) et (i1+1)");
    442    
    443     for (int p = 0; p < np; p++) {
    444    
    445         //printf(" --p = %d ------------------\n", p);
    446         // cas general
    447        
     417            MCA_VERBOSE3(display_ui32vector_number(T, e0, e0 + 9, "%5d", "T"));
     418            MCA_VERBOSE3(display_ui32vector(D[k], 0, 9, "%5d", "D\n"));
     419        }
     420        MCA_VERBOSE3(printf("\n"));
     421    }
     422   
     423    for (int p = 0; p < np; p++) {
    448424        if (p > 0) {
    449425            //printf("i0_(%d) = %d i1_{%d} = %d\n", p, mcas[p]->i0, p-1, mcas[p-1]->i1);
    … …  
    476452    (void) mca_par;
    477453   
    478     printf("*** MCA_Display_Parameters ***\n");
    479    
    480     MCA_VERBOSE1(printf("   height = %d\n", mca->height));
    481     MCA_VERBOSE1(printf("   width  = %d\n", mca->width));
    482     MCA_VERBOSE1(printf("   np     = %d\n", mca->np));
     454    MCA_VERBOSE1(printf("*** MCA_Display_Parameters ***\n"));
     455   
     456    MCA_VERBOSE2(printf("   height = %d\n", mca->height));
     457    MCA_VERBOSE2(printf("   width  = %d\n", mca->width));
     458    MCA_VERBOSE2(printf("   np     = %d\n", mca->np));
    483459   
    484460    for (int p = 0; p < np; p++) {
    485461        mca_par = mcas[p];
    486462       
    487         MCA_VERBOSE2(printf("Display MCA[%d]\n", p));
    488         MCA_VERBOSE2(printf("p = %d\n", mca_par->p));
    489         MCA_VERBOSE2(printf("i0 = %8d  i1 = %8d\n", mca_par->i0, mca_par->i1));
    490         MCA_VERBOSE2(printf("j0 = %8d  j1 = %8d\n", mca_par->j0, mca_par->j1));
    491         MCA_VERBOSE2(printf("e0 = %8d  e1 = %8d\n", mca_par->e0, mca_par->e1));
     463        MCA_VERBOSE3(printf("Display MCA[%d]\n", p));
     464        MCA_VERBOSE3(printf("p = %d\n", mca_par->p));
     465        MCA_VERBOSE3(printf("i0 = %8d  i1 = %8d\n", mca_par->i0, mca_par->i1));
     466        MCA_VERBOSE3(printf("j0 = %8d  j1 = %8d\n", mca_par->j0, mca_par->j1));
     467        MCA_VERBOSE3(printf("e0 = %8d  e1 = %8d\n", mca_par->e0, mca_par->e1));
    492468    }
    493469}
    … …  
    507483    uint32 e0, e1;
    508484   
    509     printf("*** MCA_Finalize ***\n");
     485    MCA_VERBOSE1(printf("*** MCA_Finalize ***\n"));
    510486   
    511487#if PYR_BARRIERS
    … …  
    532508        if (p == 0) {
    533509            free_ui32vector(mca_par->T, e0 - 1, e1); // car e0 = 1, on a besoin que T[0] = 0 pour FindRoot
    534 #if FEATURES
    535510            free_RegionStatsVector(mca_par->stats, e0 - 1, e1);
    536 #endif
    537511        }
    538512        else {
    539513            free_ui32vector(mca_par->T, e0, e1);
    540 #if FEATURES
    541514            free_RegionStatsVector(mca_par->stats, e0, e1);
    542 #endif
    543515        }
    544516       
    545517        free_vvector((void **) mca_par->D, 0, np - 1);
    546 #if FEATURES
    547518        free_vvector((void **) mca_par->F, 0, np - 1);
    548 #endif
    549519        free(mca_par);
    550520    }
    … …  
    564534   
    565535    if (mca->p == 0) {
    566         printf("*** MCA_Scatter_ImageX ***\n");
     536        MCA_VERBOSE1(printf("*** MCA_Scatter_ImageX ***\n"));
    567537    }
    568538   
    … …  
    593563
    594564    if (mca->p == 0) {
    595         printf("*** MCA_Gather_ImageL ***\n");
     565        MCA_VERBOSE1(printf("*** MCA_Gather_ImageL ***\n"));
    596566    }
    597567

  • soft/giet_vm/applications/rosenfeld/src-par/mca_main.c

    r821 r822  
    126126
    127127
    128 // QM : The cost of this function is horrible
    129 // but it is only for testing purpose
    130128// Renumbers object in a contiguous way, for an image which has already
    131129// been processed with several threads
    132 // --------------------------------------------------------------------
    133 static void renumber_image(uint32 ** E, int i0, int i1, int j0, int j1)
    134 // --------------------------------------------------------------------
    135 {
    136     int size = 10;
    137     int idx = 1; // next label to give, first invalid index in the equiv table
    138     uint32 * equiv = malloc(sizeof(uint32) * size);
    139     equiv[0] = 0; // unused
    140     int found;
    141 
    142     for (int i = i0; i <= i1; i++) {
    143         for (int j = j0; j <= j1; j++) {
    144             if (E[i][j] != 0) {
    145                 found = 0;
    146                 for (int k = 1; k < idx; k++) {
    147                     if (equiv[k] == E[i][j]) {
    148                         E[i][j] = k;
    149                         found = 1;
    150                         break;
    151                     }
    152                 }
    153                 if (found == 0) {
    154                     equiv[idx] = E[i][j];
    155                     E[i][j] = idx;
    156                     idx += 1;
    157                     if (idx == size) {
    158                         size = size * 2;
    159                         equiv = realloc(equiv, sizeof(uint32) * size);
    160                     }
    161                 }
     130// ------------------------------------------------------------------
     131static void renumber_image(MCA * mca, int i0, int i1, int j0, int j1)
     132// ------------------------------------------------------------------
     133{
     134    int32_t na = 0;
     135    uint32_t ** E = mca->E;
     136    uint32_t ** D = mca->mcas[0]->D;
     137
     138    uint32_t shift = mca->alpha;
     139    uint32_t mask = (1 << shift) - 1;
     140   
     141    for (int32_t p = 0; p < mca->np; p++) {
     142        MCA * mca_par = mca->mcas[p];
     143        uint32 * T = mca_par->T;
     144        for (uint32_t e = mca_par->e0; e <= mca_par->ne; e++) {
     145            if (T[e] != e) {
     146                // FindRoot_Dist
     147                uint32_t r = T[e];
     148                uint32_t a = e;
     149                do {
     150                    uint32_t e1 = r >> shift;
     151                    uint32_t e0 = r & mask;
     152                    a = r;
     153                    r = D[e1][e0];
     154                } while (r < a);
     155                T[e] = r;
     156            }
     157            else {
     158                na += 1;
     159                T[e] = na;
    162160            }
    163161        }
    164162    }
    165     free(equiv);
     163
     164    for (int32_t i = i0; i <= i1; i++) {
     165        for (int32_t j = j0; j <= j1; j++) {
     166            if (E[i][j] != 0) {
     167                uint32_t e0 = E[i][j] & mask;
     168                uint32_t e1 = E[i][j] >> shift;
     169                E[i][j] = D[e1][e0];
     170            }
     171        }
     172    }
    166173}
    167174
    … …  
    203210   
    204211    display_ui8matrix_positive(mca->X, i0, i1, j0, j1, 5, "X0");
    205 #if FEATURES
    206     for (int i = 1; i < num_threads; i++) {
    207         pthread_create(&thread_table[i], NULL, MCA_Label_Features_Rosenfeld, (void *) mca->mcas[i]);
    208     }
    209     MCA_Label_Features_Rosenfeld(mca->mcas[0]);
    210 #else
    211212    for (int i = 1; i < num_threads; i++) {
    212213        pthread_create(&thread_table[i], NULL, MCA_Label_Rosenfeld, (void *) mca->mcas[i]);
    213214    }
     215   
    214216    MCA_Label_Rosenfeld(mca->mcas[0]);
    215 #endif
     217
    216218    for (int i = 1; i < num_threads; i++) {
    217219        pthread_join(thread_table[i], NULL);
    … …  
    221223   
    222224    // -- free --
    223     printf("Finalize\n");
     225    MCA_VERBOSE1(printf("Finalize\n"));
    224226    MCA_Finalize(mca);
    225227   
    226     printf("Free_matrix\n");
     228    MCA_VERBOSE1(printf("Free_matrix\n"));
    227229    free_ui8matrix (X0, i0, i1, j0, j1);
    228230    free_ui32matrix(E,  i0, i1, j0, j1);
    … …  
    249251    Palette_18ColorsBW(palette);
    250252   
    251     printf("Loading file %s... ", infile);
     253    MCA_VERBOSE1(printf("Loading file %s... ", infile));
    252254    X = LoadPGM_ui8matrix(infile, &i0, &i1, &j0, &j1);
    253     printf("done.\n");
    254 
    255     printf("Allocating memory... ");
     255    MCA_VERBOSE1(printf("done.\n"));
     256
     257    MCA_VERBOSE1(printf("Allocating memory... "));
    256258    height = i1 - i0 + 1;
    257259    width  = j1 - j0 + 1;
    … …  
    265267    // pre-traitements
    266268    binarisation_ui8matrix(X, i0, i1, j0, j1, 20, 1, X); // pour le traitement
    267     printf("done.\n");
    268 
    269     printf("Allocating and initializing MCA... \n");
     269    MCA_VERBOSE1(printf("done.\n"));
     270
     271    MCA_VERBOSE1(printf("Allocating and initializing MCA... \n"));
    270272    mca = MCA_pConstructor_Empty();
    271273   
    … …  
    279281    MCA_Initialize(mca);
    280282    MCA_Display_Parameters(mca);
    281     printf("End of MCA allocation and initialization.\n");
     283    MCA_VERBOSE1(printf("End of MCA allocation and initialization.\n"));
    282284   
    283285    CLOCK_APP_CREATE;
    284 #if FEATURES
    285     for (int i = 1; i < num_threads; i++) {
    286         pthread_create(&thread_table[i], NULL, MCA_Label_Features_Rosenfeld, (void *) mca->mcas[i]);
    287     }
    288     MCA_Label_Features_Rosenfeld(mca->mcas[0]);
    289 #else
    290286    for (int i = 1; i < num_threads; i++) {
    291287        pthread_create(&thread_table[i], NULL, MCA_Label_Rosenfeld, (void *) mca->mcas[i]);
    292288    }
     289   
    293290    MCA_Label_Rosenfeld(mca->mcas[0]);
    294 #endif
     291
    295292    for (int i = 1; i < num_threads; i++) {
    296293        pthread_join(thread_table[i], NULL);
    … …  
    300297    if (generate_output_image) {
    301298#if TARGET_OS != GIETVM
    302         renumber_image(mca->E, i0, i1, j0, j1);
     299        renumber_image(mca, i0, i1, j0, j1);
    303300#else
    304301        printf("Warning: the output image has not been renumbered, it cannot be used as a comparison with the reference\n");
    305302#endif
    306303        mod_ui32matrix_ui8matrix(mca->E, i0, i1, j0, j1, E8);
    307         printf("Saving file %s for verification... ", outfile);
     304        MCA_VERBOSE1(printf("Saving file %s for verification... ", outfile));
    308305        SaveBMP2_ui8matrix(E8, width, height, palette, outfile);
    309         printf("done.\n");
     306        MCA_VERBOSE1(printf("done.\n"));
    310307    }
    311308
    312309    MCA_Finalize(mca);
    313     printf("Deallocating memory...");
     310    MCA_VERBOSE1(printf("Deallocating memory..."));
    314311    free_ui8matrix (X,  i0, i1, j0, j1);
    315312    free_ui8matrix (E8, i0, i1, j0, j1);
    316313    free_ui32matrix(E,  i0, i1, j0, j1);
    317     printf("done.\n");
     314    MCA_VERBOSE1(printf("done.\n"));
    318315}
    319316
    … …  
    353350    int num_threads = DEFAULT_NTHREADS;
    354351
    355     printf("*** Starting application Rosenfeld ***\n");
     352    MCA_VERBOSE1(printf("*** Starting application Rosenfeld ***\n"));
    356353
    357354#if TARGET_OS != GIETVM // @QM I think the giet has some random (uninitialized) values for argc and argv
    … …  
    410407    }
    411408
    412     printf("Parameters:\n");
    413     printf("- Number of threads: %d\n", num_threads);
    414     printf("- Input file: %s\n", infile);
    415     printf("- Output file: %s\n", outfile);
     409    MCA_VERBOSE1(printf("Parameters:\n"));
     410    MCA_VERBOSE1(printf("- Number of threads: %d\n", num_threads));
     411    MCA_VERBOSE1(printf("- Input file: %s\n", infile));
     412    MCA_VERBOSE1(printf("- Output file: %s\n", outfile));
    416413#if FAST
    417     printf("- Using decision trees (fast): yes\n");
     414    MCA_VERBOSE1(printf("- Using decision trees (fast): yes\n"));
    418415#elif SLOW
    419     printf("- Using decision trees (fast): no\n");
     416    MCA_VERBOSE1(printf("- Using decision trees (fast): no\n"));
    420417#endif
    421418#if FEATURES
    422     printf("- Computing features: yes\n");
    423 #else
    424     printf("- Computing features: no\n");
     419    MCA_VERBOSE1(printf("- Computing features: yes\n"));
     420#else
     421    MCA_VERBOSE1(printf("- Computing features: no\n"));
     422#endif
     423#if PARMERGE
     424    MCA_VERBOSE1(printf("- Parallel Merge: yes\n"));
     425#else
     426    MCA_VERBOSE1(printf("- Parallel Merge: no\n"));
     427#endif
     428#if ARSP
     429    MCA_VERBOSE1(printf("- Optimization ARemSP: yes\n"));
     430#else
     431    MCA_VERBOSE1(printf("- Optimization ARemSP: no\n"));
     432#endif
     433#if PYR_BARRIERS
     434    MCA_VERBOSE1(printf("- Pyramidal Barriers: yes\n"));
     435#else
     436    MCA_VERBOSE1(printf("- Pyramidal Barriers: no\n"));
    425437#endif
    426438
    … …  
    428440#if TARGET_OS == GIETVM
    429441    giet_tty_alloc(1);
    430     printf("Initializing heaps... ");
     442    MCA_VERBOSE1(printf("Initializing heaps... "));
    431443    for (int i = 0; i < X_SIZE; i++) {
    432444        for (int j = 0; j < X_SIZE; j++) {
    … …  
    434446        }
    435447    }
    436     printf("done.\n");
     448    MCA_VERBOSE1(printf("done.\n"));
    437449#endif
    438450
    … …  
    443455}
    444456
     457// Local Variables:
     458// tab-width: 4
     459// c-basic-offset: 4
     460// c-file-offsets:((innamespace . 0)(inline-open . 0))
     461// indent-tabs-mode: nil
     462// End:
     463
     464// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=4:softtabstop=4
     465

  • soft/giet_vm/applications/rosenfeld/src-par/mca_rosenfeld.c

    r821 r822  
    6161        r = T[r];
    6262    }
    63     if (r == 0) {
    64         printf("e = %d\n",e);
    65         assert(0);
    66     }
     63
     64    assert(r != 0);
    6765    return r;
    6866}
    … …  
    8179    int mask = (1 << shift) - 1;
    8280   
    83     MCA_VERBOSE2(printf("%s(%d, %d) \n", __func__, r, shift));
     81    MCA_VERBOSE3(printf("%s(%d, %d) \n", __func__, r, shift));
    8482    do {
    8583        e  = r;
    … …  
    8785        e0 = r & mask;
    8886        r = D[e1][e0];
    89         MCA_VERBOSE2(printf("%s: D(%d) = D[%d,%d] = %d (alpha = %d)\n", __func__, e, e1, e0, r, shift));
     87        MCA_VERBOSE3(printf("%s: D(%d) = D[%d,%d] = %d (alpha = %d)\n", __func__, e, e1, e0, r, shift));
    9088    } while (r < e);
    91     MCA_VERBOSE2(printf("%s = %d \n\n", __func__, r));
     89    MCA_VERBOSE3(printf("%s = %d \n\n", __func__, r));
    9290    assert(r != 0);
    9391    return r;
    … …  
    112110
    113111#if FEATURES && !PARMERGE
    114 // ----------------------------------------------------------------------------------------------------
    115 void SetRoot_Features_Rosenfeld_Dist(uint32 ** D, uint32 root, uint32 eps, int shift, RegionStats ** F)
    116 // ----------------------------------------------------------------------------------------------------
     112// -----------------------------------------------------------------------------------------------------------
     113static void SetRoot_Features_Rosenfeld_Dist(uint32 ** D, uint32 root, uint32 eps, int shift, RegionStats ** F)
     114// -----------------------------------------------------------------------------------------------------------
    117115{
    118116    assert(root != 0 && eps != 0);
    119117
    120     MCA_VERBOSE2(printf("F(%d) += F(%d)\n", eps, root));
     118    MCA_VERBOSE3(printf("F(%d) += F(%d)\n", eps, root));
    121119   
    122120    int mask = (1 << shift) - 1;
    123121
    124     // SetRoot_Rosenfeld_Dist
    125122    uint32 r1 = root >> shift;
    126123    uint32 r0 = root & mask;
    … …  
    148145
    149146#if FEATURES && PARMERGE
    150 // -------------------------------------------------------------------------------------------------------------
    151 bool SetRoot_Parallel_Features_Rosenfeld_Dist(uint32 ** D, uint32 root, uint32 eps, int shift, RegionStats ** F)
    152 // -------------------------------------------------------------------------------------------------------------
     147// --------------------------------------------------------------------------------------------------------------------
     148static bool SetRoot_Parallel_Features_Rosenfeld_Dist(uint32 ** D, uint32 root, uint32 eps, int shift, RegionStats ** F)
     149// --------------------------------------------------------------------------------------------------------------------
    153150{
    154151    assert(root != 0 && eps != 0);
    155152
    156     MCA_VERBOSE2(printf("F(%d) += F(%d)\n", eps, root));
     153    MCA_VERBOSE3(printf("F(%d) += F(%d)\n", eps, root));
    157154   
    158155    int mask = (1 << shift) - 1;
    159156
    160     // SetRoot_Rosenfeld_Dist
    161157    uint32 r1 = root >> shift;
    162158    uint32 r0 = root & mask;
    … …  
    177173    }
    178174    if (D[r1][r0] != root) {
    179         // Someone change the root of epsilon, need to find the new root
     175        // Someone change the root of "root", need to find the new root
    180176        printf("race cond 2\n");
    181177        pthread_spin_unlock(&F[e1][e0].lock);
    … …  
    249245
    250246
    251 #if FAST && !FEATURES
     247#if FAST && !FEATURES && !PARMERGE && !ARSP
    252248// ---------------------------------------------------------------------------------------
    253249static void vuse2_Rosenfeld_Dist(uint32 ed, uint32 el, uint32 * T, uint32 ** D, int alpha)
    … …  
    273269    }
    274270}
    275 #endif // FAST && !FEATURES
    276 
    277 
    278 #if FAST && !FEATURES
     271
     272// FAST && !FEATURES && !PARMERGE && !ARSP
     273
    279274// -----------------------------------------------------------------------------------------------------
    280275static void vuse3_Rosenfeld_Dist(uint32 ed1, uint32 ed2, uint32 el3, uint32 * T, uint32 ** D, int alpha)
    … …  
    284279    uint32 r2 = FindRoot_Dist(D, ed2, alpha);
    285280   
    286     // QM
    287     //uint32 r3 = FindRoot(T, el3); // local - distant
    288281    uint32 r3 = T[el3]; // local - distant
    289282    r3 = FindRoot_Dist(D, r3, alpha);
    … …  
    297290    uint32 eps = ui32Min3(r1, r2, r3);  // forcement positifs car appel depuis optimizedBorder qui a fait un test
    298291   
     292    // 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)
    299293    if (r1 > eps) {
    300294        SetRoot_Rosenfeld_Dist(D, r1, eps, alpha);
    301295    }
    302     //r2 = T[r2]; // @QM est-ce indispensable s'il n'y a pas de features ? (cf. slow no features)
    303     // comment est-on sur que r2 (ou r3) est local ???
    304296    if (r2 > eps) {
    305297        SetRoot_Rosenfeld_Dist(D, r2, eps, alpha);
    306298    }
    307     //r3 = T[r3];
    308299    if (r3 > eps) {
    309300        SetRoot_Rosenfeld_Dist(D, r3, eps, alpha);
    310301    }
    311302}
    312 #endif // FAST && !FEATURES
    313 
    314 
    315 #if FAST && FEATURES && !PARMERGE
    316 // -----------------------------------------------------------------------------------------------------------
    317 void vuse2_Features_Rosenfeld_Dist(uint32 ed, uint32 el, uint32 * T, uint32 ** D, int alpha, RegionStats ** F)
    318 // -----------------------------------------------------------------------------------------------------------
     303#endif // FAST && !FEATURES && !PARMERGE && !ARSP
     304
     305
     306#if FAST && FEATURES && !PARMERGE && !ARSP
     307// ------------------------------------------------------------------------------------------------------------------
     308static void vuse2_Features_Rosenfeld_Dist(uint32 ed, uint32 el, uint32 * T, uint32 ** D, int alpha, RegionStats ** F)
     309// ------------------------------------------------------------------------------------------------------------------
    319310{
    320311    assert(ed != 0 && el != 0);
    … …  
    341332    }
    342333}
    343 #endif // FAST && FEATURES && !PARMERGE
    344 
    345 
    346 #if FAST && FEATURES && !PARMERGE
    347 // -------------------------------------------------------------------------------------------------------------------------
    348 void vuse3_Features_Rosenfeld_Dist(uint32 ed1, uint32 ed2, uint32 el3, uint32 * T, uint32 ** D, int alpha, RegionStats ** F)
    349 // -------------------------------------------------------------------------------------------------------------------------
     334
     335// FAST && FEATURES && !PARMERGE && !ARSP
     336
     337// --------------------------------------------------------------------------------------------------------------------------------
     338static void vuse3_Features_Rosenfeld_Dist(uint32 ed1, uint32 ed2, uint32 el3, uint32 * T, uint32 ** D, int alpha, RegionStats ** F)
     339// --------------------------------------------------------------------------------------------------------------------------------
    350340{
    351341    assert(ed1 != 0 && ed2 != 0 && el3 != 0);
    … …  
    354344    uint32 r2 = FindRoot_Dist(D, ed2, alpha);
    355345   
    356     //uint32 r3 = FindRoot(T, el3); // local - distant
    357346    uint32 r3 = T[el3]; // local - distant
    358347    assert(r3 != 0);
    … …  
    370359        SetRoot_Features_Rosenfeld_Dist(D, r1, eps, alpha, F);
    371360    }
    372     //r2 = T[r2];
    373361    if (r2 > eps && r2 != r1) {
    374362        SetRoot_Features_Rosenfeld_Dist(D, r2, eps, alpha, F);
    375363    }
    376     //r3 = T[r3];
    377364    if (r3 > eps && r3 != r2 && r3 != r1) {
    378365        SetRoot_Features_Rosenfeld_Dist(D, r3, eps, alpha, F);
    379366    }
    380367}
    381 #endif // FAST && FEATURES && !PARMERGE
    382 
    383 
    384 #if FAST && FEATURES && PARMERGE
    385 // --------------------------------------------------------------------------------------------------------------------
    386 void vuse2_Parallel_Features_Rosenfeld_Dist(uint32 ed, uint32 el, uint32 * T, uint32 ** D, int alpha, RegionStats ** F)
    387 // --------------------------------------------------------------------------------------------------------------------
     368#endif // FAST && FEATURES && !PARMERGE && !ARSP
     369
     370
     371#if FAST && !FEATURES && PARMERGE && ARSP
     372// ----------------------------------------------------------------------------------------------------------------
     373static bool SetRoot_Parallel_Arsp_Rosenfeld_Dist(uint32 ** D, uint32 root, uint32 eps, int shift, RegionStats ** F)
     374// ----------------------------------------------------------------------------------------------------------------
     375{
     376    assert(root != 0 && eps != 0);
     377
     378    MCA_VERBOSE3(printf("F(%d) += F(%d)\n", eps, root));
     379   
     380    uint32_t mask = (1 << shift) - 1;
     381
     382    uint32_t r1 = root >> shift;
     383    uint32_t r0 = root & mask;
     384   
     385    pthread_spin_lock(&F[r1][r0].lock);
     386    if (D[r1][r0] != root) {
     387        pthread_spin_unlock(&F[r1][r0].lock);
     388        return false;
     389    }
     390
     391    D[r1][r0] = eps;
     392   
     393    pthread_spin_unlock(&F[r1][r0].lock);
     394    return true;
     395}
     396
     397// FAST && !FEATURES && PARMERGE && ARSP
     398
     399// ------------------------------------------------------------------------------------------------------------------------------
     400static inline bool FindSmallerAncestor_Link(uint32 ** D, uint32_t rl, uint32_t el, uint32_t rd, uint32_t shift, RegionStats ** F)
     401// ------------------------------------------------------------------------------------------------------------------------------
     402{
     403    bool ok;
     404    uint32_t el1, el0;
     405    uint32_t mask = (1 << shift) - 1;
     406    while (rl < el && rl > rd) {
     407        el = rl;
     408        el1 = rl >> shift;
     409        el0 = rl & mask;
     410        rl = D[el1][el0];
     411    }
     412    if (rd != rl) {
     413        if (rl == el && rl > rd) {
     414            // L'ordre s'est inversé : on fait pointer rl vers rd
     415            ok = SetRoot_Parallel_Arsp_Rosenfeld_Dist(D, rl, rd, shift, F);
     416        }
     417        else {
     418            // On fait pointer rd vers rl
     419            ok = SetRoot_Parallel_Arsp_Rosenfeld_Dist(D, rd, rl, shift, F);
     420        }
     421    }
     422    else {
     423        ok = true;
     424    }
     425    return ok;
     426}
     427
     428// FAST && !FEATURES && PARMERGE && ARSP
     429
     430// -----------------------------------------------------------------------------------------------------------------------
     431static void vuse2_Parallel_Arsp_Rosenfeld_Dist(uint32 ed, uint32 el, uint32 * T, uint32 ** D, int alpha, RegionStats ** F)
     432// -----------------------------------------------------------------------------------------------------------------------
     433{
     434    assert(ed != 0 && el != 0);
     435 
     436    uint32_t shift = alpha;
     437    uint32_t mask = (1 << shift) - 1;
     438   
     439    uint32_t rd = ed;
     440    uint32_t rl = el;
     441
     442    uint32_t ed1;
     443    uint32_t el1;
     444    uint32_t ed0;
     445    uint32_t el0;
     446
     447    bool ok;
     448
     449    // Fusion ed - el
     450    do {
     451        do {
     452            ed = rd;
     453            el = rl;
     454            ed1 = rd >> shift;
     455            el1 = rl >> shift;
     456            ed0 = rd & mask;
     457            el0 = rl & mask;
     458            rd = D[ed1][ed0];
     459            rl = D[el1][el0];
     460        } while (rl < el && rd < ed);
     461
     462        assert(rl != 0 && rd != 0);
     463
     464        if (rd != rl) {
     465            if (rd == ed) {
     466                ok = FindSmallerAncestor_Link(D, rl, el, rd, shift, F);
     467            }
     468            else {
     469                assert(rl == el);
     470                ok = FindSmallerAncestor_Link(D, rd, ed, rl, shift, F);
     471            }
     472        }
     473        else {
     474            ok = true;
     475        }
     476    } while (!ok);
     477}
     478
     479// FAST && !FEATURES && PARMERGE && ARSP
     480
     481// -------------------------------------------------------------------------------------------------------------------------------------
     482static void vuse3_Parallel_Arsp_Rosenfeld_Dist(uint32 ed1, uint32 ed2, uint32 el3, uint32 * T, uint32 ** D, int alpha, RegionStats ** F)
     483// -------------------------------------------------------------------------------------------------------------------------------------
     484{
     485    assert(ed1 != 0 && ed2 != 0 && el3 != 0);
     486 
     487    uint32_t shift = alpha;
     488    uint32_t mask = (1 << shift) - 1;
     489   
     490    uint32_t r1 = ed1;
     491    uint32_t r2 = ed2;
     492    uint32_t r3 = el3;
     493
     494    uint32_t e11;
     495    uint32_t e21;
     496    uint32_t e31;
     497    uint32_t e10;
     498    uint32_t e20;
     499    uint32_t e30;
     500
     501    uint32_t r0;
     502    uint32_t ed0;
     503    uint32_t e00;
     504    uint32_t e01;
     505
     506    // Pas d'init pour que valgrind détecte une erreur si bool est lu sans être affecté
     507    bool ok;
     508
     509    // Fusion ed1 - ed2
     510    do {
     511        do {
     512            ed1 = r1;
     513            ed2 = r2;
     514            e11 = r1 >> shift;
     515            e21 = r2 >> shift;
     516            e10 = r1 & mask;
     517            e20 = r2 & mask;
     518            r1 = D[e11][e10];
     519            r2 = D[e21][e20];
     520        } while (r1 < ed1 && r2 < ed2);
     521
     522        assert(r1 != 0 && r2 != 0);
     523
     524        if (r1 != r2) {
     525            if (r1 == ed1) {
     526                ok = FindSmallerAncestor_Link(D, r2, ed2, r1, shift, F);
     527            }
     528            else {
     529                assert(r2 == ed2);
     530                ok = FindSmallerAncestor_Link(D, r1, ed1, r2, shift, F);
     531            }
     532        }
     533        else {
     534            ok = true;
     535        }
     536    } while (!ok);
     537
     538    // Fusion r0 = min(r1, r2) avec r3
     539    if (r1 < r2) {
     540        r0 = r1;
     541        ed0 = r1;
     542        e00 = e10;
     543        e01 = e11;
     544    }
     545    else {
     546        r0 = r2;
     547        ed0 = r2;
     548        e00 = e20;
     549        e01 = e21;
     550    }
     551
     552    // r0 est déjà une racine
     553    goto r0_is_root;
     554    do {
     555        do {
     556            ed0 = r0;
     557            el3 = r3;
     558            e01 = r0 >> shift;
     559            e31 = r3 >> shift;
     560            e00 = r0 & mask;
     561            e30 = r3 & mask;
     562            r0 = D[e01][e00];
     563            r3 = D[e31][e30];
     564        } while (r0 < ed0 && r3 < el3);
     565
     566        assert(r0 != 0 && r3 != 0);
     567
     568        if (r0 != r3) {
     569            if (r0 == ed0) {
     570r0_is_root:
     571                ok = FindSmallerAncestor_Link(D, r3, el3, r0, shift, F);
     572            }
     573            else {
     574                assert(r3 == el3);
     575                ok = FindSmallerAncestor_Link(D, r0, ed0, r3, shift, F);
     576            }
     577        }
     578        else {
     579            ok = true;
     580        }
     581    } while (!ok);
     582}
     583#endif // FAST && !FEATURES && PARMERGE && ARSP
     584
     585
     586
     587#if FAST && FEATURES && PARMERGE && !ARSP
     588// ---------------------------------------------------------------------------------------------------------------------------
     589static void vuse2_Parallel_Features_Rosenfeld_Dist(uint32 ed, uint32 el, uint32 * T, uint32 ** D, int alpha, RegionStats ** F)
     590// ---------------------------------------------------------------------------------------------------------------------------
    388591{
    389592    bool ok;
    … …  
    414617    } while (!ok);
    415618}
    416 #endif // FAST && FEATURES && PARMERGE
    417 
    418 
    419 #if FAST && FEATURES && PARMERGE
    420 // ----------------------------------------------------------------------------------------------------------------------------------
    421 void vuse3_Parallel_Features_Rosenfeld_Dist(uint32 ed1, uint32 ed2, uint32 el3, uint32 * T, uint32 ** D, int alpha, RegionStats ** F)
    422 // ----------------------------------------------------------------------------------------------------------------------------------
     619
     620// FAST && FEATURES && PARMERGE && !ARSP
     621
     622// -----------------------------------------------------------------------------------------------------------------------------------------
     623static void vuse3_Parallel_Features_Rosenfeld_Dist(uint32 ed1, uint32 ed2, uint32 el3, uint32 * T, uint32 ** D, int alpha, RegionStats ** F)
     624// -----------------------------------------------------------------------------------------------------------------------------------------
    423625{
    424626    bool ok1, ok2, ok3;
    … …  
    457659    } while (!(ok1 && ok2 && ok3));
    458660}
    459 #endif // FAST && FEATURES && PARMERGE
    460 
    461 
    462 
    463 
    464 #if FAST && !FEATURES
    465 // ------------------------------------------------------------------------------------------------------
    466 static void optimizedBorder_Rosenfeld_Dist(uint32 ** E, int i, int j, uint32 * T, uint32 ** D, int alpha)
    467 // ------------------------------------------------------------------------------------------------------
     661#endif // FAST && FEATURES && PARMERGE && !ARSP
     662
     663
     664
     665#if FAST
     666// ------------------------------------------------------------------------------------------------------------------------
     667static void optimizedBorder_Rosenfeld_Dist(uint32 ** E, int i, int j, uint32 * T, uint32 ** D, int alpha, RegionStats ** F)
     668// ------------------------------------------------------------------------------------------------------------------------
    468669{
    469670    uint32 a, b, c, x;
    … …  
    473674        b = E[i - 1][j];
    474675        if (b) {
    475             vuse2_Rosenfeld_Dist(b, x, T, D, alpha); // dist, local
     676            vuse2_Rosenfeld(b, x, T, D, alpha, F); // dist, local
    476677        }
    477678        else {
    … …  
    480681                a = E[i - 1][j - 1];
    481682                if (a) {
    482                     vuse3_Rosenfeld_Dist(a, c, x, T, D, alpha); // dist, local
     683                    vuse3_Rosenfeld(a, c, x, T, D, alpha, F); // dist, local
    483684                }
    484685                else {
    485                     vuse2_Rosenfeld_Dist(c, x, T, D, alpha); // dist, local
     686                    vuse2_Rosenfeld(c, x, T, D, alpha, F); // dist, local
    486687                }
    487688            }
    … …  
    489690                a = E[i - 1][j - 1];
    490691                if (a) {
    491                     vuse2_Rosenfeld_Dist(a, x, T, D, alpha); // dist, local
     692                    vuse2_Rosenfeld(a, x, T, D, alpha, F); // dist, local
    492693                }
    493694            }
    … …  
    495696    }
    496697}
    497 #endif // FAST && !FEATURES
    498 
    499 
    500 #if FAST && !FEATURES
    501 // ---------------------------------------------------------------------------------------------------
    502 static void optimizedBorderLeft_Rosenfeld_Dist(uint32 ** E, int i, int j, uint32 * T, uint32 ** D, int alpha)
    503 // ---------------------------------------------------------------------------------------------------
     698
     699// FAST
     700
     701// ----------------------------------------------------------------------------------------------------------------------------
     702static void optimizedBorderLeft_Rosenfeld_Dist(uint32 ** E, int i, int j, uint32 * T, uint32 ** D, int alpha, RegionStats ** F)
     703// ----------------------------------------------------------------------------------------------------------------------------
    504704{
    505705    uint32 x = E[i][j];
    … …  
    507707        uint32 b = E[i - 1][j];
    508708        if (b) {
    509             vuse2_Rosenfeld_Dist(b, x, T, D, alpha); // dist, local
     709            vuse2_Rosenfeld(b, x, T, D, alpha, F); // dist, local
    510710        }
    511711        else {
    512712            uint32 c = E[i - 1][j + 1];
    513713            if (c) {
    514                 vuse2_Rosenfeld_Dist(c, x, T, D, alpha); // dist, local
    515             }
    516         }
    517     }
    518 }
    519 #endif // FAST && !FEATURES
    520 
    521 
    522 #if FAST && !FEATURES
    523 // -----------------------------------------------------------------------------------------------------------
    524 static void optimizedBorderRight_Rosenfeld_Dist(uint32 ** E, int i, int j, uint32 * T, uint32 ** D, int alpha)
    525 // -----------------------------------------------------------------------------------------------------------
     714                vuse2_Rosenfeld(c, x, T, D, alpha, F); // dist, local
     715            }
     716        }
     717    }
     718}
     719
     720// FAST
     721
     722// -----------------------------------------------------------------------------------------------------------------------------
     723static void optimizedBorderRight_Rosenfeld_Dist(uint32 ** E, int i, int j, uint32 * T, uint32 ** D, int alpha, RegionStats ** F)
     724// -----------------------------------------------------------------------------------------------------------------------------
    526725{
    527726    // copie de optimizedBorder_Rosenfeld
    … …  
    533732    if (x) {
    534733        if (b) {
    535             vuse2_Rosenfeld_Dist(b, x, T, D, alpha); // dist, local
     734            vuse2_Rosenfeld(b, x, T, D, alpha, F); // dist, local
    536735        }
    537736        else {
    538737            uint32 a = E[i - 1][j - 1];
    539738            if (a) {
    540                 vuse2_Rosenfeld_Dist(a, x, T, D, alpha); // dist, local
    541             }
    542         }
    543     }
    544 }
    545 #endif // FAST && !FEATURES
    546 
    547 
    548 #if FAST && !FEATURES
    549 // ------------------------------------------------------------------------------------------------------------------------
    550 static void borderMerging_Fast_Rosenfeld_Dist(uint8 **X, int i, int width, uint32 ** E, uint32 * T, uint32 ** D, int alpha)
    551 // ------------------------------------------------------------------------------------------------------------------------
     739                vuse2_Rosenfeld(a, x, T, D, alpha, F); // dist, local
     740            }
     741        }
     742    }
     743}
     744
     745// FAST
     746
     747// -------------------------------------------------------------------------------------------------------------------------------------------
     748static void borderMerging_Fast_Rosenfeld_Dist(uint8 ** X, int i, int width, uint32 ** E, uint32 * T, uint32 ** D, int alpha, RegionStats ** F)
     749// -------------------------------------------------------------------------------------------------------------------------------------------
    552750{
    553751    // Prologue
    554     optimizedBorderLeft_Rosenfeld_Dist(E, i, 0, T, D, alpha);
     752    optimizedBorderLeft_Rosenfeld_Dist(E, i, 0, T, D, alpha, F);
    555753    // Boucle principale
    556754    for (int j = 1; j < width - 1; j++) {
    557         optimizedBorder_Rosenfeld_Dist(E, i, j, T, D, alpha);
     755        optimizedBorder_Rosenfeld_Dist(E, i, j, T, D, alpha, F);
    558756    }
    559757    // Epilogue
    560     optimizedBorderRight_Rosenfeld_Dist(E, i, width - 1, T, D, alpha);
    561 }
    562 #endif // FAST && !FEATURES
    563 
    564 
    565 #if SLOW && !FEATURES
    566 // -------------------------------------------------------------------------------------------------------------------------
    567 static void borderMerging_Slow_Rosenfeld_Dist(uint8 ** X, int i, int width, uint32 ** E, uint32 * T, uint32 ** D, int alpha)
    568 // -------------------------------------------------------------------------------------------------------------------------
    569 {
    570     int j;
     758    optimizedBorderRight_Rosenfeld_Dist(E, i, width - 1, T, D, alpha, F);
     759}
     760#endif // FAST
     761
     762
     763
     764#if SLOW
     765// -------------------------------------------------------------------------------------------------------------------------------------------
     766static void borderMerging_Slow_Rosenfeld_Dist(uint8 ** X, int i, int width, uint32 ** E, uint32 * T, uint32 ** D, int alpha, RegionStats ** F)
     767// -------------------------------------------------------------------------------------------------------------------------------------------
     768{
     769    int j = 0;
    571770   
    572771    uint32 eps;
    … …  
    577776    // -- prologue --
    578777    // --------------
    579     MCA_VERBOSE2(printf("[%s] i = %d\n", __func__, i));
    580    
    581     j = 0;
     778    MCA_VERBOSE3(printf("[%s] i = %d\n", __func__, i));
     779   
    582780    ex = E[i][j];
    583781   
    584782    if (ex) {
    585783       
    586         MCA_VERBOSE2(printf("[%s] j = %d\n", __func__, j));
    587        
    588         e2 = E[i - 1][j];
    589         e3 = E[i - 1][j + 1];
    590 
    591         // test pour eviter acces distant
    592         r2 = e2 ? FindRoot_Dist(D, e2, alpha) : 0;
    593         r3 = e3 ? FindRoot_Dist(D, e3, alpha) : 0;
    594 
    595         rx = T[ex];
    596         rx = FindRoot_Dist(D, rx, alpha);
    597  
    598         MCA_VERBOSE2(printf("\n"));
    599         MCA_VERBOSE2(printf("e2 = %4d -> %4d\n", e2, r2));
    600         MCA_VERBOSE2(printf("e3 = %4d -> %4d\n", e3, r3));
    601         MCA_VERBOSE2(printf("ex = %4d -> %4d\n", ex, rx));
    602        
    603         eps = ui32MinNonNul3(r2, r3, rx);
    604        
    605         // Quick-Union
    606         if (r2 > eps) {
    607             SetRoot_Rosenfeld_Dist(D, r2, eps, alpha);
    608             MCA_VERBOSE2(printf("D[%4d] <- %d\n", r2, eps));
    609         }
    610         if (r3 > eps) {
    611             SetRoot_Rosenfeld_Dist(D, r3, eps, alpha);
    612             MCA_VERBOSE2(printf("D[%4d] <- %d\n", r3, eps));
    613         }
    614         if (rx > eps) {
    615             SetRoot_Rosenfeld_Dist(D, rx, eps, alpha);
    616             MCA_VERBOSE2(printf("D[%4d] <- %d\n", rx, eps));
    617         }
    618         MCA_VERBOSE2(printf("\n"));
    619     }
    620    
    621     // -----------------------
    622     // -- boucle principale --
    623     // -----------------------
    624    
    625     for (j = 0 + 1; j < width - 1; j++) {
    626    
    627         ex = E[i][j];
    628        
    629         // que le cas general (pour faire un code simple)
    630         if (ex) {
    631             MCA_VERBOSE2(printf("[%s] j = %d\n", __func__, j));
    632            
    633             e1 = E[i - 1][j - 1];
    634             e2 = E[i - 1][j];
    635             e3 = E[i - 1][j + 1];
    636        
    637             // test pour eviter acces distant
    638             r1 = e1 ? FindRoot_Dist(D, e1, alpha) : 0;
    639             r2 = e2 ? FindRoot_Dist(D, e2, alpha) : 0;
    640             r3 = e3 ? FindRoot_Dist(D, e3, alpha) : 0;
    641 
    642             rx = T[ex];
    643             rx = FindRoot_Dist(D, rx, alpha);
    644 
    645             MCA_VERBOSE2(printf("\n"));
    646             MCA_VERBOSE2(printf("e1 = %4d -> %4d\n", e1, r1));
    647             MCA_VERBOSE2(printf("e2 = %4d -> %4d\n", e2, r2));
    648             MCA_VERBOSE2(printf("e3 = %4d -> %4d\n", e3, r3));
    649             MCA_VERBOSE2(printf("ex = %4d -> %4d\n", ex, rx));
    650            
    651             eps = ui32MinNonNul4(r1, r2, r3, rx);
    652            
    653             // Quick-Union
    654             if (r1 > eps) {
    655                 SetRoot_Rosenfeld_Dist(D, r1, eps, alpha);
    656                 MCA_VERBOSE2(printf("D[%4d] <- %d\n", r1, eps));
    657             }
    658             if (r2 > eps) {
    659                 SetRoot_Rosenfeld_Dist(D, r2, eps, alpha);
    660                 MCA_VERBOSE2(printf("D[%4d] <- %d\n", r2, eps));
    661             }
    662             if (r3 > eps) {
    663                 SetRoot_Rosenfeld_Dist(D, r3, eps, alpha);
    664                 MCA_VERBOSE2(printf("D[%4d] <- %d\n", r3, eps));
    665             }
    666             if (rx > eps) {
    667                 SetRoot_Rosenfeld_Dist(D, rx, eps, alpha);
    668                 MCA_VERBOSE2(printf("D[%4d] <- %d\n", rx, eps));
    669             }
    670             MCA_VERBOSE2(printf("\n"));
    671             // attention SetRoot fait un while inutile
    672         }
    673     }
    674    
    675     // --------------
    676     // -- epilogue --
    677     // --------------
    678    
    679     j = width - 1;
    680     ex = E[i][j];
    681    
    682     if (ex) {
    683        
    684         MCA_VERBOSE2(printf("[%s] j = %d\n", __func__, j));
    685        
    686         e1 = E[i - 1][j - 1];
    687         e2 = E[i - 1][j];
    688 
    689         // test pour eviter acces distant
    690         r1 = e1 ? FindRoot_Dist(D, e1, alpha) : 0;
    691         r2 = e2 ? FindRoot_Dist(D, e2, alpha) : 0;
    692 
    693         rx = T[ex];
    694         rx = FindRoot_Dist(D, rx, alpha);
    695 
    696         MCA_VERBOSE2(printf("\n"));
    697         MCA_VERBOSE2(printf("e1 = %4d -> %4d\n", e1, r1));
    698         MCA_VERBOSE2(printf("e2 = %4d -> %4d\n", e2, r2));
    699         MCA_VERBOSE2(printf("ex = %4d -> %4d\n", ex, rx));
    700        
    701         eps = ui32MinNonNul3(r1, r2, rx);
    702        
    703         // Quick-Union
    704         if (r1 > eps) {
    705             SetRoot_Rosenfeld_Dist(D, r1, eps, alpha);
    706             MCA_VERBOSE2(printf("D[%4d] <- %d\n", r1, eps));
    707         }
    708         if (r2 > eps) {
    709             SetRoot_Rosenfeld_Dist(D, r2, eps, alpha);
    710             MCA_VERBOSE2(printf("D[%4d] <- %d\n", r2, eps));
    711         }
    712         if (rx > eps) {
    713             SetRoot_Rosenfeld_Dist(D, rx, eps, alpha);
    714             MCA_VERBOSE2(printf("D[%4d] <- %d\n", rx, eps));
    715         }
    716         MCA_VERBOSE2(printf("\n"));
    717     }
    718     return;
    719 }
    720 #endif // SLOW && !FEATURES
    721 
    722 
    723 #if SLOW && FEATURES
    724 // ----------------------------------------------------------------------------------------------------------------------------------------------------
    725 static void borderMerging_Slow_Features_Rosenfeld_Dist(uint8 ** X, int i, int width, uint32 ** E, uint32 * T, uint32 ** D, int alpha, RegionStats ** F)
    726 // ----------------------------------------------------------------------------------------------------------------------------------------------------
    727 {
    728     int j = 0;
    729    
    730     uint32 eps;
    731    
    732     uint32 e1, e2, e3, ex;
    733     uint32 r1, r2, r3, rx;
    734    
    735     // --------------
    736     // -- prologue --
    737     // --------------
    738     MCA_VERBOSE2(printf("[%s] i = %d\n", __func__, i));
    739    
    740     ex = E[i][j];
    741    
    742     if (ex) {
    743        
    744         MCA_VERBOSE2(printf("[%s] j = %d\n", __func__, j));
     784        MCA_VERBOSE3(printf("[%s] j = %d\n", __func__, j));
    745785       
    746786        e2 = E[i - 1][j];
    … …  
    758798            eps = ui32MinNonNul3(r2, r3, rx);
    759799           
    760             MCA_VERBOSE2(printf("\n"));
    761             MCA_VERBOSE2(printf("e2  = %5d -> r2 = %5d\n", e2, r2));
    762             MCA_VERBOSE2(printf("e3  = %5d -> r3 = %5d\n", e3, r3));
    763             MCA_VERBOSE2(printf("ex  = %5d -> rx = %5d\n", ex, rx));
    764             MCA_VERBOSE2(printf("eps = %5d\n", eps));
     800            MCA_VERBOSE3(printf("\n"));
     801            MCA_VERBOSE3(printf("e2  = %5d -> r2 = %5d\n", e2, r2));
     802            MCA_VERBOSE3(printf("e3  = %5d -> r3 = %5d\n", e3, r3));
     803            MCA_VERBOSE3(printf("ex  = %5d -> rx = %5d\n", ex, rx));
     804            MCA_VERBOSE3(printf("eps = %5d\n", eps));
    765805           
    766806            // Quick-Union
    767             // @QM
    768807            if (r2 > eps) {
    769                 SetRoot_Features_Rosenfeld_Dist(D, r2, eps, alpha, F);
    770                 MCA_VERBOSE2(printf("D[%5d] <- %d\n", r2, eps));
    771             }
    772             if (r3 > 0) {
    773                 r3 = FindRoot_Dist(D, r3, alpha);
     808                SetRoot_Rosenfeld(D, r2, eps, alpha, F);
     809                MCA_VERBOSE3(printf("D[%5d] <- %d\n", r2, eps));
    774810            }
    775811            // Pour le cas où r2 == r3, il ne faut pas ajouter deux fois les features
    776             //if (r3 > eps && r3 != r2) {
    777             if (r3 > eps) {
    778                 SetRoot_Features_Rosenfeld_Dist(D, r3, eps, alpha, F);
    779                 MCA_VERBOSE2(printf("D[%5d] <- %d\n", r3, eps));
    780             }
    781             rx = FindRoot_Dist(D, rx, alpha);
    782             //if (rx > eps && rx != r3 && rx != r2) {
    783             if (rx > eps) {
    784                 SetRoot_Features_Rosenfeld_Dist(D, rx, eps, alpha, F);
    785                 MCA_VERBOSE2(printf("D[%5d] <- %d\n", rx, eps));
    786             }
    787             MCA_VERBOSE2(printf("---------------------------\n"));
     812            //if (r3 > 0) {
     813            //    r3 = FindRoot_Dist(D, r3, alpha);
     814            //}
     815            //if (r3 > eps) {
     816            if (r3 > eps && r3 != r2) {
     817                SetRoot_Rosenfeld(D, r3, eps, alpha, F);
     818                MCA_VERBOSE3(printf("D[%5d] <- %d\n", r3, eps));
     819            }
     820            //rx = FindRoot_Dist(D, rx, alpha);
     821            //if (rx > eps) {
     822            if (rx > eps && rx != r3 && rx != r2) {
     823                SetRoot_Rosenfeld(D, rx, eps, alpha, F);
     824                MCA_VERBOSE3(printf("D[%5d] <- %d\n", rx, eps));
     825            }
     826            MCA_VERBOSE3(printf("---------------------------\n"));
    788827        }
    789828    }
    … …  
    799838        if (ex) {
    800839           
    801             MCA_VERBOSE2(printf("[%s] j = %d\n", __func__, j));
     840            MCA_VERBOSE3(printf("[%s] j = %d\n", __func__, j));
    802841           
    803842            e1 = E[i - 1][j - 1];
    … …  
    816855                eps = ui32MinNonNul4(r1, r2, r3, rx);
    817856
    818                 MCA_VERBOSE2(printf("\n"));
    819                 MCA_VERBOSE2(printf("e1  = %5d -> r1 = %5d\n", e1, r1));
    820                 MCA_VERBOSE2(printf("e2  = %5d -> r2 = %5d\n", e2, r2));
    821                 MCA_VERBOSE2(printf("e3  = %5d -> r3 = %5d\n", e3, r3));
    822                 MCA_VERBOSE2(printf("ex  = %5d -> rx = %5d\n", ex, rx));
    823                 MCA_VERBOSE2(printf("eps = %5d\n", eps));
     857                MCA_VERBOSE3(printf("\n"));
     858                MCA_VERBOSE3(printf("e1  = %5d -> r1 = %5d\n", e1, r1));
     859                MCA_VERBOSE3(printf("e2  = %5d -> r2 = %5d\n", e2, r2));
     860                MCA_VERBOSE3(printf("e3  = %5d -> r3 = %5d\n", e3, r3));
     861                MCA_VERBOSE3(printf("ex  = %5d -> rx = %5d\n", ex, rx));
     862                MCA_VERBOSE3(printf("eps = %5d\n", eps));
     863               
    824864               
    825865                // Quick-Union
    826                 // @QM
    827866                if (r1 > eps) {
    828                     SetRoot_Features_Rosenfeld_Dist(D, r1, eps, alpha, F);
    829                     MCA_VERBOSE2(printf("D[%5d] <- %d\n", r1, eps));
     867                    SetRoot_Rosenfeld(D, r1, eps, alpha, F);
     868                    MCA_VERBOSE3(printf("D[%5d] <- %d\n", r1, eps));
    830869                }
    831                 if (r2 > 0) {
    832                     r2 = FindRoot_Dist(D, r2, alpha);
     870                //if (r2 > 0) {
     871                //    r2 = FindRoot_Dist(D, r2, alpha);
     872                //}
     873                if (r2 > eps && r2 != r1) {
     874                //if (r2 > eps) {
     875                    SetRoot_Rosenfeld(D, r2, eps, alpha, F);
     876                    MCA_VERBOSE3(printf("D[%5d] <- %d\n", r2, eps));
    833877                }
    834                 //if (r2 > eps && r2 != r1) {
    835                 if (r2 > eps) {
    836                     SetRoot_Features_Rosenfeld_Dist(D, r2, eps, alpha, F);
    837                     MCA_VERBOSE2(printf("D[%5d] <- %d\n", r2, eps));
     878                //if (r3 > 0) {
     879                //    r3 = FindRoot_Dist(D, r3, alpha);
     880                //}
     881                if (r3 > eps && r3 != r2 && r3 != r1) {
     882                //if (r3 > eps) {
     883                    SetRoot_Rosenfeld(D, r3, eps, alpha, F);
     884                    MCA_VERBOSE3(printf("D[%5d] <- %d\n", r3, eps));
    838885                }
    839                 if (r3 > 0) {
    840                     r3 = FindRoot_Dist(D, r3, alpha);
     886                //rx = FindRoot_Dist(D, rx, alpha);
     887                if (rx > eps && rx != r3 && rx != r2 && rx != r1) {
     888                //if (rx > eps) {
     889                    SetRoot_Rosenfeld(D, rx, eps, alpha, F);
     890                    MCA_VERBOSE3(printf("D[%5d] <- %d\n", rx, eps));
    841891                }
    842                 //if (r3 > eps && r3 != r2 && r3 != r1) {
    843                 if (r3 > eps) {
    844                     SetRoot_Features_Rosenfeld_Dist(D, r3, eps, alpha, F);
    845                     MCA_VERBOSE2(printf("D[%5d] <- %d\n", r3, eps));
    846                 }
    847                 rx = FindRoot_Dist(D, rx, alpha);
    848                 //if (rx > eps && rx != r3 && rx != r2 && rx != r1) {
    849                 if (rx > eps) {
    850                     SetRoot_Features_Rosenfeld_Dist(D, rx, eps, alpha, F);
    851                     MCA_VERBOSE2(printf("D[%5d] <- %d\n", rx, eps));
    852                 }
    853                 MCA_VERBOSE2(puts("---------------------------\n"));
    854                
    855                 // attention SetRoot fait un while inutile
     892                MCA_VERBOSE3(puts("---------------------------\n"));
    856893            }
    857894        }
    … …  
    867904    if (ex) {
    868905       
    869         MCA_VERBOSE2(printf("[%s] j = %d\n", __func__, j));
     906        MCA_VERBOSE3(printf("[%s] j = %d\n", __func__, j));
    870907       
    871908        e1 = E[i - 1][j - 1];
    … …  
    883920            eps = ui32MinNonNul3(r1, r2, rx);
    884921           
    885             MCA_VERBOSE2(printf("\n"));
    886             MCA_VERBOSE2(printf("e1  = %5d -> r1 = %5d\n", e1, r1));
    887             MCA_VERBOSE2(printf("e2  = %5d -> r2 = %5d\n", e2, r2));
    888             MCA_VERBOSE2(printf("ex  = %5d -> rx = %5d\n", ex, rx));
    889             MCA_VERBOSE2(printf("eps = %5d\n", eps));
     922            MCA_VERBOSE3(printf("\n"));
     923            MCA_VERBOSE3(printf("e1  = %5d -> r1 = %5d\n", e1, r1));
     924            MCA_VERBOSE3(printf("e2  = %5d -> r2 = %5d\n", e2, r2));
     925            MCA_VERBOSE3(printf("ex  = %5d -> rx = %5d\n", ex, rx));
     926            MCA_VERBOSE3(printf("eps = %5d\n", eps));
    890927           
    891928            // Quick-Union
    892929            if (r1 > eps) {
    893                 SetRoot_Features_Rosenfeld_Dist(D, r1, eps, alpha, F);
    894                 MCA_VERBOSE2(printf("D[%5d] <- %d\n", r1, eps));
    895             }
    896             if (r2 > 0) {
    897                 r2 = FindRoot_Dist(D, r2, alpha);
    898             }
    899             //if (r2 > eps && r2 != r1) {
    900             if (r2 > eps) {
    901                 SetRoot_Features_Rosenfeld_Dist(D, r2, eps, alpha, F);
    902                 MCA_VERBOSE2(printf("D[%5d] <- %d\n", r2, eps));
    903             }
    904             rx = FindRoot_Dist(D, rx, alpha);
    905             //if (rx > eps && rx != r2 && rx != r1) {
    906             if (rx > eps) {
    907                 SetRoot_Features_Rosenfeld_Dist(D, rx, eps, alpha, F);
    908                 MCA_VERBOSE2(printf("D[%5d] <- %d\n", rx, eps));
    909             }
    910             MCA_VERBOSE2(printf("---------------------------\n"));
    911         }
    912     }
    913     return;
    914 }
    915 #endif // SLOW && FEATURES
    916 
    917 
    918 #if FAST && FEATURES && !PARMERGE
    919 // --------------------------------------------------------------------------------------------------------------------------
    920 void optimizedBorder_Features_Rosenfeld_Dist(uint32 ** E, int i, int j, uint32 * T, uint32 ** D, int alpha, RegionStats ** F)
    921 // --------------------------------------------------------------------------------------------------------------------------
    922 {
    923     // copie de optimizedBorder_Rosenfeld
    924     uint32 a, b, c, x;
    925    
    926     x = E[i][j];
    927    
    928     if (x) {
    929         b = E[i - 1][j];
    930         if (b) {
    931             vuse2_Features_Rosenfeld_Dist(b, x, T, D, alpha, F); // dist, local
    932         }
    933         else {
    934             c = E[i - 1][j + 1];
    935             if (c) {
    936                 a = E[i - 1][j - 1];
    937                 if (a) {
    938                     vuse3_Features_Rosenfeld_Dist(a, c, x, T, D, alpha, F); // dist, local
    939                 }
    940                 else {
    941                     vuse2_Features_Rosenfeld_Dist(c, x, T, D, alpha, F); // dist, local
    942                 }
    943             }
    944             else {
    945                 a = E[i - 1][j - 1];
    946                 if (a) {
    947                     vuse2_Features_Rosenfeld_Dist(a, x, T, D, alpha, F); // dist, local
    948                 }
    949             }
    950         }
    951     }
    952 }
    953 #endif // FAST && FEATURES && !PARMERGE
    954 
    955 
    956 #if FAST && FEATURES && !PARMERGE
    957 // ------------------------------------------------------------------------------------------------------------------------------
    958 void optimizedBorderLeft_Features_Rosenfeld_Dist(uint32 ** E, int i, int j, uint32 * T, uint32 ** D, int alpha, RegionStats ** F)
    959 // ------------------------------------------------------------------------------------------------------------------------------
    960 {
    961     uint32 x = E[i][j];
    962    
    963     if (x) {
    964         uint32 b = E[i - 1][j];
    965         if (b) {
    966             vuse2_Features_Rosenfeld_Dist(b, x, T, D, alpha, F); // dist, local
    967         }
    968         else {
    969             uint32 c = E[i - 1][j + 1];
    970             if (c) {
    971                 vuse2_Features_Rosenfeld_Dist(c, x, T, D, alpha, F); // dist, local
    972             }
    973         }
    974     }
    975 }
    976 #endif // FAST && FEATURES && !PARMERGE
    977 
    978 
    979 #if FAST && FEATURES && !PARMERGE
    980 // -------------------------------------------------------------------------------------------------------------------------------
    981 void optimizedBorderRight_Features_Rosenfeld_Dist(uint32 ** E, int i, int j, uint32 * T, uint32 ** D, int alpha, RegionStats ** F)
    982 // -------------------------------------------------------------------------------------------------------------------------------
    983 {
    984     // copie de optimizedBorder_Rosenfeld
    985     // test d'existance de ex en local local
    986    
    987     uint32 x = E[i][j];
    988    
    989     if (x) {
    990         uint32 b = E[i - 1][j];
    991         if (b) {
    992             vuse2_Features_Rosenfeld_Dist(b, x, T, D, alpha, F); // dist, local
    993         }
    994         else {
    995             uint32 a = E[i - 1][j - 1];
    996             if (a) {
    997                 vuse2_Features_Rosenfeld_Dist(a, x, T, D, alpha, F); // dist, local
    998             }
    999         }
    1000     }
    1001 }
    1002 #endif // FAST && FEATURES && !PARMERGE
    1003 
    1004 
    1005 #if FAST && FEATURES && PARMERGE
    1006 // -----------------------------------------------------------------------------------------------------------------------------------
    1007 void optimizedBorder_Parallel_Features_Rosenfeld_Dist(uint32 ** E, int i, int j, uint32 * T, uint32 ** D, int alpha, RegionStats ** F)
    1008 // -----------------------------------------------------------------------------------------------------------------------------------
    1009 {
    1010     // copie de optimizedBorder_Rosenfeld
    1011     uint32 a, b, c, x;
    1012    
    1013     x = E[i][j];
    1014    
    1015     if (x) {
    1016         b = E[i - 1][j];
    1017         if (b) {
    1018             vuse2_Parallel_Features_Rosenfeld_Dist(b, x, T, D, alpha, F); // dist, local
    1019         }
    1020         else {
    1021             c = E[i - 1][j + 1];
    1022             if (c) {
    1023                 a = E[i - 1][j - 1];
    1024                 if (a) {
    1025                     vuse3_Parallel_Features_Rosenfeld_Dist(a, c, x, T, D, alpha, F); // dist, local
    1026                 }
    1027                 else {
    1028                     vuse2_Parallel_Features_Rosenfeld_Dist(c, x, T, D, alpha, F); // dist, local
    1029                 }
    1030             }
    1031             else {
    1032                 a = E[i - 1][j - 1];
    1033                 if (a) {
    1034                     vuse2_Parallel_Features_Rosenfeld_Dist(a, x, T, D, alpha, F); // dist, local
    1035                 }
    1036             }
    1037         }
    1038     }
    1039 }
    1040 #endif // FAST && FEATURES && PARMERGE
    1041 
    1042 
    1043 #if FAST && FEATURES && PARMERGE
    1044 // ---------------------------------------------------------------------------------------------------------------------------------------
    1045 void optimizedBorderLeft_Parallel_Features_Rosenfeld_Dist(uint32 ** E, int i, int j, uint32 * T, uint32 ** D, int alpha, RegionStats ** F)
    1046 // ---------------------------------------------------------------------------------------------------------------------------------------
    1047 {
    1048     uint32 x = E[i][j];
    1049    
    1050     if (x) {
    1051         uint32 b = E[i - 1][j];
    1052         if (b) {
    1053             vuse2_Parallel_Features_Rosenfeld_Dist(b, x, T, D, alpha, F); // dist, local
    1054         }
    1055         else {
    1056             uint32 c = E[i - 1][j + 1];
    1057             if (c) {
    1058                 vuse2_Parallel_Features_Rosenfeld_Dist(c, x, T, D, alpha, F); // dist, local
    1059             }
    1060         }
    1061     }
    1062 }
    1063 #endif // FAST && FEATURES && PARMERGE
    1064 
    1065 
    1066 #if FAST && FEATURES && PARMERGE
    1067 // ----------------------------------------------------------------------------------------------------------------------------------------
    1068 void optimizedBorderRight_Parallel_Features_Rosenfeld_Dist(uint32 ** E, int i, int j, uint32 * T, uint32 ** D, int alpha, RegionStats ** F)
    1069 // ----------------------------------------------------------------------------------------------------------------------------------------
    1070 {
    1071     // copie de optimizedBorder_Rosenfeld
    1072     // test d'existance de ex en local local
    1073    
    1074     uint32 x = E[i][j];
    1075    
    1076     if (x) {
    1077         uint32 b = E[i - 1][j];
    1078         if (b) {
    1079             vuse2_Parallel_Features_Rosenfeld_Dist(b, x, T, D, alpha, F); // dist, local
    1080         }
    1081         else {
    1082             uint32 a = E[i - 1][j - 1];
    1083             if (a) {
    1084                 vuse2_Parallel_Features_Rosenfeld_Dist(a, x, T, D, alpha, F); // dist, local
    1085             }
    1086         }
    1087     }
    1088 }
    1089 #endif // FAST && FEATURES && PARMERGE
    1090 
    1091 
    1092 #if FAST && FEATURES
    1093 // ---------------------------------------------------------------------------------------------------------------------------------------------
    1094 void borderMerging_Fast_Features_Rosenfeld_Dist(uint8 ** X, int i, int width, uint32 ** E, uint32 * T, uint32 ** D, int alpha, RegionStats ** F)
    1095 // ---------------------------------------------------------------------------------------------------------------------------------------------
    1096 {
    1097     MCA_VERBOSE2(printf("[%s]", __func__));
    1098    
    1099 #if PARMERGE
    1100     optimizedBorderLeft_Parallel_Features_Rosenfeld_Dist(E, i, 0, T, D, alpha, F);
    1101 #else
    1102     optimizedBorderLeft_Features_Rosenfeld_Dist(E, i, 0, T, D, alpha, F);
    1103 #endif
    1104    
    1105     for (int j = 1; j < width - 1; j++) {
    1106 #if PARMERGE
    1107         optimizedBorder_Parallel_Features_Rosenfeld_Dist(E, i, j, T, D, alpha, F);
    1108 #else
    1109         optimizedBorder_Features_Rosenfeld_Dist(E, i, j, T, D, alpha, F);
    1110 #endif
    1111     }
    1112    
    1113 #if PARMERGE
    1114     optimizedBorderRight_Parallel_Features_Rosenfeld_Dist(E, i, width - 1, T, D, alpha, F);
    1115 #else
    1116     optimizedBorderRight_Features_Rosenfeld_Dist(E, i, width - 1, T, D, alpha, F);
    1117 #endif
    1118 }
    1119 #endif // FAST && FEATURES
    1120 
    1121 
    1122 #if !FEATURES
    1123 // --------------------------------------------------------------------------------------------------------------------
    1124 static void borderMerging_Rosenfeld_Dist(uint8 ** X, int i, int width, uint32 ** E, uint32 * T, uint32 ** D, int alpha)
    1125 // --------------------------------------------------------------------------------------------------------------------
    1126 {
     930                SetRoot_Rosenfeld(D, r1, eps, alpha, F);
     931                MCA_VERBOSE3(printf("D[%5d] <- %d\n", r1, eps));
     932            }
     933            //if (r2 > 0) {
     934            //    r2 = FindRoot_Dist(D, r2, alpha);
     935            //}
     936            if (r2 > eps && r2 != r1) {
     937            //if (r2 > eps) {
     938                SetRoot_Rosenfeld(D, r2, eps, alpha, F);
     939                MCA_VERBOSE3(printf("D[%5d] <- %d\n", r2, eps));
     940            }
     941            //rx = FindRoot_Dist(D, rx, alpha);
     942            if (rx > eps && rx != r2 && rx != r1) {
     943            //if (rx > eps) {
     944                SetRoot_Rosenfeld(D, rx, eps, alpha, F);
     945                MCA_VERBOSE3(printf("D[%5d] <- %d\n", rx, eps));
     946            }
     947            MCA_VERBOSE3(printf("---------------------------\n"));
     948        }
     949    }
     950}
     951#endif // SLOW
     952
     953
     954
     955// --------------------------------------------------------------------------------------------------------------------------------------
     956static void borderMerging_Rosenfeld_Dist(uint8 ** X, int i, int width, uint32 ** E, uint32 * T, uint32 ** D, int alpha, RegionStats ** F)
     957// --------------------------------------------------------------------------------------------------------------------------------------
     958{
     959#if FAST
     960    borderMerging_Fast_Rosenfeld_Dist(X, i, width, E, T, D, alpha, F);
     961#endif // FAST
    1127962#if SLOW
    1128     borderMerging_Slow_Rosenfeld_Dist(X, i, width, E, T, D, alpha);
    1129 #elif FAST
    1130     borderMerging_Fast_Rosenfeld_Dist(X, i, width, E, T, D, alpha);
    1131 #else
    1132 #error "Please define SLOW or FAST for the Rosenfeld version"
    1133 #endif
    1134 }
    1135 #endif // !FEATURES
    1136 
    1137 
    1138 #if FEATURES
    1139 // -----------------------------------------------------------------------------------------------------------------------------------------------
    1140 static void borderMerging_Features_Rosenfeld_Dist(uint8 ** X, int i, int width, uint32 ** E, uint32 * T, uint32 ** D, int alpha, RegionStats ** F)
    1141 // -----------------------------------------------------------------------------------------------------------------------------------------------
    1142 {
    1143 #if SLOW
    1144     borderMerging_Slow_Features_Rosenfeld_Dist(X, i, width, E, T, D, alpha, F);
    1145 #elif FAST
    1146     borderMerging_Fast_Features_Rosenfeld_Dist(X, i, width, E, T, D, alpha, F);
    1147 #else
    1148 #error "Please define SLOW or FAST for the Rosenfeld version"
    1149 #endif
    1150 }
    1151 #endif // FEATURES
     963    borderMerging_Slow_Rosenfeld_Dist(X, i, width, E, T, D, alpha, F);
     964#endif // SLOW
     965}
    1152966
    1153967
    … …  
    13831197    return ne;
    13841198}
    1385 #endif // FAST
    1386 
    1387 
    1388 #if FAST
     1199
     1200// FAST
     1201
    13891202// ----------------------------------------------------------------------------------------------
    13901203static uint32 optimizedAccessRight_DT_Rosenfeld(uint32 ** E, int i, int j, uint32 * T, uint32 ne)
    … …  
    14161229    return ne;
    14171230}
    1418 #endif // FAST
    1419 
    1420 
    1421 #if FAST
     1231
     1232// FAST
     1233
    14221234// -----------------------------------------------------------------------------------------
    14231235static uint32 optimizedAccess_DT_Rosenfeld(uint32 ** E, int i, int j, uint32 * T, uint32 ne)
    … …  
    14671279    return ne;
    14681280}
    1469 #endif // FAST
    1470 
    1471 
    1472 
    1473 #if FAST
     1281
     1282// FAST
     1283
    14741284// --------------------------------------------------------------------------------------------------------
    14751285static uint32 lineLabeling_Fast_Rosenfeld(uint8 ** X, int i, int width, uint32 ** E, uint32 * T, uint32 ne)
    … …  
    15171327#elif FAST
    15181328    return lineLabeling_Fast_Rosenfeld(X, i, width, E, T, ne);
    1519 #else
    1520 #error "Please define SLOW or FAST for the Rosenfeld version"
    15211329#endif
    15221330}
    … …  
    15391347
    15401348
    1541 #if !FEATURES
    1542 // ---------------------------------------------------------------------
    1543 static void solveTable_Range_Rosenfeld(uint32 * T, uint32 e0, uint32 e1)
    1544 // ---------------------------------------------------------------------
    1545 {
    1546     uint32 e, r;
    1547    
    1548     for (e = e0; e <= e1; e++) {
    1549         r = T[T[e]];
    1550         if (r < e) {
    1551             T[e] = r; // racine de la classe d'equivalence
    1552         }
    1553     }
    1554 }
    1555 #endif // !FEATURES
    1556 
    1557 
    1558 #if FEATURES
    1559 // ----------------------------------------------------------------------------------------------------------
    1560 static void solveTable_solveFeatures_Range_Rosenfeld(uint32 * T, uint32 e0, uint32 e1, RegionStats * Stats)
    1561 // ----------------------------------------------------------------------------------------------------------
     1349// ------------------------------------------------------------------------------------------
     1350static void solveTable_Range_Rosenfeld(uint32 * T, uint32 e0, uint32 e1, RegionStats * Stats)
     1351// ------------------------------------------------------------------------------------------
    15621352{
    15631353    uint32 e, r;
    … …  
    15681358        if (r < e) {
    15691359            T[e] = r; // racine de la classe d'equivalence
     1360#if FEATURES
    15701361            RegionStats_Accumulate_Stats1_From_Index(Stats, r, e);
    1571         }
    1572     }
    1573 }
    1574 #endif // FEATURES
    1575 
    1576 
    1577 #if !FEATURES
    1578 // -------------------------------------
    1579 void MCA_Label_Rosenfeld_PAR1(MCA * mca)
    1580 // -------------------------------------
     1362#endif
     1363        }
     1364    }
     1365}
     1366
     1367
     1368// --------------------------------------------
     1369static void MCA_Label_Rosenfeld_PAR1(MCA * mca)
     1370// --------------------------------------------
    15811371{
    15821372    if (mca->p == 0) {
    1583         printf("*** %s ***\n", __func__);
    1584     }
    1585    
    1586     CLOCK_THREAD_START_STEP(mca->p, 0);
     1373        MCA_VERBOSE2(printf("*** %s ***\n", __func__));
     1374    }
     1375   
    15871376
    15881377    int i0 = mca->i0;
    15891378    int i1 = mca->i1;
    1590     int width = mca->width;
     1379    int width = mca->width;
     1380
    15911381    uint32 e0 = mca->e0;
    15921382    uint32 e1 = mca->e1;
    … …  
    15981388    uint32 ** E = mca->E;
    15991389    uint32 *  T = mca->T;
    1600 
     1390    RegionStats * stats = mca->stats;
     1391
     1392    // reset sous optimal (pour le moment = voir region32)
    16011393    if (mca->p == 0) {
    16021394        set_ui32vector_j(T, e0 - 1, e1); // car e0 = 1, on a besoin que T[0] = 0 pour FindRoot
     1395#if FEATURES
     1396        zero_RegionStatsVector(stats, e0 - 1, e1);
     1397#endif
    16031398    }
    16041399    else {
    16051400        set_ui32vector_j(T, e0, e1);
    1606     }
    1607 
    1608     MCA_VERBOSE2(display_ui8matrix_positive(X, i0, i1, 0, width - 1, 5, "Xp"); printf("\n"));
     1401#if FEATURES
     1402        zero_RegionStatsVector(stats, e0, e1);
     1403#endif
     1404    }
     1405
     1406    if (mca->p == 0) {
     1407        MCA_VERBOSE3(display_ui8matrix_positive(X, i0, i1, 0, width - 1, 5, "Xp"); printf("\n"));
     1408    }
     1409
     1410    // ---------------------------- //
     1411    // -- Etiquetage d'une bande -- //
     1412    // ---------------------------- //
     1413
     1414    CLOCK_THREAD_START_STEP(mca->p, 0);
    16091415
    16101416    ne = line0Labeling_Rosenfeld(X, i0, width, E, T, ne);
     1417#if FEATURES
     1418    lineFeaturesComputation(E, i0, width, stats);
     1419#endif
     1420
    16111421    for (int i = i0 + 1; i <= i1; i++) {
    1612         ne = lineLabeling_Rosenfeld(X, i, width, E, T, ne);
    1613     }
    1614 
    1615     MCA_VERBOSE2(display_ui32matrix_positive(E, i0, i1, 0, width - 1, 5, "Ep"); printf("\n"));
     1422        ne = lineLabeling_Rosenfeld(X, i, width, E, T, ne); // Slow or Fast
     1423#if FEATURES
     1424        lineFeaturesComputation(E, i, width, stats);
     1425#endif
     1426    }
     1427    mca->ne = ne; //plus grande etiquette de l'intervalle [e0..e1]
     1428
    16161429    if (mca->p == 0) {
    1617         MCA_VERBOSE2(display_ui32vector_number(T, e0, ne, "%5d", "Tp_avant"));
    1618     }
    1619 
    1620     // fermeture transitive sans pack
    1621     solveTable_Range_Rosenfeld(T, e0, ne);
    1622     mca->ne = ne; // Plus grande etiquette de l'intervalle [e0..e1]
    1623 
    1624     MCA_VERBOSE2(nr = countTable_Range_Rosenfeld(T, e0, ne));
    1625     MCA_VERBOSE2(printf("p = %d : e = [%d..%d] -> ne = %d -> nr = %d\n", mca->p, e0, ne, (ne - e0 + 1), nr));
     1430        MCA_VERBOSE3(printf("ne = %d\n", ne));
     1431        MCA_VERBOSE3(display_ui32matrix_positive(E, i0, i1, 0, width - 1, 5, "Ep"); printf("\n"));
     1432        MCA_VERBOSE3(display_ui32vector_number(T, e0, ne, "%5d", "Tp_avant"));
     1433    }
     1434
     1435    // ------------------------------------------------------ //
     1436    // -- Fermeture transitive sans pack de chaque table T -- //
     1437    // ------------------------------------------------------ //
     1438
     1439    solveTable_Range_Rosenfeld(T, e0, ne, stats);
     1440
    16261441    if (mca->p == 0) {
    1627         MCA_VERBOSE2(display_ui32vector_number(T, e0, ne, "%5d", "Tp_apres"));
    1628     }
    1629    
     1442        MCA_VERBOSE3(nr = countTable_Range_Rosenfeld(T, e0, ne);
     1443                     printf("p = %d : e = [%d..%d] -> ne = %d -> nr = %d\n", mca->p, e0, ne, (ne - e0 + 1), nr));
     1444        MCA_VERBOSE3(display_ui32vector_number(T, e0, ne, "%5d", "Tp_apres"));
     1445    }
    16301446    CLOCK_THREAD_END_STEP(mca->p, 0);
    16311447}
    1632 #endif // !FEATURES
    1633 
    1634 
    1635 #if !FEATURES
    1636 // -------------------------------------
    1637 void MCA_Label_Rosenfeld_PYR2(MCA * mca)
    1638 // -------------------------------------
    1639 {
    1640     // input
     1448
     1449
     1450
     1451#if PARMERGE
     1452// -----------------------------------------------------
     1453static void MCA_Label_Rosenfeld_PAR2(MCA * mca)
     1454// -----------------------------------------------------
     1455{
    16411456    int p = mca->p;
    16421457    int nb_level = mca->nb_level;
    16431458
    16441459    if (mca->p == 0) {
    1645         printf("*** %s ***\n", __func__);
     1460        MCA_VERBOSE2(printf("*** %s ***\n", __func__));
    16461461    }
    16471462   
    16481463    // ------------------------------
    1649     // -- pyramidal border merging --
     1464    // -- parallel border merging --
    16501465    // ------------------------------
    16511466   
    … …  
    16621477    uint32 *  T = mca->T;
    16631478    uint32 ** D = mca->D;
    1664 
    1665     CLOCK_THREAD_START_STEP(p, 1);
    1666 #if PYR_BARRIERS
    1667     // Version optimisée qui fait faire un break aux processeurs qui n'ont plus
    1668     // à faire de merge.
    1669     // Implique de pré-calculer le nombre de threads à chaque barriÚre
    1670     if (p != 0) { // thread 0 never has any merge to do
    1671         int been_active = 0;
    1672         for (int level = 0; level < nb_level; level++) {
    1673             if ((p + (1 << level)) % (1 << (level + 1)) == 0) {
    1674                 borderMerging_Rosenfeld_Dist(X, i, width, E, T, D, alpha);  // en (i) et (i-1)
    1675                 been_active = 1;
    1676             }
    1677             else if (been_active) {
    1678                 break;
    1679             }
    1680             pthread_barrier_wait(&mca->barriers[level]);
    1681         }
    1682     }
    1683     pthread_barrier_wait(&main_barrier);
    1684 #else
    1685     for (int level = 1; level <= nb_level; level++) {
    1686         if ((p + (1 << (level - 1))) % (1 << level) == 0) {
    1687             // thread actif
    1688             borderMerging_Rosenfeld_Dist(X, i, width, E, T, D, alpha);  // en (i) et (i-1)
    1689         }
    1690         pthread_barrier_wait(&main_barrier);
    1691     }
    1692 #endif
    1693     CLOCK_THREAD_END_STEP(p, 1);
    1694    
    1695 
    1696     // ---------------------------------
    1697     // -- parallel transitive closure --
    1698     // ---------------------------------
    1699    
    1700     CLOCK_THREAD_START_STEP(p, 2);
    1701     for (uint32 e = e0; e <= e1; e++) {
    1702         uint32 r = T[e]; // acces local
    1703         if (r < e) {
    1704             r = FindRoot_Dist(D, e, alpha); // acces distant
    1705             T[e] = r; // @QM était en dehors du "if" (je pense que déjà demandé)
    1706         }
    1707         MCA_VERBOSE2(printf("p%d : T[%d] <- %d\n", p, e, r));
    1708     }
    1709     CLOCK_THREAD_END_STEP(p, 2);
    1710 }
    1711 #endif // !FEATURES
    1712 
    1713 
    1714 // -------------------------------------
    1715 void MCA_Label_Rosenfeld_PAR3(MCA * mca)
    1716 // -------------------------------------
    1717 {
    1718     // input
    1719     if (mca->p == 0) {
    1720         printf("*** %s ***\n", __func__);
    1721     }
    1722    
    1723     int i0 = mca->i0;
    1724     int i1 = mca->i1;
    1725     int j0 = 0;
    1726     int j1 = mca->width - 1;
    1727 
    1728     uint32 ** E = mca->E;
    1729     uint32 * T = mca->T;
    1730 
    1731     CLOCK_THREAD_START_STEP(mca->p, 3);
    1732     for (int i = i0; i <= i1; i++) {
    1733         for (int j = j0; j <= j1; j++) {
    1734             uint32 e = E[i][j];
    1735             if (e != 0) {
    1736                 E[i][j] = T[e];
    1737             }
    1738         }
    1739     }
    1740     CLOCK_THREAD_END_STEP(mca->p, 3);
    1741 }
    1742 
    1743 
    1744 #if FEATURES
    1745 // -----------------------------------------------------
    1746 static void MCA_Label_Features_Rosenfeld_PAR1(MCA * mca)
    1747 // -----------------------------------------------------
    1748 {
    1749     if (mca->p == 0) {
    1750         printf("*** %s ***\n", __func__);
    1751     }
    1752    
    1753     CLOCK_THREAD_START_STEP(mca->p, 0);
    1754 
    1755     int i0 = mca->i0;
    1756     int i1 = mca->i1;
    1757     int width = mca->width;
    1758 
    1759     uint32 e0 = mca->e0;
    1760     uint32 e1 = mca->e1;
    1761     uint32 ne = e0 - 1;
    1762     uint32 nr = 0;
    1763 
    1764     // local memory zones
    1765     uint8 **  X = mca->X;
    1766     uint32 ** E = mca->E;
    1767     uint32 *  T = mca->T;
    1768 
    1769     RegionStats * stats = mca->stats;
    1770 
    1771     // reset sous optimal (pour le moment = voir region32)
    1772     if (mca->p == 0) {
    1773         set_ui32vector_j(T, e0 - 1, e1); // car e0 = 1, on a besoin que T[0] = 0 pour FindRoot
    1774         zero_RegionStatsVector(stats, e0 - 1, e1);
    1775     }
    1776     else {
    1777         set_ui32vector_j(T, e0, e1);
    1778         zero_RegionStatsVector(stats, e0, e1);
    1779     }
    1780 
    1781     if (mca->p == 0) {
    1782         MCA_DISPLAY2(display_ui8matrix_positive(X, i0, i1, 0, width - 1, 5, "Xp"); printf("\n"));
    1783     }
    1784 
    1785     // ---------------------------- //
    1786     // -- Etiquetage d'une bande -- //
    1787     // ---------------------------- //
    1788 
    1789     ne = line0Labeling_Rosenfeld(X, i0, width, E, T, ne);
    1790     lineFeaturesComputation(E, i0, width, stats);
    1791 
    1792     for (int i = i0 + 1; i <= i1; i++) {
    1793         ne = lineLabeling_Rosenfeld(X, i, width, E, T, ne); // Slow or Fast
    1794         lineFeaturesComputation(E, i, width, stats);
    1795     }
    1796     mca->ne = ne; //plus grande etiquette de l'intervalle [e0..e1]
    1797 
    1798     if (mca->p == 0) {
    1799         MCA_VERBOSE2(printf("ne = %d\n", ne));
    1800         MCA_DISPLAY2(display_ui32matrix_positive(E, i0, i1, 0, width - 1, 5, "Ep"); printf("\n"));
    1801         MCA_DISPLAY2(display_ui32vector_number(T, e0, ne, "%5d", "Tp_avant"));
    1802     }
    1803 
    1804     // ------------------------------------------------------ //
    1805     // -- Fermeture transitive sans pack de chaque table T -- //
    1806     // ------------------------------------------------------ //
    1807 
    1808     solveTable_solveFeatures_Range_Rosenfeld(T, e0, ne, stats);
    1809 
    1810     if (mca->p == 0) {
    1811         MCA_VERBOSE2(nr = countTable_Range_Rosenfeld(T, e0, ne);
    1812                 printf("p = %d : e = [%d..%d] -> ne = %d -> nr = %d\n", mca->p, e0, ne, (ne - e0 + 1), nr));
    1813         MCA_DISPLAY2(display_ui32vector_number(T, e0, ne, "%5d", "Tp_apres"));
    1814     }
    1815     CLOCK_THREAD_END_STEP(mca->p, 0);
    1816 }
    1817 #endif // FEATURES
    1818 
    1819 
    1820 #if FEATURES && !PARMERGE
    1821 // -----------------------------------------------------
    1822 static void MCA_Label_Features_Rosenfeld_PYR2(MCA * mca)
    1823 // -----------------------------------------------------
    1824 {
    1825     int p = mca->p;
    1826     int nb_level = mca->nb_level;
    1827 
    1828     if (mca->p == 0) {
    1829         printf("*** %s ***\n", __func__);
    1830     }
    1831    
    1832     // ------------------------------
    1833     // -- pyramidal border merging --
    1834     // ------------------------------
    1835    
    1836     // local variables
    1837     int i = mca->i0;
    1838     int width = mca->width;
    1839     int alpha = mca->alpha;
    1840     uint32 e0 = mca->e0;
    1841     uint32 e1 = mca->ne;
    1842 
    1843     // local memory zones
    1844     uint8 **  X = mca->X;
    1845     uint32 ** E = mca->E;
    1846     uint32 *  T = mca->T;
    1847     uint32 ** D = mca->D;
    1848     RegionStats ** F = mca->F;
    1849 
    1850     CLOCK_THREAD_START_STEP(p, 1);
    1851 #if PYR_BARRIERS
    1852     // Version optimisée qui fait faire un break aux processeurs qui n'ont plus
    1853     // à faire de merge.
    1854     // Implique de pré-calculer le nombre de threads à chaque barriÚre
    1855     if (p != 0) { // thread 0 never has any merge to do
    1856         int been_active = 0;
    1857         for (int level = 0; level < nb_level; level++) {
    1858             if ((p + (1 << level)) % (1 << (level + 1)) == 0) {
    1859                 borderMerging_Features_Rosenfeld_Dist(X, i, width, E, T, D, alpha, F);  // (i) et (i-1)
    1860                 been_active = 1;
    1861             }
    1862             else if (been_active) {
    1863                 break;
    1864             }
    1865             pthread_barrier_wait(&mca->barriers[level]);
    1866         }
    1867     }
    1868     pthread_barrier_wait(&main_barrier);
    1869 #else
    1870     for (int level = 1; level <= nb_level; level++) {
    1871         if ((p + (1 << (level - 1))) % (1 << level) == 0) {
    1872             // thread actif
    1873             borderMerging_Features_Rosenfeld_Dist(X, i, width, E, T, D, alpha, F);  // (i) et (i-1)
    1874         }
    1875         pthread_barrier_wait(&main_barrier);
    1876     }
    1877 #endif
    1878     CLOCK_THREAD_END_STEP(p, 1);
    1879 
    1880 
    1881     /**
    1882      * To remove?
    1883     // -- Affichage de debug
    1884     if (mca->p == 0) {
    1885         MCA_VERBOSE1(puts("-----------------------------"));
    1886         MCA_VERBOSE1(puts("[PYR2]: avant pack sequentiel"));
    1887         MCA_VERBOSE1(puts("-----------------------------"));
    1888    
    1889         for (int p = 0; p < mca->np; p++) {
    1890    
    1891             MCA* mca_par = mcas[p];
    1892             uint32 e0 = mca_par->e0;
    1893             uint32 e1 = mca_par->ne;
    1894            
    1895             uint32*  T = mca_par->T;
    1896             RegionStats* Stats = mca_par->Stats;
    1897        
    1898             RegionStats_DisplayStats_Sparse(T, e0, e1, Stats, NULL);
    1899             puts("");
    1900         }
    1901     }
    1902     */
    1903 
    1904     // ---------------------------------
    1905     // -- parallel transitive closure --
    1906     // ---------------------------------
    1907     // identique a la version sans Features
    1908      
    1909     CLOCK_THREAD_START_STEP(p, 2);
    1910     for (uint32 e = e0; e <= e1; e++) {
    1911         uint32 r = T[e]; // acces local
    1912         if (r < e) {
    1913             r = FindRoot_Dist(D, e, alpha); // acces distant
    1914             T[e] = r;
    1915         }
    1916         MCA_VERBOSE2(printf("p%d : T[%d] <- %d\n", p, e, r));
    1917     }
    1918     CLOCK_THREAD_END_STEP(p, 2);
    1919 
    1920     // To avoid uninitialized accesses
    1921     CLOCK_THREAD_START_STEP(p, 3);
    1922     CLOCK_THREAD_END_STEP(p, 3);
    1923 }
    1924 #endif // FEATURES && !PARMERGE
    1925 
    1926 
    1927 #if FEATURES && PARMERGE
    1928 // -----------------------------------------------------
    1929 static void MCA_Label_Features_Rosenfeld_PAR2(MCA * mca)
    1930 // -----------------------------------------------------
    1931 {
    1932     int p = mca->p;
    1933     int nb_level = mca->nb_level;
    1934 
    1935     if (mca->p == 0) {
    1936         printf("*** %s ***\n", __func__);
    1937     }
    1938    
    1939     // ------------------------------
    1940     // -- parallel border merging --
    1941     // ------------------------------
    1942    
    1943     // local variables
    1944     int i = mca->i0;
    1945     int width = mca->width;
    1946     int alpha = mca->alpha;
    1947     uint32 e0 = mca->e0;
    1948     uint32 e1 = mca->ne;
    1949 
    1950     // local memory zones
    1951     uint8 **  X = mca->X;
    1952     uint32 ** E = mca->E;
    1953     uint32 *  T = mca->T;
    1954     uint32 ** D = mca->D;
    19551479    RegionStats ** F = mca->F;
    19561480
    19571481    CLOCK_THREAD_START_STEP(p, 1);
    19581482    if (p != 0) { // thread 0 never has any merge to do
    1959         borderMerging_Features_Rosenfeld_Dist(X, i, width, E, T, D, alpha, F);  // (i) et (i-1)
     1483        borderMerging_Rosenfeld_Dist(X, i, width, E, T, D, alpha, F);  // (i) et (i-1)
    19601484    }
    19611485    pthread_barrier_wait(&main_barrier);
    … …  
    19751499            T[e] = r;
    19761500        }
    1977         MCA_VERBOSE2(printf("p%d : T[%d] <- %d\n", p, e, r));
     1501        MCA_VERBOSE3(printf("p%d : T[%d] <- %d\n", p, e, r));
    19781502    }
    19791503    CLOCK_THREAD_END_STEP(p, 2);
    … …  
    19831507    CLOCK_THREAD_END_STEP(p, 3);
    19841508}
    1985 #endif // FEATURES
    1986 
    1987 
    1988 
    1989 
    1990 #if !FEATURES
    1991 // =============================================================
    1992 #if TARGET_OS == GIETVM
    1993 __attribute__((constructor)) void MCA_Label_Rosenfeld(MCA * mca)
     1509#endif // PARMERGE
     1510
     1511
     1512#if !PARMERGE
     1513// --------------------------------------------
     1514static void MCA_Label_Rosenfeld_PYR2(MCA * mca)
     1515// --------------------------------------------
     1516{
     1517    // input
     1518    int p = mca->p;
     1519    int nb_level = mca->nb_level;
     1520
     1521    if (mca->p == 0) {
     1522        MCA_VERBOSE2(printf("*** %s ***\n", __func__));
     1523    }
     1524   
     1525    // ------------------------------
     1526    // -- pyramidal border merging --
     1527    // ------------------------------
     1528   
     1529    // local variables
     1530    int i = mca->i0;
     1531    int width = mca->width;
     1532    int alpha = mca->alpha;
     1533    uint32 e0 = mca->e0;
     1534    uint32 e1 = mca->ne;
     1535
     1536    // local memory zones
     1537    uint8 **  X = mca->X;
     1538    uint32 ** E = mca->E;
     1539    uint32 *  T = mca->T;
     1540    uint32 ** D = mca->D;
     1541    RegionStats ** F = mca->F;
     1542
     1543    CLOCK_THREAD_START_STEP(p, 1);
     1544#if PYR_BARRIERS
     1545    // Version optimisée qui fait faire un break aux processeurs qui n'ont plus
     1546    // à faire de merge.
     1547    // Implique de pré-calculer le nombre de threads à chaque barriÚre
     1548    if (p != 0) { // thread 0 never has any merge to do
     1549        int been_active = 0;
     1550        for (int level = 0; level < nb_level; level++) {
     1551            if ((p + (1 << level)) % (1 << (level + 1)) == 0) {
     1552                borderMerging_Rosenfeld_Dist(X, i, width, E, T, D, alpha, F);  // (i) et (i-1)
     1553                been_active = 1;
     1554            }
     1555            else if (been_active) {
     1556                break;
     1557            }
     1558            pthread_barrier_wait(&mca->barriers[level]);
     1559        }
     1560    }
     1561    pthread_barrier_wait(&main_barrier);
    19941562#else
    1995 void MCA_Label_Rosenfeld(MCA * mca)
     1563    for (int level = 1; level <= nb_level; level++) {
     1564        if ((p + (1 << (level - 1))) % (1 << level) == 0) {
     1565            // thread actif
     1566            borderMerging_Rosenfeld_Dist(X, i, width, E, T, D, alpha, F);  // (i) et (i-1)
     1567        }
     1568        pthread_barrier_wait(&main_barrier);
     1569    }
    19961570#endif
    1997 // =============================================================
    1998 {
    1999 #if TARGET_OS == GIETVM
    2000     unsigned int x, y, lpid;
    2001     giet_proc_xyp(&x, &y, &lpid);
    2002     // Mettre à jour mca->p en fonction de x, y, lpid
    2003     // pour que les allocations faites par le main soient locales,
    2004     // i.e.
    2005     mca->p = (x * Y_SIZE + y) * NB_PROCS_MAX + lpid;
    2006     // We have :
    2007     // mca->p = 4 pour (x = 0, y = 1, lpid = 0)
    2008     // mca->p = 5 pour (x = 0, y = 1, lpid = 1)
    2009     MCA_VERBOSE2(printf("mca->p = %d pour (x = %d, y = %d, lpid = %d)\n", mca->p, x, y, lpid));
    2010 #endif
    2011 
    2012     CLOCK_THREAD_START(mca->p);
    2013     CLOCK_THREAD_COMPUTE_START(mca->p);
    2014 
    2015     MCA_Scatter_ImageX(mca);
    2016     pthread_barrier_wait(&main_barrier);
    2017 
    2018     MCA_Label_Rosenfeld_PAR1(mca);
    2019     pthread_barrier_wait(&main_barrier);
    2020    
    2021     MCA_Label_Rosenfeld_PYR2(mca);
    2022     pthread_barrier_wait(&main_barrier);
    2023    
    2024     MCA_Label_Rosenfeld_PAR3(mca);
    2025     pthread_barrier_wait(&main_barrier);
    2026 
    2027     MCA_Gather_ImageL(mca);
    2028     pthread_barrier_wait(&main_barrier);
    2029 
    2030     CLOCK_THREAD_COMPUTE_END(mca->p);
    2031     CLOCK_THREAD_END(mca->p);
    2032 
    2033 #if TARGET_OS == GIETVM
    2034     if (mca->p != 0) {
    2035         exit(0);
    2036     }
    2037 #endif
     1571    CLOCK_THREAD_END_STEP(p, 1);
     1572   
     1573
     1574    // ---------------------------------
     1575    // -- parallel transitive closure --
     1576    // ---------------------------------
     1577   
     1578    CLOCK_THREAD_START_STEP(p, 2);
     1579    for (uint32 e = e0; e <= e1; e++) {
     1580        uint32 r = T[e]; // acces local
     1581        if (r < e) {
     1582            r = FindRoot_Dist(D, e, alpha); // acces distant
     1583            T[e] = r;
     1584        }
     1585        MCA_VERBOSE3(printf("p%d : T[%d] <- %d\n", p, e, r));
     1586    }
     1587    CLOCK_THREAD_END_STEP(p, 2);
    20381588}
    20391589#endif // !FEATURES
    20401590
    20411591
    2042 #if FEATURES
     1592// -------------------------------------
     1593void MCA_Label_Rosenfeld_PAR3(MCA * mca)
     1594// -------------------------------------
     1595{
     1596    // input
     1597    if (mca->p == 0) {
     1598        MCA_VERBOSE2(printf("*** %s ***\n", __func__));
     1599    }
     1600   
     1601    int i0 = mca->i0;
     1602    int i1 = mca->i1;
     1603    int j0 = 0;
     1604    int j1 = mca->width - 1;
     1605
     1606    uint32 ** E = mca->E;
     1607    uint32 * T = mca->T;
     1608
     1609    CLOCK_THREAD_START_STEP(mca->p, 3);
     1610    for (int i = i0; i <= i1; i++) {
     1611        for (int j = j0; j <= j1; j++) {
     1612            uint32 e = E[i][j];
     1613            if (e != 0) {
     1614                E[i][j] = T[e];
     1615            }
     1616        }
     1617    }
     1618    CLOCK_THREAD_END_STEP(mca->p, 3);
     1619}
     1620
     1621
     1622
    20431623// ======================================================================
    20441624#if TARGET_OS == GIETVM
    2045 __attribute__((constructor)) void * MCA_Label_Features_Rosenfeld(void * arg)
     1625__attribute__((constructor)) void * MCA_Label_Rosenfeld(void * arg)
    20461626#else
    2047 void * MCA_Label_Features_Rosenfeld(void * arg)
     1627void * MCA_Label_Rosenfeld(void * arg)
    20481628#endif
    20491629// ======================================================================
    … …  
    20601640    // mca->p = 4 pour (x = 0, y = 1, lpid = 0)
    20611641    // mca->p = 5 pour (x = 0, y = 1, lpid = 1)
    2062     MCA_VERBOSE2(printf("mca->p = %d pour (x = %d, y = %d, lpid = %d)\n", mca->p, x, y, lpid));
     1642    MCA_VERBOSE3(printf("mca->p = %d pour (x = %d, y = %d, lpid = %d)\n", mca->p, x, y, lpid));
    20631643#endif
    20641644
    … …  
    20691649    pthread_barrier_wait(&main_barrier);
    20701650
    2071     MCA_Label_Features_Rosenfeld_PAR1(mca);
     1651    MCA_Label_Rosenfeld_PAR1(mca);
    20721652    pthread_barrier_wait(&main_barrier);
    20731653   
    20741654#if PARMERGE
    2075     MCA_Label_Features_Rosenfeld_PAR2(mca);
     1655    MCA_Label_Rosenfeld_PAR2(mca);
    20761656#else
    2077     MCA_Label_Features_Rosenfeld_PYR2(mca);
     1657    MCA_Label_Rosenfeld_PYR2(mca);
    20781658#endif
    20791659    pthread_barrier_wait(&main_barrier);
    … …  
    20871667    CLOCK_THREAD_COMPUTE_END(mca->p);
    20881668 
     1669#if FEATURES
    20891670    if (display_features) {
    20901671        if (mca->p == 0) {
    20911672            int i = 1;
    2092             printf("[STATS]\n");
     1673            MCA_VERBOSE1(printf("[STATS]\n"));
    20931674            for (int p = 0; p < mca->np; p++) {
    20941675                MCA * mca_par = mca->mca->mcas[p];
    … …  
    20971678                uint32 * T = mca_par->T;
    20981679                RegionStats * stats = mca_par->stats;
    2099                 RegionStats_DisplayStats_Sparse(T, e0, e0 + ne, stats, NULL, &i);
    2100             }
    2101             printf("[/STATS]\n");
    2102         }
    2103     }
     1680                MCA_VERBOSE1(RegionStats_DisplayStats_Sparse(T, e0, e0 + ne, stats, NULL, &i));
     1681            }
     1682            MCA_VERBOSE1(printf("[/STATS]\n"));
     1683        }
     1684    }
     1685#endif
    21041686
    21051687    CLOCK_THREAD_END(mca->p);
    … …  
    21131695    return NULL;
    21141696}
    2115 #endif // FEATURES
    21161697
    21171698
Note: See TracChangeset for help on using the changeset viewer.