8

このようなおもちゃのループがあるとします

float x[N];
float y[N];
for (int i = 1; i < N-1; i++)
    y[i] = a*(x[i-1] - x[i] + x[i+1])

そして、私のキャッシュ ラインは64 バイト(つまり、十分な大きさ) であると想定しています。次に、(フレームごとに) 基本的に RAM への 2 回のアクセスと 3 つの FLOP を行います。

  • 1 (キャッシュ) 読み取りアクセス: 3 つすべてをロードx[i-1], x[i], x[i+1]
  • 1書き込みアクセス：保存y[i]
  • 3 フロップ (1 マルチ、1 アッド、1 サブ)

運用強度はエルゴ

OI = 3 フロップ/(2 * 4 バイト)

今、私がこのようなことをしたらどうなりますか

float x[N];
for (int i = 1; i < N-1; i++)
    x[i] = a*(x[i-1] - x[i] + x[i+1])

もうありませんのでご注意くださいy。単一の RAM アクセスがあるということですか。

  • 1 (キャッシュ) 読み取り/書き込み: 読み込みx[i-1], x[i], x[i+1]、保存x[i]

またはまだ 2 つの RAM アクセス

  • 1 (キャッシュ) 読み取り: 読み込み中 x[i-1], x[i], x[i+1]
  • 1 (キャッシュ) 書き込み: 保存x[i]

どちらの場合も、運用強度のOIが異なるためです。誰もこれについて何か言うことができますか? または、いくつかのことを明確にするかもしれません。ありがとう

4

1 に答える 1

3

免責事項: 今日まで、ルーフライン パフォーマンス モデルについて聞いたことがありません。私が知る限り、アルゴリズムの「算術強度」の理論的限界を計算しようとします。これは、アクセスされたデータのバイトあたりの FLOPS の数です。このような尺度は、 のサイズが大きくなるにつれて同様のアルゴリズムを比較するのNに役立ちますが、実際のパフォーマンスを予測するのにはあまり役立ちません。

一般的な経験則として、最新のプロセッサは、データをフェッチ/保存するよりもはるかに高速に命令を実行できます (データがキャッシュのサイズよりも大きくなり始めると、これは劇的に顕著になります)。したがって、予想に反して、演算強度の高いループは、演算強度の低いループよりもはるかに高速に実行される場合があります。スケーリングの際に最も重要なNのは、アクセスされるデータの総量です (これは、現在の一般的なデスクトップ システムやサーバー システムに当てはまるように、メモリがプロセッサよりも大幅に低速である限り当てはまります)。

要するに、x86 CPU は残念ながら複雑すぎて、このような単純なモデルで正確に説明することはできません。メモリへのアクセスは、RAM にアクセスする前に、キャッシングのいくつかのレイヤー (通常は L1、L2、および L3) を通過します。すべてのデータが L1 に収まる可能性があります。ループを 2 回目に実行すると、RAM アクセスがまったくない可能性があります。

データキャッシュだけではありません。コードもメモリ内にあり、命令キャッシュにロードする必要があることを忘れないでください。各読み取り/書き込みは、ハードウェア TLB によってサポートされている仮想アドレスとの間でも行われます (極端な場合、ページ フォールトがトリガーされ、OS がループの途中でディスクにページを書き込む可能性があります)。 ）。これはすべて、プログラムがハードウェアをすべて独り占めしていることを前提としています (非リアルタイム OS では、他のプロセスとスレッドが同じ限られたリソースを求めて競合しているため、これは当てはまりません)。

最後に、実行自体はメモリの読み書きで (直接) 行われるのではなく、データが最初にレジスタにロードされます (その後、結果が格納されます)。

コンパイラーがレジスターを割り当てる方法、ループ展開、自動ベクトル化、命令スケジューリング モデル (命令間のデータ依存を避けるためのインターリーブ命令) などもすべて、アルゴリズムの実際のスループットに影響します。

最後に、生成されるコード、CPU モデル、処理されるデータ量、およびさまざまなキャッシュの状態に応じて、アルゴリズムのレイテンシは桁違いに異なります。したがって、他の多くの (非線形) 要因が関係しているため、コード (または生成されたアセンブリ) だけを検査しても、ループの動作強度を判断することはできません。

ただし、実際の質問に対処するために、ここで概説した定義からわかる限り、2 番目のループは反復ごとに平均して 1 回の追加の 4 バイト アクセスとしてカウントされるため、その OI は θ(3N FLOPS / 4N バイト）。直観的には、キャッシュには既にデータがロードされており、メイン メモリに戻る代わりに書き込みによってキャッシュを直接変更できるため、これは理にかなっています (ただし、データは最終的に書き戻す必要がありますが、その要件は最初から変更されていません)。ループ）。

于 2016-11-23T01:00:27.600 に答える