質問

この1週間、この課題を完成させるために頭を悩ませています。どなたか正しい道を示してくれることを期待しています。まず、講師の指示から説明します。

<ブロッククオート

あなたの課題は、最初の研究室の課題とは逆で、素数プログラムを最適化することです。この課題でのあなたの目的は、プログラムを悲観的にすること、つまり、より遅く実行させることです。どちらもCPUに負荷のかかるプログラムです。私たちの研究室のPCで実行すると、数秒かかります。アルゴリズムを変更することはできません。

プログラムの最適化を解除するには、Intel i7のパイプラインがどのように動作するかについての知識を使います。WAR、RAW、その他のハザードを導入するための命令パスの並べ替えを想像してください。キャッシュの効果を最小にする方法を考える。極端に無能になれ。

課題では、WhetstoneとMonte-Carloのプログラムのどちらかを選択することになっていました。 キャッシュ効果のコメントは、ほとんどWhetstoneにしか適用できませんが、私はモンテカルロシミュレーションプログラムを選択しました。

// 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 and Pattersonの教科書を使用）。
• 研究室のコンピュータはHaswell CPUを搭載
• に触れていただきました。 CPUID 命令とキャッシュサイズの決定方法、さらに、イントリンシックと CLFLUSH 命令を使用します。
• コンパイラのオプションは何でもOKで、インラインasmもOKです。
• 平方根のアルゴリズムを自分で書くのはアウトオブ眼中と発表された

メタスレのcowmoogunさんのコメントを見ると コンパイラの最適化がこれに含まれることは明らかでなく、また、このような最適化が行われることはないと考えていました。 -O0 そして、ランタイムが17％増加するのは妥当な数字だと考えました。

つまり、既存の仕事を再整理して命令レベルの並列度を下げるとか、そういうことが課題の目的だったようですが、もっと掘り下げて勉強した人がいるのは悪いことではありませんね。

---

これはコンピュータアーキテクチャーの問題であって、C++を一般に遅くする方法についての問題ではないことに留意してください。

どのように解決するのですか？

重要な背景を読み解く。 アグナー・フォッグのマイクロアークpdf と、おそらくUlrich Drepperの プログラマが知っておくべきメモリについて . の他のリンクも参照してください。 x86 タグの wiki、特に Intel の最適化マニュアル、そして David Kanter の Haswellマイクロアーキテクチャの分析、図解付き .

とてもクールな課題です。 のコードを最適化するように言われました。 gcc -O0 実際のコードでは重要でないトリックの束を学ぶことです。 この場合、あなたはCPUパイプラインについて学び、それを使って最適化解除を行うよう求められているのであって、ただやみくもに推測するのではなく、そのための指針を得ることが重要です。 この作品の最も楽しいところは、それぞれのペシミゼーションを、意図的な悪意ではなく、"極悪非道な無能さ"で正当化することです。

---

課題の文言やコードに問題がある :

このコードのuarch固有のオプションは限られています。 このコードでは配列を一切使用しておらず、コストの多くは exp / log ライブラリ関数です。 命令レベルの並列性を多かれ少なかれ持つ明白な方法はなく、ループを運ぶ依存関係の連鎖は非常に短いです。

依存関係を変更するために式を並べ替えただけで、速度が低下するのは難しいでしょう。 ILP ハザードから

Intel SandybridgeファミリーのCPUは、積極的なアウトオブオーダー設計で、多くのトランジスタと電力を使って並列性を見つけ、問題を引き起こすハザード（依存関係）を回避しています。 古典的なRISCのインオーダーパイプライン . 通常、処理速度を低下させる従来の問題は、レイテンシーによってスループットが制限されるRAW "true"依存関係だけです。

WARとWAWのハザード レジスタのリネームのおかげで、レジスタの問題はほとんどありません。 . (を除く popcnt / lzcnt / tzcnt を持つ。 インテル® CPU の場合、行き先は偽の依存性 書き込み専用であるべきなのに）。

メモリの順序付けのために、最近のCPUは ストアバッファを使用することで、キャッシュへのコミットを引退まで遅らせ、WARやWAWの危険も回避することができます。 . 参照 この回答 ストアバッファとは何か、そして OoO exec が他のコアから見えるものから実行を切り離すために必要不可欠であることについて。

Haswellでmulssが3サイクルしかかからないのはなぜか、Agnerの命令表と違うのか？(複数のアキュムレータを持つFPループのアンロール) は、FPドットプロダクトループにおけるレジスタ名の変更とFMAレイテンシの隠蔽について、より詳しく説明しています。

---

Nehalem（Core2の後継）で導入されたi7ブランド インテルのマニュアルには、Nehalemのことだと思われるのにCore i7と書かれているものもありますが、"i7"のブランドは維持されています。 サンディブリッジ用 というマイクロアーキテクチャがあります。 SnBはP6ファミリーがSnBファミリーという新種に進化したとき . 多くの点で、NehalemはSandybridgeよりもPentium IIIと共通しています（例えば、SnBでは物理レジスタファイルの使用に変更したため、レジスタリードストール、別名ROB-リードストールは起こりません）。 また、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 し、符号ビットを反転させます。 ストアフォワードのストール .
• よりもさらに重いものを使って、各反復を個別に時間設定します。 RDTSC .例えば CPUID / RDTSC またはシステムコールを行う時間関数です。 シリアライズ命令は、本質的にパイプラインに馴染まない。
• 定数による乗算をその逆数による除算に変更（"読みやすくするため")。 div は遅いし、完全にパイプライン化されていません。
• AVX (SIMD) で乗算/平方根をベクトル化するが、失敗する。 vzeroupper スカラー数学ライブラリの呼び出しの前に exp() と log() 関数を使用しているため AVX<->SSE遷移の失速 .
• RNGの出力をリンクリスト、または順不同にトラバースする配列に格納します。 各反復の結果も同じで、最後に合計を出します。

例えば、明らかに異なる/より悪いasmを生成する多くのgimp-the-compilerのアイデアなどです。

---

マルチスレッド不良

反復回数が非常に少ないループをマルチスレッド化するためにOpenMPを使用すると、速度向上よりもはるかに多くのオーバーヘッドが発生する可能性があります。 モンテカルロコードには十分な並列性があるので、特に各反復を遅くすることに成功すれば、実際に速度が上がります。 各スレッドは部分的に計算します。 payoff_sum 最後に追加されます）。 #omp parallel このループは、おそらく最適化であり、悲観化ではないでしょう。

マルチスレッドだが、両方のスレッドが同じループカウンターを共有するように強制される ( atomic をインクリメントし、反復の総数が正しくなるようにします)。 これは極悪非道な論理としか思えない。 これはつまり static 変数をループカウンタとして使用します。 これによって atomic をループカウンタに使用し、実際の キャッシュラインのピンポン (スレッドがハイパースレッディングで同じ物理コアで実行されない限り、それはないでしょう。 として が遅い)。 とにかく、これは 大いに を争わない場合よりも遅い。 lock inc . そして lock cmpxchg8b をアトミックにインクリメントすることで、コンテニューの uint64_t 32bit システムの場合、ハードウェアがアトミックな inc .

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

---

uarch特有のランダムなアイデア。

を導入することができれば 予測不可能な分岐 そうすると、コードが大幅に劣化します。 最近のx86CPUはかなり長いパイプラインを持っているので、予測ミスは15サイクル程度になります（uopキャッシュから実行した場合）。

---

ディペンデンシーチェーン

これは課題の意図した部分の1つだと思います。

複数の短い依存関係の鎖ではなく、1つの長い依存関係の鎖を持つ演算順序を選択することによって、CPUが命令レベルの並列性を利用する能力を打ち破れ。 コンパイラは、FP計算の演算順序を変更することを許されていません。 -ffast-math というのも、後述するように結果が変わってしまうことがあるからです。

これを本当に効果的にするためには、ループで運ばれる依存関係の鎖の長さを長くすることです。 しかし、何も明らかなことはありません。 このループは、ループキャリーディペンデントチェーンが非常に短く、FPアドだけです。(3サイクル)。 複数のイテレーションが一度に飛行中の計算を行うことができます。 payoff_sum += を前のイテレーションの終了時に設定します。 ( log() と exp は多くのインストラクションを必要としますが Haswellの並列性を見つけるためのアウトオブオーダーの窓。ROBサイズ=192 fused-domain uops、スケジューラサイズ=60 unfused-domain uops。 . 現在のイテレーションの実行が、次のイテレーションからの命令を発行するためのスペースを作るのに十分なほど進むとすぐに、その入力が準備できた部分（つまり独立/分離したデップチェーン）は、古い命令が実行ユニットを空けたときに実行を開始できる（例えば、スループットではなくレイテンシーがボトルネックになっているからである）。

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() です。 sqrt よりもさらに遅いです。 div ).

Paul Clayton が提案するように、式を連想/分配等価で書き直すと、より多くの作業を導入することができます。 -ffast-math でコンパイラが再最適化できるようにします)。 (exp(T*(r-0.5*v*v)) になる可能性があります。 exp(T*r - T*v*v/2.0) . 実数の計算が連想的であるのに対して、実数の計算が連想的であることに注意してください。 浮動小数点演算は ではない は、オーバーフロー/NaN を考慮しなくても、（そのために -ffast-math はデフォルトでオンになっていない)。 参照 ポールのコメント は、非常に毛深いネストされた pow() を提案します。

もし、計算を非常に小さな数字にスケールダウンできるのであれば、FPの計算オプは取る 2 つの正常な数値に対する演算が非正規の数値を生成する場合、マイクロコードにトラップするために ~120サイクルの余分なサイクルが発生します。 . 正確な数値と詳細はAgner Fogのmicroarchのpdfを参照してください。 乗算が多いので、スケールファクターが2乗になり、0.0までずっとアンダーフローするので、これはありえないことです。 必要なスケーリングを無能(極悪でも)で正当化する方法はなく、意図的な悪意しかないと思います。

---

### イントリンシックが使えるなら ( <immintrin.h> )

使用方法 movnti キャッシュからデータを退避させる . 極悪非道：新しいし、弱順序だから、その分CPUが速く動くはずでしょう？ あるいは、誰かがまさにこれを行う危険にさらされていたケースについて、リンク先の質問を参照してください（一部の場所だけがホットである散在した書き込みの場合）。 clflush は悪意がないと無理でしょう。

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

を適切に使用せずにSSE命令とAVX命令を混在させた場合 vzeroupper は、Skylake 以前のバージョンで大きな失速を引き起こします。 (また、別のペナルティ Skylakeの場合 ). それでなくとも、ベクトル化はスカラより悪いことがあります（256bベクトルで4つのモンテカルロ反復の加算/減算/剰余演算を一度に行うことで節約できるサイクルよりも、ベクトルへのデータのシャッフル/出力に費やすサイクルの方が多い）。加算/減算/剰余演算実行ユニットはフルパイプラインでフル幅ですが、256bベクトルのdivおよびsqrtは128bベクター（あるいはスカラ）の場合と同様に速くならないため、高速化しても double .

exp() と log() libm は通常 SSE2 を使用するようにコンパイルされているため、スカラ演算命令にはレガシー SSE エンコーディングが使用されます。 もし、あなたのコードが 256b ベクタを使用し、かつ exp を行わずに vzeroupper を実行すると、失速してしまいます。 復帰後、AVX-128のような命令で vmovsd のArgとして次のベクター要素を設定します。 exp も失速します。 そして exp() は、SSE 命令を実行すると、再び失速します。 これはまさにその通りです この質問では 10倍の速度低下を引き起こした。 (@ZBoson さんありがとうございます)。

こちらもご覧ください Nathan Kurz が Intel の math lib と glibc を使ってこのコードを実験しています。 . 将来のglibcには のベクトル化された実装です。 exp() などがあります。

---

もしIvB以前、特にNehalemをターゲットにしているなら、16ビットまたは8ビット操作の後に32ビットまたは64ビット操作を行うと、gccが部分レジスタストールを引き起こすようにしてみてください。 ほとんどの場合、gccは movzx は、8ビットまたは16ビット演算の後、しかし ここでは、gcc が ah を読み、その後 ax

---

(インライン)アスムで。

(インライン)asmでは、uopキャッシュが壊れる可能性があります。6uop キャッシュ 3 行に収まらない 32B のコードの塊は、uop キャッシュからデコーダへの切り替えを余儀なくされます。 無能な ALIGN (NASMのデフォルトのように)多くのシングルバイトの nop の代わりに、2つの長い nop をインナーループ内のブランチターゲットに配置することで、うまくいくかもしれません。 これはフロントエンドがボトルネックになっている場合のみ重要で、残りのコードを最小化することに成功すれば、そうなることはありません。

自己修正コードを使用して、パイプラインクリア（別名マシン・ニューク）をトリガーする。

LCP失速 8ビットに収まらないような大きな即値を持つ16ビット命令から、役に立つことはまずないでしょう。 SnB以降ではuopキャッシュがあるので、デコードのペナルティは1回で済みます。 Nehalem (最初のi7)では、28uopのループバッファに収まらないループに対して有効かもしれません。 -mtune=intel で、32bitの命令が使えたはずなのに。

---

タイミングを表す一般的な慣用句は CPUID (シリアライズする)なら RDTSC . 各反復を個別に時間指定し CPUID / RDTSC を確認するために RDTSC が以前の命令と一緒に並べ替えられると、動作が遅くなることがあります。 ロット . (実際のところ、賢い時間の計り方は、それぞれ別々に時間を計り、それらを合計するのではなく、すべての反復を一緒に時間を計ることです)。

---

キャッシュミスなどメモリ速度低下の原因多し

を使用します。 union { double d; char a[8]; } を変数の一部に使用します。 ストアフォワードの失速を引き起こす を行うことで、1つのバイトに対して狭い範囲での保存(またはRead-Modify-Write)を行うことができます。(このwikiの記事は、ロード/ストアキューに関する他の多くのマイクロアーキテクチャの事柄もカバーしています。) 例を挙げます。 の符号を反転させる。 double 上位バイトのXOR 0x80を使用した場合 の代わりに - 演算子を使用します。 極悪非道な開発者は、FPは整数より遅いと聞いて、できるだけ整数の演算子を使おうとするかもしれません。 (コンパイラは理論的にはまだこれを xorps のような定数で - しかし、x87 では、コンパイラは値を否定していることを認識しなければならず fchs または次の加算を減算に置き換える)。

---

使用方法 volatile でコンパイルしている場合は -O3 を使用せず std::atomic を使用すると、コンパイラが実際にあちこちに保存/再ロードすることを強制します。 グローバル変数(ローカル変数の代わりに)もまた、いくつかの保存/再ロードを強制しますが C++のメモリモデルの弱点である順序付け は、コンパイラが常にメモリにスピル/リロードすることを要求しません。

ローカルバーを大きな構造体のメンバーに置き換えることで、メモリレイアウトを制御することができます。

構造体内の配列をパディングに使う（乱数も格納し、その存在を正当化する）。

メモリレイアウトは、以下のように選択します。 L1キャッシュの同じquot;set"にある別の行にすべて入る。 . これは8ウェイ連想方式、つまり各セットが8つの"way"を持つだけです。 キャッシュラインは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/Memory-Disambiguation-on-Skylake )

使用方法 __attribute__((packed)) を使用すると、キャッシュラインやページの境界をまたぐように変数を並べ替えることができます。 (つまり、1つの double は2つのキャッシュラインからデータを必要とします)。 Intel i7 uarch では、キャッシュラインとページラインをまたぐ場合を除き、ミスアラインドロードは何のペナルティもありません。 キャッシュラインの分割はまだ余分なサイクルを要する . Skylake では、ページ分割ロードのペナルティが劇的に減少しています。 100サイクルから5サイクルへ。(2.1.3項) . (そして、2つのページウォークを並行して行うことができます）。

のページ分割は atomic<uint64_t> は最悪の場合 特に、片方のページが5バイトでもう片方のページが3バイトとか、4:4以外の場合です。 16B ベクタのキャッシュライン分割の場合、真ん中で分割した方が効率が良い場合もあります（IRC）。 すべてを alignas(4096) struct __attribute((packed)) (もちろんスペースを節約するため）RNGの結果を保存するための配列も含めて。 位置のずれは uint8_t または uint16_t は、カウンターの前にあるものです。

もし、コンパイラにインデックスドアドレッシングモードを使わせることができれば、それは デフオップマイクロフュージョン . もしかしたら #define を使用して、単純なスカラー変数を置き換えます。 my_data[constant] .

もし、ロードストアアドレスを早期に知ることができないような、特別なレベルのインダイレクトを導入することができれば、さらに悲観的になる可能性があります。

---

配列の非連続な順序でのトラバース

そもそも配列を導入すること自体、無能な正当化が思いつくと思います。 乱数生成と乱数利用を分離することができる。 各反復の結果は配列に格納し、後で合計することもできる（もっと極悪非道な方法だが）。

最大限のランダム性を得るために、ランダム配列に新しい乱数を書き込んでループするスレッドを持つことができます。 乱数を消費するスレッドは、乱数を読み込むためのランダムインデックスを生成することができます。 (ここで若干の手間がかかりますが、マイクロアーキテクチャ上、ロードアドレスが早期にわかると、ロードされたデータが必要になる前にロードの待ち時間を解決することができます)。 リーダとライタを異なるコアに配置すると、メモリ順序の誤認識によるパイプラインクリアが発生します(偽共有については前述のとおりです)。

最大限のペシミズムを得るには、4096バイト（つまり512倍）のストライドで配列上をループします。

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, ...

このように2次元配列にアクセスすると、次のような結果が得られます。 double rng_array[MAX_ROWS][512] が提案したように、行の中の列ではなく行をループする）。 もし極悪非道な無能者がそのような次元の2次元配列を正当化できるなら、現実世界での様々な無能者は間違ったアクセスパターンでループすることを簡単に正当化できます。 これは現実のコードで実際に起こっていることです。

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

これはまた、ページがハグページにマージされない限り、多くのTLBミスを発生させることになる( Linux は、次のような匿名（ファイルバックされていない）アロケーションに対して、臨機応変にこれを行います。 malloc / new を使用すること。 mmap(MAP_ANONYMOUS) ).

結果のリストを格納する配列の代わりに リンクリスト . すべての反復は、ポインタチェイスロード（次のロードアドレスのためのRAW真の依存性ハザード）を必要とします。 悪いアロケータを使うと、リストノードをメモリ上に散らかしてしまい、キャッシュを破壊してしまうかもしれません。 悪いおもちゃのアロケータでは、すべてのノードをそれ自身のページの先頭に置くかもしれません。 (例: アロケート時に mmap(MAP_ANONYMOUS) を適切にサポートするために、ページを分割したりオブジェクトのサイズを追跡したりすることなく、直接 free ).

---

これらはマイクロアーキテクチャに特化したものではなく、パイプラインとはほとんど関係がありません（これらのほとんどは、パイプラインでないCPUでも速度が低下します）。

少しオフトピック：コンパイラがより悪いコードを生成し、より多くの仕事をするようにします。

C++11を使用する std::atomic<int> と std::atomic<double> は、最も貧弱なコードです。 MFENCEと lock 他のスレッドからの競合がない場合でも、かなり遅いです。

-m32 は、x87 のコードが SSE2 のコードより悪くなるので、より遅いコードを作ることになります。 スタックベースの 32bit 呼び出し規約はより多くの命令を必要とし、スタック上の FP 引数さえも以下のような関数に渡します。 exp() . atomic<uint64_t>::operator++ オン -m32 が必要です。 lock cmpxchg8B ループ (i586). (だからループカウンターに使え！[悪笑])。

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

使用方法 long double / sqrtl / expl を使用する ABI では、余分な精度と余分な速度が発生します。 long double ) が 10 または 16 (アライメント用のパディングを含む) である場合。 (IRCでは、64bit Windowsは8byteの long double と同等です。 double . (いずれにせよ、10byte (80bit) FPオペランドのロード/ストアは、4 / 7 uopsとなります。 float または double にはそれぞれ1uopしかかかりません。 fld m64/m32 / fst ). でx87を強制する。 long double は自動ベクトル化を無効にします。 -m64 -march=haswell -O3 .

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

atomic<double> はコンパイルされますが、以下のような読み取り-変更-書き込みの操作が可能です。 += はサポートされていません(64bitでも)。 atomic<long double> は、アトミックロード/ストアのためだけにライブラリ関数を呼び出さなければなりません。 おそらく本当に非効率的です。 なぜなら、x86 ISA はもともとアトミックな 10 バイトのロード/ストアをサポートしていないからです。 で、ロックしない方法として唯一思いつくのが ( cmpxchg16b ) には64bitモードが必要です。

---

で -O0 大きな式を分割するために、一時的な変数に部品を代入すると、保存と再読み込みが多くなります。 また volatile など、実際のコードのビルドで使われるような最適化設定では問題ないでしょう。

C言語のエイリアシングルールでは char はあらゆるもののエイリアスになるので char* であっても、コンパイラはバイトストアの前と後のすべてを保存/再読み込みすることを強制します。 -O3 . (これは、自動ベクトル化された の配列に対して操作するコードです。 uint8_t といった具合です（笑)。

試す uint16_t ループカウンタに16ビットのオペランドサイズ（ストールの可能性）を使用し、強制的に16ビットに切り詰め、さらに movzx 命令（安全）。 符号付きオーバーフローは未定義の動作 を使用しない限りは -fwrapv または最低でも -fno-strict-overflow , 符号付きループカウンターは、反復毎に再符号拡張する必要はありません。 64ビットポインタのオフセットとして使用されている場合でも、です。

---

整数値から強制的に float に戻ります。 そして、または double <=> float の変換を行います。 命令はレイテンシ> 1で、スカラint->float( cvtsi2ss ) は、xmm レジスタの残りをゼロにしないような悪い設計になっています。 (gccは余分な pxor このため、依存関係を解消するために)

---

よくあること CPUアフィニティーを別のCPUに設定する (@Egworの提案). 極悪非道な理由。スレッドを長時間動かして、1つのコアがオーバーヒートしたら困りますよね？ 他のコアにスワップすることで、そのコアをより高いクロック速度にターボさせることができるかもしれません。 (現実には、マルチソケットシステムを除いて、このようなことが起こる可能性は極めて低いのですが）。 あとはチューニングを間違え、それを頻繁に行うだけです。 OSがスレッド状態を保存/復元するのに費やす時間以外に、新しいコアにはコールドL2/L1キャッシュ、uopキャッシュ、ブランチプレディクタがあります。

不要なシステムコールを頻繁に導入すると、それが何であれ、動作が遅くなることがあります。 しかし、重要だが単純なもの、たとえば gettimeofday は、カーネルモードに移行することなく、ユーザースペースで実装することができます。 (Linuxのglibcはカーネルの助けを借りてこれを行います: カーネルはVDSOでコードとデータをエクスポートします)。

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