独自のカーネルオプティマイザーを作成する
Write your own kernel optimiser (blog.csongor.co.uk)
要約
この記事では、パフォーマンス最適化のための新しい言語であるCachetを紹介しています。Cachetは、計算の「何を」と「どのように」を分離し、コンパイラがハードウェアの特性(キャッシュ、メモリ階層、命令セットなど)を明示的に扱うことで、パフォーマンスに関する仮定を検証できるようにします。これにより、手動最適化の複雑さを隠蔽しつつ、コンパイラによる最適化のブラックボックス化を防ぎます。
全文翻訳
独自のカーネルオプティマイザーを作成する
プログラムの最適化は、2つの方法で行われます。1つ目は、目的の結果を計算するプログラムを書き、コンパイラがそれを高速化してくれることを期待する方法です。2つ目は、それが十分でない場合に、データフローがハードウェアに適合するように手動で書き直す方法です。ここで抽象化は破綻します。NiceなPythonライブラリで書かれたものがコンパイラに手に負えなくなると、カスタムカーネル、イントリンシック、インラインアセンブリを書くことになります。
どちらの方法も、出力が出力と重複しないなどの条件の下でのみ意味を保持する変換に依存します。コンパイラ最適化により、元のプログラムを維持できますが、変換は隠蔽されます。手動で最適化されたコードは、変換の結果を示しますが、どこから始めたのかは隠蔽します。
どちらの場合も、重要な決定は、どのブロックがキャッシュに残る必要があるか、どのループがベクトル化できるかなど、私たちが直接見ることのできない場所で行われます。オプティマイジングコンパイラは、ソース言語からは隠されたハードウェアのモデルに基づいてこれらの決定を行います。手動で最適化されたコードでは、これらを頭の中、またはソースファイルのコメントに保持します。
パフォーマンスが重要である場合、私は賢いコンパイラを望みません。代わりに、コンパイラに明示的であることを求めます。それが、パフォーマンスについて推論するのに役立つ言語であるCachetの背後にある考え方です。Cachetでは、バッファがどのキャッシュに留まるか、メモリレベル間でどれだけのデータが移動するか、ハードウェアが提供する命令が言語の一部となります。これにより、情報に基づいた決定を下し、コンパイラに仮定をチェックさせることができます。プログラムが進化するにつれて仮定が保持されなくなると、パフォーマンスの低下ではなく、コンパイルエラーになります。
この記事は、変換そのものについてです。Cachetでは、「何を」計算するかを記述し、それとは別に「どのように」計算するかを記述します。一連の変換、つまりスケジュールが、計算を最適化されたプログラムに変換します。その後、コンパイラは各変換が元の意味を保持していることをチェックします。
実行例として行列乗算を使用します。1行の定義から始めて、キャッシュブロック化されたCPUカーネル、および行列ハードウェアを使用した最適化されたGPUカーネルを導出します。これらの例は私のラップトップ(M4 Max搭載)で実行しましたが、この手法にAppleのハードウェア固有のものは何もありません。CachetはすでにNVIDIAのH100向けにプログラムをチェックしていますが、まだビルドすることはできません。
進捗を確認するために、各スケジュールを同じハードウェア上の最適化ライブラリ実装と比較します。CPUのベクトル命令にはOpenBLAS、行列ユニットにはAppleのAccelerate、GPUにはMLXを使用します。途中の小さなバーは、ライブラリの速度にどれだけ近づいているかを示しており、ライブラリを100%としています。各比較では、同じ行列サイズと精度を使用します。
手動による行列乗算
行列乗算は正しく行うのは非常に簡単ですが、速く行うのは非常に困難です。定義は1行に収まります。
c[i, j] = sum k. a[i, k] * b[k, j]
マシンには少し手助けが必要です。M × K行列とK × N行列の乗算では、3つのネストされたループで操作の順序を明示できます。
c// cはすべてゼロで初期化される
for (int i = 0; i < M; i++)
for (int j = 0; j < N; j++)
for (int k = 0; k < K; k++)
c[i][j] += a[i][k] * b[k][j];
このループネストは、1024 × 1024行列で1コアあたりわずか1.17 GFLOP/s[2]に達します。これは、同じコアでのOpenBLASの速度の約1%です。改善の余地はたくさんあります。
Naiveなループネスト
1.17 GFLOP/s · 1,843.33 ms
1.1% of OpenBLAS's speed
100% = OpenBLAS · CPU · one core · 108 GFLOP/s
CPU · one core · 1024 × 1024 · f32
色は各変数がどれくらいの頻度で変化するかを示しています。iが最も少なく、jがより多く、kは各乗算で変化します。最も頻繁にアクセスされる変数が、配列をどのように移動するかを制御します。ここでは、kはaの行に沿って移動しますが、bの列に沿って移動します。
配列は行ごとに格納されます。b[0][0], b[0][1], そして次の行へと続きます。これは行優先順序と呼ばれます。プロセッサは単一の値を取得しません。値がキャッシュ(コアに近い小さく高速なメモリ)にない場合、キャッシュラインと呼ばれる隣接するバイトのチャンク全体を取得します。これらの隣接する値を読み取ることで、キャッシュされたコピーを使用でき、メインメモリへの別のアクセスを回避できます。
行に沿って移動すると、これらの隣接する値がすぐに使用されます。列に沿って移動すると、1行全体をジャンプすることになり、キャッシュは、その他の値に戻る頃にはラインを置き換えている可能性があります。2つのアクセスパターンの簡単なモデルを以下に示します。
各行はbの行を表し、4つのグループは1つのキャッシュラインです。このモデルでは、キャッシュされた読み取りは1ティック、ミスは8ティックかかります。読み取りはプリフェッチなしで、一度に1つずつ実行されます。
行に沿って
内側のループ for j
次の読み取りは次の要素です。
列に沿って
内側のループ for k
次の読み取りは、1行先の要素です。
キャッシュ内
読み取り中
メモリ待ち
このキャッシュモデルは4ラインを保持し、最も最近使用されていないラインを追い出します。そのため、8ラインの列は、ウォークが戻ってくる前に各ラインを追い出します。
ループを2つ入れ替えるだけで、行ごとのアクセスパターンを得ることができます。
c// cはすべてゼロで初期化される
for (int i = 0; i < M; i++)
for (int k = 0; k < K; k++)
for (int j = 0; j < N; j++)
c[i][j] += a[i][k] * b[k][j];
最も頻繁にアクセスされる変数はjになり、bとcの最後の添え字です。そのため、内側のループはそれらの行に沿って移動し、ラインがキャッシュされている間に隣接する値を使用します。(a[i][k]はこのループ全体で一定です。)大きな行列では、これは大きな違いを生みます。
ループの入れ替え
33 GFLOP/s · 65.64 ms
30% of OpenBLAS's speed
100% = OpenBLAS · CPU · one core · 108 GFLOP/s
CPU · one core · 1024 × 1024 · f32
ループを入れ替えることで、同じ乗算が約28倍高速になりますが、それでも1コアあたりのOpenBLASの速度の30%にすぎません。
鋭い読者はおそらく、Aの各行に対してB全体をまだウォークしていることに気づくでしょう。Bがキャッシュに収まるには大きすぎる場合、パスごとに多くの部分が再度フェッチされる必要があります。ブロック化(これは後でブロック化行列乗算で説明します)は、可能な限り多くの作業を行うまで、入力ブロックをキャッシュに保持します。
ただし、ループの入れ替えは一般的にプログラムの意味を保持しません。ここでは、cがいずれかの入力と重複しない限り、異なるjの値が異なる出力を更新します。各出力は、kの昇順で同じ積を受け取ります。私たちは異なる出力への更新がどのようにインターリーブされるかを変えただけです。これらの条件は記述されておらず、高速なカーネルにはこのような書き換えが積み重ねられています。
コンパイラにこれらの条件をチェックしてもらいたいと考えています。
何を言うか(どのようにではなく)
ループは、必要以上にこれを難しくします。各出力は独立して計算できるにもかかわらず、出力の特定のシーケンスを訪問することを約束します。そのシーケンスを変更する前に、順序のどの部分が重要かを確立する必要があります。これはプログラマーまたはコンパイラにとって面倒な作業です。計算自体を記述する構造を見つけ、それでもハードウェアによくマッピングすることは、言語設計の問題です[3]。
これで、定義をCachet関数として、通常の32ビット浮動小数点数から始めることができます。
cachetcontraction matmul
(reads a: [f32; M, K])
(reads b: [f32; K, N])
-> out c: [f32; M, N] =
c[i, j] = sum k. a[i, k] * b[k, j]
これはコントラクションです。各出力要素の等式で定義される関数です。本体は最初の式です。[f32; M, K]はM行K列の配列であり、readsはその配列を読み取ることを許可します。-> out cは結果の名前です。呼び出し元はcのスペースを提供し、matmulがそれを埋めます。
M, K, Nは次元です。等式は、どの出力が独立しているか、どの入力を合計するか、どの操作を使用するかを示しています。
iとjは左辺に現れるため、自由です。各ペアはcの1つの要素を名前付けし、それは1回だけ書き込まれます。異なるペアは独立した出力を計算します。kはsumの下にのみ現れるため、合計されます。各出力について、入力のペアを乗算し、積を合計します。*と+は要素型から来ています。ここではf32ですが、後で要素がブロック(別の行列)の場合でも同じ式が機能することを確認します。
自由なインデックスは順序について何も言わないため、出力は任意の順序で、またはすべて同時に計算できます。
ループネストの書き換え
コントラクションは、ループネストとして正確な意味を持ちます。Cachetのコンパイラcachetcにcachetc scheduledで印刷するように依頼できます。
スケジュールは、このループネストを別の関数に変換する一連の書き換えです。コンパイラはプログラムをビルドするときに書き換えを一度適用します。結果の関数を呼び出すだけでカーネルが実行されます。
すでに知っている入れ替えが最初に来ます。スケジュールは、それが生成するループ本体の上にあります。書き換えを追跡するには、以前と次を使用してください。現在のステップがハイライトされています。...はステップに関連しないコードを省略します。
schedule swapped of matmul =
zero (i, j) c
hoist (j, k) c
for i in 0 .. M do
for j in 0 .. N do
var acc'0: f32 = -0.0
for k in 0 .. K do
acc'0 = fma (load a[i, k]) (load b[k, j]) acc'0
store c[i, j] = acc'0
各出力は、ゼロから始まる積の合計をkの昇順で計算します。
1.17 GFLOP/s · 1,843.33 ms
1.1% of OpenBLAS's speed
100% = OpenBLAS · CPU · one core · 108 GFLOP/s
CPU · 1024 × 1024 · f32
開始ループネストでは、loadは値を読み取り、storeは値を書き込みます。実行中の合計acc'0はゼロから始まり、semiringパネルで説明されている理由で-0.0と書かれ、最後に一度だけ格納されます。各ステップはfused multiply-add(FMA)を使用します。fma a b accは、積を個別に丸めるのではなく、単一の丸め処理でa * b + accを計算します。
これは、スケジュールが保持しなければならない動作です。各出力は、kの昇順で同じ乗算-加算チェーンを受け取ります。
入れ替え後のループには小さな問題があります。各出力はローカル変数に実行中の合計を保持し、最後に一度だけ格納されます。入れ替え後、次の出力に進み、kの次の値に戻るまで、その合計を保持する必要があります。
最初のステップzero (i, j) cはこれを準備します。まず、独自のループでcのすべての要素にゼロを書き込み、その後、各出力の合計がそのセルが保持するものから開始するようにします。リストは、セルへの更新としてこの合計を示しています。セルから合計をロードし、積を追加し、それを再度ストアすると読むことができます。各合計はゼロから始まり、同じ積を同じ順序で受け取ります。
次にhoist (j, k) cは、合計のステップをjのループの外に移動します。各訪問はセルの合計をロードし、次の積を追加し、それを再度ストアします。
両方のステップの後、下部の行はスケジュールのクレームを要約します。これはコンパイラがチェックしたものです。ここでは、swappedとmatmulの独自のループネストは、要件を満たす任意の入力に対して、ビット単位で同一の結果を生成します。結果の関数はmatmulと同じ配列を取るため、swapped a b cとして呼び出します。
matmulで使用したhoistは、cachet:stepsライブラリのステップ関数です。これは証明レシピを持つ書き換えです。その定義は、一致させるプログラムの一部、その置換、および結果が保持されることをチェックするための指示を提供します。ステップを使用するたびに、チェッカーは実際に書き換えているプログラムに対してこれを確立する必要があります。
他のほとんどのステップは、同じ方法でcachet:stepsに定義されています。splitやorderなどのいくつかのレイアウトステップは、コンパイラに組み込まれています。
ブロック化行列乗算
ここで、鋭い読者の観察に戻ります。異なる出力に対して同じ入力を繰り返しフェッチしています。ブロック化により、複数の出力から計算する間、ブロックをキャッシュに保持できます。
内側のカーネルだけでも数百行になることがあります。BLISのHaswell用倍精度カーネルは約720行です。そのコードの多くはレジスタと命令を扱います。カーネルの周りのコードは、作業をブロックに分割し、スレッドに配布し、特定のマシンのキャッシュ階層の周りのメモリアクセスを整理します。
行列乗算の構造により、その作業を分割する方法がいくつかあります。まずCPUから始めます。ブロック化、入力のパッキング、カーネルのチューニングを行います。次に、同じコントラクションからGPUスケジュールを構築します。
合計をチャンクで処理する
各出力には、処理すべき合計があります。実行中の合計が次のチャンクから引き継がれる限り、それを連続した部分に分割できます。以下は、後で構築するCPUスケジュールtowerの最初の2つのステップです。
最初の2つのステップ
schedule tower of matmul =
zero (i, j) c
split k by 16 as gk ragged
1.5 GFLOP/s · 1,428.42 ms
1.4% of OpenBLAS's speed
100% = OpenBLAS · CPU · one core · 108 GFLOP/s
CPU · 1024 × 1024 · f32
zeroは以前と同様に出力セルを準備します。splitはkの合計を最大16個の積のチャンクに分割します。チャンクにgkという名前を付け、kはチャンク内の位置をカウントします。1つの出力を更新する部分は次の形状になります。
1つの出力のループ本体
for gk in blocks (0 .. K) 16 do
for k in 0 .. gk.len do
let acc = load c[i, j]
store c[i, j] = fma (load a[i, gk[k]]) (load b[gk[k], j]) acc
gk.lenはチャンクの長さ、gk[k]は元の合計の対応するインデックスです。K = 40の場合、チャンクはk = 0から15、次に16から31、次に32から39をカバーします。(raggedは最後のチャンクが短い可能性があることを意味します。)セルはチャンク間でリセットされません。同じ実行中の合計を同じ積を同じ順序で引き継ぎます。
各チャンクに個別の合計を与えてからそれらを結合すると、別の変換になります。これによりチャンクを独立して計算できますが、加算を再編成します。実数では違いはありません(加算は結合法則を満たすため)が、浮動小数点数では各加算が丸められるため、結果が変わる可能性があります。単純なsumではそれは許可されません。後でattentionに進むときに再編成を許可するコントラクションを使用します。
チャンク化により、各出力の合計を部分的に処理できます。隣接する出力間で入力を再利用するには、複数の出力を一緒に処理する必要があります。
出力を超えた入力の再利用
2つの8x8行列でパターンが明らかになります。それらのエントリを4x4ブロックにグループ化すると、行列の2x2行列が得られます。下の乗算は、上記の通常の2x2乗算と同じパターンに従いますが、各エントリはブロックになります。
4x4出力ブロック全体での入力の再利用
各行列を4つのブロックに再編成します。
4つのエントリはそれぞれ4x4行列になります。
読み込みアニメーション...
スクラブ
進行状況
2x2参照
各ブロックには4x4エントリが含まれます
最初の寄与
2番目の寄与
実行中の合計
たとえば、左上の出力ブロックはA[0, 0] × B[0, 0] + A[0, 1] × B[1, 0]です。ここで、インデックスはブロック全体を選択します。各×は行列乗算です。Aブロックの各行は、Bブロックの各列と乗算されます。
その1つの出力ブロックを追跡できます。最初はゼロの16個の実行中の合計を保持します。最初の入力ブロックのペアは、k = 0, 1, 2, 3の積を提供します。16個の合計すべてを更新してから、次のペア(k = 4, 5, 6, 7)の入力を置き換えます。合計はそのままです。両方のペアが寄与した後でのみ、完成した出力ブロックをストアします。
1つの出力を独立して計算するには、Aから8つの値、Bから8つの値を読み取ります。これをすべての16個の出力に対して繰り返すと、256個の入力ロードが必要になります。ブロックを処理する場合、Aから16個、Bから16個の値をロードし、それらを保持しながらすべての16個の出力を更新してから、次のペアを行います。64個の入力ロードです。各Aの値は4つの出力列に寄与し、各Bの値は4つの出力行に寄与します。
このように入力を再利用しても、算術演算は変更されません。ブロック境界を描くだけではこれを達成できません。出力を更新している間、値を近くに保持する必要があります。これらのカウントはアルゴリズムのロードを表しており、メインメモリからの転送ではありません。キャッシュはどちらのバージョンでも一部のロードを満たす可能性があります。
図のキャッシュに保持ビューは、Cの次の行からのいくつかの積を追跡します。完全な行では、Bのウォークは必要なラインを追い出しました。ブロックでは、それらのラインはまだそこにあります。(キャッシュは意図的に小さいため、含まれるすべてを確認できます。)ループの入れ替えは行内の再利用を改善しました。ブロック化により、複数の行にわたる同じ入力を再利用できます。
ブロック化された乗算は、前のものと同じ式ですが、要素が4x4ブロックである2x2行列に適用されます。それが使用する+と×は行列加算と乗算です。それがトリックです。タイリングは、異なる要素型での行列乗算です。(マシンに複数のキャッシュレベルがある場合、これを複数回行うことができます。)
CPU向けスケジューリング
32ビットと64ビットの両方のCPUバージョンが必要ですが、ループの入れ替えはf32のプロパティを何も使用しませんでした。f64のためにコントラクションを再度記述する代わりに、要素型と操作をパラメータにすることができます。
cachetcontraction matmul {S : Semiring}
(reads a: [S.Value; M, K])
(reads b: [S.Value; K, N])
-> out c: [S.Value; M, N] =
c[i, j] = sum k. a[i, k] * b[k, j]
Sは要素型S.Value、操作、およびそれらの法則を提供します。このインターフェースはsemiringと呼ばれます。PlusTimes f32は通常の浮動小数点算術を提供し、そのmul_addにはfmaを使用するため、matmul @(S = PlusTimes f32)はこれまで使用してきた計算です。記事の残りの部分では、この汎用定義を使用します。
図の最初の2つのステップが各合計をチャンクに分割するCPUスケジュールtowerは、そこから続きます。次の2つのステップは行と列もブロックに分割し、orderはループをアウトプットループの外に移動します。これにより、深さkの1つのブロックを取り、それが寄与するすべての出力を訪問します。これにより、キャッシュ内にある間にAとBのブロックを再利用する機会が得られます。このスケジュールはまだ1つのCPUコアで実行されます。図はそれをpackedに追跡し、パッキングとレジスタストレージを追加します。
schedule tower of matmul =
zero (i, j) c
split k by 16 as gk ragged
split i by 16 as gi, 4 as ui ragged
split j by 8 as gj ragged
order (gk, gj, gi, ui, i, j)
... // zero C
for i in 0 .. M do
for j in 0 .. N do
for gk in blocks (0 .. K) 16 do
for k in 0 .. gk.len do
let acc'0 = load c[i, j]
store c[i, j] = S.mul_add ... acc'0
合計は最大16ステップのブロックgkで実行され、各ステップはセルの内容を引き継ぎます。以前のチャンク化の例と同様に、各出力は1つの実行中の合計を保持し、同じ積を同じ順序で受け取ります。
1.5 GFLOP/s · 1,428.42 ms
1.4% of OpenBLAS's speed
100% = OpenBLAS · CPU · one core · 108 GFLOP/s
CPU · 1024 × 1024 · f32
各セルの実行中の合計は、深さブロックごとに引き継がれるため、加算は再編成されません。各ステップは、すべてのサイズの行列に対して結果を保持することを証明する必要があります。Sが操作をどのように実装するかを知る必要はありません。書き換えの前と後で、各出力は同じ操作を同じ値に同じ順序で適用します。したがって、towerは任意のSに対して機能します。
towerは実際にはswappedよりも遅いです。ループをブロックに分割しても、まだ高速な内部カーネルは得られていません。
図の最初のpackステップは新しいスケジュールpackedを開始し、towerが終了したところから続きます。2つのpackステップはAとBのブロックを一時バッファにコピーし、カーネルが読み取るように値を配置します。これらのバッファはpackedのパラメータになり、2つのkeepステップは各バッファがどのキャッシュに留まるべきかを示します。
最後のステップregisters (i, j) into c rows 4 lanes 8 through fmaは、深さループ全体で4x8のCブロックをベクトルレジスタに保持します。ベクトル命令は複数の値を一度に操作します。ここでは、その乗算-加算は4つのf32値を更新します。これにより、スケジュールはマシンのベクトルレジスタに結び付けられるため、SをPlusTimes f32にバインドします。
図はすべてのステップを示していますが、towerとpackedは最初の5つを共有します。これらのステップにschedule fnで名前を付け、ブロックサイズをパラメータにすることができます。
cachetschedule fn block_product (i, j, k) c (MC, MR, NC, KC) =
zero (i, j) c
split k by KC as gk ragged
split i by MC as gi, MR as ui ragged
split j by NC as gj ragged
order (gk, gj, gi, ui, i, j)
schedule tower of matmul =
block_product (i, j, k) c (16, 4, 8, 16)
schedule packed of matmul @(S = PlusTimes f32)
(mut packA: [f32; 16, 16] in PanelMajor 4 at DRAM)
(mut packB: [f32; 16, 8] at DRAM) =
block_product (i, j, k) c (16, 4, 8, 16)
pack a into packA along gi over (a0, a1)
keep packA along gi within L2 into packA_L2
pack b into packB along gj over (b0, b1)
keep packB along gj within L1 into packB_L1
registers (i, j) into c rows 4 lanes 8 through fma
hoistと同様に、(i, j, k) cは書き換えるインデックスと出力を名前付けします。MCとMRは外側と内側の行ブロックサイズを選択し、NCは列ブロックサイズ、KCは深さを選択します。両方のスケジュールは同じサイズを渡します。packedはその後、呼び出しの下のステップを追加します。
block_productの呼び出しは、コンパイラがスケジュールを読み取るときにそのステップに展開されます。後続のステップは、それらが生成するループで引き続き作業できます。packは入力をコピーし、keepはキャッシュ要件を記録し、registersは実行中の合計をレジスタに保持します。カーネルには関数呼び出しは残りません。
スケジュール関数は他のスケジュール関数を呼び出すこともできるため、最適化をより小さなものから構築できます。各書き換えは、先行するステップ(ヘルパーからのものを含む)によって残されたプログラムに対してチェックされます。チェックは変換とともに合成されます。各ステップが指定された条件の下で結果を保持する場合、シーケンス全体も保持します。
PanelMajor 4は、4行ごとのグループでAをレイアウトし、各列の4つの値を連続したメモリに配置します。内部カーネルは各深さステップで4つの値を読み取り、このレイアウトはそれらをまとめて保持します。Bのバッファは通常の行優先レイアウトを保持するため、そのステップの8つの値も連続しています。packA[i, k]はまだ書き込みますが、参照するアドレスのみが変更されます。
スクラッチバッファはメインメモリ(DRAM)にあり、keepはカーネルが読み取るキャッシュビューの名前を付けます。キャッシュ要件は、生成された関数の宣言に表示されます。
cachetscratch packA, packB
working_set
@L1 { keep packB = descriptor packB }
@L2 { keep packA = descriptor packA }
scratchは、カーネルが各バッファ位置を読み取る前に書き込むことを要求します。したがって、呼び出し元はバッファを事前にクリアする必要はありません。working_set行は、どのバッファがどのキャッシュに留まるかを示し、packedの呼び出し元はそれらが収まることを示す必要があります。メモリ階層パネルは、バッファがどこに配置されるかを示します。ブロックサイズはここでは意図的に小さくされています。
高速化
packedは、同じコアで108 GFLOP/sに達するOpenBLASに対して、47 GFLOP/sで2つの1024x1024行列を乗算します。
移動しているデータ量はどれくらいか?
入力のコピーは追加の作業です。カーネルがキャッシュから繰り返し読み取ることができ、メインメモリに戻る必要がないため、これが報われると期待しています。しかし、実際にどれだけのコピーを要求したのでしょうか?
コンパイラは各関数が行うことの記録を保持しており、cachetc accountはそれを1つの操作ごとに印刷します。以下はpackedの短縮版です。
packed
operations
loop host x 1
writes c 4 * M * N
loop host x ceil (K / 16) * ceil (N / 8)
reads b 512; writes packB 512
loop host x ceil (K / 16) * ceil (M / 16) * ceil (N / 8)
reads a 1024; writes packA 1024
loop host x ceil (K / 16) * ceil (M / 16) * ceil (N / 8)
reads c 512, packA_L2 1024, packB_L1 2048; writes c 512; work fma 2048, ...
各xの後の数値は、その操作が実行される回数を示します。最初の行はcをゼロにし、そのすべての4 * M * Nバイトをゼロにします。次の2行は、Bの16x8ブロックとAの16x16ブロックをバッファにコピーします。readsとwritesはバイト数を数え、work fmaは乗算-加算の回数を数えます。
最後の行は1つのブロックでの計算です。L2からパックされたAを、L1からパックされたBを読み取り、2,048回の乗算-加算を実行します。繰り返し回数はM、N、Kを使用するため、作業がどのように行列とともに増加するかを確認できます。
生成された関数は、上記のworking_setの隣に、このトラフィックの制限も宣言します。これらの行は、各パックによって移動されたキャッシュラインの数を数えます。
cachetmovement
traffic packB_pull = ceil (K / 16) * ceil (N / 8) *
lines (span_bytes packB.span) from DRAM to L1 and back
traffic packA_pull = ceil (K / 16) * ceil (N / 8) * ceil (M / 16) *
lines (span_bytes packA.span) from DRAM to L2 and back
呼び出し元はこのトラフィックに制限を設けることもできます。32x32行列2つでは、上記のループ順序は、深さブロック、列ブロック、行ブロックのすべての組み合わせに対してAを1回パックします。2x4x2 = 16回のパックです。呼び出し元が8回のみ許可する場合、呼び出しは拒否されます。スケジュールを変更するか、追加のトラフィックを許可する必要があります。完全な例と拒否は、呼び出し元がこの予算をどのように記述するかを示しています。
アカウントは、キャッシュのモデルであるプラットフォームファイル内で正確ですが、プリフェッチャー、置換ポリシー、またはキャッシュを共有する別のプロセスについては何も知りません。これらのカウントを減らすことがカーネルをさらに高速化するかどうかは、測定する必要があります。
カーネルのチューニング
私たちのブロックは読み取るには十分小さいですが、保持されているキャッシュよりもはるかに小さいです。明らかな次のステップは、それらを大きくすることです。
schedule packed of matmul @(S = PlusTimes f32)
(mut packA: [f32; 16, 16] in PanelMajor 4 at DRAM)
(mut packB: [f32; 16, 8] at DRAM) =
...
keep packB along gj within L1 into packB_L1
registers (i, j) into c rows 4 lanes 8 through fma
for gk in blocks (0 .. K) 16 do
for gj in blocks (0 .. N) 8 do
... // pack B and keep it at L1
for gi in blocks (0 .. M) 16 do
... // pack A and keep it at L2
for ui in blocks (0 .. gi.len) 4 do
var acc'0: [Vec f32 8; 4] = ...
... // load C, accumulate across k, and store C
packedは、ブロックサイズが16行、8列、深さ16ステップ、および4x8レジスタイルのままです。
47 GFLOP/s · 45.39 ms
44% of OpenBLAS's speed
100% = OpenBLAS · CPU · one core · 108 GFLOP/s
CPU · 1024 × 1024 · f32 · NEON vectors
packed: bits of matmul_PlusTimes_f32
最初のステップ、より大きなブロックは、主にサイズを変更します。Aのブロックは現在512行x256列(512KB)、L2に保持され、Bのブロックは256x8、L1に保持されます。これらの背の高い長方形ブロックはしばしばパネルと呼ばれます。驚くべきことに、ほとんど速くなりません。48 GFLOP/sです。(正しさの証明はこれに完全に満足しています。)
トラフィックアカウントは、繰り返しのコピーが多いことを示しています。Aのトラフィック行のceil (N / 8)という係数は、gjから来ています。これはまだgiの外にあります。Bの各パネルに対してAのパネルを再度パックします。1024x1024の場合、1つの乗算で512KBのコピーが1,024回行われます。これらのサイズで書かれたトラフィック契約は、この順序を拒否できます。
行優先はorderでgiをgjの前に置くため、行が列の外側にあり、ceil (N / 8)という係数がBの行に移動します。そのパネルは64倍小さいです。これにより66 GFLOP/sになります。
それでもOpenBLASの約61%にすぎません。もう1つの問題は、自分の結果を待っていることです。M4 Maxのベクトルfmaは、同じチェーンの次のfmaで結果を使用できるようになるまで4サイクルかかります。コアはサイクルあたり4つの独立したベクトルfmaを開始できるため、以前の結果が送信されている間にそれを行うには16個の独立したチェーンが必要です。
各ベクトルは4つのf32値を保持するため、4x8タイルは8つのベクトルしか占有しません。それら8つを更新した後、再度更新する前に待つ必要があります。タイルを広げると、その間に作業できる独立した合計が増えます。
出力タイル
各グループ4つの合計は1つのベクトルです。
v1 v5 v9 v13
v2 v6 v10 v14
v3 v7 v11 v15
v4 v8 v12 v16
4 × 8
8個の独立したベクトル
エッジをドラッグするか、上のサイズを選択します。
4つのベクトルFMAパイプライン
1つのパイプラインあたり1サイクルあたり1つの更新。
開始
準備完了、4サイクル遅延
v1 v5 v9 v13
v2 v6 v10 v14
v3 v7 v11 v15
v4 v8 v12 v16
4サイクルで開始された更新
4
4
4つの更新を開始できます。
8つのベクトルは2サイクルの作業を提供し、その後最初の結果を待つ2サイクルの作業を提供します。タイルを広げると、その間に更新できる独立した合計が増えます。
4サイクルウィンドウの繰り返し、スローダウン。これは更新間の依存関係を分離します。ロードやその他の命令は省略されています。
プラットフォームファイルは、ベクトルあたりの値の数(lanes)、サイクルあたりに開始できるfmaの数(fma_pipes)、および結果を使用する前の遅延(fma_latency)を提供します。これらを使用して、スケジュールの隣に要件を記述できます。最後のステップはregisters (i, j) into c rows MR lanes NR through fmaになります。
cachetconst MR : Nat = 4
const NR : Nat = 8
proof enough_chains =
assert MR * ceil (NR / platform.lanes @Vec @f32) >=
platform.fma_pipes @Vec * platform.fma_latency @Vec
4x8タイルでは拒否されます。
could not prove proof enough_chains: MR * ceil (NR / platform.lanes Vec f32) >= platform.fma_pipes @Vec * platform.fma_latency @Vec
カウントしている独立したチェーンの数を数えていた読者は、何を試すべきかを知っているでしょう。NR = 16です。4行それぞれが4つのベクトルを占有し、16個の独立したチェーンを提供します。そして証明は通ります。fastは現在、OpenBLASと同じくらい高速な116 GFLOP/sで実行されます。
各変更が1コアで追加するもの
1つのコアで、より広いタイルはfastをOpenBLASの速度に近づけ、packedの約2.4倍の速度にします。
CPU · one core
1024 × 1024 · f32 · NEON vectors
| チューニングステップ | ライブラリに対する相対速度 | GFLOP/s | ライブラリ速度 |
|---|---|---|---|
packed 初期スケジュール | 47 | ||
| より大きなブロック キャッシュをより多く使用 | 48 | ||
| 行優先 小さなパネルを再パック | 66 | ||
| より広いタイル 4x16出力 · fast | 116 | ||
| OpenBLAS NEONカーネル | 108 |
GFLOP/s、高いほど良い。破線は、この実行でのOpenBLASの速度を示します。すべてのバージョンは、matmulとまったく同じ結果を生成します。これらのチューニングステップは、下の概要とは別の実行で一緒に測定されました。
fastは依然としてmatmulとまったく同じ結果を生成します。後でレジスタを節約するためにタイルを狭くした場合、enough_chainsチェックは失敗し、再導入する依存関係を指摘します。このチェックはプラットフォームファイルの数値に依存します。Appleはレイテンシやスループットを公開していないため、ファイルは公開された測定値を使用します。
幅を見つけるためにCachetに尋ねることもできました。MRは4に固定されたままで、const NR : Nat = 16を次のように置き換えることができます。
cachetsynth const NR : Nat =
minimize n in (n): n where
n > 0, n <= 64,
n % platform.lanes @Vec @f32 == 0,
MR * ceil (n / platform.lanes @Vec @f32) >=
platform.fma_pipes @Vec * platform.fma_latency @Vec
これは、ベクトル全体を埋め、十分な独立したチェーンを提供する、1から64までの最小の幅を求めます。上記のプラットフォームでは、それは16です。したがって、4x8タイルを拒否した条件は、幅を選択することもできます。synth constはコンパイル時に数値を決定し、残りのスケジュールはその数値が配置された状態でチェックされます。自分で記述したかのように。
複数のパラメータを一緒に選択することもでき、候補はコスト式(たとえば、乗算-加算あたりの推定ロードコスト)でランク付けされます。有望な候補は引き続きベンチマークします。モデルでの低コストは、短い実行時間を意味する必要はありません。
他のコアの使用
これで1コア用の高速カーネルができました。他のコアを使用するには、出力行をそれらの間で分割できます。bandsでは、parallel giは64行のブロックに対するループを独立した反復のグリッドに変換します。これはホストで実行されるため、CPUスレッドが行のバンドを取得します。
各反復には書き込みウィンドウがあります。これは、更新を許可されている出力の部分です。コンパイラは、格納する行からこれを推測し、ウィンドウが重複しないことをチェックします。スレッドは同じ入力を読み取ることができますが、互いの出力を書き込むことはできません。
parallelもライブラリステップであり、完全に表示するには短すぎます。
cachetstep fn parallel t =
from
for t in $lo .. $hi do
$body
to
grid t in $lo .. $hi do
$body
この場合、relate証明レシピはありません。生成されるグリッドは、ウィンドウが重複しないことを証明する必要があります。
スレッドはパックされた入力を共有します。Aは深さブロックごとに1回、各行に対してパックされ、Bは16列のグループでパックされ、L2に保持されます。
cachetschedule bands of matmul @(S = PlusTimes f32)
(mut packA: [f32; M, 256] in PanelMajor 4)
(mut packB: [f32; 256, 1024] in ColumnPanels 16 at DRAM) =
zero (i, j) c
// Block and reorder the loops.
split k by 256 as gk ragged
split j by 1024 as gj, 16 as uj ragged
split i by 64 as gi, 4 as ui
order (gk, gj, gi, ui, uj, i, j)
// Give each CPU thread a band of output rows.
parallel gi
// Pack the inputs for reuse across the output bands.
pack a into packA along gk over (a0, a1)
strip a0 4 (pa, ra)
interchange (ra, a1)
parallel pa
pack_lanes b into packB along gj over (b0, b1, bt) lanes 16
keep packB along gj within L2 into packB_L2
parallel b0
// Accumulate a 4 × 16 output block in vector registers.
registers (i, j) into c rows 4 lanes 16 through fma
757 GFLOP/s · 2.84 ms
88% of OpenBLAS's speed
100% = OpenBLAS · CPU · all cores · 863 GFLOP/s
CPU · all cores · 1024 × 1024 · f32
パッキングループも並列です。strip a0 4 (pa, ra)はAの行を4行ごとのグループに分割し、paがグループを選択し、raが行を選択します。interchange (ra, a1)は列ループをそれらの4行の外に移動させるため、コピーはPanelMajor 4順序で隣接する値を書き込みます。parallel paにより、個別のスレッドが個別のグループをパックできます。
Bの場合、ColumnPanels 16は16列ごとのグループを格納し、各グループの行は互いに隣接しています。pack_lanesは、そのレイアウトに一度に16個の値をコピーし、parallel b0は行を分散します。NEONでは、16個のf32値は4つのベクトルに収まります。
すべてのコアで、bandsは757 GFLOP/sに達し、OpenBLASは863に達します。合計はスレッド間で分割されないため、結果はmatmulと同一です。
CPU行列ユニット
fastとbandsはCPUのベクトル命令であるNEONを使用します。M4には、SME、ArmのScalable Matrix Extensionを介してアクセスされる行列ユニットもあります。倍精度浮動小数点数(f64)には、別の乗算-加算であるouter_fma_primitiveを選択できます。これは8x8ブロックを外積で更新します。外積は、Aの8つの値のそれぞれをBの8つの値のそれぞれと乗算し、ブロックの64個の合計それぞれに1つの積を寄与します。smeはCの32x16タイルを8つのそのようなブロックとして保持し、M4 Maxの2つの行列ユニット(パフォーマンスコアの各クラスタに1つ)のために残りの作業をレイアウトします。
schedule sme of matmul @(S = PlusTimes f64)
(mut packA: [f64; M, 3072] in PanelMajor 32)
(mut packB: [f64; 3072, 256] in ColumnPanels 16 at DRAM) =
split k by 3072 as gk ragged
split j by 256 as gj, 16 as uj
...
for i in 0 .. M do
for j in 0 .. N do
var acc'0: f64 = -0.0
for k in 0 .. K do
acc'0 = fma ... acc'0
store c[i, j] = acc'0
以前と同じコントラクション。
0.83 GFLOP/s · 69,476.69 ms
<0.1% of Accelerate's speed
100% = Accelerate · CPU · matrix units · 871 GFLOP/s
CPU · 3072 × 3072 · f64 · SME matrix instructions
bandsと同様に、smeは行をバンドに分割しますが、より大きなブロックを使用します。1536行の各バンドは独自のコアで実行されるため、3072x3072では各行列ユニットが1つのバンドを処理します。入力のパッキングは単なるコピーであるため、その作業はすべてのコアで実行できます。
バンド内では、ステップ4のorderはCの行に沿ってタイルを訪問します。次の32行に移動する前に同じ32行を処理するため、Cへのアクセスは同じメモリページに保持されます。列に沿ってタイルを訪問すると、各タイルが32個の新しい行で開始されます。
この行列サイズでは、1つの深さブロックが全体の合計をカバーします。3072ステップです。各タイルの実行中の合計は、合計が完了するまで行列ユニットに保持でき、結果は一度だけストアされます。768個のブロックの場合、各出力タイルを4回書き込み、ブロック間で再度読み取る必要があります。これらの追加転送は、実行時間の約10分の1を消費します。
ここでもzeroステップはありません。最初の深さブロックは行列ユニットで実行中の合計を-0.0で開始するため、Cをクリアしてから再度読み取る必要はありません。このサイズでは、Cは一度だけ書き込まれます。2つのライブラリステップといくつかの新しいチェッカー規則により、matmulの結果と同一の結果を維持しながら、これが可能になります。
深さ沿いの各ステップで、Aの列とBの行を一度ロードし、SME2のマルチベクトルロード命令を使用します。その後、すべての8x8ブロックがこれらの値を再利用します。
チェッカーの場合、outer_fma_primitiveは、アキュムレータの各アクティブセルに対するスカラーfmaです。ここではLLVMバックエンドが行列命令を選択します。独自のテンプレートを提供することなく、コンパイラとハードウェアが操作を正しく実装することに依存します。
3072x3072のf64行列で、smeは894 GFLOP/sに達し、同じ行列ユニットで871 GFLOP/sのAppleのBLASであるAccelerateよりもわずかに高速です。bandsと同様に、スレッド間で合計を分割しないため、matmulと同じ結果を生成します。
GPU向けスケジューリング
GPUスケジュールはmatmulから再度開始されます。以下の例では、SをPlusTimes f32にバインドし、パフォーマンスバーは4096x4096行列でのMLXと比較します。
独立した出力
CPUスレッドに独立した出力行のバンドを割り当てました。GPUでは、作業単位は1つの出力要素です。
A GPUは同じ小さなプログラム、カーネルと呼ばれるものを何度も実行します。各呼び出しはスレッドであり、そのインデックスはどの作業部分を実行するかを伝えます。スレッド(i, j)はc[i, j]を計算します。Aの行iとBの列jを読み取り、1つの実行中の合計を保持します。GPUは利用可能なスペースとしてスレッドをハードウェアに割り当てます。それらはすべて同時に実行される必要はありません。
ここでもグリッドを使用します。
schedule rows of matmul @(S = PlusTimes f32) on M4Gpu =
grid over (i, j)
for i in 0 .. M do
for j in 0 .. N do
var acc'0: f32 = -0.0
for k in 0 .. K do
acc'0 = fma ... acc'0
store c[i, j] = acc'0
各出力は、ゼロから始まる積の合計をkの昇順で計算します。
0.65 GFLOP/s · 211,498.49 ms
<0.1% of MLX's speed
100% = MLX · GPU · 13,113 GFLOP/s
CPU · 4096 × 4096 · f32
grid over (i, j)は、rowsと同様に、独立した出力から開始します。このスケジュールでは、各反復は1つのGPUスレッドとして実行されます。on M4Gpuは、ファイルの上部にあるターゲットマシンの説明からデバイスを選択します。結果の関数はrows a b cで呼び出します。
グリッドは通常のCachet構造であるため、rowsを手動で記述することもでき、同じ方法でチェックされます。特に、グリッドのヘッダーは、各反復が何を書き込むことができるかを示しています。
cachetgrid on M4Gpu i in 0 .. M, j in 0 .. N writes c[i, j] as ct do
writes c[i, j]は、グリッド本体でctとして参照される反復の書き込みウィンドウを提供します。Cachetは、異なる反復のウィンドウが重複しないこと、および各反復が自身のウィンドウ内のみに書き込むことをチェックします。たとえば、32x32行列に対してこのグリッドを手動で記述したが、各結果を1列右のc[i, (j + 1) % 32]に格納した場合を考えます。チェッカーは、ウィンドウ外に書き込むスレッドを見つけます。
could not prove a grid iteration reaches only its own window: i == i && (j + 1) % 32 == j
counterexample: j = 0
rowsはmatmulと同じ乗算-加算を同じ順序で実行しますが、GPUで実行します。GPUはCPUとは異なる方法で一部の浮動小数点値を処理する場合があります。たとえば、M4 MaxのGPUはサブノーマル(ゼロに近い非常に小さい数)をゼロにフラッシュします。したがって、保証は、rowsがそのGPUの算術演算を使用して評価されたmatmulとまったく同じ結果を生成することです。
グリッドレイアウトは現在組み込みステップです。そのサイドコンディションはチェックされますが、その書き換え法則は信頼するコンパイラの一部です。
タイル
rowsは各グリッド反復に1つの出力数を与えます。代わりに、複数のスレッドが協力して1つの出力タイル全体を与えることができます。Cachetでは、そのタイルは通常のローカル行列値です。アキュムレータ、または入力からロードされたブロックです。グリッドは独立した作業を分割します。タイルは各反復が処理する値を保持します。
図は32x32行列を使用し、16x16の出力タイルで、kに沿って8ステップずつ進みます。
M4のGPUは、SIMDグループと呼ばれる32個のスレッドのグループでスレッドを実行します。グループは8x8行列演算を集合的に実行できます。私たちの16x16出力タイルには4つの8x8部分があるため、各部分を1つのSIMDグループに割り当てます。それら4つのグループがスレッドグループを構成し、1つのタイルで協力します。個別のスレッドグループが4つの独立した出力タイルを計算します。
32x32出力をスレッドまたはスレッドグループに分割
1,024スレッド。それぞれ1つの出力。
アウトラインはC[9, 10]をマークしています。
スケジュールは次のとおりです。
schedule tiled of matmul @(S = PlusTimes f32) on M4Gpu =
grid over (i, j)
tiles (i, j, k) (16, 16) (8, 8)
for i in 0 .. M do
for j in 0 .. N do
var acc'0: f32 = -0.0
for k in 0 .. K do
acc'0 = fma ... acc'0
store c[i, j] = acc'0
各出力は、ゼロから始まる積の合計をkの昇順で計算します。
0.65 GFLOP/s · 211,498.49 ms
<0.1% of MLX's speed
100% = MLX · GPU · 13,113 GFLOP/s
CPU · 4096 × 4096 · f32
grid over (i, j)はrowsと同様に独立した出力から始まります。tilesステップはそれらを16x16タイルにグループ化し、各SIMDグループに8x8部分を割り当てます。これらの部分は重複しないため、各出力には依然として1つの所有者がいます。
kについては、tilesはtowerと同様に、チャンク全体で同じ実行中の合計を保持します。使用するGPU行列命令はsimdgroup_mma8と呼ばれます。その参照本体は、各ブロックの8つの積をkの昇順で加算するため、各出力は同じ乗算-加算チェーンを受け取ります。これは現在8つずつです。
tは出力タイルの実行中の合計をゼロから開始し、xとyは次の入力ブロックのペアです。mma x y tは行列乗算-加算です。2つの入力ブロックを乗算し、それらの積をtに追加します。合計は深さループ全体でtに保持され、最後にストアされます。
実際には、tilesは各要素を8x8行列にし、simdgroup_mma8をその乗算-加算とします。これはまだ私たちのmatmulですが、異なる要素型です。要素の1つを表示するには、レベルを選択します。
3つの行列型での1つの要素
[f32; 8, 8]
1つの8x8ブロック。1つのSIMDグループのタイルの部分。各simdgroup_mma8はkの8つのステップをすべての64個の出力に一度に加算します。
入力はSIMDグループ内で再利用されます。異なるグループは依然として入力を個別にロードします。それらのロードも共有するには、スレッドグループメモリ、つまりスレッドグループ内のすべてのグループがアクセスできる小さなメモリが必要になります。各グループにさらに多くの出力を処理させることもできます。これにより、各入力がより多く再利用されますが、より多くの実行中の合計のためのスペースが必要になります。次に、より大きなタイルを試します。
コンパイラは行列乗算-加算の参照実装を推論し、コードテンプレートを使用してGPU命令に置き換えます。GPU命令を参照に対してテストしますが、それらが常に同一の結果を生成することを証明しないため、テンプレートは信頼できる仮定のままです。
tiles自体はライブラリステップです。その関係はhoistと同様の方法でチェックされます。
より大きなタイル
tiledは各SIMDグループにアキュムレータの8x8ブロックを1つだけ与えます。より多くの出力を与えることができるため、各入力がより多く再利用されます。64x32の出力タイルと32x16の部分を使用すると、各SIMDグループは8つのアキュムレータブロックを保持します。
cachetschedule big_tiles of matmul @(S = PlusTimes f32) on M4Gpu =
grid over (i, j)
tiles (i, j, k) (64, 32) (32, 16)
12,407 GFLOP/s · 11.08 ms
95% of MLX's speed
100% = MLX · GPU · 13,113 GFLOP/s
GPU · 4096 × 4096 · f32
4096x4096で、big_tilesは12,407 GFLOP/sに達します。これはtiledの速度の約2.3倍、MLXの95%です。結果は依然としてtiledと同一です。
結果の比較
これで、スカラーfma、ベクトルfma、CPUのouter_fma_primitive、GPUのsimdgroup_mma8という4つの異なる乗算-加算操作を使用して、同じmatmulを実装しました。各ケースで、スケジュールは一度に更新する出力ブロックを選択し、それを更新する命令を選択します。
ここでは、使用するハードウェアごとにグループ化されたすべての行列乗算スケジュールをまとめます。各グループは、Cachetと同一の行列サイズと精度を持つライブラリを比較します。
スケジュールがライブラリと比較される方法
Apple M4 Max。GFLOP/sが高いほど、乗算は高速になります。各グループでは、破線はライブラリの速度で、100%に設定されています。
CPU · one core
1024 × 1024 · f32 · NEON vectors
| スケジュール | ライブラリに対する相対速度 | GFLOP/s | ライブラリ速度 |
|---|---|---|---|
matmul | 1.2 | ||
swapped | 33 | ||
tower | 27 | ||
packed | 49 | ||
fast | 116 | ||
| OpenBLAS | 108 |
CPU · all cores
1024 × 1024 · f32 · NEON vectors
| スケジュール | ライブラリに対する相対速度 | GFLOP/s | ライブラリ速度 |
|---|---|---|---|
bands | 757 | ||
| OpenBLAS | 863 |
CPU · matrix units
3072 × 3072 · f64 · SME matrix instructions
| スケジュール | ライブラリに対する相対速度 | GFLOP/s | ライブラリ速度 |
|---|---|---|---|
sme | 894 | ||
| Accelerate | 871 |
GPU
4096 × 4096 · f32 · Metal
| スケジュール | ライブラリに対する相対速度 | GFLOP/s | ライブラリ速度 |
|---|---|---|---|
rows | 2,399 | ||
tiled | 5,282 | ||
big_tiles | 12,407 | ||
| MLX | 13,113 |
バーの長さは、各スケジュールを独自のライブラリベースラインと比較したもので、他のハードウェアグループとの比較ではありません。行列サイズと精度はグループ間で異なります。各グループ内では、Cachetとライブラリで同じです。
これらのサイズでは、fastは1コアでOpenBLASと同等であり、smeはAccelerateよりもわずかに高速です。bandsは全コアでOpenBLASの速度の88%に達し、big_tilesはGPUでMLXの95%に達します。各カーネルは、ターゲットデバイスの算術演算を使用してmatmulとまったく同じ結果を生成する必要があります。ライブラリはこれを約束しません。タイミングを取る前に、各カーネルをその参照と比較しました。
Attention
これまでのところ、すべてのスケジュールは加算の元の順序を保持してきました。Attentionは、この要件を緩和する理由を与えてくれます。
Attentionは、シーケンス内の各位置が他の位置からの情報を混合できるようにし、関連性の高いものにより多くの重みを与えます。各位置には、他の位置のキーと比較するためのクエリがあり、結果の重みは各値をどれだけ含めるかを示します。Attention Is All You NeedのTransformerはこれを次のように記述しています。
Attention(Q, K, V) = softmax(QKT / √dk)V
2つの行列乗算があり、その間にsoftmaxがあります。最初の乗算はスコアを計算し、softmaxは各行を合計が1になる重みに変換し、2番目の乗算は値を混合します。クエリ幅dkの平方根でスコアを割ります。以下の例では、このスケールファクターを省略します。
コントラクションとしての表示。qはクエリ、ktは転置されたキー、vは値です。Onlineは重み付き合計のライブラリ実装であり、すぐに展開します。
cachetcontraction attend
(reads q: [f32; 64, 16])
(reads kt: [f32; 16, 32])
(reads v: [f32; 32, 16])
-> out y: [f32; 64, 16] =
s[i, j] = sum c. q[i, c] * kt[c, j]
y[i, d] = normalised (reduce[reassoc] Online j. key (s[i, j]) (v[j, d]))
スコア行列には、すべてのクエリ-キーペアのエントリがあります。自己アテンションの場合、シーケンス長を2倍にすると、その行列は4倍になります。その行列の格納と再読み取りのコストを回避することが、FlashAttentionの動機です。
スコアのブロックを計算し、使用し、破棄したいと思います。Softmaxはこれを厄介にします。各スコアを指数化し、まだ計算していないスコアを含む行のすべての指数化された値の合計で割ります。オーバーフローを防ぐために、指数化する前に、行の最大スコアを減算します。その最大値もまだわかりません。
Onlineは、より大きなスコアが到着したときに再スケーリングできる実行中の概要を保持します。key s vは1つのキーの概要を作成し、reduce[reassoc] Online j.はsumが数値を結合するように、これらの概要をj全体で結合します。概要は、合計の重みと値の重み付き合計を保持します。最後に、normalisedは重み付き合計を合計の重みで割ります。サイドパネルは実装を示しています。[reassoc]アノテーションは、削減の再編成を許可するものです。
コントラクションはキーを1つずつ結合します。代わりに、スケジュールは古い概要とスコアのブロック全体にわたる最大値を見つけ、概要を一度再スケーリングしてから、ブロックの寄与を追加します。重みの合計と値の重み付き合計の両方を同じ係数で再スケーリングすると、実数上でのそれらの比率は変更されません。実数上では比率は変更されませんが、浮動小数点数では結果が変わる可能性があります。
1つのキーを1つずつ結合すると、削減が再編成されるため、浮動小数点数で結果が変わる可能性があります。以下は6つのf32値で、左側は1つずつ、右側はペアで追加されたものです。
加算順序が丸めに影響する方法
各ツリーは同じ6つのf32値を加算します。すべての+は、最も近い表現可能な値に丸められ、タイは偶数に丸められます。正確な合計は1です。
左から右
5つの依存加算
+2²⁵
+0
+1
+1
+1
2²⁵
0
-2²⁵
1
0
0
結果: 1
3つの部分合計
3つの依存レベル
+2²⁵
+-2²⁵
+0
+0
+0
2²⁵
0
-2²⁵
1
0
0
結果: 0
チェーンは1になり、グループ化された合計は0になります。どちらも5回の加算を実行します。依存レベルは、どの加算が同時に実行できるかを示しており、測定時間ではありません。
どちらの式も実数上では1に等しくなります。f32では、-2²⁵に1を加えると-2²⁵に丸められるため、ペアバージョンは1を失い、ゼロを返します。どちらの順序も一般的に精度が高いわけではありません。他の値では、チェーンが精度を失う方になる可能性もあります。しかし、それらは異なるため、Cachetはコントラクションが再編成を許可した削減のみを再編成します。それがattendの[reassoc]の目的です。これは異なる丸めを許可します。これがないと、以下のスケジュールは拒否されます。
a fused block of `j` combines a block's keys at once, regrouping the reduction, which it permits with `[reassoc]`, `reduce[reassoc] Online j.`
その許可があれば、ブロックのキー全体を実行中の概要と結合するライブラリ法則を使用できます。タイル操作が残りを処理します。それらは、行に沿って最大値または合計を見つけ、各スコアを指数化し、結果の重みを別の行列乗算で使用できます。スコアは全体を通してローカルに保持されるため、完全なスコア行列を書き出す必要はありません。積の後のReLUと同様に、コントラクションの中間値は、スケジュールが要求した場合にのみ独自のバッファを取得します。
スケジュールされたバージョンをflashと呼びます。丸めを変更することを許可したため、attendとまったく同じ結果を生成することを要求できなくなりました。新しい削減順序に従う参照が必要です。Cachetはこのシャドウを、コントラクションに順序変更のみを行うステップを適用することによって構築します。グリッド、タイル、またはスレッドのないプレーンなループが残ります。flashは、この参照とまったく同じ結果を生成する必要があります。これはクレームのflash_shadowとして表示されます。
schedule flash of attend on M4Gpu =
split i by 32, j by 8, c by 16
grid over i.outer
compute s at j.outer
reduce j.inner by (max: halving, sum: order)
parts [8, 16]
element [f32; 8, 8]
for i in 0 .. 64 do
for d in 0 .. 16 do
var acc'1: Online.Value = Online.empty ()
for j in 0 .. 32 do
... // compute this key's score in acc'0
acc'1 = Online.combine acc'1 (key acc'0 (load v[j, d]))
store y[i, d] = normalised acc'1
スコアを中間値とする1つのコントラクション。
ここにはタイミングバーを省略しました。クエリが64、キーが32、幅が16しかないため、GPU起動オーバーヘッドが支配的です。したがって、この例はスケジュールの速度の有用な比較には小さすぎます。
cachetc scheduled --shadowは参照ループを印刷します。以下は短縮版です。mはこれまで見た最大スコア、lはそれにスケーリングされた重みの合計、oは対応する値の重み付き合計です。
cachetfn flash_shadow
(reads q: [f32; 64, 16])
(reads kt: [f32; 16, 32])
(reads v: [f32; 32, 16])
-> out y: [f32; 64, 16]
=
for i in 0 .. 64 do
for d in 0 .. 16 do
var m: f32 = from_bits (4286578688 as u32) // Negative infinity
var l: f32 = -0.0
var o: f32 = -0.0
for gj in 0 .. 4 do
var s_0: f32 = -0.0
for c in 0 .. 16 do
s_0 = fma (load q[i, c]) (load kt[c, gj * 8 + 0]) s_0
...
let m2: f32 =
max
m
(max
(max (max s_0 s_4) (max s_2 s_6))
(max (max s_1 s_5) (max s_3 s_7)))
let alpha: f32 = rescale m m2
l =
l * alpha +
(-0.0 + exp (s_0 - m2) + exp (s_1 - m2) + ... + exp (s_7 - m2))
var mix: f32 = o * alpha
mix = fma (exp (s_0 - m2)) (load v[gj * 8 + 0, d]) mix
...
mix = fma (exp (s_7 - m2)) (load v[gj * 8 + 7, d]) mix
o = mix
m = m2
store y[i, d] = o / l
各gjの反復は8つのキーを処理します。まずそれらのスコアを計算し、次にペアを比較してブロックの最大値を見つけます(スケジュールでのmax: halvingのように)。m2はその最大値と以前のmの大きい方です。概要はm2に一度スケーリングされ、ブロックの重みは順序通りに追加されます(sum: orderのように)。初期のfrom_bits値は負の無限大です。
これらのループは、GPUの仕組みなしで算術演算を明示します。flashはこれらのループとまったく同じ結果を生成する必要があります。丸め効果も含まれます。シャドウを読むと、ハードウェアに実行させた計算が何であるかを知ることができます。
まだそれらのループをattendと関連付ける必要があります。それは、実数上でライブラリが述べる概要の結合に関する法則に依存します。Cachetはこれらの法則を信頼して受け入れます。証明しません。
結果のクレームは2つの部分からなります。カーネルとそのシャドウは同一の結果を生成し、ライブラリの法則を仮定すると、シャドウとattendは実数演算で同じ結果を計算します。tiledと同様に、これは信頼できるレイアウトステップと行列命令のテンプレートにも依存します。cachetc scheduledは、命令テンプレートとそれに依存するライブラリ法則を含む完全なクレームを印刷します。
結論
ループ順序、ブロックサイズ、命令を選択する必要はまだありました。しかし、それらの選択を行った後、コンパイラにチェックを依頼できます。この書き換えは結果を変更しません。これらのバッファはキャッシュモデルに適合します。このループはトラフィック予算内に収まります。選択を変更すると、再度チェックをパスする必要があります。
サブタイトルのアスタリスクはまだ残っています。意図的に合計を再編成する場合、カーネルはシャドウとまったく同じ結果を生成する必要があります。これは丸めの影響で元のコントラクションと異なる場合があります。ライブラリやプラットフォームからの追加の仮定(Onlineの法則や命令のテンプレートなど)は、クレームにリストされています。
これが私が明示的なコンパイラに求めるものです。カーネルの実行方法を選択でき、元の定義を保持でき、コンパイラに変更が私の仮定のいずれかを壊したときに通知させることができます。
完全な例は、小さなカーネルがmatmulとまったく同じ結果を生成することを確認し、ベンチマークはフルサイズのカーネルについても同様です。Attentionはこの実行には含まれていません。関連作業パネルは、これらのアイデアがどこから来たのか、そしてコントラクションが十分でない場所について説明しています。
フットノート
- 浮動小数点数の合計など、一部のケースでは、保持は厳密には成り立ちません。これらの場合、浮動小数点加算を結合法則と見なすことをコンパイラに伝えることができます。これにより、合計をスレッドに分割できます。↩
- 毎秒数十億回の浮動小数点演算。乗算-加算を2回の演算としてカウントします。↩
- ハンマーしかない場合…↩
onのないグリッドはホストで実行されます。ビルドされた実行可能ファイルは、最も外側のループを複数のスレッドで実行しますが、Cachetのインタープリターは反復を順序通りに実行します。どの反復も他の反復の効果を観察できないため、両方とも同一の結果を生成します。↩