HN 日本語サマリー

← 一覧へ戻る
AI・機械学習

FastLanes Unified Transport Layout

The FastLanes Unified Transport Layout (blog.dave.tf)

3 pointsby raggi0 コメント

要約

FastLanesプロジェクトから生まれたUnified Transport Layout (UTL)は、デルタデコーディングをデータ並列化することを目指しています。この記事では、SIMDコンピューティングの基本を理解している読者向けに、UTLのレイアウトを分かりやすく解説します。特に、1024ビットの仮想SIMDレジスタサイズを前提としたアルゴリズム設計と、要素サイズ(64ビット、32ビット、16ビット、8ビット)に関わらず効率的なデータ並列処理を実現する幅非依存レイアウトについて説明します。

全文翻訳

The FastLanes Unified Transport Layout

UTLはFastLanesに由来し、デルタデコーディングを非常にデータ並列にするように設計されています。しかし、論文のレイアウトの説明は私には分かりにくかったため、ここでは私自身の説明を試みます。

デルタエンコーディングとは何か、そしてSIMDコンピューティングの基本を知っていると仮定します。

基本的なデルタエンコーディング/デコーディングは、各値の計算に前のすべての値の計算が必要となるため、本質的に逐次的な問題です。この投稿で興味のあるFastLanesの部分は、問題に並列性を追加することを目指しており、それによってSIMDを使用してデルタエンコーディングと(特に)デコーディングを非常に高速化できます。

前提: ベクトルレジスタ

SIMD ISAには、幅広のベクトルレジスタ専用セットが付属しています。最新のシステムでは、128ビット(SSE、ArmのNeon)から512ビット(AVX-512)までサイズが異なり、さまざまなサイズのレーンにスライスできます。命令は、すべてのレーンで同じ操作を並列に実行します。これは、最新の基準では非常に小さい64ビットベクトルレジスタで、8ビット、16ビット、32ビットのレーンに分解されています。

[画像: 64ビットベクトルレジスタ。8ビット値の8レーン、16ビット値の4レーン、または32ビット値の2レーンを保持できる]

FastLanesは、主流のISAでは処理できない、仮想的な1024ビットSIMDレジスタサイズを中心にアルゴリズムを設計しています。これは、幅広のレジスタ向けに設計されたアルゴリズムを、より狭いレジスタを使用して実装することが容易であるためです。つまり、各幅広の操作を複数の狭い操作として実装します。

逆に、狭いSIMD幅向けに設計されたアルゴリズムを、より幅広のレジスタで高速化することは非常に困難です。なぜなら、同じレジスタの異なるレーン間でデータ依存関係が生じる可能性が高いからです。そのような依存関係はパフォーマンスを完全に低下させるため、この状況に陥ることは絶対に避けたいところです。

したがって、私たちが検討しているFastLanesアルゴリズムはすべて、1024ビットレジスタで動作し、レーンサイズは16x64b、32x32b、64x16b、または128x8bです。1024ビットレジスタで効率的なアルゴリズムは、実際のマシンとその128/256/512ビットレジスタでも同様に効率的になります。

レーン並列デルタデコーディング

デルタエンコードしたい1024個の64ビット整数の配列から始めましょう。

[画像: 0から1023までラベル付けされた1024個の値の配列の図]

前述のように、これは本質的に逐次的なアルゴリズムです。最初の値を保持し、後続のすべての値を前の値からの差分にします。各値は、差分を計算するために前の値にアクセスする必要があります。SIMDでは、これは隣接するレーンに手を伸ばすことを意味します。

1024ビットSIMDレジスタの場合、同時に計算できる16個の独立したデルタストリームが必要です。複数のベース値を格納することをいとわないのであれば、1024個の値を16個のチャンクに分割することで実現できます。

[画像: 1024要素の配列。各64個の値の16行として配置]

メモリ内のレイアウトはまだ変更されていません。これは、16個のチャンクを行として視覚化するための単なるラップです。

次に、この2次元配列を1列ずつ処理すると想像してください。各列は16x64bの値で、正確に1つの1024ビットレジスタに相当します。さらに、各行を下に見ると、行内の値はデルタエンコーディングの正しい順序のままです。つまり、最初の列全体をベース値として格納する場合、16行は同時に計算できる16個の独立したデータストリームになります。まさに私たちが求めているものです!

1つの問題は、各列の値がまだメモリのいたるところに散らばっていることです。SIMDのロード/ストア命令は、それらの値が連続していることを望みます。この配列を16x64の行列と見なし、転置することで、これを簡単に解決できます。

[画像: 上記の16x64配列を64x16に転置。値は行ごとではなく列ごとに増加する]

これで、16個の値のチャンクごとにこの配列を処理できます。これは1024ビットSIMDレジスタにきれいに収まり、16個のデルタエンコーディングストリームを同時に処理できます。

幅に依存しないレイアウト

上記の転置はうまく機能しますが、理想的な分割と転置は要素サイズに依存します。上記のレイアウトは64ビット値には最適ですが、32ビット値に切り替えると再び問題が発生します。今度は、16個の値の行がSIMDレジスタサイズの半分、つまり512ビットにしかなりません。16ビット値や8ビット値を考慮すると、さらに悪化します!

「誰が気にする」と言って、データ型ごとに異なる転置を行うこともできます。32ビット値には32個の行、16ビット値には64個の行、8ビット値には128個の行を使用します。それは機能しますが、異なるデータ型の2つの列の値が異なる順序になることを意味します。これは、クエリ実行中に値をフィルタリングする場合と、一貫した結果をまとめて返す場合の両方で悪夢となるでしょう。

理想的には、要素サイズに関係なく、1024ビットレジスタを最大限に活用できる単一の入力配列の順列を見つけたいと考えています。そして、まさにそれがUTL順列です。

それがどのように、そしてなぜ機能するかを見るために、段階的に導出してみましょう。

32ビット値

上記では、64ビット値にうまく機能する順列(64行x16列)をすでに持っています。これを32ビット値に縮小し、64ビット値と32ビット値の両方に機能するようにレイアウトを調整できるかどうかを見てみましょう。

32ビットの場合、各行は2倍の値が必要であり、それらの値は各列で独立したデータストリームを形成する必要があります。これは、下位32行を切り取り、上位32行の隣に貼り付けることで簡単に実現できます。

[画像: 64x16レイアウトの下位32行が切り取られ、上位32行の右側に移動された]

これで32x32の行列ができました。各列は依然として独立した値のストリームです。32ビット値の場合はこれで問題ありません。一度に1行(32個の値)を処理できます。しかし重要なのは、少し順序を外してチャンクをロードすることをいとわないのであれば、このレイアウトを64ビット値にも機能させることができることです。

[画像: 32ビット値は一度に32個ずつ、単純なメモリ順序で処理される]

64ビット値の場合、SIMDレジスタは一度に16個の値しか処理できません。各行の左側を最初に処理し、次に先頭に戻って右側を処理することで、連続する値の16個のストリームを依然として取得できます。

[画像: 64ビット値は一度に16個ずつ、2回のパスで処理される]

必要な16個の値のチャンクは配列内にありますが、連続した位置ではありません。幸いなことに、チャンクをロードする必要がある順序は固定されているため、一度計算して高速なアンロールループを書いてすべてを処理できます。

ここで、順序外のメモリアクセスが、線形スキャンと比較して多くのキャッシュミスと遅延を引き起こすのではないかと心配するかもしれませんが、心配する必要はありません。このすべての処理は固定長の1024個の値に対して行われ、64ビット値の場合でもわずか8KiBです。Intel Haswell CPU(執筆時点から13年前)は、コアあたり32KiBのL1データキャッシュを持っています。したがって、実際には、アクセスパターンに関係なく、配列全体に一定のレイテンシでアクセスできます。

また、32ビット値の場合、列ごとに1つずつ、ベース値の数を2倍格納する必要があることを忘れないでください。しかし、値の幅が半分になったため、ベース値を格納するためのバイト数は64ビットの場合と同じです。

16ビット値

さて、これで64ビットと32ビットの両方にうまく機能する単一の順列ができました。16ビット値を混合すると、行はさらに2倍の幅が必要になります。幸いなことに、先ほど使用したトリックを繰り返すことができます。下位16行を切り取り、上位16行の隣に貼り付けます。

[画像: 分割プロセスが繰り返される。32x32レイアウトの下位16行が切り取られ、上位16行の右側に移動された]

前の演習を繰り返します。16ビット値の処理は簡単です。一度に1行全体を処理できます。ここでもベース値の数を2倍にする必要がありますが、各値のサイズは半分になったため、格納される合計バイト数は同じです。

[画像: 16ビット値は一度に64個ずつ、単純なメモリ順序で処理される]

32ビット値は2回のパスで処理できます。まず、各行の最初の2つのチャンクを一緒に実行し、次に2番目のチャンクを実行します。

[画像: 32ビット値は一度に32個ずつ処理される。まず各行の最も左の32個の値、次に最も右の32個の値]

64ビット値のメモリアクセスパターンは再び複雑になります。各行の4つの16値チャンクを[0, 1, 2, 3]と名付けると、64ビットコーデックは最初にすべての行のチャンク0を処理し、次に先頭に戻ってチャンク2でシーケンス内の次の値を見つけます。次にチャンク1に戻り、最後にチャンク3にジャンプします。このイラストについては申し訳ありませんが、映画『Primer』のタイムラインよりも絡み合ってきています。

[画像: 64ビット値は一度に16個ずつ処理される。各行は16個の値の4つのチャンクに分割される。すべての行のチャンク0が最初に処理され、次にすべての行のチャンク2、次にすべての行のチャンク1、最後にすべての行のチャンク3が処理される]

しかし、ここでも重要なのは、チャンク処理順序がどれほど複雑であっても、一度計算して高速なアンロールSIMDコードを書いて実行できる固定シーケンスであるということです。

8ビット値

ご想像の通り、また同じトリックを使います!ボックスが小さすぎて、入力する値が多すぎるため、イラストは省略します。しかし、現時点での状況は想像できると思います。

結果として、128個の値を持つ8行が得られます。あるいは、上記のイラストのようにグループ化すると、8x16タイルの8セットが得られます。これが論文で説明されている処理の基本単位です。以前と同様に、これらのタイルを並べ替え後の出現順に[0, 1, 2, 3, 4, 5, 6, 7]と名付けます。

演習を繰り返します。8ビット値の場合、1024ビットSIMDレジスタは行全体を一度に処理できます。現在128個のベース値を格納する必要があります。

16ビット値は2回のパスで処理されます。最初のパスは[0, 1, 2, 3]をまとめて処理し、次に[4, 5, 6, 7]をまとめて処理します。値がどのようにシャッフルされたかを考えると、タイル4の列はタイル0で開始された値ストリームを実際に継続しています。これは1->5、2->6、3->7も同様です。

32ビット値は4回のパスで処理されます。以前に示されたものと同じ巻き道ですが、今回は一度に2つのタイルを使用します。[0, 1]、次に[4, 5]、次に[2, 3]、最後に[6, 7]です。ここでも、各タイルの列を訪問順に貼り付けると、すべての列が連続した値のストリームであることがわかります。

そして最後に、64ビット値は8回のパスで処理されます。一度に1つのタイルを使用し、さらに複雑な順序になります。[0], [4], [2], [6], [1], [5], [3], [7]です。この目を引く進行をたどると、すべての列が連続値のストリームを見ることがわかります。

UTL順序への配列のシャッフル

要約すると、配列をUTL順序にするには次の手順を実行します。

  • 配列を概念的に16x64の行列に配置します。
  • 行列を64x16に転置し、独立した値ストリームである列を生成します。
  • 64行を8つのグループに分割し、8x16タイルのセットを作成します。
  • タイルを順列[0, 4, 2, 6, 1, 5, 3, 7]で並べ替えます。
  • タイルを転置します(ただし、タイル内の値は転置しません)。これにより、8x1タイルのレイアウトが1x8になります。

別の見方をすると、配列インデックスが転置された位置にどのように変換されるかを見ることができます。1024要素の配列のインデックスは、正確に10ビットを占有します。

  • 16x64行列として配置された場合、10ビットインデックスは行と列のインデックスに分解されます:[row:4b][col:6b]。
  • これらの2つのインデックスを入れ替えて64x16に転置します:[t_row:6b][t_col:4b]。
  • 6ビット行インデックスを8行の8タイルに分解します:[tile:3b][row_in_tile:3b][t_col:4b]。
  • タイルを入れ替えます。これはタイルインデックスのみを順列化することで実行できます:[p_tile:3b][row_in_tile:3b][t_col:4b]。
  • タイルを行ごとに転置します。つまり、すべてのタイルの行0が最初に表示され、次に1行目などが表示されます:[row_in_tile:3b][p_tile:3b][t_col:4b]。

コードに翻訳すると、これはout[translate(i)] = in[i]という関数になり、配列の各iについてin[i]をどこに移動させるかを示します。

結論

UTLレイアウトで配置された場合、8/16/32/64ビットの値はすべて、最大限に効率的なSIMDルーチンでデルタエンコードおよびデコードできます。異なるデータ型の列はすべて同じ順序で値を持つため、クエリエンジンはマルチカラム述語を理解できます。

論文では、タイルのマジック順列がこのプロパティを持つ唯一の順列であることも証明されており、これは興味深い点です。

もちろん、欠点もあります。

  • データレイアウトは人間には全く理解できません。デバッグしようとしているときに、この形式を見つめるのが楽しくないことは確かです。
  • 配列を非常に異なる順序でトラバースする必要があるため、値のサイズごとに個別のSIMDルーチンが必要です。世界の終わりではありませんが、おそらく最も低いレベルのプリミティブをコード生成したいと思うでしょう。
  • 挿入順で結果を返す必要がある場合は、クエリ実行の最後にすべてを逆順列化する必要があります。論文では、多くのカラムストアアプリケーションでは挿入順序はあまり重要ではなく、このステップをスキップできることが示唆されています。

それでも、非常に巧妙なアイデアのセットであり、論文の数値によると、L1キャッシュスループットの速度でデルタエンコードされたカラムの線形スキャンを処理できるため、非常に印象的です。