全点対間最短路を高速に求める

2015年11月29日

フィックスターズは今年も ACM ICPC つくば大会 にスポンサーとして協賛しております。今年はコンテスト後の懇親会でクイズを出題しているのですが、その問題準備の際に作ったはいいものの結局使われなかったコードが大量に出てきてしまったため、それらをまとめて簡単な解説とともに公開いたします。

全点対間最短路問題

全点対間最短路問題はN個の頂点を持つ有向グラフにおける任意の2点間の最短路を求める問題です。密なグラフの全点対間最短路を求めるアルゴリズムとしてワーシャル-フロイド法が広く知られており、以下のような非常にシンプルなコードで求めることができます。

// 入力: A[i][j] = 頂点iと頂点jを結ぶ辺の重み
// 出力: A[i][j] = 頂点iから頂点jまでの最短路の重みの総和
for(int k = 0; k < N; ++k)
  for(int i = 0; i < N; ++i)
    for(int j = 0; j < N; ++j)
      A[i][j] = min(A[i][j], A[i][k] + A[k][j]);

愚直な並列化

上に示したワーシャルフロイド法のアルゴリズムは i, j ループを並列化した以下のようなコードでも正常に動作します。

for(int k = 0; k < N; ++k)
#pragma omp parallel
  for(int i = 0; i < N; ++i)
    for(int j = 0; j < N; ++j)
      A[i][j] = min(A[i][j], A[i][k] + A[k][j]);

……正常に動作して正しい結果は返してくれるのですが、演算資源より先にメモリ帯域を使い切ってしまうため少ないコア数でもあっという間に性能が頭打ちしてしまいます。

ICPCの際に出題したクイズには、上記のコードと同様の方針で並列化したCUDAコードを並べてどれくらいの性能差か予測するという問題を出したのですが、どちらのコードもまだかなりの性能向上の余地があります。

ワーシャル-フロイド法を高速化するアルゴリズム

再帰的に分割する

愚直な i, j ループの並列化がスケールしないのはメモリ律速になってしまっているのが原因です。メモリアクセスのコストを減らすためには、キャッシュやレジスタに収まるサイズに問題を分割し、その範囲の演算をまとめて行うことでメインメモリへのアクセスを減らすブロッキングがよく用いられます。ワーシャルフロイド法の高速化においてもブロッキングは有効で、分割の方法もいくつか提案されているのですが今回は再帰的に分割していく方法 [1] を使用しました。

行列積に落とし込む

ある程度以上のパフォーマンスチューニングは非常に労力がかかるのですが、問題の一部を既存の研究されつくしたカーネルに任せることで比較的容易に非常に効率の良いアルゴリズムを実装できることがあります。再帰的に分割するワーシャル-フロイド法でもそのようなアプローチをとることができ、処理の大部分をトロピカル半環(加算と乗算の代わりにminと加算を用いる)の行列積に帰着させることができます [2]。

行列積と聞くと理論ピークに近い性能が出せそうな気がしてきますね!

行列積のピーク性能

行列積といえばプロセッサの浮動小数点数演算回路をほぼフルに使う処理のひとつとして有名ですが、今回扱う行列積は add, mul の代わりに min, add を使用しているため、FMA が利用できないなど通常のそれとまったく同じとはいかない箇所があります。

ここでは、今回使用したプロセッサでトロピカル半環の行列積を求める際の理論ピーク性能を求めておきます。

CPU

今回使用したプロセッサ (Core i7-4930K) では 3.4 [GHz] × 6 [コア] × 8 [ベクトル長] で 163.2 [GFLOPS] が限界となります(TurboBoostを無視した場合)。通常の行列積ではさらにスーパースカラが効いて2倍の 326.4 [GFLOPS] となるのですが、IvyBridge では add と min が両方とも同じポートを使用するため、スーパースカラの効果が得られず限界値が低くなってしまいます。

GPU

今回使用した GPU (GeForce GTX 980) では 1.126 [GHz] × 16 [SMM] × 64 [SMMあたりのminのスループット] × 2 [スーパースカラ] で 2306 [GFLOPS] が限界となります(Boostを無視した場合)。CPU の時とは対照的に、こちらはスーパースカラが効いて min と add が並列に処理できているようでした。一方、通常の行列積では FMA を用いることでさらに倍の演算を行うことができるため、通常の行列積との比較だと GPU でも半分がピークとなります。

行列積のチューニング

cuBLASなどのライブラリではあまりトロピカル半環の行列積はサポートされていないため、今回はキャッシュやレジスタでブロッキングする程度のチューニングを施したカーネルを自前で用意しました。

# 行列積のチューニングはまじめに書くとそれだけで記事1本以上のボリュームになってしまうので割愛します……

性能評価

評価環境

評価したコード

これらのコードとビルドスクリプトなどはBitBucketで公開しています。

評価結果

N = 8192
アルゴリズム 処理時間 [ms] GFLOPS 愚直な実装に対する性能向上
CPU: 愚直な並列化 257656 4.26
CPU: 再帰的分割 28405 38.70 ×9.07
CPU: 再帰的分割+行列積 10213 107.65 ×25.22
GPU: 愚直な並列化 25460 43.18
GPU: 再帰的分割+行列積 604 1817.70 ×42.09
N = 16384 (参考)
アルゴリズム 処理時間 [ms] GFLOPS
CPU: 再帰的分割+行列積 84806 103.71
GPU: 再帰的分割+行列積 4685 1877.21

それぞれのプロセッサ用の愚直な実装と比べてみると、CPUでは約25倍、GPUでは約42倍の性能向上となりました。
また、CPUでは限界の65%程度、GPUでは限界の80%程度の性能を出すことができています。

なんとなくではありますがCPU版はもう少し詰められそう、GPU版はCUDA Cでここから先はきつくなりそうといった気がします。

まとめ

ワーシャル-フロイド法を通して、同じハードウェア・同じ計算量であっても性能に大きな差が出る例を示しました。

ICPCのようなコンテストではあまり定数倍のチューニングは重要視されませんが、このような方法でのアルゴリズムの高速化にも興味を持っていただければ幸いです。

参考文献

  • [1] Joon-Sang Park, Michael Penner and Viktor K Prasanna. “Optimizing graph algorithms for improved cache performance”. IEEE Transactions on Parallel and Distributed Systems, vol.15, no.9, Pages 769-782. September 2004.
  • [2] Aydın Buluç, John R. Gilbert and Ceren Budak. “Solving path problems on the GPU”. Parallel Computing Volume 36 Issue 5-6, Pages 241-253. June 2010.

Tags

About Author

hiragushi

Leave a Comment

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください

Recent Comments

Social Media