x86/x64 での CAS の低レベルの仕組みを理解しようとしていますが、助けや洞察をいただければ幸いです。
私がこれについて考えてきた理由は、指数バックオフについて推論し、バックオフ遅延の正しい単一単位がどうあるべきかを原理的に理解しようとしているからです。
指数関数的バックオフなしでロックフリー フリーリスト ベンチマークを見ると、スレッド数が増えると、パフォーマンスが急速に横ばいになることがわかります。
Release 7 Lock-Free Freelist Benchmark #1
M
N
S
L3U
L2U L2U
L1D L1D
L1I L1I
P P
L L L L total ops,mean ops/sec per thread,standard deviation,scalability
0 0 0 1 310134488,31013449,0,1.00
0 1 0 1 136313300,6815665,38365,0.22
0 1 0 1 136401284,6820064,50706,0.22
1 1 1 1 111134328,2778358,23851,0.09
0 0 1 1 334747444,16737372,2421,0.54
1 1 1 1 111105898,2777647,40399,0.09
ご存知のように、各スレッドが他のスレッドの進行を妨げるライブロックが発生する可能性があります。
私の当初の考えは、今では間違っていると思いますが、CAS が CAS に干渉しているというものでした。つまり、CAS 命令自体が別の CAS と破壊的に衝突する可能性があります。どちらも失敗します。(おそらく、イーサネットについて考えていたからです)。
これは「明らかに」結果を説明しています - これらすべての CAS 命令は同時に動作しており、破壊的に中断される前に完全に実行される機会はほとんどありません。
もう少し考えてみると、そんなことはあり得ないと今では思っています。CAS 命令には、実際には障害モードがありません。宛先が比較対象と等しいか等しくないかがわかります。それで全部です。戻ってきて、「ああ、ごめんなさい、他の誰かにぶつかった」とは言いません。
破壊的な干渉は発生していますが、データ構造アルゴリズム自体のより高いレベルで発生しています。フリーリストから/へプッシュまたはポップするとき、実際にはスワップしようとしています。プッシュ/ポップを完了できるように、デスティネーションを読み取り、必要な作業を実行し、変更されていないことを確認できるように、デスティネーションが十分長く安定している必要があります。
他のスレッドが CASing を続けると、destination は安定せず、変化し続け、操作を再試行する必要が生じます。
しかし今、私は混乱しています。
1 つのスレッドが約 3,000 万回のプッシュ/ポップ操作を実行していることがわかります。操作が成功するためには、これらの操作のいずれかが実行されている間、宛先が安定している必要があるため、3,000 万の「スロット」があることがわかります。スレッドが 2 つある場合、理論上の最大パフォーマンスはスレッドあたり 1,500 万回です。各スレッドは半分のスロットを使用します。
では、CAS に戻りましょう。CAS には故障モードがありません。では、別のスレッドが既に CAS を実行しているときに、2 番目のスレッドが CAS を試行するとどうなるでしょうか? スワップが発生しなかったため、2 番目のスレッドはデータ構造レベルで失敗し、スワップを再試行します。
しかし、たくさんのスレッドがあると想像してください。CAS を開始する最初のスレッドは成功します (各 CAS にまったく同じ時間がかかると仮定すると、そうではありませんが、その仮定は基本的なものを何も変更しないため、推論しても問題ありません)。他のすべては失敗します。
ただし、最初のスレッドが終了すると、新しい宛先値を読み取る次のスレッドで CAS が成功します (さらに、まだ CAS を実行しているか、新しい CAS を開始している他のすべてのスレッドは失敗します)。
では、なぜ完全なスケーリングが見られないのでしょうか? すべての「スロット」を使用する必要があるためです。
そのため、私は CAS を正しく理解していないと思います。
Intel の Architecture Software Developer's Manual を読むと、すべてのデータがキャッシュに存在する場合 (私が興味を持っている状況)、キャッシュ コヒーレンシ プロトコルが CAS を処理することがわかりました。
Drepper は、彼のホワイト ペーパーで LL/SC と、MESI を使用してそれがどのように機能するかについて説明しています。
CAS が同様の方法で動作することは、私には理にかなっているように思えます。
2 スレッドの場合を考えてみましょう。最初のスレッドがその CAS を開始します。宛先を含むキャッシュ ラインはそのキャッシュ内にあり、排他的とマークされています。
2 番目のスレッドが CAS に開始されます。最初のコアはそのキャッシュ ラインを 2 番目のコアに送信し、両方のコアがそのキャッシュ ラインを共有とマークします。
最初のスレッドが CAS を完了し、キャッシュ ラインに書き込みます (比較が false であっても、x86/x64 では常に書き込みが発生します。元の値を書き込むだけです)。
書き込み動作は、キャッシュ ラインを変更済みとしてマークします。RFO が発生し、2 番目のコアがそのキャッシュ ラインを無効としてマークします。
2 番目のスレッドが CAS を完了するようになり、そのキャッシュ ラインが無効であることに気付きます。ARM の LL/SC ではアセンブリでこのループを実行する必要があるため、命令が成功するまで内部的にループされる CPU にあるとは信じがたいです。しかし、CAS 命令は宛先の値が変更されたことを認識しているため、その比較の結果は無効です。しかし、CAS でエラーが発生することはありません。比較に対して常に true または false を返します。しかし、命令が完了するまでループしたとしても、完璧なスケーリングが期待できます。各「スロット」は引き続き使用する必要があります。
それでどうなるの？CASに何が起こっているのですか？
私が見ているのは、スレッド数が増えるにつれて、実行される作業がますます少なくなるということです - 利用可能なすべての「スロット」は確実に使用されていません。何かがこれを引き起こしています。CAS命令間の破壊的干渉ですか？それとも、多数の RFO が CPU->ノースブリッジ バスを占有しているのでしょうか?
私が非常に興味深く注目しているのは、同じ物理コア上の 2 つのスレッドが完全にスケーリングされることです。その場合、何か特別で異なることが起こっています。別々の物理コア上の 2 つのスレッドも同様に半分にスケーリングされます。しかし、すべてを説明するには十分な手がかりではありません。