85.30 GFLOPS Single-Core FP32 Matrix Multiplication on AMD Zen 3: A Systematic Study of Cache Blocking, Register Blocking, FMA Chaining, and On-the-Fly Packing

あなたは、巨大な倉庫の片側から反対側へ、大量の砂（データ）を移動させようとしていると想像してください。ただし、あなたは非常に小さく、かつ超高速なロボットアーム（プロセッサ）を使ってこれを行わなければなりません。目標は、その砂を特別な数式（行列乗算）とできるだけ速く混ぜ合わせることです。この論文は、ある研究者であるルーカスが、AMD Zen 3と呼ばれる特定の種類のコンピュータチップ上で、いかにしてそのロボットアームを人間が到達しうる限界まで速く動かすか試行錯誤した詳細な記録です。

大きな目標：何をもって「速い」とするのか？

ロボットアームには、理論上の最高速度である 134.4 GFLOPS（1秒間に1344億回の演算）があります。これは高速道路の制限速度のようなものです。ルーカスは、新しい車を作り直すのではなく、単にエンジンのチューニングを行うだけで、どれだけこの制限速度に近づけることができるかを知りたいと考えました。

28種類もの異なる運転戦略をテストした結果、彼は「チャンピオン」となる設定（MX24と呼ばれます）を見つけ出し、それは 85.30 GFLOPS に達しました。これは最大速度の約 63.5% です。100%の完璧な数値ではありませんが、出発点であった、わずか 1.51 GFLOPS しか出せない不器用で遅い手法と比較すれば、驚異的な飛躍です。実際、彼の最高の手法は、基本となる最適化されていないバージョンの 57倍速い ものでした。

勝利の戦略：「4行・チェイン4」のダンス

このスピードを実現するために、ルーカスは砂の配置とロボットの動きをどのように تنظيمすべきかを突き止めなければなりませんでした。彼が発見した主要な動きは以下の通りです。

1. 「オンザフライ（即時）」パッキングのトリック
砂が、次の粒を掴むために斜めに歩かなければならないようなグリッド状に保管されていると想像してください。それは遅くて疲れる作業です。ルーカスは、ロボットが必要とする直前に、砂の小さな塊を整然とした直線へとコピーする（これをオンザフライ・パッキングと呼びます）ことが、魔法の動きであることを発見しました。これは、ヘルパーが先回りしてレンガを完璧な列に積み上げておき、ロボットが躓くことなく次々と掴めるようにするようなものです。これは、単にそのままの状態で掴むという古い方法よりも優れており、倉庫全体を事前に並べ替える方法よりも優れた結果を出しました。

2. 「4行」の積み重ね
ロボットには、作業中に砂を保持するための限られた数の「手」（レジスタ）があります。ルーカスは、砂の行数を2行、4行、8行と保持することを試しました。

• 2行: 不足していました。ロボットは新しい砂を補充するために頻繁に停止しなければなりませんでした。
• 8行: 多すぎました！ロボットの手がいっぱいになりすぎて、砂を床（メモリ）に落としてしまい、それを何度も拾い直さなければなりませんでした。これは悲惨な結果でした。
• 4行: これがスイートスポット（最適解）でした。たとえ砂を少し床に落として拾い直す作業（これを「スピル（溢れ出し）」と呼びます）が発生したとしても、一度に処理できる砂の量が増えるため、その追加作業は価値がありました。この一つの変更だけで、ロボットは2行のメソッドよりも 59%速く なりました。

3. 「チェイン4」のリズム
ロボットのアームは、同じ砂に対して次の数学的動作を開始できるようになる前に、単一の動作を完了するのに 4サイクル かかります。もしロボットが1つの動作を行い、その後待機してしまうと、3サイクルの間、アイドル状態（空転）になってしまいます。
ルーカスは、ロボットが手に 4つの異なる砂の山 を持ち、それらをループの中で処理する（チェイン4）方法を見つけました。一つの山が「調理中」である間に、他の山に対して作業を行うのです。これがロボットの4サイクルの調理時間に完璧に一致し、エンジンをフルスピードで回転させ続けることができました。

何がうまくいかなかったのか（「やってはいけない」リスト）

時として、上手くいきそうに見えることが、実際には状況を悪化させることがあります。ルーカスはいくつかの人気のあるアイデアをテストしましたが、この特定のロボットにとってはひどい結果になることを発見しました。

• 「プリフェッチ（事前読み込み）」のミス: 人々はしばれてロボットに対し、次に必要となる前に次の砂の粒を「先読み」して掴むよう指示します。ルーカスがこれを試したところ、ロボットの組み込みの「目」はすでにパターンを見抜く能力が十分に高かったため、余計な「先読み」コマンドがかえって邪魔になってしまいました。これにより、ロボットの速度は約 8% 低下しました。
• 「ノン・テンポラル（非一時的）」な廃棄: 砂をビンに入れる前に、直接床に捨てるというテクニックがあります。これはゴミを捨てる場合には非常に有効です。しかし、ここではロボットは砂を「混ぜる」必要があるため、再び拾い上げなければなりません。直接捨ててしまうと、ロボットは自分の足に躓いてしまい、速度は悲惨な 1.24 GFLOPS まで急落しました。
• 「8行」のオーバーロード: 前述の通り、8行の砂を保持しようとすると、砂を落としすぎてしまい、動くことよりも拾い集めることに時間を費やすことになりました。

その信頼性は？

この論文の数値は、単なる推測ではなく、実際に測定されたものであるため、非常に高い信頼性を持っています。ルーカスは各戦略についてコードを 15回 実行し、計算の狂い（異常な挙ニック）を避けるために最も速い実行と最も遅い実行を除外し、残りの平均値を出しました。また、高速版が「ズル」をしていないかを確認するために、単純で遅いバージョンとの比較も行いました。

彼はさらに、戦略を実行する前にその速度を予測するための、一種の水晶玉のような数学的な**「プリフィルター・モデル」**を構築しました。この水晶玉は非常に優秀で、ほとんどの戦略において、実際の速度の 11.3% 以内の誤差に収まりました。このモデルはやや保守的な傾向があり、最良の戦略を 78.1 GFLOPS と予測しましたが、実際に実行してみると 85.30 GFLOPS に達しました。

まとめ

この論文は、驚異的なスピードを得るために、必ずしも「アセンブリ言語」（ロボットのネイティブな言葉）を書く魔術師である必要はないことを証明しています。標準的なツール（C++ インストリンジクス）を使用し、「ダンスのステップ」（ブロッキング、チェイニング、パッキング）を注意深く調整することで、コンピュータを理論上の最大速度の 63.5% まで走らせることができるのです。

教訓は、**「推測するな」**ということです。ある種類のロボット（またはコンピュータチップ）で機能することが、別のものでは壊れてしまう可能性があります。ルーカスは、最適な組み合わせを見つけるために28通りの組み合わせをテストしました。これは、時として「当たり前」と思われるテクニック（先読みや直接的な廃棄など）が、実は間違った動きであることもあるということを示しています。