Dist

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

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