はじめに｜行列積高速化#0

以前書いた行列計算DGEMMを高速化する記事が、あまりに長すぎた（20万文字以上）ので、記事あたり１万字以内を目安に、章ごとに記事を分割することにしました。

元の記事が有料記事のため、高速化の重要なカギになる章は有料にさせていただいています。全記事をご購入いただくと1000円になります。元の記事は560円ですので、全ての章を読むなら元の記事の方が割安になっています。一部の章は元の記事で有料部分に含まれていましたが、分割したので無料でもお読みいただけるようになりました。

元の記事は、行列積サブルーチンとして有名なDGEMMを高速化していく過程を記録したものです。元の記事では、CPUのピーク性能に対して56%までしか達成できませんでしたが、高速化のための手続きは全て記録したつもりです。

その後、もう少し試行錯誤を続けて93%までは高速化に成功しています。その工夫も、一部を「行列積チューニングその後１」という記事にしています。この記事も、同じ内容になりますが、シリーズの続きとして含めたいと思います。

元の記事を分割したリストは下記の通りです。

#1  評価環境
#2  理論性能の見積もり
#3  テストプログラムの作成
#4  簡単な行列積計算プログラム
#5  キャッシュブロッキング　（100円）
#6  キャッシュコピー　（100円）
#7  ループ交換1回目
#8  行列データの直列化　（100円）
#9  カーネル関数の作成
#10  ループ交換2回目
#11  行列転置をコピー関数で吸収する　（100円）
#12  計算ブロックの順序最適化　（100円）
#13  アンローリング　（100円）
#14  インラインアセンブラの書き方
#15  アライメントを揃える方法
#16  ベクトル化の設計
#17  アセンブラによるベクトル化　（100円）
#18  プリフェッチの挿入
#19  アセンブラ命令順序の最適化　（100円）
#20  行列コピー関数のテストプログラム作成
#21  行列コピー関数の最適化　（100円）
#22  行列スケール関数のテストプログラム作成
#23  行列スケール関数の最適化　（100円）
#24  行列積の性能測定
#25  カーネル関数の性能推定

DGEMMとは？

DGEMMは、数値計算ライブラリBLASに含まれる行列積サブルーチン名です。BLASは、ライセンス不要のパブリックドメインとして公開されているため、商用でも改造・再配布が自由に可能です。そのため、HPCベンダー各社はこれを独自にチューニングしたライブラリを提供しています。

HPC業界ではTop500ランキングでもベンチマークプログラムとして使われていて、今でも世界最高速が競われています。近年は、ディープラーニングの畳み込み計算などにも利用されているようで、あまり表には出てきませんが、様々なプログラムの裏方として頑張っているアルゴリズムになります。

The Linpack Benchmark | TOP500

しかし、行列積の高速な実装はあるものの、行列積の高速化方法はなかなか解説が見つかりません。

そこで、自分のチューニングしていく過程をお見せすることで、「何を考えてどう実装するのか」を後世に残しておくことにしました。今後も、CPUの進化は続くので、実装そのものではなく、考え方が伝われば嬉しいです。

次の記事

元の記事

ソースコードは、GitHubで公開しています。

jyam45/dgemm

高速なBLASのライブラリは、下記の記事で紹介しています。