[解決済み] 原子演算コスト

質問

アトミック操作（コンペア＆スワップ、アトミック・アド／デクリメントのいずれか）のコストはどのくらいですか？どのくらいのサイクルが消費されますか? SMP または NUMA 上で他のプロセッサを一時停止しますか、またはメモリ アクセスをブロックしますか? アウトオブオーダーの CPU で並べ替えバッファをフラッシュしますか？

キャッシュにどのような影響がありますか？

x86、x86_64、PowerPC、SPARC、Itanium など、最近の一般的な CPU に興味があります。

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

過去数日間の実際のデータを探しましたが、何も見つかりませんでした。 しかし、アトミック操作のコストとキャッシュ ミスのコストを比較する研究は行いました。

x86 の LOCK 接頭辞のコスト、( lock cmpxchg を含む) のコストは、PentiumPro 以前では (doc で説明されているように)、メモリ アクセス (キャッシュ ミスなど) と、他のプロセッサによるメモリ操作の停止、およびバスを LOCK しようとする他のプロセッサとの競合になります。しかし、PentiumPro 以降、通常の Writeback キャッシュ可能なメモリ (ハードウェアと直接会話しない限り、アプリケーションが扱うすべてのメモリ) では、すべてのメモリ操作をブロックするのではなく、関連するキャッシュラインのみをブロックします (以下のリンクに基づきます)。 osgx の回答 ).

つまり、コアは、MESI共有とRFO要求への回答を、実際の lock 操作のストア部分の後まで待ちます。 これはキャッシュ ロックと呼ばれ、その 1 つのキャッシュ ラインにのみ影響します。 他のコアは同時に他の行をロード/保存したり、CAS したりすることができます。

実際、CAS のケースはより複雑で、次のサイトで説明されています。 このページ で説明されています。タイミングは不明ですが、信頼できるエンジニアによる洞察に満ちた説明です。 (少なくとも、実際の CAS の前に純粋なロードを行う通常のユースケースについては)。

あまり詳しく説明する前に、LOCKされたオペレーションは1回のキャッシュミスと同じキャッシュライン上の他のプロセッサとの競合の可能性を要しますが、CAS＋先行ロード（常に0と1をCASするmutexを除いてほとんど常に必要です）は2回のキャッシュミスを要することがあると言っておきます。

彼は、Load-Linked/Store-Conditional のように、1 つの場所でのロード + CAS が実際に 2 つのキャッシュミスを引き起こすことができると説明しています (後者については、こちらを参照してください)。彼の説明は MESI キャッシュ コヒーレンス プロトコル . これは、キャッシュラインに対して 4 つの状態を使用します。M(odified), E(xclusive), S(hared), I(nvalid) (だから MESI と呼ばれる) の4つの状態を使用し、必要に応じて以下に説明する。説明すると、シナリオは以下の通りです。

• LOAD がキャッシュ ミスを引き起こした場合 - 関連するキャッシュラインは共有状態でメモリからロードされます (つまり、他のプロセッサはまだそのキャッシュラインをメモリに保持することができます。この状態では変更は許可されていません)。もしその場所がメモリ内にあれば、このキャッシュミスはスキップされます。 可能なコスト：1キャッシュ・ミス。 (キャッシュラインが Shared、Exclusive、または Modified 状態である場合、つまりデータがこの CPU の L1 キャッシュにある場合はスキップされます)。
• プログラムは保存する新しい値を計算します。
• そして、アトミックなCAS命令を実行します。
  • 同時改変を避けなければならないので、他の CPU のキャッシュからキャッシュラインのコピーを削除し、キャッシュラインを Exclusive 状態に移行させなければなりません。 可能なコスト: 1 つのキャッシュ ミス。 すでに排他的に所有されている場合、つまり Exclusive または Modified 状態の場合は、この必要はありません。どちらの状態でも、他の CPU はキャッシュラインを保持しませんが、Exclusive 状態では (まだ) 変更されていません。
  • この通信の後、変数は CPU のローカル キャッシュで変更され、その時点で他のすべての CPU からグローバルに見えるようになります (他の CPU のキャッシュは私たちのキャッシュとコヒーレントであるため)。 それは最終的に、通常のアルゴリズムに従ってメイン メモリに書き込まれます。
  • その変数を読み取りまたは変更しようとする他のプロセッサは、まず共有モードまたは排他モードでそのキャッシュラインを取得する必要があり、そのためにこのプロセッサに連絡してキャッシュラインの更新版を受け取ります。 LOCK された操作では、キャッシュミスのみが発生します (キャッシュラインは Exclusive 状態で直接要求されるため)。

すべての場合において、キャッシュラインのリクエストは、すでにデータを変更している他のプロセッサによって停止される可能性があります。