Travelling salesman problem in Open MP

General OpenMP discussion

Travelling salesman problem in Open MP

Postby Oldboy » Thu Nov 14, 2019 3:50 am

I have found this link:
https://github.com/abhishek510/tsp_openmp

Something is wrong as the speedup is very small from 1 to 4 threads and none at all at 16 threads.
Oldboy
 
Posts: 27
Joined: Wed Oct 31, 2012 2:39 am

Re: Travelling salesman problem in Open MP

Postby MarkB » Thu Nov 14, 2019 11:34 am

This implementation doesn't attempt to do any load balancing of the parallel branch-and-bound algorithm. Using nested tasks might be a better way to go.
MarkB
 
Posts: 782
Joined: Thu Jan 08, 2009 10:12 am
Location: EPCC, University of Edinburgh

Re: Travelling salesman problem in Open MP

Postby Oldboy » Wed Nov 27, 2019 3:11 am

Thank you Mark!

This Boruvka version of TSP works better:
https://github.com/dimitris21gr/Boruvka_and_Dijkstra_Parallel/tree/master/openMP_boruvka

A "small" misstake must be corrected parralel -> parallel in the c-code.
Oldboy
 
Posts: 27
Joined: Wed Oct 31, 2012 2:39 am


Return to Using OpenMP

Who is online

Users browsing this forum: No registered users and 8 guests