現代プロセッサアーキテクチャのためのアルゴリズム

2025年7月23日原文(lemire.github.io)

概要

Daniel Lemire教授による 現代プロセッサ の性能と最適化手法の解説
命令数削減 や 並列処理 による高速化技術の紹介
SIMD や SWAR などのデータ並列性活用事例
分岐予測 や パイプライン の効率化ポイント
実測値や ベンチマーク の注意点と結論

現代プロセッサの進化と性能指標

Xeon Max プロセッサは 64 GB HBM を搭載し、 800 GB/s の帯域幅を実現
プロセッサの クロック周波数 は4 GHz以上、1サイクルは0.25ナノ秒
1バイト/サイクル で4 GB/sの処理速度
CPUボトルネック 発生の容易性
トランジスタ数の増加 とその用途（コア数増加、スーパースカラ実行、投機的実行、キャッシュ拡大、SIMD強化）
- 例: Apple M4は 4.5 GHz/28億トランジスタ、AMD Zen 5は 5.7 GHz/500億トランジスタ

命令数削減とバッチ処理

命令数最小化 がバッチ処理での最適性能に直結
バッチ処理単位の拡大 による命令節約
分岐・メモリアクセス・I/O が性能制約要因

数値パースの最適化

fast_float::from_chars による高速数値パース
主要ブラウザやGCC, C#, Rust で採用
従来手法(strtod等)より大幅に命令数削減
SWAR （SIMD within a register）による並列化
- 64bitレジスタを8バイトとして扱い、ASCII判定を効率化

バッチ処理とループアンローリング

forループのアンローリング で1回の繰り返しあたりの命令数削減
例: 乗算処理で 6-7命令→3-5命令 へ短縮

ランダムシャッフルの高速化

Knuthのアルゴリズム をバッチ化し、乱数生成・分岐数を削減
Apple M4 で大規模配列（8MB）に対して高速化実績

分岐予測とUnicode検証

UTF-16検証 で分岐が多いと性能低下
有限状態機械（FSM） を活用し、分岐レスで高速検証
Apple M4 で1文字/サイクルの検証速度（4GB/s）
分岐の学習限界 ：Apple M4で1万ランダム分岐まで対応可能

パイプラインとメモリレベル並列性

パイプライン によるレイテンシ隠蔽
メモリレベル並列性 ：大規模配列やSattoloのアルゴリズムでランダムアクセスパス生成
Littleの法則 ：レイテンシはスループットに悪影響、並列性で解消

Bloomフィルタとデータレベル並列性

Bloomフィルタ ：キャッシュミス半減、8ハッシュ関数利用
SIMD （Single Instruction, Multiple Data）：1命令で16バイト以上を同時処理
- ASCII小文字化 や デルタ計算 などで実用
- Apple M4 はSIMD自動ベクトル化対応

UTF-16のSIMD補正関数

v8（Google Chrome, Microsoft Edge） で実際に導入
SIMD補正関数 は非SIMD検証より高速
- AVX2/AVX-512/NEON/SVE/SVE2/RISC-V vector など各アーキテクチャでSIMDサポート

ベンチマークと実測値の注意点

測定値は正規分布とは限らない
現実の測定値 ：最小値が信頼できる指標となる場合が多い
平均値と最小値の差（マージン） を重視

結論とルール

プロセッサは進化し続け、幅広い並列処理が可能
ホットスポット最適化よりも全体の命令数削減が重要
分岐が多いコードは合成ベンチマークで良く見えるが、実際には注意が必要

参考：プロセッサの分岐学習能力（Apple M4）

| size | ns/value | GHz | cycles/value | instr/value | i/c | |--------|---------:|-----:|-------------:|------------:|-----:| | 1048576| 1.59 | 4.51 | 7.20 | 8.01 | 1.11 | | 524288 | 1.50 | 4.51 | 6.76 | 8.01 | 1.19 | | 262144 | 1.31 | 4.51 | 5.90 | 8.01 | 1.36 | | 131072 | 0.76 | 4.52 | 3.43 | 8.01 | 2.34 | | 65536 | 0.49 | 4.52 | 2.20 | 8.01 | 3.64 | | 32768 | 0.49 | 4.52 | 2.19 | 8.02 | 3.66 |

ハクソク