ベクトル化されパフォーマンスポータブルなQuicksort

ベクトル化されパフォーマンスポータブルなQuicksort | Google Open Source Blog Google Open Source Blog オープンソースのリリース、主要プロジェクト、イベント、および初期キャリア開発者向けの広報プログラムに関するGoogleの最新ニュース。 ベクトル化されパフォーマンスポータブルなQuicksort 2022年6月2日 本日、C++のstd::sortよりも約10倍高速に数値配列をソートでき、最先端のアーキテクチャ固有のアルゴリズムをも凌駕する、すべての最新CPUアーキテクチャでポータブルなオープンソースコードを共有します。以下に、これをどのように達成したかを説明します。 まず、背景を説明します。最近、レコードのすべてのフィールドを次のレコードの前に格納するのではなく、特定列のすべての値を連続して格納するカラム型データベースへの傾向があります。これは、SQLクエリの主要な構成要素であるフィルタリングやソートを高速化できるため、このデータレイアウトに焦点を当てています。 ソートはこれまで徹底的に研究されてきたことを考えると、どのようにして10倍の高速化を見つけることができるのでしょうか？答えはSIMD/ベクトル命令にあります。これらは、単一の命令で複数の独立した要素に操作を実行します。例えば、AVX-512命令セットを使用する場合、一度に16個のfloat32を操作したり、Arm NEONでは4個を操作したりします。 SIMDに既に慣れている方は、スーパーコンピュータ、機械学習アプリケーションの線形代数、ビデオ処理、またはJPEG XLのような画像コーデックで使用されていることを聞いたことがあるかもしれません。しかし、SIMD操作は独立した要素のみを含む場合、要素の並べ替えを伴うソートをどのように行うことができるのでしょうか？ 例えば256要素の配列をソートする特別な方法があると想像してください。その場合、より大きな配列をソートするためのQuicksortアルゴリズムは、配列を2つのサブ配列に分割することからなります。1つは「ピボット」値（理想的には中央値）より小さい要素、もう1つはそれ以外の要素です。その後、サブ配列が最大256要素になるまで再帰し、それらをソートするために特別な方法を使用します。パーティショニングはCPU時間の大部分を占めるため、SIMDを使用して高速化できるなら、高速なソートが可能です。幸いなことに、最新の命令セット（Arm SVE、RISC-V V、x86 AVX-512）には、パーティショニングに適した特別な命令が含まれています。ピボットより小さいかどうかを示す、個別のyes/no値の入力が与えられると、この「compress-store」命令は、対応する入力が「yes」である要素のみを連続メモリに格納します。その後、yes/no値を論理的に否定し、命令を再度適用して、他のパーティションに要素を書き込むことができます。この戦略は、AVX-512固有のQuicksortで使用されてきました。しかし、compress-storeを持たないAVX2のような他の命令セットはどうでしょうか？以前の研究では、permute命令を使用してこの命令をエミュレートする方法が示されています。 私たちはこれらの技術を基盤として、3つのアーキテクチャにわたる6つの命令セットにポータブルな最初のベクトル化Quicksortを実現し、実際には以前のアーキテクチャ固有のソートを凌駕しています。私たちの実装はHighwayのポータブルSIMD関数を使用しているため、プラットフォームごとに約3,000行のC++を再実装する必要はありません。Highwayは、compress-storeが利用可能な場合はそれを使用し、そうでない場合は同等のpermute命令を使用します。以前の最先端技術（32ビット整数に特化していた）とは異なり、16〜128ビットの入力の全範囲をサポートしています。 私たちの単一のポータブル実装にもかかわらず、AVX2、AVX-512（Intel Skylake）、およびArm NEON（Apple M1）の両方で記録的な速度を達成しています。100万個の32/64/128ビットの数値に対して、Apple M1で実行される私たちのコードは、499/471/466 MB/sの速度でソート済み出力を生成できます。3 GHz SkylakeでAVX-512を実行する場合、速度は1123/1119/1120 MB/sです。興味深いことに、AVX-512はAVX2よりも1.4〜1.6倍高速です。これは、追加の労力なしで価値のある高速化です（HighwayはCPUで利用可能な命令を確認し、利用可能な最良のものを使用します）。AVX2で実行する場合、798 MB/sを測定しますが、以前の最先端技術でAVX2用に最適化されたものは699 MB/sしか管理できません。比較すると、標準ライブラリは同じCPUで58/128/117 MB/sに達するため、数値の種類に応じて9〜19倍の高速化を達成しました。 以前は、ソートは高コストであると考えられていました。CPUコアあたり1 GB/sでソートできるようになったことで、どのような新しいアプリケーションや機能がアンロックされるかを見るのが楽しみです。Apache2ライセンスのソースコードはGithubで入手可能であり（質問やコメントがあれば遠慮なくissueを開いてください）、私たちの論文では、実装の詳細な説明と評価（256要素の特殊ケースを含む）を提供しています。 Jan Wassenberg – Brain Computer Architecture Research による ラベル: SIMD, Sorting