Description
Introduction
In this assignment you are asked to parallelize the traveling salesman problem given the sequential solution (provided on Quercus) by using POSIX threads.
Please note that, the sequential solution already uses a queue to put and get the partial paths, which is what the parallel solution is supposed to use.
Logistics
You are allowed to work individually or in teams of 2 or 3.
Provide a tsp.tar.gz file including your solution and a report in which you analyze the speedup of your parallelized code compared to the performance of the sequential code for several problem sizes.
Explain the sources of the speedup of your code, or lack thereof compared to the sequential version. You should submit a .tar.gz file with your code and performance analysis as instructed below to be graded. Please remember to include the names of all the members of your team in your report.
Account Information
I recommend you work on the ug machines located in the GB 243 lab. They are accessible by ssh — hostnames are ugxyz.eecg.toronto.edu (ug250 for instance is one of those machines). The
ug machines run Debian; they are multicore and have plenty of RAM.
If you do not have an account, please send an email to Tim Trant at tim@eecg.toronto.edu regarding accounts on these machines – mentioning your need for the account for the ECE 1747 class.
Please copy the code I provided into your account and measure your code execution time on one of the ug machines. When you are ready, submit your work by running the command below on one of the ug machines:
submitece1747f 1 tsp.tar.gz
