Solving the Traveling Salesman Problem (TSP) with brute force and parallelism just for teaching and illustrative purpose.

Traveling Salesman Problem

Brute force parallelism to solve TSP

The code here is mostly adapted from the very nice talk by David Olsen, Faster Code Through Parallelism on CPUs and GPUs at CppCon 2019.

I've just slightly changed the way the permutations are computed which turns out to be slightly faster than the original.

See also companion slides by D. Olsen (Nvidia) at GTC2019 s9770-c++17-parallel-algorithms-for-nvidia-gpus-with-pgi-c++.pdf

Timings

Timings reported here are measured on my own desktop.

Hardware :

• CPU Intel(R) Core(TM) i5-9400F @ 2.90 GHz - 6 cores
• GPU Nvidia GeForce RTX 2060

Software:

• Ubuntu 20.04
• Nvidia hpc sdk version 20.11 with cuda 11.2
• g++ 9.3

serial version (reference)

Number of cities	time (seconds)
10	0.064
11	0.66
12	8.48
13	130.7
14	1997.9

OpenMP pragmas

GNU compiler

Number of cities	time (seconds)
10	0.044
11	0.152
12	1.64
13	24.2
14	368.3

OpenMP target for Nvidia

We need an OpenMP 4.5 capable compiler:

Just follow the steps mentioned here:

• how-to-build-and-run-your-modern-parallel-code-in-c-17-and-openmp-4-5-library-on-nvidia-gpus
• Clang_with_OpenMP_Offloading_to_NVIDIA_GPUs

Performance are quite slow (compared to PGI/OpenAcc or Kokkos::CUDA below) by a factor of x3 when N >= 12.

Number of cities	time (seconds)
10	0.077
11	0.104
12	0.39
13	3.56
14	59.5

I tried three compile toolchains:

• clang 10.0 with cuda 10.1
• clang 11.0 with cuda 11.2
• clang 12.0 with cuda 11.3

OpenAcc (PGI compiler)

OpenAcc for multicore CPU

These results are strange, much too slow (maybe related to my host configuration ?). I also a strong performance drop when using nvhpc 20.11 versus 20.5 (??).

Number of cities	time (seconds)
10	0.030
11	0.25
12	7.21
13	XX
14	XX

OpenAcc for GPU

Performance looks good (similar to Kokkos::CUDA below).

Number of cities	time (seconds)
10	0.107
11	0.128
12	0.25
13	1.51
14	20.5

Kokkos

To build, you just need to edit kokkos/Makefile, and change the first line by modifying variable KOKKOS_PATH to the full path where you cloned kokkos sources.

Kokkos - OpenMP

Just run make in subdir kokkos.

Timings are similar to OpenMP pragma.

Number of cities	time (seconds)
10	0.015
11	0.152
12	1.84
13	24.5
14	376.6

Kokkos - Cuda

Just run make KOKKOS_DEVICES=Cuda in subdir kokkos.

Timings are very similar to Openacc (GPU).

Number of cities	time (seconds)
10	0.01
11	0.01
12	0.106
13	1.41
14	22.4

stdpar

stdpar for multicore cpu (nvc++ compiler)

Again, performance obtained here is odd; it's much slower than OpenMP with g++, but should be similar....

Number of cities	time (seconds)
10	0.027
11	0.128
12	5.10
13	114.0
14	TODO

stdpar for GPU (nvc++ compiler)

Similar performance as OpenAcc and Kokkos/Cuda.

Number of cities	time (seconds)
10	0.007
11	0.016
12	0.15
13	1.40
14	21.3

SYCL

There are a lot of SYCL implementation available, here we tried

• Intel OneAPI DPC++ (linux) for x86 multi-core
• Intel LLVM (linux) for Nvidia GPU (see https://github.com/intel/llvm)

SYCL OneAPI for x86 multicore

module load compiler/2021.1.1

Number of cities	time (seconds)
10	1.29
11	1.40
12	2.62
13	21.3
14	TODO

for large values of N, we retrieve the expected results (OpenMP, Kokkos::OpenMP, ...).

SYCL OneAPI for Nvidia GPU (LLVM/intel)

module load llvm/12-intel-sycl-cuda

These results should be optimized by changing the number of block of threads and the block size (à la CUDA).

Performance are correct, maybe a bit slow for N=14.

Number of cities	time (seconds)
10	0.001
11	0.008
12	0.11
13	1.86
14	37.4