Java視点からCPUキャッシュと疑似共有を理解する
5444 ワード
転載元:http://ifeve.com/from-javaeye-cpu-cache/ http://ifeve.com/from-javaeye-false-sharing/ CPUはコンピュータの脳で、プログラムを実行する命令を担当しています.メモリはデータを保存します.プログラム自体のデータを含みます.メモリはCPUよりかなり遅いですが、メモリの一つのデータを取得するには200以上のCPU周期(CPU cycles)が必要です.CPUレジスタは通常CPU周期で十分です. ウェブブラウザは速度を上げるために、本機にキャッシュ前に閲覧したデータを保存します.従来のデータベースまたはNoSQLデータベースは、クエリを加速するためにメモリにキャッシュを設定し、ディスク(遅い)IOを低減します.同じメモリとCPUの速度の違いがあまりにも大きいので、CPU設計者たちはCPUにキャッシュ(CPU Cache)を追加しました.同じロットのデータを何回も操作する必要があるなら、CPUに近いキャッシュにデータを置くと、プログラムに大きなスピードがかかります.例えば、循環カウントをして、カウント変数をキャッシュに入れると、毎回メモリにデータをアクセスする必要がなくなります.以下はCPU Cacheの簡単な概略図である. 
マルチコアの発展に伴い、CPU Cacheは3つのレベルに分かれた.L 1、L 2、L 3.レベルが小さいほどCPUに近いので、速度も速いし、容量が小さいという意味もあります.L 1は最もCPUに近いもので、容量が最小で、例えば32 Kで、速度が最も速く、各コアにL 1 Cacheがある(正確には、各コアにL 1 Cacheが二つあり、一つのデータL 1 d Cache、一つのコマンドL 1 i Cache).L 2 Cacheはもっと大きいです.例えば256 Kは速度が遅くなります.一般的に各核に独立したL 2 Cacheがあります.L 3 Cacheは、3級キャッシュの中で最大の1級であり、例えば12 MBであり、最も遅い1級でもあり、同じCPUスロットの間で1つのL 3 Cacheを共有する. データベースcacheのように、データを取得する時はまず一番早いcacheの中でデータを探します.命中していないなら、次のレベルに探してください.三階のCacheが見つからないまで、メモリにデータが必要です.毎回当たらないとデータを取る時間が長くなります. キャッシュに効率的にアクセスするためには、単に単一条データをバッファに書き込むのではない.キャッシュはキャッシュ行からなり、典型的な行は64バイトである.CPUアクセスキャッシュは動作最小単位で動作します.Java longタイプは8バイトを占めていますので、キャッシュ行から8つのlong型変数を取得できます.したがって、long型配列にアクセスすると、cacheにロードされたlongがあると、他の7つを消費せずにロードされるので、配列を速く遍歴することができます. 典型的なCPUマイクロアーキテクチャが3段階のキャッシュを持っていますが、各コアが自分のプライベートL 1、L 2キャッシュを持っています.マルチスレッドプログラムの場合、他のコアのスレッドが現在のコアL 1、L 2キャッシュ行のデータにアクセスしたい場合、どうすればいいですか? 第2の核を通じて第1の核のキャッシュ行に直接アクセスできる方法がある.これは可能ですが、この方法はあまり速くないです.核にまたがる訪問はメモリ・コントロラーを通過しなければならないが、典型的な状況は第2の核が常に第1の核にアクセスするこのデータであり、毎回核横断の消費がある.さらに悪い場合は、第2のコアと第1のコアが一つのスロット内にない可能性があり、さらにメモリコントローラのバス帯域幅は限られており、これだけのデータ転送を担げない.第2の核がこのデータを必要とするなら、第1の核から直接データを送るべきで、データは一回だけ送るべきです. キャッシュ行の転送はいつ発生しますか?答えは簡単です.一つの核がもう一つの核の汚いキャッシュを読み込む必要がある時に発生します.しかし前者は、後者のキャッシュが汚れているとどう判断しますか? 以下では以上の問題を詳しく解いて、まず一つの協議---MESI協議に言及します.現在主流のプロセッサはキャッシュのコヒーレンスとメモリのコヒーレンスを保証するためにそれを使っています.M、E、S、Iは、MESIプロトコルを使用するときのキャッシュ行の4つの状態を表す. M(修正、Modified):ローカルプロセッサはキャッシュ行を修正しました.つまり、汚い行です.その内容はメモリの内容と違います.このcacheはローカルのコピーしかありません. E(専用、Exclusive):キャッシュ行の内容はメモリと同じで、他のプロセッサはこの行のデータがありません. S(共有、Shared):キャッシュ行の内容はメモリと同じで、他のプロセッサもこのキャッシュ行のコピーが存在する可能性があります. I(無効、Invalid):キャッシュ行が無効になり、使用できません. 以下では、キャッシュ行の4つの状態がどのように変換されるかを簡単に説明する. 初期:最初の時点では、キャッシュ行にはデータがロードされていませんので、I状態になります. ローカル書き込み(Local Write):I状態のキャッシュ行にローカルプロセッサがデータを書き込むと、キャッシュ行の状態はMになります. ローカル読み(Local Read):ローカルプロセッサがI状態のキャッシュ行を読み出すと、明らかにこのキャッシュにはデータがありません.この時は2つの場合に分けます.(1)他のプロセッサのキャッシュにもこの行のデータがない場合は、メモリからデータをキャッシュ行にロードした後、E状態にします.これは私の家族だけがこのデータを持っています.他のプロセッサは全部ないということです.(2)他のプロセッサのキャッシュにこの行のデータがある場合、このキャッシュ行の状態をS状態とする.P.S.M状態のキャッシュ行があれば、ローカルプロセッサによって書き込み／読み出しされても、状態は変わりません. リモート読み(Remote Read):2つのプロセッサc 1とc 2があると仮定する.c 2が他のプロセッサc 1のキャッシュ内容を読む必要がある場合、c 1は、キャッシュ行の内容をメモリコントローラを介してc 2に送信する必要があり、c 2は受信後、対応するキャッシュ行状態をSに設定する.設定する前に、メモリもバスからこのデータを得て保存します. リモート書き込み(Remote Write):確かにリモートで書くのではなく、c 2がc 1のデータを手に入れた後、読むためではなく、書くために、ローカルで書くということですが、c 1もこのデータのコピーを持っています.どうすればいいですか?c 2は、この行のデータの権限を持つ必要があるRFO(Request For Owner)要求を発行し、他のプロセッサの対応するキャッシュ行をIとして設定します.この行のデータを動かすことができないのは、自分以外の誰ですか?これはデータの安全を保証し、RFO要求を処理し、Iを設定するプロセスは書き込み動作に大きな性能消費をもたらす. 上記の内容は、書き込み操作の価格が高く、特にRFOメッセージを送信する必要がある場合を知っています.プログラムを作成する時、いつRFO要求が発生しますか?次の2つがあります 1.スレッドの動作は1つのプロセッサから別のプロセッサに移り、その動作のすべてのキャッシュ行は新しいプロセッサに移る必要があります.その後、キャッシュ行を書き換えると、このキャッシュ行は、異なる核上に複数のコピーがあり、RFO要求を送信する必要がある. 2.2つの異なるプロセッサは確実に同じキャッシュ行を操作する必要があります. Javaプログラムでは、配列のメンバーはキャッシュにおいても連続している.Javaオブジェクトの隣のメンバ変数からも同じキャッシュ行にロードされます.複数のスレッドが異なるメンバー変数を操作しても、同じキャッシュ行である場合、疑似共有(False Sharing)問題が発生します. 例えば、プロセッサcore 1で動作するスレッドは変数Xの値を更新したいと思いますが、もう一つはプロセッサcore 2で動作するスレッドは変数Yの値を更新したいと思います.しかし、この2つの頻繁に変更された変数は同じキャッシュ行にあります.二つのスレッドは順番にRFOメッセージを送り、このキャッシュ行の所有権を占めます.core 1が所有権を取得してXの更新を開始すると、core 2に対応するキャッシュ行はI状態にする必要がある.core 2が所有権を取得してYの更新を開始すると、core 1に対応するキャッシュ行はI状態(無効状態)にする必要がある.順番に所有権を奪うことは、大量のRFOメッセージをもたらすだけではなく、あるスレッドがこの行のデータを読む必要がある場合、L 1とL 2のキャッシュには無効なデータがあり、L 3キャッシュだけが同期されたデータである.L 3のデータを読んで性能に非常に影響して、更に悪い情況は溝にまたがって読み取るので、L 3はすべてmissを要して、メモリの上からロードすることしかできません. 表面上のXとYは独立したスレッドで動作し,両動作の間には何の関係もない.ただし、それらはキャッシュ行を共有していますが、競合はすべて共有から発生します. では、どうやって疑似共有を避けるべきですか?キャッシュ行は64バイトであり、Javaプログラムのオブジェクトヘッダは8バイト(32ビットシステム)または12バイト(64ビットシステムはデフォルトで圧縮を開始し、16バイトの圧縮を行わない.6つの無駄な長さを記入して6*8=48バイトを補完し、異なる変数を異なるキャッシュ行にするだけで、疑似共有を回避できます.たとえば:
いくつかのJavaコンパイラは、使用されていないデータを補完します.たとえば、コードの6つの長さの整数がコンパイル時に最適化されても、プログラムにいくつかのコードを追加してコンパイルの最適化を防ぐことができます.
マルチコアの発展に伴い、CPU Cacheは3つのレベルに分かれた.L 1、L 2、L 3.レベルが小さいほどCPUに近いので、速度も速いし、容量が小さいという意味もあります.L 1は最もCPUに近いもので、容量が最小で、例えば32 Kで、速度が最も速く、各コアにL 1 Cacheがある(正確には、各コアにL 1 Cacheが二つあり、一つのデータL 1 d Cache、一つのコマンドL 1 i Cache).L 2 Cacheはもっと大きいです.例えば256 Kは速度が遅くなります.一般的に各核に独立したL 2 Cacheがあります.L 3 Cacheは、3級キャッシュの中で最大の1級であり、例えば12 MBであり、最も遅い1級でもあり、同じCPUスロットの間で1つのL 3 Cacheを共有する. データベースcacheのように、データを取得する時はまず一番早いcacheの中でデータを探します.命中していないなら、次のレベルに探してください.三階のCacheが見つからないまで、メモリにデータが必要です.毎回当たらないとデータを取る時間が長くなります. キャッシュに効率的にアクセスするためには、単に単一条データをバッファに書き込むのではない.キャッシュはキャッシュ行からなり、典型的な行は64バイトである.CPUアクセスキャッシュは動作最小単位で動作します.Java longタイプは8バイトを占めていますので、キャッシュ行から8つのlong型変数を取得できます.したがって、long型配列にアクセスすると、cacheにロードされたlongがあると、他の7つを消費せずにロードされるので、配列を速く遍歴することができます. 典型的なCPUマイクロアーキテクチャが3段階のキャッシュを持っていますが、各コアが自分のプライベートL 1、L 2キャッシュを持っています.マルチスレッドプログラムの場合、他のコアのスレッドが現在のコアL 1、L 2キャッシュ行のデータにアクセスしたい場合、どうすればいいですか? 第2の核を通じて第1の核のキャッシュ行に直接アクセスできる方法がある.これは可能ですが、この方法はあまり速くないです.核にまたがる訪問はメモリ・コントロラーを通過しなければならないが、典型的な状況は第2の核が常に第1の核にアクセスするこのデータであり、毎回核横断の消費がある.さらに悪い場合は、第2のコアと第1のコアが一つのスロット内にない可能性があり、さらにメモリコントローラのバス帯域幅は限られており、これだけのデータ転送を担げない.第2の核がこのデータを必要とするなら、第1の核から直接データを送るべきで、データは一回だけ送るべきです. キャッシュ行の転送はいつ発生しますか?答えは簡単です.一つの核がもう一つの核の汚いキャッシュを読み込む必要がある時に発生します.しかし前者は、後者のキャッシュが汚れているとどう判断しますか? 以下では以上の問題を詳しく解いて、まず一つの協議---MESI協議に言及します.現在主流のプロセッサはキャッシュのコヒーレンスとメモリのコヒーレンスを保証するためにそれを使っています.M、E、S、Iは、MESIプロトコルを使用するときのキャッシュ行の4つの状態を表す. M(修正、Modified):ローカルプロセッサはキャッシュ行を修正しました.つまり、汚い行です.その内容はメモリの内容と違います.このcacheはローカルのコピーしかありません. E(専用、Exclusive):キャッシュ行の内容はメモリと同じで、他のプロセッサはこの行のデータがありません. S(共有、Shared):キャッシュ行の内容はメモリと同じで、他のプロセッサもこのキャッシュ行のコピーが存在する可能性があります. I(無効、Invalid):キャッシュ行が無効になり、使用できません. 以下では、キャッシュ行の4つの状態がどのように変換されるかを簡単に説明する. 初期:最初の時点では、キャッシュ行にはデータがロードされていませんので、I状態になります. ローカル書き込み(Local Write):I状態のキャッシュ行にローカルプロセッサがデータを書き込むと、キャッシュ行の状態はMになります. ローカル読み(Local Read):ローカルプロセッサがI状態のキャッシュ行を読み出すと、明らかにこのキャッシュにはデータがありません.この時は2つの場合に分けます.(1)他のプロセッサのキャッシュにもこの行のデータがない場合は、メモリからデータをキャッシュ行にロードした後、E状態にします.これは私の家族だけがこのデータを持っています.他のプロセッサは全部ないということです.(2)他のプロセッサのキャッシュにこの行のデータがある場合、このキャッシュ行の状態をS状態とする.P.S.M状態のキャッシュ行があれば、ローカルプロセッサによって書き込み／読み出しされても、状態は変わりません. リモート読み(Remote Read):2つのプロセッサc 1とc 2があると仮定する.c 2が他のプロセッサc 1のキャッシュ内容を読む必要がある場合、c 1は、キャッシュ行の内容をメモリコントローラを介してc 2に送信する必要があり、c 2は受信後、対応するキャッシュ行状態をSに設定する.設定する前に、メモリもバスからこのデータを得て保存します. リモート書き込み(Remote Write):確かにリモートで書くのではなく、c 2がc 1のデータを手に入れた後、読むためではなく、書くために、ローカルで書くということですが、c 1もこのデータのコピーを持っています.どうすればいいですか?c 2は、この行のデータの権限を持つ必要があるRFO(Request For Owner)要求を発行し、他のプロセッサの対応するキャッシュ行をIとして設定します.この行のデータを動かすことができないのは、自分以外の誰ですか?これはデータの安全を保証し、RFO要求を処理し、Iを設定するプロセスは書き込み動作に大きな性能消費をもたらす. 上記の内容は、書き込み操作の価格が高く、特にRFOメッセージを送信する必要がある場合を知っています.プログラムを作成する時、いつRFO要求が発生しますか?次の2つがあります 1.スレッドの動作は1つのプロセッサから別のプロセッサに移り、その動作のすべてのキャッシュ行は新しいプロセッサに移る必要があります.その後、キャッシュ行を書き換えると、このキャッシュ行は、異なる核上に複数のコピーがあり、RFO要求を送信する必要がある. 2.2つの異なるプロセッサは確実に同じキャッシュ行を操作する必要があります. Javaプログラムでは、配列のメンバーはキャッシュにおいても連続している.Javaオブジェクトの隣のメンバ変数からも同じキャッシュ行にロードされます.複数のスレッドが異なるメンバー変数を操作しても、同じキャッシュ行である場合、疑似共有(False Sharing)問題が発生します. 例えば、プロセッサcore 1で動作するスレッドは変数Xの値を更新したいと思いますが、もう一つはプロセッサcore 2で動作するスレッドは変数Yの値を更新したいと思います.しかし、この2つの頻繁に変更された変数は同じキャッシュ行にあります.二つのスレッドは順番にRFOメッセージを送り、このキャッシュ行の所有権を占めます.core 1が所有権を取得してXの更新を開始すると、core 2に対応するキャッシュ行はI状態にする必要がある.core 2が所有権を取得してYの更新を開始すると、core 1に対応するキャッシュ行はI状態(無効状態)にする必要がある.順番に所有権を奪うことは、大量のRFOメッセージをもたらすだけではなく、あるスレッドがこの行のデータを読む必要がある場合、L 1とL 2のキャッシュには無効なデータがあり、L 3キャッシュだけが同期されたデータである.L 3のデータを読んで性能に非常に影響して、更に悪い情況は溝にまたがって読み取るので、L 3はすべてmissを要して、メモリの上からロードすることしかできません. 表面上のXとYは独立したスレッドで動作し,両動作の間には何の関係もない.ただし、それらはキャッシュ行を共有していますが、競合はすべて共有から発生します. では、どうやって疑似共有を避けるべきですか?キャッシュ行は64バイトであり、Javaプログラムのオブジェクトヘッダは8バイト(32ビットシステム)または12バイト(64ビットシステムはデフォルトで圧縮を開始し、16バイトの圧縮を行わない.6つの無駄な長さを記入して6*8=48バイトを補完し、異なる変数を異なるキャッシュ行にするだけで、疑似共有を回避できます.たとえば:public final static class VolatileLong {
public volatile long value = 0L;
public long p1, p2, p3, p4, p5, p6;
}いくつかのJavaコンパイラは、使用されていないデータを補完します.たとえば、コードの6つの長さの整数がコンパイル時に最適化されても、プログラムにいくつかのコードを追加してコンパイルの最適化を防ぐことができます.
public static long preventFromOptimization(VolatileLong v) {
return v.p1 + v.p2 + v.p3 + v.p4 + v.p5 + v.p6;
}