1

I'm trying to parallelize the following C function using OpenMP:

struct pixel {
    double r, g, b;
};

double min_dist_sum_parallel(struct pixel *pixels, int n_pixels,
                             struct pixel *centroids, int n_centroids)
{
    double t0 = omp_get_wtime();

    double min_dist_sum = 0.0;

    #pragma omp parallel for reduction(+:min_dist_sum)
    for (int i = 0; i < n_pixels; ++i) {
        int closest_centroid = 0;
        double min_dist = DBL_MAX;

        for (int j = 0; j < n_centroids; ++j) {
            double dr = pixels[i].r - centroids[j].r;
            double dg = pixels[i].g - centroids[j].g;
            double db = pixels[i].b - centroids[j].b;

            double dist = sqrt(dr * dr + dg * dg + db * db);

            if (dist < min_dist) {
                closest_centroid = j;
                min_dist = dist;
            }
        }

        min_dist_sum += min_dist;
    }

    return min_dist_sum;
}

I have tested this on a machine with two CPU cores supporting two hyper-threads each. Limiting the maximum number of OpenMP threads to two by setting the OMP_NUM_THREAD environment variable speeds up the program by about a factor of two (as expected) for adequate problem sizes (e.g. n_pixels = 1000000, n_centroids = 10).

Allowing three threads on the other hand does not yield further performance gains, in fact the program then runs on average about 10% slower than in the two-thread case. Performance for four threads is again similar to performance for two threads.

I believe I understand why this is happening: because no especially computationally expensive operations are performed between memory accesses, multiple hyper-threads on the same CPU core are unable to effectively share the workload.

Is this explanation sound? In any case I don't understand how this would explain three OpenMP threads being slower than either two or four.

3
  • 2
    Please edit your question to include your system specifications, compilation details, and specific measurement results (numbers!).
    – Zulan
    Apr 12, 2018 at 19:47
  • As Zulan pointed out, we would need to know a lot more about what you are doing to give more than a guess about the answer you request. Common possibilities for increasing number of threads reducing performance might be exceeding cache capacity or causing the thread placement to rotate among cores, reducing cache effectiveness. You should test with and without affinity (e.g. OMP_PLACES=cores) or tell us if your OpenMP doesn't support it.
    – tim18
    Apr 13, 2018 at 1:42
  • 1
    Use performance analysis tools to diagnose the issue (vtune, paraver, hoctoolkit, Tau,...)
    – Harald
    Apr 13, 2018 at 7:21

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.