Description

Multicore Processors: Architecture & Programming
Lab 1

In this lab you will implement a method for solving a modified version of the traveling salesman problem in OpenMP.

What is the problem definition?

What is the input?

The input to your program is a text file that contains an NxN matrix, one row per line, representing the distance between any two cities. Your program will be called ptsm (for parallel tsm). The command line then will be:

./ptsm x t filename.txt

Where :
x is the number of cities t is the number of threads filename.txt is the file that contains the distance matrix

What is output?

You program must output, to screen, the best path you found and the total distance. Here is an example output:

Best path: 0 1 3 4 5 2 Distance: 36

This means the best path your program found is 0->1->3->4->5->2 with total distance of 36.

How will you solve this?

This problem is a combinatorial optimization problem (n! possible solutions for n cities). This means an exact optimal solution will take very long time. However, in this lab we will test your submission with a relatively small number of cities. So, you will implement an exact solution.
We will not test your submission with more than 12 cities and we will not test with more threads than cities.
For example if we have 10 cities and we have two threads. We always start with city 0. Thread 0 will be responsible for exploring paths that start from 0 and go to either 1, 2, 3, 4, or 5; while thread 1 will explore threads going from 0 to 6, 7, 8, or 9. Each thread can use recursion to check the paths. At the end, each thread will pick the shortest path from the paths it has explored. The final answer is the shortest path found among all threads.

How will we grade this?

The total grade is out of 40
• 5 points if your program outputs a legal solution (i.e. each city visited once) but not necessarily one of the shortest paths.
• 20 points for the report
• 15 points if your solution is the optimal solution.

To help you:

We are providing you with two executables:
• ./tsm : This program generates test files (usage: ./tsm numcities). The output of this program is citiesx,txt that contains the matrix of the x city distances. It will also print a (sub) optimal solution on the screen. The file citiesx.txt is a text file that you can open and take a look.
• ./tsmoptimal : This programs prints the optimal solution on the screen (usage: ./tsmoptimal x citiesx.txt) for the x cities problem. This is a sequential program.

The report

You need to write a report that includes the following:

• A graph that shows speedup over single-thread version for a problem of size 4 cities, another graph of problem of size 8 cities, and a third graph for 12 cities. For each graph, the x-axis the number of threads (1, 2, 3, and 4) and y-axis is the time generated by time command (real, not user or system).

Regarding compilation

• Name your source file: netID.c (where netID is your netID number) and add as many comments as you can. This will help us give partial credit in case your program does not compile.
• Do the compilation and execution on crunchyx (x = 1, 3, 5, or 6) machines.
• Use the latest version of gcc on crunchy by typing: module load gcc-9.2

What to submit?

Add the source code netID.c as well as the pdf file that contains your graphs and analysis to a zip file named: lastname.firstname.zip
Where lastname is your last name, and firstname is your first name.

How to submit? NYU classes  Assignments  lab1

Have Fun!