Hardware Memory Models 訳 - x86 Total Store Order（x86-TSO）

• 元記事
• x86 Total Store Order (x86-TSO)
• モダンな x86 メモリモデルは次のハードウェア図に対応している
• 書き込みキューは先入れ先出し
• The Path to x86-TSO へ続く

元記事

research!rsc: Hardware Memory Models (Memory Models, Part 1)

A long time ago, when everyone wrote single-threaded programs, one of the most effective ways to make a program run faster was to sit back and do nothing. Optimizations in the next generation of hardware and the next generation of compilers would make the program run exactly as before, just faster.

research.swtch.com

x86 Total Store Order (x86-TSO)

The memory model for modern x86 systems corresponds to this hardware diagram:

x86 Total Store Order (x86-TSO)

モダンな x86 メモリモデルは次のハードウェア図に対応している

All the processors are still connected to a single shared memory, but each processor queues writes to that memory in a local write queue. The processor continues executing new instructions while the writes make their way out to the shared memory. A memory read on one processor consults the local write queue before consulting main memory, but it cannot see the write queues on other processors.The effect is that a processor sees its own writes before others do. But—and this is very important—all processors do agree on the (total) order in which writes (stores) reach the shared memory, giving the model its name: total store order , or TSO. At the moment that a write reaches shared memory, any future read on any processor will see it and use that value (until it is overwritten by a later write, or perhaps by a buffered write from another processor).

• 全てのプロセッサは 1 つのシェアドメモリにつながっているが、それぞれのプロセッサはローカルの書き込み用キューのメモリに入れる
• プロセッサはシェアドメモリに書き込む間新しい処理を実行し続ける
• 1 つのプロセッサで読まれたメモリはメインメモリを参照する前に、ローカル書き込みキューを参照するが、他のプロセッサからはその書き込みキューはみえない
• その結果、プロセッサが他のプロセッサの処理をみる前に自分自身の書き込みを認識する
• これは非常に重要なことであり、すべてのプロセッサは、書き込み（ストア）がシェアドメモリに到達する順番に合意する。このモデルのことを total store order（TSO）と呼ぶ
• 書き込みがシェアドメモリに到達した時点で、任意のプロセッサでの読み込みは、それらを認識し、その値を利用する（後続の書き込みに上書きされるか、他のプロセッサのバッファリングされた書き込みに上書きされるまで）

The write queue is a standard first-in, first-out queue: the memory writes are applied to the shared memory in the same order that they were executed by the processor. Because the write order is preserved by the write queue, and because other processors see the writes to shared memory immediately, the message passing litmus test we considered earlier has the same outcome as before: r1 = 1, r2 = 0remains impossible.

書き込みキューは先入れ先出し

• メモリ書き込みは、プロセッサによって実行されたのと同じ順番でシェアドメモリに適用される
• なぜなら、書き込み順番は、書き込みキューによって保持され、他のプロセッサは即座にシェアドメモリの書き込みがみえるので、前に考えたリトマステストは、同じ結果になる
• つまり、前にも確認したリトマステストでは、r1 = 1、r2 = 0 となることはない

The write queue guarantees that thread 1 writes x to memory before y, and the system-wide agreement about the order of memory writes (the total store order) guarantees that thread 2 learns of x's new value before it learns of y's new value. Therefore it is impossible for r1 = y to see the new y without r2 = x also seeing the new x. The store order is crucial here: thread 1 writes x before y, so thread 2 must not see the write to y before the write to x.

• 書き込みキューはスレッド 1 が y の前に、メモリ x へ書き込みことを保証する
• TSO はスレッド 2 が y の値を取得する前に x の値を取得することを保証する
• r2 = x に値が入ることなく r1 = y に値が入ることは起こり得ない
• つまり、 スレッド 1 は y の前に x に書き込むので、スレッド 2 は x に書き込む前に y へ書き込まれてはならない

The sequential consistency and TSO models agree in this case, but they disagree about the results of other litmus tests. For example, this is the usual example distinguishing the two models:

• このケースにおいて SC や TSO モデルは保証されるが、他のリトマステストで保証されないケースはある
• 次の例はこれは 2 つのモデルを区別するよくある例である

In any sequentially consistent execution, either x = 1 or y = 1 must happen first, and then the read in the other thread must observe it, so r1 = 0, r2 = 0 is impossible. But on a TSO system, it can happen that Thread 1 and Thread 2 both queue their writes and then read from memory before either write makes it to memory, so that both reads see zeros.

• 逐次一貫性の実行において x = 1 か y = 1 は必ず最初になり、他のスレッドでの読み込みはそれらを監視するので r1 = 0、r2 = 0 は発生しえない
• TSO システムでは、スレッド 1 とスレッド 2 の両方とも書き込みをキューに入れ、それぞれの書き込みがメモリに書き込みをする前にメモリから読まれるので、r1 = 0、r2 = 0 は発生しうる

This example may seem artificial, but using two synchronization variables does happen in well-known synchronization algorithms, such as Dekker's algorithm or Peterson's algorithm, as well as ad hoc schemes. They break if one thread isn’t seeing all the writes from another.

• この例は意図的に見えるが、2 つの同期する値は下記のようなよく知られた同期アルゴリズムで発生する
•  Dekker's algorithm or Peterson's algorithm など
• あるスレッドが、他のスレッドからのすべての書き込みを認識していないとアルゴリズムが崩壊する（アルゴリズムを守るために後述のメモリバリアが存在する）

To fix algorithms that depend on stronger memory ordering, non-sequentially-consistent hardware supplies explicit instructions called memory barriers (or fences) that can be used to control the ordering. We can add a memory barrier to make sure that each thread flushes its previous write to memory before starting its read:

• より強力なメモリ順序に依存するアルゴリズムを修正するために、逐次一貫性のないハードウェアは、メモリバリアと呼ばれる明確な命令を提供する
• メモリバリアは、順序をコントロールするために利用される
• メモリバリアを追加することで、それぞれのスレッドが読み込み始める前に、以前の書き込みをメモリに対しフラッシュすることができる

With the addition of the barriers, r1 = 0, r2 = 0 is again impossible, and Dekker's or Peterson's algorithm would then work correctly. There are many kinds of barriers; the details vary from system to system and are beyond the scope of this post. The point is only that barriers exist and give programmers or language implementers a way to force sequentially consistent behavior at critical moments in a program.

• メモリバリアを追加することで、r1 = 0, r2 = 0 は再び不可能になり、デッカーやピーターソンのアルゴリズムは正しく動作するようになる
• また、多くの種類のメモリバリアが存在するが、詳細を深堀りすることはこの投稿のスコープを超えるので言及しない
• 重要なのは、メモリバリアが存在することで、プログラムの重要な瞬間においてだけ、プログラマや言語実装者に対し、強制的に逐次一貫性の振る舞いが提供できるということである

One final example, to drive home why the model is called total store order. In the model, there are local write queues but no caches on the read path. Once a write reaches main memory, all processors not only agree that the value is there but also agree about when it arrived relative to writes from other processors. Consider this litmus test:

• 最後の例として、なぜこのモデルが TSO と呼ばれるかについて言及する
• ローカルに書き込みキューがあるが、読み込み側にはキャッシュがない
• 一度メインメモリに書き込みが到達すると、すべてのプロセッサは値がシェアドメモリにあることに合意するだけでなく、他のプロセッサからの書き込みと比較して値がいつ到達したかにも合意する
• このリトマステストについて考えてみる

If Thread 3 sees x change before y, can Thread 4 see y change before x? For x86 and other TSO machines, the answer is no: there is a total order over all stores (writes) to main memory, and all processors agree on that order, subject to the wrinkle that each processor knows about its own writes before they reach main memory.

• スレッド 2 が y が変わる前に x を確認する場合、スレッド 4 は x が変わる前に y を確認することができるかというと、x86 と他の TSO マシンにおいて、その答えは NO
• メインメモリへのすべてのストア（書き込み）には、すべて全順序（total order）がある

The Path to x86-TSO へ続く