High-Performance Computing
Distributed TSP Solver
A distributed-memory Traveling Salesman Problem solver written in C99 and OpenMPI, combining Parallel Tempering, local search, constant-time route updates, and coordinated replica exchange.
20.7×reported speedup
24tested cores
86%parallel efficiency
O(1)route-delta updates
Problem
The Traveling Salesman Problem has a rapidly growing search space. Distributed optimisation can improve runtime, but it also introduces communication, synchronization, and scaling challenges.
My contribution
- Implemented distributed Parallel Tempering using C99 and OpenMPI.
- Used 2-opt route modifications with a stochastic acceptance strategy.
- Precomputed a distance matrix for constant-time route-delta evaluation.
- Designed an odd-even replica-exchange protocol.
- Automated strong-scaling benchmarks and performance plots.
Parallel methodology
Search
Multiple temperature replicas help the optimisation escape local minima.
Communication
Neighbouring replicas exchange states using an ordered odd-even protocol.
Performance
Distance lookup tables reduce the cost of the inner optimisation loop.
Representative results
Results
- The repository reports a 20.7× speedup on a 24-core cluster.
- Reported parallel efficiency remains at 86% at 24 cores.
- Computation remains the dominant cost while communication overhead grows gradually.
- Solution quality remains stable across the tested processor counts.
Next steps
Planned extensions include hybrid MPI/OpenMP execution, CUDA acceleration, and comparisons across additional TSP datasets.