20Q3.05B

FPGA を用いた「組合せ問題」の高速計算(5)

前回は、最大クリーク問題専用 Dist アルゴリズムの FPGA 実装について述べました。今回は、実装と性能評価の結果、および、このハードウェアの改良すべき点について述べ、連載を締めくくりたいと思います。性能評価実装結果実装には、台湾の TUL 社製の XIL-ACCEL-RD-KU115 ボードを使用しました。このボードには、Xilinx 社の Kintex Ultrascale KU115 が搭載されています。4096頂点、400万エッジのグラフを処理可...

FPGAを用いた「組合せ問題」の高速計算 (4)

前回は、Parital MaxSAT の発見的解法である Dist アルゴリズムの FPGA 実装にあたっての難点を挙げ、アプリケーションを最大クリーク問題に特化することでそれらを回避できることを述べました。今回は、その FPGA 実装について述べていきます。全体像まず、前回示した最大クリーク問題専用 Dist アルゴリズムを図 1 に再掲します。図1 最大クリーク問題に特化した Dist アルゴリズム次に、データを保持するためのテーブル類を図 2 に示...

FPGAを用いた「組合せ問題」の高速計算(3)

前回は、MaxSAT の一種である Partial MaxSAT の定義、最大クリーク問題の Partial MaxSAT への変換、局所探索法に基づく Parital MaxSAT の発見的解法である Dist アルゴリズムについて述べました。今回は、Dist の FPGA 実装に当たっての難点と、それを回避するためにどのようにアルゴリズムの簡略化を行ったかについて説明します。 Dist アルゴリズム図1に、Dist アルゴリズムの全体像を再掲します (ステップ5 〜 ...

FPGAを用いた「組合せ問題」の高速計算(2)

前回は、 FPGA のアプリケーションのひとつに「決定問題」や「最適化問題」などの「組合せ問題」があること、決定問題の代表例である SAT、 SAT を最適化問題に拡張した MaxSAT について述べ、また、 FPGA による組合せ問題の高速計算に関する文献を幾つか紹介しました。今回から、筆者らの事例を題材に、組合せ問題の FPGA による高速計算について触れていきたいと思います。前回も述べましたが、これは、グラフ理論の最大クリーク問題を MaxSAT に置き換え、 FPGA 上で高速...

FPGA を用いた「組合せ問題」の高速計算 (1)

この連載では、 FPGA の応用事例として、「組合せ問題」を高速に解く試みについて触れていきます。 FPGA のアプリケーションとしては、画像処理や深層学習 (いわゆるAI) などが有名ですが、組合せ問題を FPGA で高速に解こうという試みは FPGA 研究の比較的早い時期 (90年代末) に起こり、今日に至っています。この連載では、組合せ問題の定義や用途、組合せ問題を解くためのアルゴリズム、その FPGA を用いた高速化に関して、実装例などを交えて紹介します。なお、初回は FPGA...

タイトルとURLをコピーしました