並列プログラミング(その1)
1.マルチプロセッサ時代の並列プログラミング
Pentium4でHyperThreadingが採用されてから、一般的なPC用のCPUでも並列動作が発生するようになりました。 マルチスレッドプログラムにおいて、シングルプロセッサ環境では問題にならなかった事が、マルチプロセッサ 環境では問題になってきます。
もちろん、pthreadなどを利用して普通にプログラムを書いている場合は、複数のスレッドから同一の メモリにアクセスするところを全てMutexやSemaphoreで同期しておけば問題ありません。が、プロセッサ間の 同期ってどんな問題があってどうやって対処しているのか気になったので、調べてみました。
IntelやAMDのDeveloper's Manualなどを読んで勉強しながら書いているので、間違っている部分が あるかもしれません。間違いに気づかれた方は、宜しければコメントやトラックバックでご指摘 下さい。
2.Load/StoreのAtomic性
一般論
ある32bitのメモリの値が、今、0xCCCCCCCCだとします。プロセッサAがこれに0x33333333を上書きし、 同時にプロセッサBが同じメモリを読み出します。
StoreがAtomicで無いと、例えばプロセッサAの上書き動作で、メモリの内容が以下のように変化します。
0xCCCCCCCC -> 0xCCCC3333 -> 0x33333333
この間の状態でプロセッサBのLoadが実行されると、プロセッサBは0xCCCC3333という本来無かった値を 読み込んでしまう事になります。
今度は、StoreがAtomicだけどLoadがAtomicでない場合を考えて見ましょう。メモリは以下のように変化します。
0xCCCCCCCC -> 0x33333333
メモリ上では値が不正なタイミングは存在しないのですが、プロセッサBが「先に下位をLoadして、次に上位をLoadする」 場合、プロセッサBが読み込んだ値はやはり0xCCCC3333になってしまいます。
Load/StoreのAtomic性が保証されていない場合、複数のスレッドからRead/Writeされるメモリは常に Mutexかなにかで同期してやる必要があります。しかし、Atomic性が保証されている場合は、幾つかの 条件で同期をしないで良いことがあります。
例えば、あるカウンタが一つのスレッドにインクリメントされていき、他のスレッドは全て値を参照する だけだとします。この部分を同期しない場合、参照側はタイミングによって±1の誤差はありますが妥当な値を 読むことができ、書き込み側は他にWriteするスレッドが存在しないので同期無しでも安全にRead-Modify-Writeを 実行できます。
i686やAMD64環境での動作
さて、一般的なPCで使用されているCPUにおいて、Atomicが保証されるケース、保証されないケースに ついて調べてみたところ、Intel社の 「Intel 64 and IA-32 Architectures Software Developer's Manual Volume 3A: System Proguramming Guide, Part 1」 の 「7.1.1 Guaranteed Atomic Operations」 に記載されていました。
Accesses to cacheable memory that are split across bus widths, cache lines, and page boundaries are not guaranteed to be atomic by the Intel Core 2 Duo, Intel Core Duo, ...
"bus width" がどのバス幅を指しているのかが判らないのですが、cache lineは64byte、 pageは通常4KBなので、とりあえず64byte境界をまたがるメモリアクセスは危険だと判ります。 実際にCore 2 Duoのシングルプロセッサ(デュアルコア)でテストしてみたところ、32byte境界を またがるだけなら2億回Readしても壊れた値が読めることはありませんでしたが、64byte境界をまたがると簡単に 上位と下位で整合性の取れない値が読めてしまいました。
ただし、"bus width"がFSBの64bitの事を言っているのであれば、8byte境界をまたぐだけで 保証はされなくなるので、キャッシュラインに乗っているから安心とは限りません。
普通にCでプログラムを書くときには、普通の変数は大抵 natural alignment (32bitの変数なら32bit境界に あわせて配置される)されているので、問題はありません。gccで __attribute__((packed)) された構造体を使う場合や、 ポインタの強引なキャストを行った場合は、気をつける必要があります。