☰

Intel Sandybridge ファミリー CPU のパイプラインのプログラムを非最適化する 質問する

tag-icon • tag-icon c++ optimization x86 intel cpu-architecture
Intel Sandybridge ファミリー CPU のパイプラインのプログラムを非最適化する 質問する

私はこの課題を完了するために 1 週​​間頭を悩ませてきましたが、ここで誰かが私を正しい道に導いてくれることを願っています。まずは講師の指示から始めましょう。

この課題は、素数プログラムを最適化するという最初のラボ課題の逆です。この課題の目的は、プログラムを悲観的にすること、つまり実行速度を遅くすることです。これらは両方とも CPU を集中的に使用するプログラムです。ラボの PC で実行すると数秒かかります。アルゴリズムを変更することはできません。

プログラムを非最適化するには、Intel i7 パイプラインの動作に関する知識を活用します。命令パスの順序を変更して WAR、RAW、その他の危険をもたらす方法を想像します。キャッシュの有効性を最小限に抑える方法を考えます。極悪非道な無能者になりましょう。

課題では、Whetstone プログラムまたは Monte-Carlo プログラムを選択できます。キャッシュの有効性に関するコメントは、主に Whetstone にのみ適用されますが、私は Monte-Carlo シミュレーション プログラムを選択しました。

// Un-modified baseline for pessimization, as given in the assignment
#include <algorithm>    // Needed for the "max" function
#include <cmath>
#include <iostream>

// A simple implementation of the Box-Muller algorithm, used to generate
// gaussian random numbers - necessary for the Monte Carlo method below
// Note that C++11 actually provides std::normal_distribution<> in 
// the <random> library, which can be used instead of this function
double gaussian_box_muller() {
  double x = 0.0;
  double y = 0.0;
  double euclid_sq = 0.0;

  // Continue generating two uniform random variables
  // until the square of their "euclidean distance" 
  // is less than unity
  do {
    x = 2.0 * rand() / static_cast<double>(RAND_MAX)-1;
    y = 2.0 * rand() / static_cast<double>(RAND_MAX)-1;
    euclid_sq = x*x + y*y;
  } while (euclid_sq >= 1.0);

  return x*sqrt(-2*log(euclid_sq)/euclid_sq);
}

// Pricing a European vanilla call option with a Monte Carlo method
double monte_carlo_call_price(const int& num_sims, const double& S, const double& K, const double& r, const double& v, const double& T) {
  double S_adjust = S * exp(T*(r-0.5*v*v));
  double S_cur = 0.0;
  double payoff_sum = 0.0;

  for (int i=0; i<num_sims; i++) {
    double gauss_bm = gaussian_box_muller();
    S_cur = S_adjust * exp(sqrt(v*v*T)*gauss_bm);
    payoff_sum += std::max(S_cur - K, 0.0);
  }

  return (payoff_sum / static_cast<double>(num_sims)) * exp(-r*T);
}

// Pricing a European vanilla put option with a Monte Carlo method
double monte_carlo_put_price(const int& num_sims, const double& S, const double& K, const double& r, const double& v, const double& T) {
  double S_adjust = S * exp(T*(r-0.5*v*v));
  double S_cur = 0.0;
  double payoff_sum = 0.0;

  for (int i=0; i<num_sims; i++) {
    double gauss_bm = gaussian_box_muller();
    S_cur = S_adjust * exp(sqrt(v*v*T)*gauss_bm);
    payoff_sum += std::max(K - S_cur, 0.0);
  }

  return (payoff_sum / static_cast<double>(num_sims)) * exp(-r*T);
}

int main(int argc, char **argv) {
  // First we create the parameter list                                                                               
  int num_sims = 10000000;   // Number of simulated asset paths                                                       
  double S = 100.0;  // Option price                                                                                  
  double K = 100.0;  // Strike price                                                                                  
  double r = 0.05;   // Risk-free rate (5%)                                                                           
  double v = 0.2;    // Volatility of the underlying (20%)                                                            
  double T = 1.0;    // One year until expiry                                                                         

  // Then we calculate the call/put values via Monte Carlo                                                                          
  double call = monte_carlo_call_price(num_sims, S, K, r, v, T);
  double put = monte_carlo_put_price(num_sims, S, K, r, v, T);

  // Finally we output the parameters and prices                                                                      
  std::cout << "Number of Paths: " << num_sims << std::endl;
  std::cout << "Underlying:      " << S << std::endl;
  std::cout << "Strike:          " << K << std::endl;
  std::cout << "Risk-Free Rate:  " << r << std::endl;
  std::cout << "Volatility:      " << v << std::endl;
  std::cout << "Maturity:        " << T << std::endl;

  std::cout << "Call Price:      " << call << std::endl;
  std::cout << "Put Price:       " << put << std::endl;

  return 0;
}

私が行った変更により、コードの実行時間が 1 秒長くなったようですが、コードを追加せずにパイプラインを停止するには何を変更すればよいのかよくわかりません。正しい方向を示していただけるとありがたいです。ご返答いただければ幸いです。

アップデート：この課題を出した教授が詳細を投稿した

ハイライトは次のとおりです。

  • これはコミュニティ カレッジの 2 学期目の建築学の授業です (Hennessy と Patterson の教科書を使用)。
  • 研究室のコンピュータにはHaswell CPUが搭載されている
  • CPUID学生たちは、命令とキャッシュ サイズの決定方法、および組み込み関数と命令について学習しましたCLFLUSH。
  • 任意のコンパイラ オプションが許可され、インライン asm も許可されます。
  • 独自の平方根アルゴリズムを書くことは、常識外であると発表されました

Cowmoogunのメタスレッドのコメントによると、コンパイラの最適化がこれに含まれるかどうかは明らかではなく、-O0実行時間が 17% 増加するのは妥当であることがわかりました。

つまり、課題の目的は、学生に既存の作業を並べ替えて、命令レベルの並列性などを減らすことだったようですが、人々がより深く掘り下げてより多くのことを学んだことは悪いことではありません。

これはコンピュータ アーキテクチャに関する質問であり、C++ を全体的に遅くする方法に関する質問ではないことに注意してください。

ベストアンサー1

重要な背景情報:アグナー・フォグのマイクロアーチ pdf、そしておそらくウルリッヒ・ドレッパーのすべてのプログラマがメモリについて知っておくべきこと. その他のリンクもご覧くださいタグウィキ、特にインテルの最適化マニュアルとデビッド・カンターのHaswellマイクロアーキテクチャの分析（図付き）。

とてもクールな課題です。私が今まで見たものよりずっと良いです。学生たちはいくつかのコードを最適化するよう求められた。gcc -O0、実際のコードでは重要ではないたくさんのトリックを学びます。この場合、CPU パイプラインについて学び、それを使用して最適化解除の取り組みを導くように求められます。盲目的な推測ではありません。この場合の最も楽しい部分は、意図的な悪意ではなく、「極悪非道な無能さ」で各悲観論を正当化することです。

割り当ての文言とコードに関する問題:

このコードの uarch 固有のオプションは限られています。配列は使用されず、コストの多くはexp/logライブラリ関数の呼び出しです。命令レベルの並列性を高めるまたは低下させる明確な方法はなく、ループで運ばれる依存関係チェーンは非常に短いです。

依存関係を変更して式を並べ替えるだけで速度を低下させることは難しいでしょう。国際光危険から。

Intel SandybridgeファミリーCPUは、並列性を見つけ、問題となる危険性（依存関係）を回避するために多くのトランジスタと電力を費やす積極的なアウトオブオーダー設計です。典型的なRISCインオーダーパイプライン通常、速度を低下させる唯一の従来の危険は、レイテンシによってスループットが制限される RAW の「真の」依存関係です。

WARとWAWの危険レジスタの名前変更のおかげで、レジスタの削除はほとんど問題になりません。（popcnt/ lzcnt/は例外でtzcnt、Intel CPUへの誤った依存（書き込み専用であるはずなのに）。

メモリの順序付けには、現代のCPUはバッファを保存してキャッシュへのコミットをリタイアするまで遅らせ、WARとWAWの危険も回避する参照この答えストア バッファとは何か、そして OoO exec にとって実行を他のコアから見えるものから切り離すために不可欠であるかどうかについて説明します。

Agner の命令テーブルとは異なり、Haswell では mulss が 3 サイクルしかかからないのはなぜですか? (複数のアキュムレータを持つ FP ループの展開)レジスタ名の変更と FP ドット積ループでの FMA レイテンシの非表示について詳しく説明します。

「i7」というブランド名はNehalem（Core2の後継機）で導入され、一部のIntelのマニュアルではNehalemを意味しているように見えるのにCore i7と書かれていることさえあるが、「i7」というブランド名はそのまま残されている。サンディブリッジそしてその後のマイクロアーキテクチャ。SnBはP6ファミリーが新しい種であるSnBファミリーに進化したときである。多くの点で、Nehalem は Sandybridge よりも Pentium III と共通点が多いです (たとえば、レジ​​スタ読み取りストール (ROB 読み取りストールとも呼ばれる) は SnB では発生しません。これは、物理レジスタ ファイルを使用するように変更されたためです。また、uop キャッシュと異なる内部 uop 形式もあります)。「i7 アーキテクチャ」という用語は役に立ちません。なぜなら、SnB ファミリを Nehalem とグループ化して Core2 とグループ化しないことにはほとんど意味がないからです (ただし、Nehalem は複数のコアを接続するための共有包括的 L3 キャッシュ アーキテクチャを導入しました。また、統合 GPU も導入しました。したがって、チップ レベルでは、命名の方が理にかなっています)。

悪魔的な無能さが正当化できる良いアイデアの要約

極悪非道な人でも、明らかに無駄な作業や無限ループを追加する可能性は低く、C++/Boost クラスを混乱させることは課題の範囲を超えています。

  • 単一の共有 ループ カウンターを備えたマルチスレッドなのでstd::atomic<uint64_t>、反復の合計回数が正しく実行されます。アトミック uint64_t は特に では悪くなります-m32 -march=i586。ボーナス ポイントを得るには、位置がずれるように調整し、不均等な分割 (4:4 ではない) でページ境界を越えるようにします。
  • その他の非アトミック変数の偽共有-> メモリ順序の誤った推測パイプラインがクリアされ、追加のキャッシュミスも発生します。
  • FP 変数を使用する代わりに-、上位バイトと 0x80 を XOR して符号ビットを反転し、ストア転送を停止させます。
  • 各反復を個別に計測します。これには、 . RDTSCeg CPUID/RDTSCまたはシステム コールを実行する時間関数よりもさらに重いものを使用します。シリアル化命令は、本質的にパイプラインに適していません。
  • 定数による乗算をその逆数による除算に変更します (「読みやすくするため」)。divは遅く、完全にパイプライン化されていません。
  • vzeroupperAVX (SIMD) を使用して乗算/平方根をベクトル化しますが、スカラー数学ライブラリexp()とlog()関数への呼び出しの前に使用できないため、 AVX<->SSE 遷移が停止します。
  • RNG 出力をリンク リストに保存するか、順序に関係なく走査する配列に保存します。各反復の結果も同様に行い、最後に合計します。

また、この回答で取り上げられているが、要約からは除外されているもの: パイプライン化されていない CPU で同様に遅くなる提案、または極悪非道な無能さをもってしても正当化できないと思われる提案。たとえば、明らかに異なる/より悪い asm を生成する多くの gimp-the-compiler のアイデアなど。

マルチスレッドが下手

おそらく、OpenMP を使用して、非常に少ない反復でループをマルチスレッド化しますが、速度の向上よりもオーバーヘッドの方がはるかに大きくなります。ただし、モンテカルロ コードには、特に各反復を遅くすることに成功した場合は、実際に速度を向上させるのに十分な並列性があります。(各スレッドは部分 を計算しpayoff_sum、最後に追加されます)。#omp parallelそのループでの は、おそらく最適化であり、悲観的ではありません。

マルチスレッドですが、両方のスレッドが同じループカウンタを共有するように強制します（atomic反復の合計回数が正しいように増分します）。staticこれは非常に論理的です。これは変数をループカウンタとして使用することを意味します。これによりatomic、forループカウンタの使用が正当化され、実際のキャッシュライン ピンポン(スレッドがハイパースレッディングを使用して同じ物理コアで実行されない限り、それほど遅くならない可能性があります)。いずれにせよ、これはまたはの競合のないケースよりもはるかに遅くなります。また、 32 ビット システムで競合をアトミックに増分するには、ハードウェアにアトミック を調停させるのではなく、ループで再試行する必要があります。lock xaddlock declock cmpxchg8buint64_tinc

また、複数のスレッドがプライベート データ (RNG 状態など) を同じキャッシュ ラインの異なるバイトに保持する、偽の共有も作成します。(パフォーマンス カウンターの確認を含む、Intel のチュートリアル)これにはマイクロアーキテクチャ特有の側面があります。Intel CPUはメモリの順序ミスが発生しないことを想定しており、少なくとも P4 では、これを検出するためのメモリ順序マシンクリアパフォーマンスイベントペナルティはHaswellではそれほど大きくないかもしれません。そのリンクが指摘しているように、locked命令はこれが起こることを想定して、誤った推測を回避します。通常のロードは、ロードが実行されてからプログラム順序でリタイアするまでの間に他のコアがキャッシュラインを無効にしないと推測します（使用しない限りpause)。edlock命令のない真の共有は通常バグです。非アトミック共有ループ カウンターをアトミックの場合と比較すると興味深いでしょう。本当に悲観的にするには、共有アトミック ループ カウンターを維持し、他の変数に対して同じまたは異なるキャッシュ ラインで偽の共有を引き起こします。

ランダムな uarch 固有のアイデア:

予測できない分岐を導入すると、コードが大幅に悲観的になります。最新の x86 CPU のパイプラインは非常に長いため、予測ミスには約 15 サイクルかかります (uop キャッシュから実行する場合)。

依存関係チェーン:

これは課題の意図された部分の一つだったと思います。

複数の短い依存関係チェーンではなく 1 つの長い依存関係チェーンを持つ操作の順序を選択することで、命令レベルの並列処理を活用する CPU の能力を無効にします。 を使用しない限り、コンパイラは FP 計算の操作順序を変更できません。-ffast-mathこれは、 によって結果が変わる可能性があるためです (以下で説明します)。

これを本当に効果的にするには、ループで運ばれる依存関係チェーンの長さを増やします。しかし、これほど明白なことはありません。記述されたループには、非常に短いループで運ばれる依存関係チェーンがあります。FP 追加だけです。(3 サイクル)。複数の反復では、前の反復の終了よりかなり前に計算を開始できるため、一度に実行中の計算を実行できます。payoff_sum +=(多くの命令が必要ですが、log()expHaswell の並列処理を見つけるためのアウトオブオーダー ウィンドウ: ROB サイズ = 192 融合ドメイン uop、スケジューラ サイズ = 60 非融合ドメイン uop現在の反復の実行が十分に進み、次の反復からの命令を発行する余地ができるとすぐに、入力の準備ができている部分 (つまり、独立した/別の依存関係チェーン) は、古い命令によって実行ユニットが空いたときに実行を開始できます (たとえば、スループットではなくレイテンシでボトルネックになっているため)。

RNG 状態は、 よりも長いループ伝達依存関係チェーンになることはほぼ確実ですaddps。

より遅い/より多くの FP 演算 (特により多くの除算) を使用します。

0.5 を掛ける代わりに 2.0 で割る、などです。FP 乗算は Intel 設計で高度にパイプライン化されており、Haswell 以降では 0.5c のスループットにつき 1 つの処理があります。FP /divsdはdivpd部分的にのみパイプライン化されています。(ただし、Skylake は に対して 4c のスループットにつき 1 つの優れた処理がありdivpd xmm、レイテンシは 13～14c ですが、Nehalem (7～22c) ではまったくパイプライン化されていません)。

はdo { ...; euclid_sq = x*x + y*y; } while (euclid_sq >= 1.0);明らかに距離をテストしているので、明らかにそれが適切でしょうsqrt()。:P (sqrtは よりもさらに遅いですdiv)。

-ffast-math@Paul Clayton が示唆しているように、結合的/分配的等価性を持つ式を書き直すと、より多くの作業が必要になる可能性があります (コンパイラが再最適化できるように を使用しない限り)。(exp(T*(r-0.5*v*v))は になる可能性がありますexp(T*r - T*v*v/2.0)。実数の計算は結合的ですが、浮動小数点演算はオーバーフロー/NaNを考慮しなくても（これが-ffast-mathデフォルトでオンになっていない理由です）。ポールのコメント非常に複雑なネストされたpow()提案です。

計算を非常に小さな数値にスケールダウンできる場合、2 つの正規数の演算で非正規化数が生成されるときに、FP 数学演算でマイクロコードにトラップするのに約 120 サイクル余分にかかります。正確な数値と詳細については、Agner Fog の microarch pdf を参照してください。乗算が多数あるため、スケール係数が 2 乗されて 0.0 までアンダーフローするため、これは起こりそうにありません。必要なスケーリングを無能 (極悪非道でさえ) で正当化する方法は見当たりません。意図的な悪意があるだけです。

<immintrin.h>###組み込み関数（ ）を使用できる場合

movntiキャッシュからデータを削除するために使用します. 悪魔的: これは新しく、順序が弱いため、CPU はより高速に実行できるはずですよね? または、リンクされた質問を参照して、誰かがまさにこれを実行する危険があったケースを確認してください (一部の場所だけがホットな分散書き込みの場合)。clflush悪意がなければおそらく不可能です。

バイパス遅延を発生させるには、FP 数学演算間で整数シャッフルを使用します。

SSEとAVX命令を適切に使用せずに混在させると、vzeroupperSkylake以前のバージョンでは大きなストールが発生します。（そして別の罰則スカイレイク）。それがなくても、下手にベクトル化するとスカラーよりも悪くなる可能性があります (256 ビット ベクトルで 4 回のモンテ カルロ反復の add/sub/mul/div/sqrt 演算を一度に実行することによって節約されるサイクル数よりも、ベクトルへのデータのシャッフルやベクトルからのデータのシャッフルに費やされるサイクル数が多くなります)。add/sub/mul 実行ユニットは完全にパイプライン化され、フル幅ですが、256 ビット ベクトルの div と sqrt は 128 ビット ベクトル (またはスカラー) ほど高速ではないため、 では劇的な高速化は見られませんdouble。

exp()ハードウェア サポートがないためlog()、その部分ではベクトル要素をスカラーに抽出し、ライブラリ関数を個別に呼び出し、結果をベクトルに戻す必要があります。libm は通常、SSE2 のみを使用するようにコンパイルされるため、スカラー数学命令のレガシー SSE エンコーディングを使用します。コードが 256b ベクトルを使用し、最初にexp実行せずに呼び出すと、停止します。戻った後、次のベクトル要素を引数として設定するvzeroupperなどの AVX-128 命令も停止します。そして、SSE 命令を実行すると再び停止します。これがまさに起こったことです。vmovsdexpexp()この質問では10 倍の速度低下を引き起こします。 (@ZBoson に感謝します)。

参照Nathan Kurz による Intel の数学ライブラリと glibc のこのコードの比較実験将来のglibcにはexp()などのベクトル化された実装。

IvB以前、特にNehalemをターゲットにしている場合は、16ビットまたは8ビット操作の後に32ビットまたは64ビット操作が続く場合にgccで部分レジスタストールが発生するようにしてください。ほとんどの場合、gccはmovzx8ビットまたは16ビット操作の後に使用しますが、ahこれはgccが変更して読み取るケースですax

(インライン)アセンブリを使用する場合:

(インライン) asm を使用すると、uop キャッシュが壊れる可能性があります。3 つの 6uop キャッシュ ラインに収まらない 32B のコード チャンクは、uop キャッシュからデコーダーへの切り替えを強制します。内側のループ内の分岐ターゲットで、 2、3 の long の代わりにALIGN多くの single-byte を使用する無能な (NASM のデフォルトのような)方法は、うまくいくかもしれません。または、アラインメント パディングをラベルの前ではなく後に配置します。:P これは、フロントエンドがボトルネックになっている場合にのみ重要であり、残りのコードを悲観的にすることに成功すれば、ボトルネックにはなりません。nopnop

自己修正コードを使用して、パイプライン クリア (マシン ニュークとも呼ばれます) をトリガーします。

LCPの失速16 ビット命令で、即値が 8 ビットに収まらないほど大きい命令は、役に立たない可能性があります。SnB 以降の uop キャッシュでは、デコード ペナルティは 1 回だけ発生します。Nehalem (最初の i7) では、28 uop ループ バッファに収まらないループでも機能する可能性があります。gcc は、-mtune=intel32 ビット命令を使用できる場合でも、このような命令を生成することがあります。

タイミングの一般的な慣用句はCPUID（シリアル化して）RDTSC. 各反復を / で個別に計測して、CPUID以前RDTSCのRDTSC命令と順序が入れ替わらないようにします。順序が入れ替わると、処理速度が大幅に低下します。 (実際には、各反復を個別に計測して合計するのではなく、すべての反復をまとめて計測するのが賢い方法です)。

キャッシュミスやその他のメモリの速度低下が多発する

union { double d; char a[8]; }いくつかの変数にはを使用します。店舗転送の停止を引き起こすバイトの 1 つだけに狭いストア (または読み取り、変更、書き込み) を行うことによって実現します (この wiki の記事では、ロード/ストア キューに関する他の多くのマイクロアーキテクチャについても説明しています)。たとえば、演算子ではなく、上位バイト のみで XOR 0x80 を使用しての符号を反転しますdouble-。極悪非道な開発者は、FP は整数よりも遅いと聞いて、整数演算を使用してできる限りのことを行おうとするかもしれません。(コンパイラは理論的には、 のxorpsような定数を使用してこれを にコンパイルすることもできます-が、x87 の場合、コンパイラは値を否定していることを認識するか、fchs次の加算を減算に置き換える必要があります。)

を使ってコンパイルしていて を使っていないvolatile場合に、コンパイラに実際にあらゆる場所への保存/再読み込みを強制するためにを使用します。グローバル変数（ローカル変数の代わりに）もいくつかの保存/再読み込みを強制しますが、-O3std::atomicC++ メモリモデルの弱い順序付けコンパイラが常にメモリに書き込んだり再ロードしたりする必要はありません。

ローカル変数を大きな構造体のメンバーに置き換えて、メモリ レイアウトを制御できるようにします。

パディングのために構造体内の配列を使用します (また、その存在を正当化するために乱数を格納します)。

メモリレイアウトを選択してすべてがL1キャッシュ内の同じ「セット」内の異なる行に格納されます。8 ウェイ アソシエイティブのみです。つまり、各セットには 8 つの「ウェイ」があります。キャッシュ ラインは 64B です。

さらに良いのは、正確に4096B離して配置することです。なぜなら、ロードは、ページ内の同じオフセットを持つ異なるページへのストアに誤った依存関係を持つからです。積極的なアウトオブオーダーCPUは、結果を変えずにロードとストアを並べ替えることができるタイミングを判断するためのメモリの曖昧さ解消、そしてIntelの実装には誤検知があり、ロードが早く開始されるのを妨げます。おそらく、TLBが仮想ページから物理ページへ上位ビットを変換する前に開始できるように、ページオフセット以下のビットのみをチェックしているのでしょう。Agnerのガイドと同様に、この答え、および同じ質問に対する @Krazy Glew の回答の最後のほうのセクション。(Andy Glew は、Intel の PPro - P6 マイクロアーキテクチャの設計者でした。) (関連:https://stackoverflow.com/a/53330296そしてhttps://github.com/travisdowns/uarch-bench/wiki/Skylake のメモリ曖昧性解消）

__attribute__((packed))変数をミスアラインして、キャッシュ ラインまたはページ境界にまたがるようにするために使用します。(つまり、1 つのロードdoubleには 2 つのキャッシュ ラインからのデータが必要です)。キャッシュ ラインとページ ラインをまたぐ場合を除き、どの Intel i7 uarch でも、ミスアライン ロードによるペナルティはありません。キャッシュライン分割には依然として余分なサイクルがかかるSkylakeはページ分割読み込みのペナルティを大幅に削減します。100サイクルから5サイクルへ。（セクション2.1.3）（2 つのページウォークを並行して実行できます）。

のページ分割は、atomic<uint64_t>特に 1 つのページに 5 バイト、もう 1 つのページに 3 バイトの場合、または 4:4 以外の場合は、ほぼ最悪のケースになります。一部の uarch では、16B ベクトルのキャッシュ ライン分割では、真ん中での分割でもより効率的です (IIRC)。RNG 結果を格納する配列を含め、すべてを に配置します (もちろん、スペースを節約するため)。カウンターの前にまたはalignas(4096) struct __attribute((packed))を使用して、不整合を実現します。uint8_tuint16_t

コンパイラにインデックスアドレッシングモードを使用させることができれば、uopマイクロフュージョンを倒すおそらく、#defines を使用して単純なスカラー変数を に置き換えることによってmy_data[constant]。

間接レベルをさらに追加して、ロード/ストア アドレスが早期にわからないようにすると、状況はさらに悪化する可能性があります。

配列を非連続な順序で走査する

そもそも配列を導入する理由としては、乱数生成と乱数使用を分離できるという、無能な言い訳が考えられます。また、各反復の結果を配列に格納して、後で合計することもできます (さらに悪質な無能さで)。

「最大のランダム性」を得るには、スレッドをランダム配列にループさせて、そこに新しいランダムな数値を書き込むことができます。 ランダムな数値を消費するスレッドは、ランダムな数値をロードするためのランダムなインデックスを生成できます。 (ここでは多少の手間がかかりますが、マイクロアーキテクチャ的には、ロード アドレスが早期にわかるため、ロードされたデータが必要になる前に、起こり得るロード遅延を解決できます。) リーダーとライターを異なるコアに配置すると、メモリ順序付けの誤った推測パイプラインがクリアされます (前述の偽共有のケースで説明したように)。

最大限の悲観化を行うには、4096バイト（つまり512個のdouble）のストライドで配列をループします。例：

for (int i=0 ; i<512; i++)
    for (int j=i ; j<UPPER_BOUND ; j+=512)
        monte_carlo_step(rng_array[j]);

したがって、アクセス パターンは 0、4096、8192、...、
8、4104、8200、...
16、4112、8208、...となります。

これは、2D 配列に間違った順序でアクセスした場合に発生する結果ですdouble rng_array[MAX_ROWS][512](@JesperJuhl の提案どおり、内部ループで行内の列ではなく行をループします)。極悪非道な無能さがこのような次元の 2D 配列を正当化できるのであれば、現実世界のありふれた無能さが間違ったアクセス パターンでのループを簡単に正当化します。これは現実世界の実際のコードで発生します。

配列がそれほど大きくない場合は、同じページを再利用するのではなく、必要に応じてループ境界を調整して、多くの異なるページを使用します。ハードウェア プリフェッチは、ページ間では (まったく) 機能しません。プリフェッチャーは、各ページ内で 1 つの前方ストリームと 1 つの後方ストリームを追跡できます (ここで行われているのはこれです)。ただし、メモリ帯域幅が非プリフェッチで飽和していない場合にのみ動作します。

ページが巨大ページにマージされない限り、多くのTLBミスも発生します（mallocLinuxは、 /newのような匿名の（ファイルベースではない）割り当てに対してこれを都合よく行います。mmap(MAP_ANONYMOUS)）。

結果のリストを格納する配列の代わりに、リンク リスト を使用できます。すべての反復処理で、ポインタ追跡ロードが必要になります (次のロードのロード アドレスに対する RAW の真の依存関係ハザード)。不良なアロケータを使用すると、リスト ノードをメモリ内に分散させ、キャッシュを無効にする可能性があります。不良なおもちゃのアロケータを使用すると、すべてのノードを独自のページの先頭に配置する可能性があります (たとえば、mmap(MAP_ANONYMOUS)ページを分割したり、オブジェクト サイズを追跡したりせずに、 を直接割り当てて、 を適切にサポートしますfree)。

これらは実際にはマイクロアーキテクチャ固有のものではなく、パイプラインとはほとんど関係がありません (これらのほとんどは、パイプライン化されていない CPU でも速度低下の原因になります)。

少し話がそれますが、コンパイラーに悪いコードを生成させたり、より多くの作業を行わせたりします。

最も悲惨なコードにはC++11 を使用してください。MFENCE と ed 命令はstd::atomic<int>、別のスレッドとの競合がなくてもかなり遅くなります。std::atomic<double>lock

-m32x87 コードは SSE2 コードよりも劣るため、より遅いコードになります。スタックベースの 32 ビット呼び出し規約では、より多くの命令が必要になり、スタック上の FP 引数さえも などの関数に渡されますexp()。atomic<uint64_t>::operator++オンにはループ-m32が必要ですlock cmpxchg8B(i586) (ループ カウンターにはこれを使用してください。[悪魔のような笑い])。

-march=i386も悲観的になります (@Jesper さん、ありがとうございます)。 FP との比較はfcom686 よりも遅くなりますfcomi。 586 より前では、アトミックな 64 ビット ストア (cmpxchg は言うまでもありません) が提供されていないため、すべての 64 ビットatomic操作は libgcc 関数呼び出しにコンパイルされます (これはおそらく、実際にロックを使用するのではなく、i686 用にコンパイルされています)。 最後の段落の Godbolt Compiler Explorer リンクで試してみてください。

sizeof( ) が 10 または 16 (アライメント用のパディングを含む)である ABI で、精度と速度をさらに高めるためにlong double/ sqrtl/を使用します。(記憶が正しければ、64 ビット Windows はに相当する8 バイトを使用します。(いずれにしても、10 バイト (80 ビット) FP オペランドのロード/ストアは 4 / 7 uops であるのに対し、または では/に対してそれぞれ 1 uops しかかかりません)。x87 を で強制すると、gcc の場合でも自動ベクトル化が無効になります。expllong doublelong doubledoublefloatdoublefld m64/m32fstlong double-m64 -march=haswell -O3

atomic<uint64_t>ループ カウンターを使用しない場合は、long doubleループ カウンターを含むすべてに を使用します。

atomic<double>コンパイルはできますが、読み取り、変更、書き込みなどの操作は+=サポートされていません（64ビットでも）。atomic<long double>アトミックロード/ストア専用のライブラリ関数を呼び出す必要があります。おそらく非常に非効率的です。x86 ISAは10バイトのアトミックロード/ストアを自然にサポートしていないため、ロック ( ) なしで考えられる唯一の方法は、cmpxchg16b64 ビット モードを必要とすることです。

では-O0、大きな式の一部を一時変数に割り当てることで分割すると、保存/再読み込みがさらに発生します。volatileまたは がなければ、実際のコードの実際のビルドで使用される最適化設定では、これは問題になりません。

C のエイリアス規則では、 はchar何でもエイリアスできるため、 を介して保存するとchar*、 であっても、バイトストアの前/後のすべてを保存/再ロードするようにコンパイラに強制します-O3。(これは自動ベクトル化の問題です。配列を操作するコードuint8_t、 例えば。）

ループ カウンターを試してuint16_t、16 ビットのオペランド サイズ (潜在的なストール) や追加のmovzx命令 (安全) を使用することで、16 ビットへの切り捨てを強制します。符号付きオーバーフローは未定義の動作です、または-fwrapv少なくともを使用しない限り-fno-strict-overflow、符号付きループカウンタは反復ごとに再符号拡張する必要がない64 ビット ポインタへのオフセットとして使用される場合でも同様です。

整数から整数への変換とfloatその逆の変換を強制します。および/またはdouble<=>float変換。命令のレイテンシは 1 を超えており、スカラー int->float ( cvtsi2ss) は xmm レジスタの残りの部分をゼロにしないように設計が間違っています。(pxorこのため、gcc は依存関係を壊すために余分なものを挿入します。)

頻繁にCPU アフィニティを別の CPU に設定します(@Egwor の提案)。 悪質な推論: スレッドを長時間実行することで 1 つのコアが過熱するのは避けたいですよね? 別のコアにスワップすると、そのコアのクロック速度が急上昇する可能性があります。 (実際には、コア同士は熱的に非常に近いため、マルチソケット システム以外では、これはほとんどあり得ません)。 今度は、チューニングを間違えて、頻繁にやりすぎます。 OS がスレッド状態を保存/復元するのにかかる時間以外に、新しいコアにはコールド L2/L1 キャッシュ、uop キャッシュ、および分岐予測子があります。

頻繁に不要なシステム コールを導入すると、それが何であれ、速度が低下する可能性があります。ただし、 などの重要だが単純なシステム コールはgettimeofday、カーネル モードに移行せずにユーザー空間で実装できます (Linux の glibc はカーネルの助けを借りてこれを実行します。カーネルは VDSO でコードとデータをエクスポートします)。

システムコールのオーバーヘッド（コンテキストスイッチ自体だけでなく、ユーザー空間に戻った後のキャッシュ/TLBミスを含む）の詳細については、FlexSC ペーパー現在の状況に関する優れたパフォーマンス カウンター分析と、大規模なマルチスレッド サーバー プロセスからのシステム コールをバッチ処理するための提案が含まれています。

おすすめ記事