DGIS Sort: Hardware-Optimized Parallel Hybrid Sort

DGIS Sort は、特定条件下においてマルチコアCPUのハードウェア性能（キャッシュ機構、SIMD命令、メモリアクセス帯域）を引き出すことを目的として開発された、C++による実験的なハイブリッド・バケットソートアルゴリズムです。

本プロジェクトは「汎用的なソートアルゴリズム」を作ることではなく、データの分布や特性が既知であるという前提のもと、**「データ指向設計（Data-Oriented Design）とアーキテクチャへの最適化によって、ソフトウェアはどこまでハードウェアの限界を引き出せるか」**を検証する技術的なPoC（概念実証）として実装されました。

🚀 コア・アーキテクチャと最適化手法

標準ライブラリ（std::sort の並列実行ポリシー）を上回るため、以下の低レイヤ最適化をパイプラインとして統合しています。

1. L2 Cache-Aware Radix Sort (キャッシュを意識した基数ソート)

バケットソートの各バケットサイズを意図的に TARGET_BUCKET_SIZE = 32768（約 256 KB）に制限しています。これは、Intel Core 13世代等のモダンなCPUの L2キャッシュ（1.25 MB 〜 2 MB）内にデータを収めるための設計 です。メインメモリ（RAM）へのアクセスストールを防ぎ、L2キャッシュ上での高速なRadix Sortを実現しています。

2. AVX2 Vectorization & Cache-Line Alignment (SIMDとキャッシュラインの最適化)

各スレッドの書き込みバッファを BUFFER_SIZE = 8（64 バイト ＝ キャッシュライン1行分）にアライメントしています。バッファの満杯判定をポインタの下位3ビットに対するビット演算で行い、満杯になった瞬間に _mm256_storeu_pd（256-bit AVX2命令）を用いて、メインメモリへ一度にフラッシュすることでメモリ帯域を最大限活用しています。

3. Branchless Memory Scatter (分岐予測ミスの排除)

データのヒストグラム（バケットごとの要素数）を算出する際、if 文による境界チェックを行わず、正規化係数（norm）を用いた純粋な浮動小数点演算のみでインデックスを計算するブランチレス実装を採用し、CPUのパイプラインストールを回避しています。

4. Zero-Overhead Arena Allocation

OSによる動的メモリ割り当て（malloc / new）のオーバーヘッドとフラグメンテーションを防ぐため、64バイトアライメントされた巨大なメモリブロック（Arena）を一度だけ確保し、スレッドごとのワークスペースとして切り分けて使用しています。

---

🎯 前提条件と既知のトレードオフ (Assumptions & Limitations)

本アルゴリズムは最高速度を達成するために、以下の前提条件（トレードオフ）を設けています。実運用に組み込む場合は、データの前処理やフォールバック機構の追加が必要です。

• データ分布（一様分布の想定）: データが均等に分散している状況で最大の効果を発揮します。極端な外れ値が存在するデータセットの場合、特定のバケットにデータが集中し、スレッド間のロードインバランス（負荷の偏り）が発生してパフォーマンスが著しく低下します。
• データ型（正の浮動小数点数専用）: 現在、IEEE 754フォーマットのビット列表現を直接 uint64_t として基数ソートにかけています。そのため、負の数や NaN などを処理するためには、Radix Sortの前後でビット反転等の前処理を追加する必要があります。

---

📊 ベンチマークとアーキテクチャ考察 (Benchmarks & Insights)

本アルゴリズムのハードウェア・スケーリングを検証するため、マイクロアーキテクチャおよびキャッシュ構成が異なる3種類のCPUで、要素数 $N$ を変動させた比較テストを実施しました。（※乱数生成：std::uniform_real_distribution<>(0.0, 100.0)）

1. 大規模データにおけるピーク性能 (N = 300,000,000)

データの分散処理が十分に機能する大規模データセット（3億要素、約 2.4 GB）における計測結果です。

CPU Model	L2 Cache	L3 Cache	DGIS Time (s)	std::sort par (s)	Speedup
Ryzen 7 7800X3D	8.0 MB	96.0 MB	0.700126	4.176695	5.96x
Intel Core i7 11th Gen	10.0 MB	24.0 MB	1.661053	8.461430	5.09x
Intel Core i7 13th Gen	9.5 MB	24.0 MB	0.974029	4.559788	4.68x

【考察: L3キャッシュ容量とスループットの相関】 Ryzen 7 7800X3Dが 0.70 秒という極めて高いスループットを出しています。これは同CPUに搭載された巨大な3D V-Cache（96 MB L3キャッシュ）が、バケットへのデータ散布（Scatter）フェーズにおけるランダムなメモリアクセス遅延を強力に隠蔽・吸収しているためと考えられます。メモリアクセスがボトルネックになる本アルゴリズムにおいて、L3キャッシュ容量が直接的に性能へ寄与することが実証されました。

2. スケールダウン時の逆転現象 (Overhead Analysis)

以下は Intel Core i7 13th Gen における、要素数 $N$ の縮小に伴う推移です。

N (要素数)	Buckets	DGIS Time (s)	std::sort (s)	Speedup
10,000,000	512	0.043299	0.146231	3.37x
1,000,000	32	0.007652	0.017515	2.28x
200,000	16	0.004026	0.004045	1.00x (Crossover)
100,000	16	0.003394	0.002078	0.61x

【考察: 並列化オーバーヘッドと固定費の壁】 $N = 200,000$ を境界として、DGISが std::sort に逆転される現象が確認できます。これは、DGISが内包する「OpenMPスレッドプールの起動・同期コスト」や「Arenaメモリの一括確保コスト」といった固定のオーバーヘッドが、データ量の減少に伴って相対的に肥大化したためです。 この分析から、実運用環境への導入を仮定した場合、「要素数が $N \le 200,000$ の場合は動的に std::sort にフォールバックする」 というハイブリッド分岐を設計することが最適解であると結論付けられます。

---

🛠️ ビルド要件

最大のパフォーマンスを引き出すため、必ず Release モードでコンパイルし、以下のフラグを有効にしてください。

• コンパイラ: C++17 以上
• 必須フラグ:
  • 最高レベルの最適化 (-O3 または /O2)
  • OpenMPによる並列化 (-fopenmp または /openmp)
  • アーキテクチャのネイティブ命令・AVX2の有効化 (-march=native または /arch:AVX2)