2021.1 Vitis™ - The Traveling Salesperson Problem - Tutorial

See Vitis™ Development Environment on xilinx.com

The Traveling Salesperson Problem

Introduction

In this tutorial we 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, we 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, we need 12 * 6.2 = 75 billion memory lookups to identify the shortest route.

Run a simple CPU Implementation

A simple 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 we will see in this tutorial how an FPGA can solve the problem in less than a second…

Setup Vitis

The labs in this tutorial use:

  • BASH Linux shell commands.

  • 2021.1 Vitis core development kit release and the xilinx_u200_gen3x16_xdma_1_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 Xilinx® Alveo™ Data Center accelerator cards, ensure the card and software drivers have been correctly installed by following the instructions To complete installation, follow the instructions on the Alveo Product Documentation tab.

Setup 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/2021.1/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.