Mohammad Malik -- CMSC 502 | Fall 2020 -- Assignment 2
The purpose of this paper and this implementation was to explore the EMST version of the Travelling Salesman Problem and utilizing a more advanced method of calculating the optimal solution via Boruvka's algorithm. Boruvka's algorithm that can be found here[https://www.geeksforgeeks.org/boruvkas-algorithm-greedy-algo-9/] is inherently designed to be a faster algorithm when done in parallel when compared to Prim's or Kruskal's as a way to find a Minimum Spanning Tree. In this instance we had to find the Euclidean distance as the weight for each edge of the MST to be our TSP weight. Furthermore, had this implementation been completed, it would have yielded better results than compared to the MPI, Serial as well as multi-threaded Versions of both Dynammic Programming as well as EMST of finding the optimal solution of the Travelling Salesman Problem that were completed in the previous iteration of this paper.
Some assumptions were made outside of the prompt that drastically simplified the solution while not changing the base prompt significantly. These assumptions were that: first, each process must only be allowed to generate coordinates within their maximum x and y coordinates respective to what process number they are when the MPI library divies up the entire range of coordinates. Secondly, the biggest assumption is that the coordinate plane will only be split vertically, ie. on the x axis, equally by the number of processes. These two combine to speedup the total time taken to find the optimal solution, however they also cause the accuracy to be slightly less than that of one where if the coordinate plane was split across both the x and y axis. It simplifies the number of local TSP solutions that require being joined.
First the number of cities must be determined for each processor and that will then have to solve each respective process's local TSP. The Coordinate plane will then be divied up equally by the number of processes in only the x axis. Then the generation of the coordinates for the cities is done, each process getting an equal amount of cities, which is then converted into a tree that can have Boruvka's algorithm applied to it in order to find the Euclidean Minimum Spanning Tree. In relation to measure the speedup, in the prior iteration, preorder traversal was used and therefore it was used again as well to measure the true nature of the difference in algorithm's as well as the fact that preorder traversal in the last iteration proved to also be the best traversal technique for MSTs. From this a decent approximation is formed calculating the optimal local TSPon each processor. After the approximations are calculated, this implementation checks for the intersection of any two edges on the path and if any exist an inversion is done. This inversion is designed to flip the edges to minimize the total distance a bit more by swapping the edges that intersect. Once that is completed for the entire tree, each process combines each of their local TSP solutiosn together and stitches the pieces together of the entire coordinate plane. This occurs by happening through `ceil(log2(numProcesses)) iterations and each iteration works by using the rank of each MPI process and sending it's local TSP to it's left neighbor and attempting to connect the two blocks together while also checking to minimize the distance as well as not having any intersections. If data is sent from the process, MPI_Send is utilized to send over both the coordinates, ie the absolute X and Y position on the coordinate plane, as well as the cities themselves. The receiving process creates a temporary buffer theat will merge both TSPs together and will then have one larger connected TSP. Once the optimal Tsp is calculated the final distance is totaled up using the Euclidean distance between two points. Finally, intersections are checked for once more where inversion is applied if any are found and the total distance is minimized once again.
The time complexity for this algorithm is rigorous and has multiple steps involved with it. First the generation of the cities, second finding the MST, third doing the preorder traversal of the MST, and lastly the final combination of the local TSPs into onle globally optimal TSP. In serial, these calculations are O(n) + O(E log(V)) where e = (V * ( V - 1) / 2) and V = n and O(n) = O((n * (n - 1) / 2) * log(n)). To calculate the parallel runtime, the serial runtime is divided by the total number of processes in addition to the time complexity of combining the local optimal solutions. Using Tp to denote parallel runtime, p(Tp) = serial runtime, and the number of processes equals p = n^2. Solving for n results in the Isoefficacy is 0. The total cost of the entire algorithm in parallel is (Time Complexity) * (number of Processes) which is found to be ((n * (n - 1) / 2) * log (n)) / p + n^4. Lastly the efficiency of the parallel algorithm is calculated by finding parallel runtime / serial runtime. This is: O((n * (n - 1) / 2) * log(n)) + ((V * ( V - 1) / 2) * n) / ((((n * (n - 1) / 2) * log (n)) / p + n^4) * n).
The code implementation is not complete, however, in theory this method can be utilized to calculate a very close approximation to very large Travelling Salesman Problems very quickly and efficiently and potentially lead the making the Travelling Salesman Problem no longer be an NP-Hard problem as it can hopefully one day be solved in finite polynomial time. The use of parallelism is something that will be widely more utilized in the near future and more work should be done exploring the underlying capabilities of parallelism.