Traveling Salesperson Problem - 2023.2 English

Version: Vitis 2023.2

Introduction

In this tutorial, you look into the Traveling Salesperson Problem (TSP), which is a classic “NP-hard problem.” That is, in computational complexity theory, NP-hardness defines a class of problems that are informally “at least as hard as the hardest problems in NP.” For more information refer to this Wikipedia Travelling Salesman Problem article.

To ensure the shortest route, you must test each possible combination of cities. So, the time complexity of the algorithm scales with the factorial of the number of cities, ~0(n!). For instance, with 13 cities, there are 13! = 6.2 billion routes to compare.

Then each route requires 12 memory lookups to calculate the distance, you need 12 *6.2 =75 billion memory lookups to identify the shortest route.

Run a Simple CPU Implementation

A simple central processing unit (CPU) implementation in the CPU_POC directory. Notice how much time it takes for N=13 cities when running on the CPU.

Build and run in a terminal with:

cd CPU_POC
g++ -O3 main_gold.cpp && ./a.out

The execution could take over a minute for 13 cities depending on your CPU, and you will see in this tutorial how an field programmable array (FPGA) can solve the problem in less than a second.

Set Up Vitis

The labs in this tutorial use:

• BASH Linux shell commands.

• 2023.2 Vitis core development kit release and the xilinx_u200_gen3x16_xdma_2_202110_1 platform. If necessary, it can be easily ported to other versions and platforms.

IMPORTANT:

• Before running any of the examples, make sure you have installed the Vitis core development kit as described in Installation in the Application Acceleration Development flow of the Vitis Unified Software Platform Documentation (UG1416).

• If you run applications on the AMD Alveo™ Data Center accelerator cards, ensure the card and software drivers have been correctly installed by following the instructions To complete the installation, follow the instructions on the Alveo Product Documentation tab.

Set Up the Environment to Run Vitis

To configure the environment to run Vitis, run the following scripts which set up the environment to run in a specific command shell.

source <Vitis_install_path>/Vitis/2023.2/settings64.sh
source /opt/xilinx/xrt/setup.sh

NOTE: .csh scripts are also provided, but this tutorial assumes a bash shell is used.

To specify the location of any Data Center or Embedded platforms you have installed, set the following environment variable:

export PLATFORM_REPO_PATHS=<path to platforms>

NOTE: On some Ubuntu distributions, you must also export LIBRARY_PATH to properly set up Vitis.

export LIBRARY_PATH=/usr/lib/x86_64-linux-gnu

For more information, see Xilinx AR 73698.

Accessing the Tutorial Files

1. To access the reference files, type the following into a terminal: git clone https://github.com/Xilinx/Vitis-Tutorials.

2. Navigate to the Hardware_Acceleration/Design_Tutorials/04-traveling-salesperson directory.

Next Steps

Complete these labs in the following order:

• Load the Vitis HLS project

• Understand the design structure

• Run the C simulation

• Run the C synthesis

• Run the RTL/C cosimulation

• Export the design and evaluate performance in Vivado

• Improved performance with 4 parallel distance lookups

_{Copyright © 2020–2023 Advanced Micro Devices, Inc}

^{Terms and Conditions}