Transformerで行列計算を行う様子をKV cache付きで実装する。 ここでは、自然言語的な出力の正確性などは一切考えず、単純に行列計算を高速化する方法に着目する。
llm.cpp
はC++17の標準ライブラリだけを使った逐次実装である。
固定seedでモデルの重みと入力トークンID列を生成する。
重みは未学習なので、出力するID列に自然言語としての意味は求めない。
入力列を最初に処理する段階を prefill、その後にトークンを1つずつ処理して続きを生成する段階を decode と呼ぶ。 現在のキャッシュ付きprefillは、入力を1トークンずつ順に処理する単純な方式である。 G個生成する場合、最初の1個はprefillの結果から選ぶので、decodeの計算はG−1回になる。
--mode cached
では新しいトークンだけを各層で計算し、過去のK/Vを再利用する。
--mode recompute では生成のたびに入力列全体を再計算する。
--check は長さ1〜8の固定入力列で両方式の全logitsを比較し、
--mode both
は両方式で生成したトークン列が一致するか確認する。
std::chrono でprefillとdecodeの時間を計測し、処理速度とKV
cache容量も出力する。
具体的には、以下の箇所が並列化の候補になる。現在のコードは逐次版であり、並列化は今後行う。 複数の値の合計や最大値を求める際は、部分結果を並列に計算してからまとめる「リダクション」を利用できる。
| 箇所 | 並列化の方法 |
|---|---|
線形変換(Matrix::operator()) |
出力成分ごとにCPUスレッドやGPUスレッドへ分担する。各成分の内積もSIMDやリダクションで計算できる。Q/K/V、Attention出力、FFN、語彙への変換に適用できる。 |
| Q/K/Vの3つの変換 | LayerNormの完了後、同じ入力からQ・K・Vを独立に計算できる。 |
| Attentionの各ヘッド | ヘッドごとの計算は独立している。並列化時には、現在使い回している
score 配列をヘッドごとに用意する。 |
| Attentionのスコア | 現在のQと各位置のKとの内積を、参照するトークン位置ごとに並列計算できる。内積の成分方向の和にもリダクションを使える。 |
| Softmax | 最大値の探索と指数関数の値の合計はリダクションにできる。指数関数の計算と正規化は要素ごとに並列化できる。最大値、指数関数、合計、正規化の順序は守る。 |
| Vの加重和 | 出力成分ごとに分担できる。参照位置方向に分割する場合は、同じ出力への同時加算を避けるため、部分和を最後にまとめる。 |
LayerNorm(norm) |
平均・分散をリダクションで計算し、正規化を成分ごとに並列化する。現在の計算方法では平均、分散、正規化の順に処理する。 |
| 埋め込み・位置情報、GELU、残差加算 | ベクトルの成分ごとの処理が独立しており、SIMDやGPUの要素ごとの処理に向いている。 |
次のトークンの選択(argmax) |
語彙を分担して最大スコアとIDを求め、結果をまとめる。同点の場合は小さいIDを選び、現在の実装と同じ規則にする。 |
| KV cacheへの書き込み | K/Vやヘッド、成分ごとに異なる配列領域へ書き込める。Attentionが参照する前に書き込みを完了する必要がある。 |