最初から設計するSIMDアルゴリズム
(mcyoung.xyz)SIMDアルゴリズム設計
- SIMD最適化の説明: SIMDは単一命令・複数データを意味し、回路設計者のように考える必要がある。
- SIMDは性能やHPC（高性能コンピューティング）でよく言及されるが、初心者にとって親しみやすいテーマではない。
- ほとんどのプログラミング言語で、SIMDプログラミングAPIは使いにくい。
- SIMDアルゴリズムは手続き型プログラミングの考え方では理解しにくく、関数型プログラミングが役立つ。
- 本文はRustの
std::simdライブラリを使ってbase64コーデックを実装したvb64についての内容。
物理的限界
- コンピュータは現実世界に存在し、物理法則に拘束される。
- 初期のコンピューティング時代には、新しいコンピュータを購入することで性能を向上させられた。
- デナードスケーリングの効果が崩れ、より小さいトランジスタはより多くの電力消費を意味するようになった。
- コア数を増やすことが新たなトレンドになった。マルチスレッディングによってCPU性能を向上できるが、同期オーバーヘッドが発生する。
手続き型コードの遅さ
- 現代のコンピュータコアはコードを1行ずつ実行しているわけではない。
- 命令レベル並列性により、データ依存性がない場合は複数の演算を同時に実行する。
- コンパイラがデータハザードを解決できるとき、並列性は高まる。
- 分岐とメモリ操作はストールを発生させ、これがコードを遅くする。
SIMDとレーン
- SIMDとベクトルはしばしば同義語として使われる。
- SIMD命令は、固定サイズの数値配列であるベクトルを基本単位として使う。
- ベクトルの各要素をレーンと呼び、SIMDベクトルは一般に小さいサイズである。
実際のベクトルに対する演算
- SIMDベクトルは通常のレジスタよりも複雑な演算を提供する。
- ベクトルレジスタはビット演算、レーンごとの算術演算、レーンごとの比較、シャッフルなど多様な演算をサポートする。
- シャッフルは、SIMDプログラミングでデータを適切な位置に移動させるうえで重要である。
組み込み関数と命令選択
- SIMDコードを書く際に利用できる演算はアーキテクチャによって異なる。
- コンパイラは、ユーザーが要求した演算をどの命令で実現するかを決める命令選択問題を解決する。
- ポータブルなSIMDコードの作成は複雑だが、ランタイム機能検出によってさまざまなプロセッサで最適なコードを生成できる。
SIMDによるパース
- SIMDを使ってテキストをパースでき、非常に高速になりうる。
- 例として、base64デコードをSIMDで実装することが挙げられる。
- すべての分岐を取り除くことが、SIMD版を作る過程の核心である。
GN⁺の見解
この記事で最も重要なのは、SIMDプログラミングが従来の手続き型プログラミング方式とは異なり、データを並列に処理して性能を向上できるという点です。SIMDは高性能コンピューティング分野で非常に重要であり、特にRustのような現代的なプログラミング言語でSIMDを効果的に使う方法を理解することは、ソフトウェアエンジニアにとって非常に興味深いテーマになりえます。SIMDを通じて複雑なアルゴリズムを最適化し、実際のハードウェアの限界を乗り越える方法を学べるからです。
1件のコメント
Hacker News のコメント
_mm256_cvtps_epu32はAVX2の命令ではなくAVX-512の命令であり、AVX1では整数は符号付きの形で存在し、その命令は_mm256_cvtps_epi32である。