CSE-746 2024 Assignment #3 (CUDA)

Your task is to write a CUDA version of the serial code ~syam/CSE746/Assignment3/tsp.c (on graham). This is a brute force Monte Carlo (random) search for the solution of the Traveling Salesman Problem. The problem is stated as follows: given a list of N cities (x,y coordinates; flat geometry is assumed for simplicity), find the shortest itinerary which would start from the city #1, visit all the other cities once, and come back to the original city. (For simplicity, traveling is assumed to be done in straight lines connecting the two cities). The problem has the difficulty of (N-1)! order, meaning that it is practically impossible to find the best solution using brute force approach when N>30. Your program should not attempt to find the absolutely best solution – instead it should find the best solution in a given number of random (Monte Carlo) attempts. The core of the algorithm is the generation of random permutations of the cities list. No attempts should be made to test if your random permutations of the cities list are unique (this will dramatically slow down the execution, and will not give much of an advantage). The code should print both the shortest distance and the corresponding itinerary.

More detailed instructions are given in the header of the file tsp.c. On graham (P100), the timing of the CUDA version of the code should be around 0.14 seconds. You should put comments inside your code explaining what you are doing.

Marks will be taken off for code bugs (some or all the results are wrong), for insufficient commenting in the code, and for poor performance. It must be your own work and you are responsible for adhering to the Senate Policy Statement on Academic Ethics.

Due date: Monday March 25, 2024 , send me the solution through email, to syam@physics.mcmaster.ca . Late submissions will have their mark reduced by 10% every day.

This assignment is worth 10 percent of the course grade.