
2026/11/11 4:17
独自のカーネル最適化ツールを開発する
RSS: https://news.ycombinator.com/rss
要約▶
Japanese Translation:
Cachet は、コンパイラ最適化と手動コーディングの複雑さというトレードオフを解決するために、ソースコード内でハードウェアパフォーマンスを明示化する新しいプログラミング言語です。計算と最適化スケジュールを分離することにより、開発者は
[reassoc] などの単純な許可を用いて、データ移動やブロッキング戦略を明示的に制御でき、これによって浮動小数点数の加算における丸め誤差を防ぎつつ、多様なハードウェアで大幅な高速化を実現します。
この言語は、naive な行列乗算アプローチ(1.17 GFLOP/s)を開発し、OpenBLAS などの確立されたライブラリと同等のパフォーマンスに達させることでこの能力を実証しています。これには、
synth キーワードを介した最適なブロックサイズの自動選択、およびベクトルユニットをBusyに保ちながらハードウェア固有の命令(M4 Max における SME など)を利用する特定の CPU/GPU スケジュールが含まれます。特に重要なのは、特化型深層学習の専門知識を必要とせずとも、GPU で MLX パフォーマンスの 95% に達することです。さらに、FlashAttention といった高度な操作では、Cachet が検証された丸め動作を持つ正確なローカル合計を実現します。結果として、この言語を採用するだけで、主記憶のフェッチを大幅に削減し、エネルギー効率を向上させながら、ほぼピークパフォーマンスを実現することができます。本文
プログラム最適化と Cachet: 明示的なコンパイルアプローチ
1. 最適化のアプローチ
プログラム最適化には主に 2 つのアプローチが存在します。
- 期待する手法(自動最適化)
- コンパイラに高速化を任せる方法です。
- Python ライブラリなどで記述された処理に対して、コンパイラはハードウェアの特性を把握できず、諦めた挙動を示すことがあります。
- 手動最適化(カスタム実装)
- コンパイラが十分でない場合、コードを手動で書き換えます。
- 抽象概念を捨て、データの流れをハードウェアに適合させるため、カスタムカーネルや固有関数(intrinsics)、インラインアセンブリを書く必要があります。
変換の信頼性
どちらのアプローチも、意味を保証する特定の条件の下でのみ有効な変換に基づいています。
- 例:出力データが入力データと重複していないことなど。
決定事項の隠蔽 vs. 明示化
- コンパイラによる最適化: 背後で行われている変換(キャッシュ管理やベクトル化など)を隠蔽します。
- 手動最適化: 結果を示しますが、元々の構造や変換過程は隠されます。
重要な決定事項(どのブロックをキャッシュに保つか、どのループをベクトル化するか)は、コンパイラが背後で判断するのではなく、我々が明示的に行う必要があります。
- Cachetという言語では、「パフォーマンスに関する推論」そのものを支援する理念に基づいています。
2. Cachet と変換(Matrix Multiplication の例)
Cachet は「何を計算するか」と「どのように計算するか」を別々に記述し、一連の変換(スケジューリング)によって最適化されたプログラムへと導きます。 コンパイラは、各変換が元のプログラムの意味を保証するかどうかをチェックします¹。
本稿では 行列積計算(Matrix Multiplication) を例に挙げて解説します。
- 対象環境:MacBook (M4 Max 搭載)。Apple ハードウェア特有の技術ではありません。
- 検証状況:Cachet は NVIDIA H100 のプログラムを検証はできるが、ビルドは現在还不能しています²。
比較ライブラリ
各スケジューリングを以下の最適化ライブラリと比較しました。
| ハードウェア | ライブラリ |
|---|---|
| CPU (ベクトル指令) | OpenBLAS |
| CPU (行列演算ユニット) | Apple Accelerate |
| GPU | MLX |
パフォーマンス指標: 速度はライブラリを基準(100%)として測定しています。
3. 最適化ステップ:行列積計算の実践
3.1 手動による単純な実装と問題点
定義は一行で記述できますが、マシンにとっては手助けが必要です。
基本的なループネスト: $$c[i, j] = \sum_k a[i, k] \times b[k, j]$$
// 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];
性能課題:
- 速度: $1.17 \text{ GFLOP/s}$($1024 \times 1024$ の行列、単一コア)。
- OpenBLAS 比較: 約 1% です。
キャッシュの効率化
この実装では、熱い変数(更新頻度の高い $k$)が内部ループを支配し、配列のアクセスパターンが悪いです。
- 配列は**行順(row-major order)**で保存されています。
- プロセッサはキャッシュライン単位でメモリを読み取ります。
- 列を下るアクセス: キャッシュラインが上書きされる前に、必要な値に戻れずミスヒットを引き起こします。
解決策:ループの入れ替え 内部ループを入れ替えることで、行に沿ったアクセス(隣接するデータの再利用)を実現できます。
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];
- 改善結果: $33 \text{ GFLOP/s}$(OpenBLAS の 30%)。単純な入れ替えでは限界があります。
ブロッキング(Blocking)の必要性
$M \times N$ の行列が大きすぎると、入力データがキャッシュに収まりません。
- 各パスでデータを再フェッチするのを避けるため、ブロッキングを用いてキャッシュにデータを保持します。
- しかし、単純なループ入れ替えだけでは、プログラムが持つ意味(例:出力の重複しない条件)を保証できません。コンパイラによる厳密なチェックが必要です。
3.2 「何を」記述する(Cachet の定義)
Cachet では、計算の構造を明確に記述します。
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]
構成要素の解説:
- $M, K, N$: 行列の次元。
: 関数が配列を読み取る権限を持つことを示します。reads
: 結果の名前と、呼び出し側がメモリを確保する場所を示します。-> out c- 式の意味:
- $i, j$: 「自由な添え字」。出力は独立して計算可能です(順序は任意)。
- $k$: 「総和」の下にあるため、各出力について入力ペアの積を合計します。
- 演算(
,*
)は要素型(ここでは+
)から派生します。f32
この記述は「何を計算するか」に焦点を当て、「どのように計算するか(ループネスト)」はコンパイラが決定する対象です。
3.3 スケジューリング:変換のプロセス
Cachet のコンパイラ
cachetc に cachetc scheduled を適用することで、ループネストに変換されます。
スケジューリングとは:
- コンパイラがプログラムをビルドする際に適用する一連の書き換えです。
- 結果として生成された関数を呼び出すだけでカーネルが実行されます。
スケジュール変換の追跡 (schedule swapped
)
schedule swappedschedule swapped of matmul = zero (i, j) c hoist (j, k) cfor 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
変換のポイント:
: 出力を初期化。zero
: 総和(hoist
)の更新ステップをループの外へ持ち上げます。acc'0- これにより、内部ループで各要素へのアクセスを削減し、キャッシュ効率を高めます。
(Fused Multiply-Add): $a \times b + acc$ を一度に計算し、丸め誤差を減らします。fma
検証(チェッキング)
コンパイラは生成されたコードが元の収束式の意味を保証しているかチェックします(例:各出力が正しい順序で更新されているか)。
hoist はライブラリステップであり、定義自体と置換先、および結果の整合性を証明する指示を与えます。
3.4 ブロッキングとタイル化(CPU スケジューリング)
単一のコアでの高速化には、キャッシュを有効活用する必要があります。
チャンク単位での分割
合計処理をチャンクに分割し、入力データをキャッシュ内に保持します。
schedule tower of matmul = zero (i, j) c split k by 16 as gk ragged
ステップの解説:
: $k$ ループをブロック(例:幅 16)に分割し、各チャンクの名前をsplit
にします。gk- チャンク間ではセルのリセットを行わず、総和は継続されます。
パック化(Packing)とキャッシュ利用
より高度な最適化では、入力データをパック化してキャッシュに保持します。
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 packA along gi within L2 into packA_L2 keep packB along gj within L1 into packB_L1 registers (i, j) into c rows 4 lanes 8 through fma
主な動作:
: 入力データを一時バッファにコピーし、値を整えます。pack
: バッファを特定のキャッシュ階層(L1, L2)内に保持します。keep
: 総和をベクトルレジスタに保持し、一度に複数の値を更新します。registers
パフォーマンスの結果
単一コアでの性能比較 ($1024 \times 1024$, f32):
| スケジューリング | GFLOP/s | OpenBLAS 相対速度 |
|---|---|---|
(単純) | 1.17 | 1.1% |
(入れ替え) | 33.0 | 30% |
(チャンク分割) | 27.0 | 27% |
(パック化) | 47.0 | 45% |
(最適化) | 116 | 108% |
は、キャッシュ階層、ベクトル指令、およびデータ依存性を考慮した最適化により、OpenBLAS と同等の速度に達しました。fast- これらの変更はすべて、元のプログラムの意味を保証します。
3.5 マトリクスユニット(Matrix Units)と GPU の活用
M4 Max は Matrix Unit を有しており、より高度な指令を利用できます。
CPU マトリクスユニット (SME)
Arm の Scalable Matrix Extension (SME) を介してアクセスします。
- $8 \times 8$ ブロックの外積演算を実行し、$f64$ で計算します。
- 結果: $3072 \times 3072$ 行列 ($f64$) で 894 GFLOP/s。Apple Accelerate の 103% の性能を発揮しました。
GPU スケジューリング (Metal)
GPU ではスレッド(グリッド)単位で並列計算を行います。
: 各出力要素を独立したスレッドに割り当てます(単純)。rows
: 複数のスレッドが協力して $16 \times 16$ のタイルを計算します。tiles
: さらに大きなタイル ($64 \times 32$) で、SIMD グループ間で入力を有効活用します。big_tiles
GPU パフォーマンス結果 ($4096 \times 4096$, f32, MLX vs Cachet):
| スケジューリング | GFLOP/s | MLX 相対速度 |
|---|---|---|
(独立要素) | ~1.8 | <0.1% |
(タイル) | 5,282 | ~40% |
| 12,407 | 95% |
は、MLX に迫る 95% の性能を発揮しました。big_tiles
4. Attention(注意機構)の実装とシャドウ
Attention 機構では、計算順序の変更が許容される場合があります。 $$Attention(Q, K, V) = \text{softmax}(QK^T / \sqrt{d_k})V$$
オンライン Attention と再グループ化
- スコア($Q \times K^T$)を計算して保持し、その後に Softmax を適用する「Online」手法があります。
- 問題: 行内のすべての値で最大値を求める必要があり、オーバーフローを防ぐために正規化が必要です。
- ブロック処理: ブロックごとにスコアを計算・破棄したい場合(FlashAttention)、加算順序を変更して再グループ化(reassoc)を行う必要があります。
シャドウ(Shadow)の構築
浮動小数点計算では加算順序を変えると結果が異なります(丸め誤差)。 Cachet は、この違いを検出し、シャドウ関数を定義することで「同じ結果」を保証します。
: 元の収束式。厳密な順序を保証。attend
: ブロック処理を行い、加算順序を変更するスケジューリング。flash
:flash_shadow
がflash
と同じ結果を与えることを数学的に証明する基準(シャドウ)を自動生成します。attend
これにより、「加算順序を変えたが、計算結果は保証されている」という状態をコンパイラが検証できます。
5. 結論:明示的なコンパイラの利点
Cachet は、プログラマが「どのように計算するか」を選択できるようにし、コンパイラがその選択を検証するアプローチを提供します。
- 最適化の透明性: ループ順序やブロックサイズを明示的に記述できる。
- 自動検証: コンパイラが結果の整合性、キャッシュモデル適合性、トラフィック予算などをチェックする。
- 仮定の早期発見: プログラムの進化に伴って成り立たなくなった仮定は、コンパイルエラーとして早期に発見される。
手動で最適化する場合でも、コンパイラが背後で行うべき変換(ベクトル化、キャッシュ管理など)を隠さず、我々が「パフォーマンスに関する推論」を行える環境を提供します。
コマンドを用いることで、シャドウを含む完全な検証済みのコードを生成できます。cachetc scheduled --shadow