0

I implemented the Dijkstra's algorithm In C. I'm trying to compare the runtime with and without using OpenMP, but for some reason OpenMP is always slower. I read something about how expensive new threads are but expanding the graph does not solve it.

I would like to use omp here

#pragma omp parallel for
for(index=0; index<nodes[n].size; index++){
        int ct = nodes[n].paths[index].connectsTo;
        if(notVisited[ct]){
            int dist = dis[n]+nodes[n].paths[index].weight;
            if(dist<dis[ct]){
                prev[ct] = n;
                dis[ct] = dist;
            }
        }
    }
Jens Gustedt
  • 76,821
  • 6
  • 102
  • 177
Mario Flores
  • 146
  • 2
  • 7
  • 2
    Sometimes the overhead multithreading itself (spawning threads generally) outweighs the speed boost, though its also relevant to know what is your method for benchmarking and the number of nodes you are testing on. – Joseph Franciscus May 23 '18 at 00:15
  • I am using clock() to measure time and the graph has 10,000 nodes – Mario Flores May 23 '18 at 00:16
  • 2
    I think that's actually just too small to get performance increases, try with a larger amount. Also some things that may help you. https://stackoverflow.com/questions/10673732/openmp-time-and-clock-calculates-two-different-results https://unix.stackexchange.com/questions/80424/why-using-more-threads-makes-it-slower-than-using-less-threads – Joseph Franciscus May 23 '18 at 00:20
  • 1
    As you are summing CPU times of all threads, it would be unusual to see a decrease with increased number of threads. – tim18 May 23 '18 at 01:28
  • This also looks racy. Consider what happens if two different nodes connect to the same third node. Given that "notVisited[ct]" is not updated, more than one thread can be assigning prev[ct] and dist[ct] at the same time! – Jim Cownie May 23 '18 at 10:06
  • What OS and compiler and compile options are you using. `clock()` with *nix C runtimes does not measure the wall time. Consider using `omp_get_wtime()`. – Z boson May 23 '18 at 11:31
  • Possible duplicate of [OpenMP time and clock() calculates two different results](https://stackoverflow.com/questions/10673732/openmp-time-and-clock-calculates-two-different-results) – Zulan May 23 '18 at 23:45
  • 1
    1) Fix the time measurement using `omp_get_wtime()`. 2) Prepare a [mcve] including compilation command. 3) Show the specific results, system specs -> edit the question or post a new one – Zulan May 23 '18 at 23:47

0 Answers0