Vitis™ アプリケーションアクセラレーション開発フローチュートリアル

巡回セールスマン問題¶

バージョン: Vitis 2021.2

概要¶

このチュートリアルでは、巡回セールスマン問題 (TSP: Traveling Salesperson Problem) について説明します。TSP は、NP 困難 (NP-hard) と呼ばれる問題のクラスに属します。NP 困難とは、計算複雑性理論において、問題が「NP に属する任意の問題と比べて、少なくとも同等以上に難しい」ことを意味します。詳細は、Wikipedia の巡回セールスマン問題に関する記事を参照してください。

セールスマンが複数の都市を 1 回ずつ巡回する場合に経路が最短になるようにするには、考えられる都市の組み合わせをすべてテストする必要があります。アルゴリズムの時間計算量は ~0(n!) で、都市数の階乗に対応します。たとえば、都市数が 13 の場合、13! = 約 62 億の経路を比較することになります。

経路ごとにメモリルックアップを 12 回実行して距離を計算する必要があるため、最短経路を特定するのに 12 * 62 億 = 約 750 億回のメモリルックアップが必要になります。

シンプルな CPU インプリメンテーションの実行¶

CPU_POC ディレクトリでシンプルな CPU インプリメンテーションを実行します。 CPU での実行中に N = 13 都市の場合にかかる時間を確認します。

次を使用してターミナルでビルドして実行します。

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

CPU によって異なりますが、13 都市の場合は実行に 1 分以上かかることがあります。このチュートリアルでは、FPGA で 1 秒以内に問題を解決する方法を示します。

Vitis の設定¶

このチュートリアルでは、次を使用します。

BASH Linux シェルコマンド。
2021.2 Vitis コア開発キットリリースおよび xilinx_u200_gen3x16_xdma_1_202110_1 プラットフォーム。必要であれば、ほかのバージョンおよびプラットフォームを使用するように変更することもできます。

重要:

例を実行する前に、『Vitis 統合ソフトウェアプラットフォームの資料』 (UG1416) のアプリケーションアクセラレーション開発フローのインストールの手順に従って、Vitis コア開発キットをインストールしてください。

ザイリンクス Alveo™ データセンターアクセラレータカードでアプリケーションを実行する場合は、各 Alveo カードのリンク先の [資料] タブに表示される資料で説明されるように、カードとソフトウェアドライバーを正しくインストールしてください。

Vitis を実行する環境の設定¶

Vitis を実行する環境を設定するには、次のスクリプトを実行して、特定のコマンドシェルで実行する環境を設定します。

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

注記: .csh スクリプトも提供されていますが、このチュートリアルでは bash シェルが使用されていることを前提としています。

インストールしたデータセンタープラットフォームまたはエンベデッドプラットフォームのディレクトリを指定するには、次の環境変数を設定します。

export PLATFORM_REPO_PATHS=<path to platforms>

注記: Ubuntu ディストリビューションによっては、Vitis を正しく設定するために LIBRARY_PATH もエクスポートする必要があります。

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

詳細は、ザイリンクスアンサー 73698 を参照してください。

チュートリアルファイルの入手¶

リファレンスファイルを入手するには、ターミナルに git clone https://github.com/Xilinx/Vitis-Tutorials と入力します。
Hardware_Acceleration/Design_Tutorials/04-traveling-salesperson ディレクトリに移動します。

次の手順¶

この演習は、次の順序で実行します。

Licensed under the Apache License, Version 2.0 (the “License”); you may not use this file except in compliance with the License. You may obtain a copy of the License at: http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an “AS IS” BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

Vitis™ アプリケーション アクセラレーション開発フロー チュートリアル