A project to speed up a sequential C program that solves the Travelling Sales Person problem. Achieved a speed up of 29.5% using OpenMP threading and SIMD vector programming.

We based our optimised program on the code given originally in sales.c. We tried a few things; Firstly we threaded the inner loop but this slowed down the program as we had to write a crticial section which only one thread could access at a time.

Secondly we tried to vectorise the function that calculates the distance from point to point with the library "xmmintrin.h" as it offered a square vector function. This did not work however as it was hard to manually vectories in an elegant way especially with the branch "if (!visited[j])" It was also difficult to keep track of the cities' indexes as their distances were being mashed up in Vectors.

We came to our solution by altering the original program in a way that would allow each thread to work correctly without having to enter a Critical Section. Our solution lead us to first creating a ncities*ncities table which could simply done with threading with a "#pragma omp parallel for" on the outer loop and then we discovered that a "#pragma omp simd" was optimal for the inner loop. Once we created this table we then started creating the trip itinery by searching through the current points (ThisPt) distances and finding the closest then update ThisPt to that point and loop. We put a "#pragma omp SIMD" declaration above the inner loop in this this part and also declared the distance function as "#pragma omp declare simd" as this lead to a small increase in optimisation.

When we ran the original code with 10,000 cities we averaged 2022007 microseconds This code runs 29.5% quicker than the original, running on average at 1427421 microseconds Load this file onto a stoker machine and run the following compiling comand using GCC.