mercredi 2 novembre 2016

Parallel Algorithm for calculating the maximum difference

I am currently implementing an parallel algorithm for calculating the maximum difference between two elements such that the smaller number appears before the larger number. I am using the parallel_invoke from the tbb library to achieve this. My implementation is as following

int calculateMaxDiff(int *src, int start, int end){
    int maxVal = -1;
    int maxRight = src[end -1];

    for(int i = end - 2; i >= start; i--){
        if(src[i] > maxRight){
            maxRight = src[i];
        }else{
            int diff = maxRight - src[i];
            if(diff > maxVal){
                maxVal = diff;
            }
        }
    }


    return maxVal;
};

int compute_max_diff(int *src, int size)
{
    int half1_diff;
    int half2_diff;

    parallel_invoke([&]{ half1_diff = calculateMaxDiff(src, 0, size/2);},
                    [&]{ half2_diff = calculateMaxDiff(src, size/2, size);});


    int maxDiff = half1_diff + half2_diff;

    return maxDiff;
}

Now for the above code segment i am using the following as the sample array

int src[] = {12, 9, 18, 3, 7, 11, 6, 15, 6, 1, 10};
int size = 11;

For the above sample the output or maximum difference needs to be 12 but i seem to be getting 18. I ran the algorithm sequentially and got the expected result. But once i introduce parallel_invoke i can't seem to be getting the right result.

Aucun commentaire:

Enregistrer un commentaire