Computer Science 400

Parallel Processing and High Performance Computing

Fall 2017, Siena College

Our last programming project will be a series of tasks related to the
famous *Traveling Salesperson Problem (TSP)*.

You may work alone or in a group of 2 or 3 on this project.

Getting Set Up

You will receive an email with the
link to follow to set up your GitHub repository
`tsp-project-yourgitname` for this Programming Project. One member of the
group should follow the link to set up the repository on GitHub,
then that person should email the instructor with the other group
members' GitHub usernames so they can be granted access. This will
allow all members of the group to clone the repository and commit
and push changes to the origin on GitHub. At least one group member
should make a clone of the repository to begin work.

Your initial repository should include the source code described in Section 6.2 of Pacheco related to the text's TSP implementations.

Serial Implementations

(Recommendation: complete this part by November 17.)

Read the first part of Section 6.2 of Pacheco, pages 299-306, and
study the implementations in `tsp_rec.c`, `tsp_iter1.c` and
`tsp_iter2.c`.

The input to these programs is a file describing a directed graph,
where the edge weight in row `r`, column `c` is the cost to
travel from place number `r` to place number `c`. Costs are
integers. Places are defined only by number.

Example files are in a public repository that you should fork into your own GitHub account, then clone onto the computer(s) where you are working on this project.

Parallelization with pthreads

(Recommendation: complete this part by December 1.)

Read the next part of Section 6.2 of Pacheco, pages 306-315, and
study the implementations in `pth_tsp_stat.c` and
`pth_tsp_dyn.c`.

Parallelization with MPI

Read the part of Section 6.2 of Pacheco relating to the MPI
implementation of TSP, pages 319-341, and study the implementations in
`mpi_tsp_stat.c` and `mpi_tsp_dyn.c`.

`MPI_Comm_size`

should be 64, 128, 256, ...,
4096), using a problem size such that the single-thread version runs
for at least 30 minutes. Present and analyze your timing
results. (10 points)Submitting

Your submission requires that all required deliverables are committed and pushed to the master for your repository on GitHub. For the new data sets, pull requests should be made to the common repository.

Grading

This assignment is worth 65 points, which are distributed as follows:

> Feature | Value | Score |

Q1: New datasets | 5 | |

Q2: 6.17 | 6 | |

Q3: timings for serial versions | 10 | |

Q4: expected times for serial versions | 3 | |

Q5: 6.18 | 3 | |

Q6: 6.20 | 6 | |

Q7: timings and analysis for pthreads versions | 10 | |

Q8: pthreads/MPI comparison | 10 | |

Q9: timings and analysis for MPI versions | 10 | |

Q10: big problem size | 2 | |

Q11: run and analysis of big problem on many nodes | 10 (Bonus) | |

Total | 65 | |