FastLanes Unified Transport Layout

David Anderson著 2026年8月8日 FastLanes Unified Transport Layout Unified Transport Layout (UTL)はFastLanesから生まれ、デルタデコーディングを非常にデータ並列化するように設計されています。しかし、論文では私が混乱するような方法でレイアウトが説明されているため、ここでは私自身の説明を試みます。デルタエンコーディングとSIMDコンピューティングの基本はご存知だと仮定します。 基本的なデルタエンコーディング/デコーディングは、基本的に逐次的な問題です。なぜなら、各値を計算するには、まずすべての先行する値を計算する必要があるからです。この投稿で関心のあるFastLanesの部分は、問題に並列性を追加することを目的としており、SIMDを使用してデルタエンコーディング（特にデコーディング）を非常に高速化できるようにします。 前提：ベクトルレジスタ SIMD ISAには、専用の幅広ベクトルレジスタセットが付属しています。最新のシステムでは、サイズは128ビット（SSE、ArmのNeon）から512ビット（AVX-512）まで様々で、異なるサイズのレーンにスライスできます。命令は、すべてのレーンで同じ操作を並列に実行します。これは、現代の基準では非常に小さい64ビットベクトルレジスタで、8ビット、16ビット、32ビットのレーンに分解されています。 FastLanesは、主要なISAでは処理できない、仮想1024ビットSIMDレジスタサイズを中心にアルゴリズムを設計しています。これは、幅広レジスタ用に設計されたアルゴリズムを、より狭いレジスタを使用して実装することが容易であるためです。つまり、各幅広操作を複数の狭い操作として実装します。逆に、狭いSIMD幅用に設計されたアルゴリズムを、幅広レジスタで高速化することは非常に困難です。なぜなら、同じレジスタの異なるレーン間でデータ依存関係が生じる可能性が高いからです。そのような依存関係はパフォーマンスを完全に低下させるため、この状況を回避することが非常に重要です。したがって、私たちが検討しているFastLanesアルゴリズムはすべて、1024ビットレジスタで動作し、レーンは16x64b、32x32b、64x16b、または128x8bです。1024ビットレジスタで効率的なアルゴリズムは、実際のマシンとその128/256/512ビットレジスタでも同様に効率的になります。 レーン並列デルタデコーディング デルタエンコードしたい1024個の64ビット整数の配列から始めましょう。前述したように、これは基本的に逐次的なアルゴリズムです。最初の値を保持し、後続のすべての値を前の値からの差分にします。各値は、差分を計算するために前の値に触れる必要があるため、SIMDでは隣接するレーンに手を伸ばすことを意味します。1024ビットSIMDレジスタの場合、同時に計算できる16個の独立したデルタストリームが必要になります。複数のベース値を格納することを厭わない場合、1024個の値を16個のチャンクに分割することで実現できます。 メモリ内のレイアウトはまだ変更されていません。これは、16個のチャンクを行として視覚化するための単なるラッパーです。ここで、この2次元配列を1列ずつ処理すると想像してください。各列は16x64bの値で、ちょうど1つの1024ビットレジスタです。さらに、各行を下に見ると、行内の値はデルタエンコーディングの正しい順序のままです。つまり、最初の列全体をベース値として格納すると、16行は同時に計算できる16個の独立したデータストリームになります。まさに私たちが求めているものです。 1つの問題は、各列の値がまだメモリのいたるところに散らばっていることです。SIMDのロード/ストア命令は、これらの値が連続していることを望みます。この配列を16x64の行列と見なし、転置することで、これを簡単に解決できます。 これで、16個の値のチャンクごとにこの配列を処理できます。これは1024ビットSIMDレジスタにきれいに収まり、16個のデルタエンコーディングストリームを同時に処理できます。 幅非依存レイアウト 上記の転置はうまく機能しますが、理想的な分割と転置は要素サイズに依存します。上記のレイアウトは64ビット値に最適ですが、32ビット値に切り替えると再び問題が発生します。今度は、16個の値の行は2倍の幅が必要になり、それらの値はSIMDレジスタのサイズの半分である512ビットにしかなりません。16ビットおよび8ビットの値も考慮すると、さらに悪化します。 「誰が気にする」と言って、データ型ごとに異なる転置を行うこともできます。32ビット値には32行、16ビット値には64行、8ビット値には128行を使用します。それは機能しますが、異なるデータ型を持つ2つの列の値が異なる順序で終わることを意味します。これは、クエリ実行中に値をフィルタリングする場合と、一貫した結果をまとめる場合の両方にとって悪夢となるでしょう。理想的には、要素サイズに関係なく、1024ビットレジスタを最大限に活用できる入力配列の単一の順列を見つけたいと考えています。そして、まさにUTL順列がそれです。それがどのように、そしてなぜ機能するかを見るために、段階的に導き出してみましょう。 32ビット値 すでに64ビット値にうまく機能する順列があります。64行16列です。それから始め、要素サイズを32ビットに縮小し、64ビット値と32ビット値の両方に機能するようにレイアウトを調整できるかどうかを見てみましょう。32ビットの場合、各行は2倍の値が必要であり、それらの値は各列で独立したデータストリームを形成する必要があります。これは、下位32行を切り取って上位32行の隣に貼り付けることで簡単に実現できます。 これで32x32の行列ができました。各列は依然として独立した値のストリームです。32ビット値の場合、これは問題ありません。一度に32個の値の行を処理できます。しかし重要なのは、少し順不同でチャンクをロードすることを厭わないのであれば、このレイアウトを64ビット値にも機能させることができることです。64ビット値の場合、SIMDレジスタは一度に16個の値しか処理できません。各行の左側を最初に処理し、次に先頭に戻って右側を処理する場合、連続する値の16個のストリームを依然として取得できます。必要な16個の値のチャンクは配列内にありますが、連続した位置にはありません。幸いなことに、チャンクをロードする必要がある順序は固定されているため、一度計算して高速なアンロールループを記述してすべてを処理できます。 この時点で、順不同のメモリアクセスがキャッシュミスを大量に発生させ、線形スキャンと比較して遅くなるのではないかと心配するかもしれませんが、心配する必要はありません。このすべての処理は固定長の1024個の値で行われ、64ビット値の場合でもわずか8KiBです。Intel Haswell CPU（執筆時点で13年前）は、コアあたり32KiBのL1データキャッシュを備えています。したがって、実際には、アクセスパターンに関係なく、配列全体を一定のレイテンシでアクセスできます。また、32ビット値の場合、64ビットケースと同じバイト数を格納する必要があるにもかかわらず、各列ごとに1つのベース値をさらに多く格納する必要があることも覚えておいてください。 16ビット値 さて、これで64ビットと32ビットの両方にうまく機能する単一の順列ができました。16ビット値を混合すると、行はさらに2倍の幅が必要になります。幸いなことに、使用したトリックを繰り返すことができます。下位16行を切り取って上位16行の隣に貼り付けます。 前の演習を繰り返します。16ビット値の処理は簡単で、一度に行全体を処理できます。ここでもベース値の数を2倍にする必要がありますが、各値のサイズは半分になっているため、格納される合計バイト数は同じです。32ビット値は2回のパスで処理できます。まず、各行の最初のペアのチャンクを処理し、次に2番目のペアを処理します。64ビットのメモリアクセスパターンは再び複雑になります。各行の4つの16値チャンクを[0、1、2、3]と名付けると、64ビットコーデックは最初にすべての行のチャンク0を処理し、次にチャンク2にジャンプしてシーケンス内の次の値を見つけます。次にチャンク1に戻り、最後にチャンク3にジャンプします。このイラストについては申し訳ありませんが、Primerのタイムラインよりも絡み合ってきています。しかし、重要なのは、チャンク処理の順序がどれほど乱雑であっても、一度計算して高速なアンロールSIMDコードを記述して実行できる固定シーケンスであるということです。 8ビット値 お察しの通り、同じトリックを繰り返します。箱が小さすぎて、入力する値が多すぎるため、イラストは省略します。しかし、おそらくあなたは