Vitis™ ハードウェアアクセラレーションチュートリアル

巡回セールスマン問題¶

バージョン: Vitis 2022.1

入門チュートリアル

このチュートリアルでは、巡回セールスマン問題 (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 シェルコマンド。
2022.1 Vitis コア開発キットリリースおよび xilinx_u200_gen3x16_xdma_2_202110_1 プラットフォーム。必要であれば、ほかのバージョンおよびプラットフォームを使用するように変更することもできます。

重要:

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

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

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

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

source<Vitis_install_path>/Vitis/2022.1/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 ディレクトリに移動します。

次の手順¶

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

Apache ライセンス、バージョン 2.0 (以下「ライセンス」) に基づいてライセンス付与されています。本ライセンスに準拠しないと、このファイルを使用することはできません。ライセンスのコピーは、http://www.apache.org/licenses/LICENSE-2.0 から入手できます。

適切な法律で要求されるか、書面で同意された場合を除き、本ライセンスに基づいて配布されるソフトウェアは、明示的または黙示的を問わず、いかなる種類の保証または条件もなく、「現状のまま」配布されます。ライセンスに基づく権限と制限を管理する特定の言語については、ライセンスを参照してください。

Vitis™ ハードウェア アクセラレーション チュートリアル