CS/ECE 566 Parallel Processing
Programming Assignment 4
1 Goals
In this assignment, you will compute a solution to the Travelling Salesman Problem (TSP), using parallel
search and MPI. You will be using the EXTREME parallel cluster provided by ACCC as the experimetal
testbed.
The following links will tell you more of the TSP.
1. https : //en.wikipedia.org/wiki/Travelling salesman problem
2. http : //www.math.uwaterloo.ca/tsp/
3. http : //elib.zib.de/pub/mp− testdata/tsp/tsplib/tsplib.html
Compute an exact solution, using the branch-and-bound tree search algorithm.
2 Experiment
1. Experiment the timing, speedup, and efficiency variations by varying the different parameters along
the lines suggested here. Note that these are only suggestions: the actual parameter ranges you vary
will depend on various factors such as the workload on and the availability of the EXTREME nodes,
OS limits etc..
n, size of the TSP: use small data sets first
p, number of processors: p = 1, 2, 4, 8, 16, 32, 64
3 Input and Testing
• For input, use the data sets at
http : //elib.zib.de/pub/mp− testdata/tsp/tsplib/tsp/index.html
• While you debug your code, please work with small data sets, and few processors i.e., small n, small p.
4 Output
1. Submit a hard copy of all the files including the code file.
2. Submit a hard-copy report describing your experiment. The report must have the following sec-
tions/information.
(a) Formulations: Describe your branch-and-bound alogrithm formulation in 3-4 pages. Include the
list of MPI calls you used in the implementation of each formulation.
(b) Results: Give the tables and plot the graphs showing the timing, speedup, and efficiency varia-
tions for the range of parameters you used. Remember to use appropriate scales for the graphs.
(c) Analysis: Analyse the results. Give your interpretation and reading of the results.
(d) Lessons: What insights you learned from this assignment.
1
5 Grading
The problem is reasonably well-formulated but the experimental approach is open-ended. Your goal is to get
the most parallelism in solving the TSP. Your assignment will also be judged on how comprehensively and
methodically you have designed and run the experiment, and reported on the results. Your insights into the
analysis of the results will also be considered in judging the assignment. Your grade will be based primarily
on your report; (assuming, of course, that you have managed to run your programs).
6 Reference Material/Chapters
https : //en.wikipedia.org/wiki/Travelling salesman problem
2