世界初のベクトル化クイックソートを開発
We've created the first vectorized Quicksort
Brain Computer Architecture Researchは、従来のC++ std::sortと比較して約10倍高速な、ベクトル化されたクイックソートアルゴリズムをオープンソースで公開しました。このアルゴリズムは、最新のCPUアーキテクチャ間で移植可能であり、SIMD/ベクトル命令を活用してソート処理を高速化します。特に、現代の命令セット(Arm SVE、RISC-V V、x86 AVX-512)に含まれる「compress-store」命令を利用し、配列のパーティショニングを効率化します。AVX2などのcompress-store命令を持たないアーキテクチャ向けには、permute命令を用いたエミュレーションも可能です。この実装は、HighwayライブラリのポータブルSIMD関数を使用しており、32ビット整数に限定されていた従来の最先端技術とは異なり、16ビットから128ビットまでの幅広い入力に対応しています。Apple M1では499/471/466 MB/s、Intel Skylake (AVX-512) では1123/1119/1120 MB/sという記録的な速度を達成し、従来の標準ライブラリと比較して9〜19倍の高速化を実現しています。この技術は、1GB/sでのソートを可能にし、新たなアプリケーションの可能性を開くと期待されています。
- Brain Computer Architecture Researchが、従来のC++ std::sort比で約10倍高速なベクトル化クイックソートアルゴリズムをオープンソースで公開した。
- 最新CPU命令セットの compress-store 命令(Arm SVE、RISC-V V、x86 AVX-512)を利用して配列のパーティショニングを効率化し、命令を持たないAVX2などではpermute命令によるエミュレーションに対応する。
- HighwayライブラリのポータブルSIMD関数を用いることで最新CPUアーキテクチャ間で移植可能とし、32ビット整数限定だった従来の最先端技術と異なり16〜128ビットの入力幅に対応した。
- Apple M1で499/471/466 MB/s、Intel Skylake (AVX-512)で1123/1119/1120 MB/sの記録的速度を達成し、従来の標準ライブラリ比で9〜19倍の高速化を実現、1GB/sでのソートを可能にした。
ベクトル化クイックソートのオープンソース公開は、既存CPUのSIMD命令を最大限引き出すソフトウェア最適化であり、ハードウェアを増やさずに処理性能を9〜19倍高められる点が投資家視点で注目される。特にArm SVE、RISC-V V、x86 AVX-512のcompress-store命令を活用しつつHighwayライブラリで移植性を確保しているため、特定アーキテクチャに依存しない普及が期待できる。データ処理基盤やデータベース、ストリーミング処理を手掛ける企業にとってはライセンス費用なしで性能向上を取り込める一方、ソート性能を売りにするソフトウェア資産の差別化要因を弱める可能性もあり、採用動向とエコシステムの広がりを注視したい。