サイクル最適化手法の紹介

プログラムの実行時間のほとんどはサイクルです。情報の計算、受信、処理などが可能です。 サイクルを最適化するための技術を正しく適用すると、プログラムの速度が向上します。 しかし、最適化に着手する前に、プログラムのボトルネックを強調し、パフォーマンス低下の理由を見つけ出す必要があります。



サイクルでのコードの実行時間は、メモリ構成、サポートされる命令セットを含むプロセッサアーキテクチャ、パイプライン、キャッシュ、およびプログラマの経験に依存します。

ループの最適化方法のいくつかを検討してください：ループの展開、ループの融合、ループの分配、ループの整列、ループの交換、ループのブロック。

最適化を適用する前に、最も単純なことを行います。ループ内で変化しない変数をすべて削除します 。

サイクルの中でプログラムの速度が低下する原因は何ですか？

1. ループの反復は依存関係にあり、並行して実行することはできません。
2. ループの本体が大きく、必要なレジスタが多すぎます。
3. ループの本体または反復回数は小さく、ループの使用を完全に放棄するためにより有益です。
4. ループには、サードパーティライブラリからの関数とプロシージャの呼び出しが含まれます。
5. このサイクルでは、1つのプロセッサ実行ユニットが集中的に使用されます。
6. ループには条件付き遷移があります。

スイープサイクル

このような最適化は、サイクルの本体が小さいときに実行されます。 反復ごとに実行デバイスをより効果的に使用する必要があります。 したがって、実行するデバイスの数に応じて、サイクルの本体を繰り返し複製します。 しかし、そのような最適化はデータの依存関係を引き起こす可能性があり、それを取り除くために追加の変数が導入されます。

に	後	番号2の後
for ( int i = 0; i < iN; i++){ res *= a[i]; }	for ( int i = 0; i < iN; i+=3){ res *= a[i]; res *= a[i+1]; res *= a[i+2]; }	for ( int i = 0; i < iN; i+=3){ res1 *= a[i]; res2 *= a[i+1]; res3 *= a[i+2]; } res = res1 * res2 * res3;

以下のキーをgccに適用できます： -funroll-all-loops -funroll-loops 。

サイクル統合

サイクルには、平方根の抽出などの実行時間の長い命令が含まれる場合があります。 または、同じインデックス間隔で実行されるループがいくつかあります。 したがって、実行デバイスのよりバランスの取れた負荷のために、サイクルを結合することをお勧めします。

に	後
for ( int i = 0; i < iN; i++){ a[i] = b[i] - 5; } for ( int i = 0; i < iN-1; i++){ d[i] = e[i] * 3; }	for ( int i = 0; i < iN-1; i++){ a[i] = b[i] - 5; d[i] = e[i] * 3; } a[iN-1] = b[iN-1] - 5;

切断サイクル

この最適化は、ループの本体が大きく、変数が十分なレジスターでない場合に使用されます。 したがって、データは最初にキャッシュにプッシュされ、すべてが完全に不良である場合はRAMにプッシュされます。 また、RAMへのアクセスには約300プロセッササイクルがかかり、L2へのアクセスは約10だけです。 大きなステップでメモリにアクセスすると、プログラムの速度がさらに低下します。 2 ^nの増分でメモリを「ウォークスルー」することが最適です。ここで、nはかなり小さい数（<7）です。

に	後
for ( int j = 0; j < jN; j++){ for ( int k = 0; k < kN; k++){ for ( int m = 0; m < mN; m++){ i = j * k + m; a[i] = b[i] * c[i] + f[i]/e[i]+ x[i] - y[i] + z[i]/r[i] + d[i] * x[i]; } } }	for ( int j = 0; j < jN; j++){ for ( int k = 0; k < kN; k++){ double tmp; for ( int m = 0; m < mN; m++){ i = j * k + m; tmp = b[i] * c[i] + f[i]/e[i]; a[i] = tmp - y[i] + z[i]/r[i] + (d[i] + 1) * x[i]; } } }

スワップサイクル

ネストされたループでは、ネストの順序が重要です。 したがって、配列がメモリに格納される方法を覚えておく必要があります。 古典的な例：c / c ++は行列を行ごとに保存し、Fortran-を列に保存します。

に	後
for ( int i = 0; i < iN; i++){ for ( int j = 0; j < jN; j++){ for ( int k = 0; k < kN; k++){ c[i][j] = c[i][j] + a[i][k] * b[k][j]; } } }	for ( int i = 0; i < iN; i++){ for ( int k = 0; k < kN; k++){ for ( int j = 0; j < jN; j++){ c[i][j] = c[i][j] + a[i][k] * b[k][j]; } } }

ここで、配列aを順番に呼び出します。

サイクルのブロックへの分割

ループの本体が複雑な場合は、この最適化を適用して、データをメモリ内により適切に配置し、キャッシュの使用を改善できます。 最適化の結果は、プロセッサアーキテクチャに大きく依存します。

に	後
for ( int i = 0; i < iN; i++){ for ( int j = 0; j < jN; j++){ a[i][j] = a[i][j] + b[i][j]; } }	// int iBlk, jBlk; for ( int k = 0; k < iN/iBlk; k++){ for ( int m = 0; m < jN/jBlk; m++){ for ( int i = k * iBlk; i < ((k + 1) * iBlk); i++){ for ( int j = m * jBlk; j < ((m + 1) * jBlk); j++){ a[i][j] = a[i][j] + b[i][j]; } } } }

この原理についてMPIテクノロジーは機能します。大きなアレイをブロックに分割し、個々のプロセッサーに送信します。

依存関係の解決

最善の解決策は、取り除くことです。 しかし、すべての依存関係で機能するわけではありません。

for ( int i = 1; i < N; i++){

a[i] = a[i-1] + 1;

}

この例では、スキャンを適用することをお勧めします。 計算の結果はレジスタに残ります。 しかし、これらのサイクルのほとんどは完全に最適化（または並列化）することができず、結果はサイクルの前のターンに依存します。

サイクルの独立性を確認するには、サイクルの移動方向を逆にします。 計算の結果が変更されていない場合、ループの反復は独立しています。

条件付き変換

コンベアをロールバックする必要があるため、移行の予測のエラーが原因で時間の損失が発生します。 したがって、条件構造を放棄するのが最善です。 しかし、これが不可能な場合は、遷移予測モジュールの作業を促進する必要があります。 これを行うには、最も可能性の高いブランチをブランチの先頭に配置し、可能であれば、ループ外の条件構造を取り出します。

結論の代わりに

プロセッサ時間を大量に消費する複雑なプログラムを作成する場合、

1. プロセッサアーキテクチャを確認します（プロセッサの数と実行デバイス、パイプラインの数、L1およびL2キャッシュのサイズを確認します）。
2. 異なるコンパイラと異なるキーを使用してプログラムをコンパイルしてみてください。
3. オペレーティングシステムの影響を考慮してください。

この記事を読むこともお勧めします。

私自身の経験から言えば、最適化を適切に使用することで、プログラムの速度を数倍向上させることができます。



自分で最適化を練習したい場合は、Pi番号を計算してみてください。





以下は悪いコードです。

long N = 10000000;

double dx, sum, x;

sum = 0.0;

x = 0.0;

dx = 1.0 / ( double ) N;

for ( long i = 0; i < N; i++){

sum += 4.0 / (1.0 + x * x);

x += dx;

}

double pi = dx * sum;

私が話していないこと：計算のベクトル化（SSE命令）; メモリの操作を簡単にするプリフェッチについて。 「興味がある」人がいる場合は、サイクルのベクトル化に関する別の記事を書きます。

ソースコードハイライターの強調表示 。