原文はこちら。
The original article was written by William Sjöblom (Computer Engineering at Linköping University, Stockholm, Sverige).
https://inside.java/2021/01/27/extending-c2-autovectorization-capabilities/
この記事で記載している成果は、Oracle、Uppsala大学、KTHによる共同研究の一環によるものです。ストックホルムのOracle DevelopmentオフィスでのJVM研究について詳細を知りたい方は、inside.javaのブログをフォローしてください。
Oracle, Uppsala University, and KTH in joint JVM research projects
https://inside.java/2020/06/12/joint-research-projects/
私William Sjöblomは、2020年後半、リンショーピング大学（Linköping University）の計算機工学修士修士課程の5年間の最後の年を締めくくる修士論文をOracleで書きました。
修士論文では、OpenJDKに含まれるHotSpot C2コンパイラにおける自動ベクトル化のさらなる可能性について調査しました。具体的には、Javaクラスライブラリでの繰り返し多項式ハッシュ関数（recurring polynomial hash functions）を処理することを最初の目標として、反復依存性を持つ最内周ループの自動ベクトル化を調査しました。つまり、C2にこれらのハッシュ関数のデータ並列性を認識させ、パフォーマンスの高いSIMDコードを生成することです。
これを実現するために、ループ最適化パスを追加しました。この新たなパスでは、バイナリ演算や配列のロードなどのプリミティブな演算を表すノードとともにループ本体のデータフローをツリーベースの表現で抽出します。最初のツリーがあらかじめ定義されたイディオムに対応している場合には、ツリーが1つのノードになるように、一連の書き換えルールに基づいてこのツリーが刈り込まれます。ここでいうイディオムとは、コンパイラがより性能の高いSIMD実装を認識している既知のcomputational kernelのことです。つまり、刈り込みプロセスで単一のノードが生成された場合、最適化の対象となるループを事前に定義したSIMD実装に置き換えるだけです。
現状では、最適化パスはreductionとprefix sum（scanとも）という2つのイディオムを認識しています。reductionイディオムは、（前述の多項式ハッシュ関数を含め）広範囲の配列のreductionを網羅しており、SIMD実装には再帰的倍加法を使用しています。
A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equations
https://ieeexplore.ieee.org/document/5009159
prefix sumイディオムは、この技術の一般性を示すために実装されたもので、配列のすべての累計を計算するループを包含し，SIMD実装にはHillisとSteleが提案した並列prefix sumアルゴリズムを使用しています。
Data parallel algorithms
https://dl.acm.org/doi/10.1145/7902.7903
上図は、性能評価の中でも特に興味深い2つの結果で、前述の2つの多項式ハッシュ関数の性能値を示しています。ベースラインのスカラー実装と、自動ベクトル化実装（128ビットと256ビットのベクトル長を使用）の性能をプロットしています。ご覧のように、これらの手法で得られたデータ並列性を利用することで、パフォーマンスを得ることができます。同様に、prefix sumについても大幅な速度向上が見られ、recurring computational kernelのベクトル化は確かに価値のある行為であることがわかりました。
いま修士論文ならびに専門教育の最後の段階にあり、学生生活を最高の形で締めくくる機会を与えてくれたOracleのJPGチームに感謝しております。HotSpotという壮大なエンジニアリングに取り組ませてくれたこと、そしてその過程で必要なサポートをいただきました。私の貢献がいつの日かOpenJDKのメインラインにマージされ、皆さんもString.hashCodeがとんでもないスピードで処理されるという大きな喜びを味わっていただけることを願っております。
Logico Inside 