Enhanced Automated Vectorization

原文はこちら。
The original article was written by Andrew Craik (Compiler Optimization & Performance Specialist, Oracle).
https://medium.com/graalvm/enhanced-automated-vectorization-in-graalvm-76cd99925b6d

この記事では、GraalVM Enterpriseが21.2で導入された新しいハードウェアアーキテクチャ向けのループベクトル化（loop vectorization）と線形ベクトル化（linear vectorization）の最適化のアプローチ方法を見ていきます。また、GraalVMのネイティブ・イメージ機能に関連した考慮事項や、実際に試すことのできるデモについても触れています。ここで説明する最適化機能は、Oracle Java SE Subscriptionで利用可能なGraalVM Enterpriseの一部です。

Oracle Java SE Subscription
https://www.oracle.com/java/java-se-subscription/

新世代のチップ製造技術が開発されるたびに、チップ上のトランジスタ数が増加します。これらのトランジスタを使い、プロセッサに機能を追加して性能を向上させています。最近のメーカーの傾向としては、これらのトランジスタを使って、アーキテクチャのSIMD（Single Instruction Multiple Data）機能を追加、強化、拡張しています。インテルのAVX512拡張やARMのNEON拡張などがその例です。SIMDを使うと、1つの命令で、複数のデータ要素を詰め込んだvectorと呼ばれるデータに対して、同じ処理を同時に行うことができます。これらの命令がどのように動作するかを直感的に理解するために、次のようなループを考えてみましょう。

for (int i = 0; i < 4; i++) {
  array[i] = array[i] + 1;
}

このループをスカラ（非SIMD）アセンブリで実装すると、4回のload、4回のadd、4回のstoreが必要になります。SIMD命令を使用すると、このループの実装に必要なのは1回のload、1回のadd、1回のstoreで、それぞれが4つのデータ要素を同時に処理します。このようなSIMD命令を言語ランタイムで利用することで、ユーザーが期待する優れたパフォーマンスを実現することができますが、このような命令を利用する機会を作り、利用するためには、コンパイラによる特別なサポートが必要です。

GraalVM上でアプリケーションを実行する際の素晴らしい点の1つは、GraalVM Enterprise Editionのコンパイラが、対象のハードウェアプラットフォームで利用可能な最新のSIMD命令の機能をアプリケーションが利用できるように設計された、豊富な自動ベクトル化最適化のセットを提供している点にあります。この記事では、GraalVMが提供する機能の概要を説明し、この技術の利点を実際に試すことができるサンプルアプリケーションを紹介します。

Vectorization Optimizations

コンパイラはどのようにしてSIMD命令を利用する機会を見つけるのでしょうか？GraalVM Enterprise Editionでは、SIMDを利用するための2つの異なる潜在的なソースをターゲットとした2つの最適化を行っています。

Loop vectorizer – ループを分析し、ループ全体をSIMD形式に変換します。
Linear vectorizer – シーケンシャルコードを分析し、SIMD化の機会を探します。

GraalVMのLoopVectorizationフェーズは、GraalVM Enterprise Editionの最近のすべてのリリースでデフォルトで有効になっていますが、SIMDVectorizationフェーズはGraalVM Enterprise Edition 21.2の新機能で、-Dgraal.VectorizeSIMD=trueで有効にできます。

Loop Vectorization

ループは、アプリケーションにおける計算の複雑さの最も大きな原因の一つです。ループベクトル化は、機械学習、コンピュータグラフィックス、科学技術計算などのアプリケーション領域でよく見られる特定の種類のループに最適です。これらのループは通常、大きな数値の配列に対する純粋な算術計算です。このような計算が複雑なループをSIMD命令に変換することができれば、アプリケーションのパフォーマンスに大きなプラスの影響を与えることができます。
GraalVM loop vectorizerは、ループ全体を見て、隣接するループの反復にSIMDの並列性がある計算パターンを特定します。つまり、ベクトル化されたループは、元のループのいくつかの反復を並行して実行します。loop vectorizerは、map loopとfold loopという2つの主要なループパターンを認識します。
map loopは、1つまたは複数の配列から要素を順次読み込み、それらの要素に対して算術演算を行い、結果の値をターゲット配列に順次書き込むものです。ソース配列とターゲット配列は同じであってもかまいません。

for (int i = 0; i < z.length; i++) {
  z[i] = 3 * x[i] + y[i] + 7;
}

Fold loopまたはReduce loopは，1つまたは複数の配列から要素を順次読み込み、それらをアキュムレータで結合する算術演算を行います．計算の最後には1つの値が得られます。ただしmap loopとは異なり、この手の算術演算には結合性と可換性が必要です。浮動小数点演算は、丸めの関係で結合性がないため、整数に対するfold loopのSIMDコードしか生成できません。

for (int i = 0; i < array.length; i++) {
  sum += array[i];
}

ループ内での分岐計算は、一般的にベクトル化が難しく、ここはGraalVMのloop vectorizerで現在開発が進んでいる分野です。JVM上ですでにうまく機能している重要なケースとして、ガード (guard) があります。guardとは、非常に稀にしか実行されない、あるいは全く実行されないことが予想されるコードをマークする、コンパイラ内部の特別な構成要素です。例えば、JVMのプロファイリング情報により、コンパイラは、これまで一度も実行されておらず、今後も実行されることがないと予想されるコードを特定できます。

次のコードは、実際のワークロードから抜粋したもので、double型の配列に対して計算を行い、それぞれに誤ったNaN (非数) の値がないかどうかをチェックしています。

boolean seenError = false;
for (int i = 0; i < array.length; i++) {
  if (Double.isNaN(array[i])) {
    seenError = true;
  }
  array[i] = array[i] + increment;
}

このコードがコンパイルされる前にisNaNチェックが一度も失敗していない場合、errorブランチ全体が到達していないコードとしてguardでマークされ、ブランチの実際の内容は無関係であり、コンパイラには見えないことさえあります。guardの条件がベクトル化できる限り（この場合、単純なSIMD比較です）、このループはGraalVMでベクトル化できます。guardが失敗することがあった場合のみ、コード全体を再コンパイルして、非SIMDループの実装に戻す必要があります。

また、GraalVM loop vectorizerは、map演算やfold演算を条件式を用いてベクトル化できます。ここで生成または蓄積する値を選択する条件は、読み込まれた値に基づきます。一般的に、GraalVM loop vectorizerは、任意の個数のfold演算map演算を含むループを変換できます。ただし、guardを含むループをベクトル化できるのは、その構成演算がfold演算またはmap演算だけの場合のみです。fold演算とmap演算の混在は、guardを含むループではサポートされていません。

最後に、SIMD命令セットの中には、連続していないインデックスから配列の要素を読み込むgather命令が含まれているものがあります。CPUがサポートしている場合、GraalVM loop vectorizerは、アクセスされた各インデックスが基礎となる配列の境界内にあるかどうかをチェックするための暗黙のguardも含め、このようなgather演算のためのSIMDコードの生成をサポートしています。GraalVM loop vectorizerは現在、連続しない配列要素への書き込みのためのdual scatter演算をサポートしていません。

Linear Vectorizer

linear vectorizerは、GraalVM Enterprise Edition バージョン21.2で導入された新しい最適化で、loop vectorizerを補完するように設計されています。linear vectorizerは、線形なコードセグメントに着目し、SIMD命令を使用する機会を特定します。linear vectorizerは、loop vectorizerで処理される形式のループ本体を無視しますが、loop vectorizerで処理されないループ本体内の線形なコードセグメントを処理して、個々のループの反復処理を高速化しようとします。

linear vectorizerはパターンマッチングのメカニズムで動作します。マッチングは3個のフェーズで動作します。

load演算とマッチさせ、読み込み対象のオブジェクトとフィールドや要素に基づいてグループ化する
アーキテクチャ固有の演算にマッチさせる
store演算にマッチし、書き込み対象のオブジェクトとフィールドや要素に基づいてグループ化する

マッチングが完了すると、アルゴリズムはアーキテクチャ固有の演算をグループ化し、storeとloadの接続を試みます。接続に成功すると、グループ化された演算に対してSIMD命令を使用するようにプログラムが変換されます。また、この最適化では、ループ本体の処理や、値を構成要素に分解したり、構成要素を組み合わせて新しい値を作成するパターンマッチングの操作を特別にサポートしています。

より具体的な例として，隣り合う4つの配列要素をインクリメントする次のコードを考えてみましょう。

data[1] = data[1] + 1;
data[2] = data[2] + 1;
data[3] = data[3] + 1;

linear vectorizerは、load、add、store演算をパターンマッチさせ、次の疑似コードのように、SIMD命令を使ってload、add、storeを3命令で行うようにプログラムを変換できます。

int[] data = …;data[<0,1,2,3>] = data[<0,1,2,3>] + <1,1,1,1>

linear vectorizerはGraalVM Enterprise Edition version 21.2でデフォルトでは有効になっていません。有効化したい場合には、 -Dgraal.VectorizeSIMD=true を指定する必要があります。ある状況では、最適化により一部のメソッドのコンパイル時間が明らかに増大する場合があるため、VMの起動時間や、ピークスループット増加のための時間が重要な場合に、この最適化を有効にすることは現時点ではおすすめしません。デフォルトでlinear vectorizerを有効化するまでに、この制限に対応する予定です。

Native Image Considerations

GraalVMのNative Imageをビルドする際には、ループベクトル化と線形ベクトル化の両最適化がサポートされていますが、いくつかの制限があるので注意が必要です。

ベクトル化最適化を可能にする方法でプログラムを変換する最適化の中には、ループ回数に関する情報を必要とするものがあります。結果として、profile-guided optimization (PGO) を使ってビルドされたNative Imageのみが、GraalVMのベクトル化機能の恩恵を最大限に受けることができます。
Native Imageにおけるguardの実装方法の違いにより、GraalVMでNative Imageを構築する場合、guardを持つループベクトル化ができない場合があります。
ベクトル化の最適化は、x86プロセッサのAVX、AVX2、AVX-512 SIMD命令セットをターゲットにする方法を知っています。しかし、これらの命令セットはそれぞれオプションであり、必ずしもすべてのプロセッサでサポートされているわけではありません。そのため、NativeArchitecture フラグや CPUFeatures フラグを使用して、生成されるイメージを動作させたいプロセッサに応じて、どの命令サブセットの使用が許可されているかをコンパイラに伝える必要があります。

命令セットのバリエーションがネイティブイメージのパフォーマンスに与える影響を軽減するための取り組みを実施中です。現在、AArch64プラットフォームでは、命令サブセットの制限はありません。

A Practical Demonstration

ここまで、GraalVM Enterprise Edition 21.2のベクトル化最適化の機能について説明してきましたが、ここでは、ループベクトル化と線形ベクトル化の最適化の効果を確認するために実行できるサンプルプログラムを紹介します。このサンプルプログラムは、機械学習や物理学の領域でよく見られる数学的な演算であるドット積 (dot product) をベースにしています。

このサンプルプログラムでは、ドット積を使って、2つのベクトルデータ（ここではサイン波とコサイン波）の相関関係を計算します。

	class SignalCorrelation {

	/** Approximate {@code sin(i / 1000)}. */
	public static double sin(int i) {
	double x = i / 1000.0;
	double term3 = (xxx) / (3 * 2 * 1);
	double term5 = (xxxxx) / (5 * 4 * 3 * 2 * 1);
	return x - term3 + term5;
	}

	public static double[] sinTable(int n) {
	double[] table = new double[n];
	for (int i = 0; i < n; i++) {
	table[i] = sin(i);
	}
	return table;
	}

	/** Approximate {@code cos(i / 1000)}. */
	public static double cos(int i) {
	double x = i / 1000.0;
	double term2 = (xx) / (2 1);
	double term4 = (xxxx) / (4 3 * 2 * 1);
	return 1 - term2 + term4;
	}

	public static double[] cosTable(int n) {
	double[] table = new double[n];
	for (int i = 0; i < n; i++) {
	table[i] = cos(i);
	}
	return table;
	}

	public static double correlate(double[] a, double[] b) {
	double correlation = 0.0;
	for (int i = 0; i < a.length; i++) {
	correlation += a[i] * b[i];
	}
	return correlation;
	}

	public static double computeCorrelation(double[] a, double[] b) {
	return correlate(a, b);
	}

	public static void main(String[] args) {
	int n = args.length > 0 ? Integer.valueOf(args[0]) : 100_000_000;

	for (int j = 0; j < 10; j++) {
	long tablesStart = System.nanoTime();
	double[] sin = sinTable(n);
	double[] cos = cosTable(n);
	long tablesEnd = System.nanoTime();
	System.out.println("table computation: " + (tablesEnd - tablesStart) / 1_000_000 + " ms");

	long correlationStart = System.nanoTime();
	double sinSin = computeCorrelation(sin, sin);
	double sinCos = computeCorrelation(sin, cos);
	double cosSin = computeCorrelation(cos, sin);
	double cosCos = computeCorrelation(cos, cos);

	double sinSinNormalized = sinSin / sinSin;
	double sinCosNormalized = sinCos / Math.sqrt(sinSin * cosCos);
	double cosSinNormalized = cosSin / Math.sqrt(cosCos * sinSin);
	double cosCosNormalized = cosCos / cosCos;
	long correlationEnd = System.nanoTime();

	System.out.println("sin/sin correlation: " + sinSinNormalized);
	System.out.println("sin/cos correlation: " + sinCosNormalized);
	System.out.println("cos/sin correlation: " + cosSinNormalized);
	System.out.println("cos/cos correlation: " + cosCosNormalized);
	System.out.println("correlation: " + (correlationEnd - correlationStart) / 1_000_000 + " ms");
	}
	}
	}

view raw SignalCorrelation.java hosted with ❤ by GitHub

この例では、sinTable、cosTable、相関関数の本体を形成する3つのループが注目されます。アプリケーションを実行すると、データテーブル（sinTableとcosTableが主役）の生成にかかった時間と、相関関係（correlateが主役）の計算にかかった時間が表示されます。

sinTableとcosTableのループは、GraalVM Enterprise Editionのloop vectorization最適化によってうまく処理されるmapループの典型的な例です。correlateループでドット積を計算します。このループは計算量が多く、ベクトル化の恩恵を受けているように見えます。このループは浮動小数点値を累積しているため、loop vectorizerにはあまり適していません。浮動小数点演算の順序を変更すると、中間結果の丸め方が異なるため、微妙に異なる結果になります。このようなちょっとした潜在的差異を気にしないのであれば、ループを手作業で展開して、linear vectorizerで利用可能なintra-iteration parallelismを晒すことができます。

	public static double correlate(double[] a, double[] b) {
	if (a.length != b.length) {
	return Double.NaN;
	}
	double partial[] = new double[4];
	int i = 0;
	for ( ; i + 3 < a.length; i += 4) {
	partial[0] += a[i+0] * b[i+0];
	partial[1] += a[i+1] * b[i+1];
	partial[2] += a[i+2] * b[i+2];
	partial[3] += a[i+3] * b[i+3];
	}
	double correlation = partial[0] + partial[1] + partial[2] + partial[3];
	for ( ; i < a.length; i++) {
	correlation += a[i] * b[i];
	}
	return correlation;
	}

view raw correlate.java hosted with ❤ by GitHub

ここでは、中間値を保持するためにローカルに割り当てられた配列を使用しています。これは、中間値がメモリ内で隣接していることが保証され、値の読み書きをSIMD演算にまとめるのが適しているためです。この配列は実際にはメモリ上に割り当てられません。最適化が完了した後、配列の構成値は実際にSIMDレジスタに保持されます。次の擬似コードは、ベクトル化の結果を示しています。

	public static double correlate(double[] a, double[] b) {
	if (a.length != b.length) {
	return Double.NaN;
	}
	double <w,x,y,z> = <0,0,0,0>;
	int i = 0;
	for ( ; i + 3 < a.length; i += 4) {
	<w,x,y,z> += a[<i,i+1,i+2,i+3>] * b[<i,i+1,i+2,i+3>];
	}
	double correlation = w + x + y + z;
	for ( ; i < a.length; i++) {
	correlation += a[i] * b[i];
	}
	return correlation;
	}

view raw correlate-pseudo.java hosted with ❤ by GitHub

サンプルコードをコンパイルし、以下のように実行できます。テーブル計算と相関時間の最後の繰り返しから時間を読み取ります。

sin/sin correlation: 1.0
sin/cos correlation: 0.9949874370939154
cos/sin correlation: 0.9949874370939154
cos/cos correlation: 1.0
correlation: 731ms...

プログラムを理解し、相関関数の潜在的な並列性を明らかにしたので、ループベクトル化と線形ベクトル化の利点を観察するためのいくつかの実験をしてみましょう。まず、GraalVM Enterprise Edition 21.2上で、 -Dgraal.VectorizeLoops の値を変えてプログラムを実行し、テーブルの計算時間に対するループベクトル化の最適化の効果（約30％の改善）を確認します。

> java -Dgraal.VectorizeLoops=false SignalCorrelation...table computation: 1227ms
sin/sin correlation: 1.0
sin/cos correlation: 0.9949874370939154
cos/sin correlation: 0.9949874370939154
cos/cos correlation: 1.0
correlation: 436ms> java -Dgraal.VectorizeLoops=true SignalCorrelation...table computation: 878ms
sin/sin correlation: 1.0
sin/cos correlation: 0.9949874370939154
cos/sin correlation: 0.9949874370939154
cos/cos correlation: 1.0
correlation: 415ms

GraalVM 21.2では、部分ループ展開の最適化（partial loop unrolling optimization）はlinear vectorizerとあまり相互作用しない場合があります。この件はGraalVMの将来バージョンで修正の予定ですが、現時点では、部分ループ展開を -Dgraal.PartialUnroll=false で無効化できるので、 -Dgraal.VectorizeSIMD=true の有無のパターンで実行してみると、線形ベクトル化によりおよそ30％のパフォーマンス改善を確認できます。

> java -Dgraal.PartialUnroll=false SignalCorrelation...table computation: 851ms
sin/sin correlation: 1.0
sin/cos correlation: 0.9949874370939154
cos/sin correlation: 0.9949874370939154
cos/cos correlation: 1.0
correlation: 453ms> java -Dgraal.PartialUnroll=false -Dgraal.VectorizeSIMD=true SignalCorrelation...table computation: 859ms
sin/sin correlation: 1.0
sin/cos correlation: 0.9949874370939154
cos/sin correlation: 0.9949874370939154
cos/cos correlation: 1.0
correlation: 350ms

最後に、最高のパフォーマンスを出すGraalVMの構成（-Dgraal.PartialUnroll=false -Dgraal.VectorizeSIMD=true）で実行し、HotSpot C2の場合とでパフォーマンスを比較すると、GraalVM Enterprise Edition 21.2では全体として40％ほど高速であることがわかります。

> java -Dgraal.PartialUnroll=false -Dgraal.VectorizeSIMD=true SignalCorrelation...table computation: 881ms
sin/sin correlation: 1.0
sin/cos correlation: 0.9949874370939154
cos/sin correlation: 0.9949874370939154
cos/cos correlation: 1.0
correlation: 364ms> java -server -d64 SignalCorrelation...table computation: 2444ms
sin/sin correlation: 1.0
sin/cos correlation: 0.9949874370939154
cos/sin correlation: 0.9949874370939154
cos/cos correlation: 1.0
correlation: 537ms

GraalVM Enterprise Editionに搭載されている素晴らしい最適化技術の一部をご紹介しました。GraalVMが提供するパフォーマンスをご自身のワークロードで試してみたいと思っていただければ幸いです。

GraalVM Enterprise Edition Download
https://www.oracle.com/downloads/graalvm-downloads.html

日	月	火	水	木	金	土
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30	31

Logico Inside

Enhanced Automated Vectorization

Vectorization Optimizations

Loop Vectorization

Linear Vectorizer

Native Image Considerations

A Practical Demonstration

コメントを残すコメントをキャンセル

Vectorization Optimizations

Loop Vectorization

Linear Vectorizer

Native Image Considerations

A Practical Demonstration

共有:

いいね:

コメントを残す コメントをキャンセル

コメントを残すコメントをキャンセル