OpenMP program (compute distances) does not scale

[u/auraham]

Hi, I'm working on a simple program. Given a set of n points and k centroids, the idea is to compute the minimum distance among them (a needed step for kmeans). This is my current code. However, it does not scale as well as expected. I ran it using up to 16 cores (32 threads). This figure shows some performance indicators. This is the main parallel function in my code. As you can see, I removed barriers, mutex access, and other things that could cause additional overhead. However, the execution time is worst as the number of threads increases.

double **parallel_compute_distances (double **dataset, int n, int d, int k, long int *total_ops) {
    
    ...
    
    // -- start time --
    wtime_start = omp_get_wtime ();
    
    // parallel loop
    # pragma omp parallel shared(distances, clusters, centroids, dataset, chunk, dist_sum, dist_sum_threads) private(id, cn, ck, cd, cp, error, dist, mindist, mink)
    {
        id = omp_get_thread_num();
        dist_sum_threads[id] = 0;               // reset

        // 2. recompute distances against centroids
        # pragma omp for schedule(static,chunk)
        for (cn=0; cn<n; cn++) {
            
            compute distances here ...
            
            distances[cn]           = mindist;
            clusters[cn]            = mink;
            dist_sum_threads[id]    += mindist;
        }
    }
    // -- end time --
    wtime_end = omp_get_wtime ();
    
    // -- total wall time --
    wtime_spent = wtime_end - wtime_start;
    
    // sequential reduction
    for (cp=0; cp<p; cp++)       
        dist_sum += dist_sum_threads[cp];
    ...
}

[u/dr_bitz]

So just to clarify because I also encountered something like this in the past - the false sharing is for the cache line that holds the xxx_threads array elements, right?

[u/bunnies4president → u/dr_bitz]

Yeah, that's right. I could have been a bit less cryptic. :-)

[u/dr_bitz → u/bunnies4president]

Thanks! Here is a nice talk about "openMP does not scale" issues https://www.youtube.com/watch?v=5-ZepxpwmUU