以前の投稿で、 生産性に影響する主な問題...パフォーマンス分析は難しいタスクであり、ほとんどの場合、ソースコードを分析せずに、このアルゴリズムまたはそのアルゴリズムがどのように実装されているかを研究せず、計算アーキテクチャの知識がなければ解決できないと書きました、アプリケーションが実行される場所。 この投稿では、ループを破るという考えに基づいたプログラム最適化の例を示したいと思います。
ループ最適化の基本的な考え方
サイクルは、プログラムの計算において非常に重要であり、原則として、さまざまなサイクルを実行し、アプリケーションのホットな機能です。 実行中の時間のかかる機能。 最初のコンピューティングアーキテクチャは、主にさまざまなサイクルを幅広く使用する高性能コンピューティングを対象としています。したがって、それらを最適化するというアイデアは非常に長い間驚くべきものであり、非常に多くの異なるサイクル最適化が提案されてきました。 サイクル最適化の主なアイデアは、実行される作業の順序を変更することです。 計算コアのレベルで命令の並べ替えが計算パイプラインのパフォーマンスを向上させるのに役立つ場合、ループ最適化を実行する場合、ステートメントの並べ替えは、メモリサブシステムの動作の改善、ベクトル化と自動並列化の実装、命令並列性の改善、データの再利用、分岐予測のパフォーマンスの改善など、よりグローバルな目標で実行されますなど さまざまな要因があるため、コンパイラには、可能性のある長所と短所を評価し、これまたはその高レベルの最適化を行うかどうかを決定する何らかのヒューリスティックなメカニズムが必要です。
ループ最適化パフォーマンスの簡単な例
一般的なループ分布最適化の簡単な例を見てみましょう。これは通常、逆ループ融合最適化と密接に関連しており、最適化が一部の模擬テストのパフォーマンスにどのように影響するかを確認します。 合成テストはまったく意味がありませんが、コンピューティングコアの特定のパターンを明らかにするのに役立ちます。 配列は、ポインターベクトルとして実装されます。 PERFマクロでは、最初の大きなサイクルは3つのサイクルに分割され、各サイクルには、最初のサイクルから相互接続された計算の一部が含まれます。
#include <stdio.h> #include <stdlib.h> #define N 1000 int main() { int i,j,rep; int volatile nnn; float **a1,**a2,**a3; float **b1,**b2, **b3; double **c1, **c2, **c3; double sum1,sum2,sum3; nnn = 2000; // upper bound for repeat loop .... // memory allocation and initialization for(rep=0;rep<nnn;rep++) { #ifndef PERF for(j=1;j<N-1;j++) for(i=0;i<N;i++) { sum1 = sum1 + (a1[j][i]+a2[j][i]+a3[j][i]); sum2 = sum2 + (b1[j][i]+b2[j][i]+b3[j][i]); sum3 = sum3 + (c1[j][i]+c2[j][i]+c3[j][i]); sum1 = sum1 - (a1[j-1][i]+a2[j-1][i]+a3[j-1][i]); sum2 = sum2 - (b1[j-1][i]+b2[j-1][i]+b3[j-1][i]); sum3 = sum3 - (c1[j-1][i]+c2[j-1][i]+c3[j-1][i]); sum1 = sum1 - (a1[j+1][i]+a2[j+1][i]+a3[j+1][i]); sum2 = sum2 - (b1[j+1][i]+b2[j+1][i]+b3[j+1][i]); sum3 = sum3 - (c1[j+1][i]+c2[j+1][i]+c3[j+1][i]); } #else for(j=1;j<N-1;j++) for(i=0;i<N;i++) { sum1 = sum1 + (a1[j][i]+a2[j][i]+a3[j][i]); sum1 = sum1 - (a1[j-1][i]+a2[j-1][i]+a3[j-1][i]); sum1 = sum1 - (a1[j+1][i]+a2[j+1][i]+a3[j+1][i]); } for(j=1;j<N-1;j++) for(i=0;i<N;i++) { sum2 = sum2 + (b1[j][i]+b2[j][i]+b3[j][i]); sum2 = sum2 - (b1[j-1][i]+b2[j-1][i]+b3[j-1][i]); sum2 = sum2 - (b1[j+1][i]+b2[j+1][i]+b3[j+1][i]); } for(j=1;j<N-1;j++) for(i=0;i<N;i++) { sum3 = sum3 + (c1[j][i]+c2[j][i]+c3[j][i]); sum3 = sum3 - (c1[j-1][i]+c2[j-1][i]+c3[j-1][i]); sum3 = sum3 - (c1[j+1][i]+c2[j+1][i]+c3[j+1][i]); } #endif } printf("%lf %lf %lf \n",sum1,sum2,sum3); ... //deallocation }
–O1オプションを指定してIntelコンパイラーを使用します。 コンパイラーは、このオプションについて（icl –help）と言います：
/ O1は最高速度に最適化されますが、コードサイズを大きくして速度を少し向上させる最適化を無効にします
実際、このオプションを使用すると、コンパイラーは自動ベクトル化などのループ最適化を行いません。 したがって、彼は提案された実験に干渉しません。
–DPERFオプションを使用してコンパイルし、オプションを使用しないでコンパイルした結果、2つの実行可能ファイルが作成されます。
icl -O1 distr.c -Fedistr.exe
icl -O1 -DPERF distr.c -Fedistr2.exe
Windows Server 2008 R2 EnterpriseとIntel Xeon X5570プロセッサを実行している実験室のマシンでは、結果のテストの実行時間は次のとおりです。
distr.exe：38.8秒
distr2.exe：31.2秒
2番目のサイクルのパフォーマンスははるかに優れています。 Intel VTune Amplifier XE2013が作成したGeneral Explorationプログラムを見て、両方のプログラムの結果を比較しましょう。
ここで何が問題なのでしょうか？
コンピューティングコアの分析方法を学習できる特別なガイド「Intel @ Core TM i7プロセッサーおよびIntel @ Xeon TM 5500プロセッサーのパフォーマンス分析ガイド」があります。 VTuneアンプには、さまざまなイベントの簡単な説明も含まれています。 したがって、ここに記載されている名前の一部の意味について疑問がある場合は、この情報を参照できます。 また、誰かが私を修正したり、サイクルの最適化がそのような効果を示す理由について追加のアイデアをくれたりして嬉しいです。
レポートを比較するとき、プログラムの両方のバリアントのINST_RETIRED.ANYがほぼ同じであることに注意できます。 つまり 奇跡（ベクトル化など）はなく、両方のケースで実行される作業量はほぼ同じです。 しかし同時に、最適化されたバージョンでは、CPIレートがはるかに優れているため、どのように発生したかを理解する必要があります。
プログラムオプションの1つに、リモートDRAMによってサービスされるLLCロードミスの興味深い外観があります。 理論的には、この問題はマルチスレッドアプリケーションに典型的であり、不均等なメモリアクセス（NUMA）を備えたコンピューティングアーキテクチャに典型的な別のコアに属するメモリのコンピューティングコアによる使用に関連しています。 この場合、この状況は、異なるコンピューティングコア間でのコンピューティングプロセスの移行が原因で発生します。 星が形成されたため、2番目のプログラムはコンピューティングコアを介して移行することができなくなりました。 プログラムを特定の計算コアにバインドして、オペレーティングシステムによって引き起こされるカーネル間の切り替えが結果に影響しないようにすることができます。 以下の実験は、特定のコアを参照して行われました。
VTune AmplifierのNehalemアーキテクチャ用に定義されているさまざまなイベントの標準のメモリアクセス分析は使用しませんが、独自のイベントセットを取得してコンパイルし、プログラムの2つの変更について比較します。 私は次の分析について得ました：
メモリのダウンロード数が変わったのは驚くべきことです（MEM_INST_RETIRED.LOADS）。 ただし、両方のバージョンのプログラムのアセンブラを比較すると、元のバージョンでメモリを操作するための命令の数は本当に多くなります。 これは、多数の配列を同時に処理しているときに、中間結果を格納するのに十分なレジスタがなく、プログラムスタックとレジスタ間で絶えず交換されるためです。 おそらく、この問題は重大ではないはずです。なぜなら、一定の使用によるスタックはキャッシュ内にあるからです。
メモリサブシステムの構成を思い出せば、コンピューティングコアには32KBのL1データキャッシュがあります。 プログラムの初期バージョンでは、反復ごとに多数の異なるデータストリームを処理します。 つまり 各反復で、27箇所からデータを読み取る必要がありますa1 [j-1] [i]、a1 [j] [i]、a1 [j + 1] [i]、a2 [j-1] [i]、...、 c1 [j + 1] [i]。 ただし、このデータの一部は、jに対する前回の反復でキャッシュサブシステムにロードする必要があります。 a1 [j + 1] [：]、a2 [j + 1] [：]、a3 [j + 1] [：]、b1 [j + 1] [：]、...、c3 [ j + 1] [：]。 floatのサイズは4バイト、doubleのサイズは8バイトです。 行列の行の要素数は-1000です。 4000 * 3 + 4000 * 3 + 8000 * 3 =〜47KBのデータを各反復でキャッシュサブシステムに配置する必要があります。 明らかに、プログラムの初期バージョンでは、各反復で、L1Dキャッシュが完全に更新されます。 変更されたバージョンでは、各反復で、実数行列で最大12 KB、実倍精度で最大24 KBが更新されます。 以前の反復で読み取られたデータは、メモリに部分的に保存する必要があります。 これは、L1D_CACHE_LD.I_STATEイベント（キャッシュミス）とL1D_CACHE_LD.MESI（キャッシュヒットの総数）の比率を比較することで確認できます。 「遅い」バージョンでは、この比率は〜13.6％です。 「高速」バージョンでは、約7％です。 その結果、変更されたバージョンでは、待機時間が長くなり遅延が少なくなります。
ハードウェアプリフェッチデバイスも、この計算のパフォーマンスに影響するはずです。 L1およびL2キャッシュで動作するプリフェッチデバイスがあります。 情報は全能ではなく、異なるアーキテクチャでは異なる数のデータストリームをサポートしているというドキュメントから収集できます。 [j] [i]などの特定の配列文字列へのアピールは、そのようなデータストリームです。 同時に処理されるスレッドが一定数に達すると、プリフェッチが機能しないスレッドが表示されるはずです。 さらに、スレッドの数が多いと、ハードウェアのプリフェッチがまったく機能しなくなる可能性があります。 したがって、L1DおよびL2ハードウェアプリフェッチデバイスの操作に関連するイベントを配置する新しい種類の分析を作成しました。
私の意見では、この分析は以下を示しています。 「良い」場合にL1Dプリフェッチデバイスによって生成されるクエリ（L1D_PREFETCH.REQUESTS）の数は、「遅い」場合よりもさらに多くなります。 これは奇妙ですが、プリフェッチャーのデータストリームを提供する能力が制限されているという考えを少しだけ確認します。 L2キャッシュのデバイスのプリフェッチに関しては、L2_DATA_RQSTS.DEMAND.MESI（L2データデマンドリクエスト）とL2_DATA_RQSTS.PREFETCH.MESI（すべてのL2データプリフェッチャー）の2つの興味深いイベントがあります。
つまり メモリアクセスの一部はプリフェッチデバイスによって処理され、メモリアクセスの2番目の部分はコンピューティングコアにとって驚きです。 そして、ここでも興味深い写真が観察されます。 「良い」ケースでは、プリフェッチデバイスが生成するプロアクティブリクエストの数が大幅に増えます。 また、「悪い」ケースが、サービスを受けていないクエリプリフェッチデバイスのほぼ2倍であることも重要です。
サイクルの組み合わせ/分割のサイクル最適化のペアは、条件の質量に依存します。 キャッシュにうまく収まる小さな配列の場合、各反復でより独立した計算が存在し、分岐が削減されるため、最初のオプションはより高速になる可能性があります。 この場合、アレイのサイズ、実験が行われるコンピューターシステムなどがわかっているため、分析は大幅に簡素化されます。
この場合、コンパイラは何をしますか？
この場合、最適化インテル®コンパイラーが何を行うかを確認するときが来ました。 私たちを対等な立場に置くために、コンパイラーから自動ベクトル化を行う機会を取ります。 （ここで私はまばたきのスマイリーを置きたいです。）
icl -O2 / Qvec- distr.c -Fedistr_comp.exe
時間distr_comp.exe
...
コマンドのCPU時間： 'distr_comp.exe'
実41.799秒
-O1オプションを使用したコンパイラは、-O2を使用した場合よりも優れたパフォーマンスを示します。 テストがどのように最適化されたかは明らかではありません。 オプション/ Qopt_reportがあります。 これを使用すると、コンパイラーがループの分割を完了したことがわかります。
_mainの54行目のループ分布
追加の分析（ダンプを使用する機能）の助けを借りて、パーティションがどの程度行われたかを理解できます。
for(j=1;j<N-1;j++) { for(i=0;i<N;i++) { sum3 = sum3 + (c1[j][i]+c2[j][i]+c3[j][i]); sum3 = sum3 - (c1[j-1][i]+c2[j-1][i]+c3[j-1][i]); sum3 = sum3 - (c1[j+1][i]+c2[j+1][i]+c3[j+1][i]); } for(i=0;i<N;i++) { sum1 = sum1 + (a1[j][i]+a2[j][i]+a3[j][i]); sum2 = sum2 + (b1[j][i]+b2[j][i]+b3[j][i]); sum1 = sum1 - (a1[j-1][i]+a2[j-1][i]+a3[j-1][i]); sum2 = sum2 - (b1[j-1][i]+b2[j-1][i]+b3[j-1][i]); sum1 = sum1 - (a1[j+1][i]+a2[j+1][i]+a3[j+1][i]); sum2 = sum2 - (b1[j+1][i]+b2[j+1][i]+b3[j+1][i]); } }
このような状況を「心からの災い」と呼びます。 明らかに、一方でコンパイラには創造的な可能性があります。 彼は、1つのグループの従属計算を見つけ出し、選択しました。 しかし、何らかの理由で、内側のループを分割することのみに制限され、このループが機能するデータの局所性を改善することで考えられるすべての利点を無効にしました。 さまざまな遷移の数が増加し、この最適化によるデータの局所性の改善は達成されませんでした。 2番目のサイクルは、データストリームの数を推定するという点では面倒です。
何らかの形でコンパイラーの苦味を和らげるために、この場合に自動ベクトル化がもたらすものを見てみましょう。
icl -O2 distr.c -Fedistr_compvec.exe
コマンドのCPU時間： 'distr_compvec.exe'
実24.020秒
結論：
この小さな研究では、パフォーマンス分析がかなり興味深く複雑なアクティビティであることをほのめかしていただけです。 プログラムの速度に影響を与える要因の数は非常に多いです。 さまざまなプロセッサ内イベントを測定する機会があったとしても、何らかの要因によってプログラムのパフォーマンスに与えられた寄与を評価することは非常に困難です。 理論的には、最適な結果を得るために、コンパイラの発見的メカニズムは多くの規則性を分析する必要があり、これには特定の最適化の正当性を証明する複雑さは含まれません。 さらに、多くの場合、コンパイラは、プログラムが動作するデータや、このプログラムが実行されるコンピューティングシステムについて何も知りません。