Maps and openMP parallel dispatching

Question

I'm trying to parallelize a piece of code but there are some problems, the critical part for the insertion in a shared map create a bottleneck in my execution. There is a way to parallelize the insertion?

Second problem regards how to iterate with openMP on a maps a predefined number of times. Here is the code, I'm using g++-5 on Clion.

else if (PERF_ROWS <= MAX_ROWS && function_switch == false)
{
    int array_dist_perf[PERF_ROWS];
    int array_dist[MAX_ROWS];

    multimap<float, int> temp_map;

    #pragma omp parallel for schedule(dynamic) private(array_dist_perf) shared(temp_map)
    for (int i = 0; i < MAX_COLUMNS; i++)
    {
        if (i % PERF_CLMN == 1) continue;

        for (int j = 0; j < PERF_ROWS; j++) //truncation perforation
        {
            array_dist_perf[j] = abs(input[j] - input_matrix[j][i]);
        }

        float av = mean(PERF_ROWS, array_dist_perf);

        float temp_score = score_func(av);

        #pragma omp critical(map_update)
        temp_map.insert({temp_score, i});
    }

    map<float,int>::reverse_iterator rit;

    int iter = 0;

    #pragma omp parallel for schedule(dynamic) private(array_dist) shared(iter)
    for (rit=temp_map.rbegin(); rit!=temp_map.rend(); rit++)
    {
        int s = rit->second;

        for (int k = 0; k < MAX_ROWS; k++)
        {
            array_dist[k] = abs(input[k] - input_matrix[k][s]);
        }

        float av_real = mean(MAX_ROWS, array_dist);

        float score_real = score_func(av_real);

        rank_function(score_real, s);

        #pragma omp atomic
        iter++;

        if (iter == THRESHOLD_NUM)

            break;
    }
}

Why are you using `schedule(dynamic)`? Your iteration workloads don't seem to be wildly varying to me. — Klaas van Gend, Apr 14 '16 at 14:40
Also: you are performing an 'early exit' (the `break`). You should use the `cancel` and `cancellation_point` mechanism of OpenMP4 - otherwise, behavior of your code is undefined. — Klaas van Gend, Apr 14 '16 at 14:42
I'm using schedule(dynamic) for the continue part that makes me skip some iterations. I'm using break because I don't know how to iterate on a map an arbitrary number of times and not from begin to end. — CIVI89, Apr 14 '16 at 14:47
But you are right @KlaasvanGend in the map loop a can avoid to use dynamic...but what do you mean cancel/cancellation point? Sorry is my first day openmp. — CIVI89, Apr 14 '16 at 15:00
@CIV89 See e.g. https://software.intel.com/en-us/node/524512 . There's a specific `cancel` clause in omp that will trigger an early exit. To make the other threads follow the exit, you define cancellation points, see https://software.intel.com/en-us/node/524513 . — Klaas van Gend, Apr 19 '16 at 12:52

score 2 · Accepted Answer · edited May 23 '17 at 11:59

2

In Open MP 4 (which should be supperted by g++5) it is possible to define your own reduction. I dont want to make some unneccesarry duplication, so please look at this answer: C++ OpenMP Parallel For Loop - Alternatives to std::vector

If i understand your problem correct, you can use order and schedule(static, chuncksize) where chunksize is the number of iterations a thread gets.

edited May 23 '17 at 11:59

Community

1
1

answered Apr 14 '16 at 12:32

Mehno

868
2
8
21

The problem is that I have to use an ordered map, not a vector. OpenMP seems to be not capable to dispatch in parallel the insertions in an ordered multi map, unless i mark this operation as critical. I can use the same reduction also for the map? Thanks anyway for your answer. – CIVI89 Apr 14 '16 at 12:58
Ok I understand the concept, but I don't know practically how to declare a reduction for the insertion in a map. For what concern the second part I did not mean number of iterations per thread, I simply mean number of total iterations on the map, in a way to avoid the break. – CIVI89 Apr 14 '16 at 14:25
I didn't tried it now, because i use in the moment the MVSC, but why is it not possible to change in the example the std::vector with your map?? – Mehno Apr 14 '16 at 14:51
I don't know how to complete this #pragma omp declare reduction (merge : std::multimap :.....) – CIVI89 Apr 14 '16 at 14:53
after that comes the operation you want to reduce, in your case insert. Where do you want to insert something? In your output. So write omp_out.insert(omp_in.begin(),omp_in.end()) – Mehno Apr 14 '16 at 14:59
Ok seems to work, I have to leave temp_map.insert({temp_score, i}) and to delete the critical part right? Sorry is my first day openmp =) – CIVI89 Apr 14 '16 at 15:06
Everything is allright. Yeah, exeactly. Just go on learning ;) This little trick with the reduction is sometimes really useful. I learned a lot from: https://computing.llnl.gov/tutorials/openMP/ The reduction part isn't covered, cause it's new in OpenMP 4 – Mehno Apr 14 '16 at 15:10

Maps and openMP parallel dispatching

1 Answers1