一度に1つのCPUのみRAMにアクセスできますか？

Question

私は現在、複数のコアを使ってプログラミングを始めようとしています。私はC++/Python/Java（私はJavaが最も単純なものになるだろうと思う）で並列行列の乗算を書いたり実装したりしたい。

私が自分で答えることはできない1つの質問は、RAMアクセスが複数のCPUでどのように動作するかということです。

私の考え

我々はCが* Bを=計算したい2つの行列AとBがあります。

n個の場合は、並列実行が唯一、速くなりますが、Mまたはpは大きいです。したがって、n、m、p> = 10,000とします。簡単にするために、n = m = p = 10,000 = 10^4と仮定してください。

私たちは、だから我々は、並行しておきC_ {I、J}を計算することができ、我々はC.の他のエントリを見てwithouthそれぞれの$ C_ {I、J} $を計算することができることを知っている：

しかし、すべてのc_ {1、i}（i \ in 1、...、p）にはAの最初の行が必要です。Aは10^8倍の配列なので、800 MBが必要です。これはCPUキャッシュよりもはるかに大きいです。しかし、1行（80kB）はCPUキャッシュに収まるでしょう。ですから、私は、Cのすべての行をちょうど1つのCPUに（CPUが解放されるとすぐに）割り当てることをお勧めします。したがって、このCPUは少なくともキャッシュにAを持ち、そこから利益を得ます。

がどのようにRAMへのアクセスは、（通常のインテルのノートブックに）異なるコアのために管理されている私の質問？

私は一度に1つのCPUへの排他的アクセスを与える1つの「コントローラ」がなければならないと思います。このコントローラーには特別な名前がありますか？

偶然、2つ以上のCPUが同じ情報を必要とする可能性があります。彼らは同時にそれを得ることができますか？ RAMアクセスは行列乗算問題のボトルネックになりますか？

マルチコアプログラミング（C++/Python/Java）を紹介した良い本をご存じの時に教えてください。

Answer 1

行列の乗算をキャッシュフレンドリーな方法で分離する必要があります（複数の方法があります。「タイリング」の検索を参照してください。here's a nice explanation from Berkeley）。共有キャッシュとメモリ。第1の方法は、キャッシュスラッシングを回避し、データの効果的な再利用を（所定のキャッシュ階層で）達成する方法を指し、後者はメモリ帯域幅利用率を指す。 2つが接続されていることは事実ですが、キャッシングが良いとアウトバウンド帯域幅が低下するため、相互に排他的です（これはパフォーマンスと電力の両方にとって望ましいことです）。ただし、データを再利用できない場合、またはアルゴリズムをキャッシュに収めるように変更できない場合は、実行できません。このような場合、メモリBWがボトルネックになる可能性があり、異なるコアはできるだけベストを共有するだけです。

最新のCPUのほとんどには、最終レベルのキャッシュを共有する複数のコアがあります（これはスマートフォンの一部ではわかりませんが、通常はノートブック/デスクトップ/サーバー用です）。そのキャッシュは、今度は、ノースブリッジと呼ばれる別のチップに座っていたメモリコントローラと交信しますが、数年後には高速アクセスのためにほとんどのCPUに統合されています。 メモリコントローラを介して、CPU全体がDRAMと通信し、何をフェッチするかを指示できます。MCは通常、アクセスを結合するのに十分スマートであるため、フェッチするための時間と労力を最小限に抑える必要があります（DRAMからのページのフェッチは長いタスクであり、センスアンプでバッファされた現在のページを）。

この構造は、MCが複数のコアと別々に話す必要はなく、最後のレベルのキャッシュにデータをフェッチするだけであることに注意してください。コアは、最後のレベルのキャッシュ（それを過ぎるキャッシュ不可能なアクセスや別のコントローラを持つIOアクセスなどの例外を除き、アクセスが最後のレベルのキャッシュを通してフィルタリングされるため、メモリコントローラと直接通信する必要はありません。すべてのコアは、独自のプライベートキャッシュに加えて、そのキャッシュストレージを共有します。

ここで共有に関する注記 - 2つ（またはそれ以上）のコアで同じデータが同時に必要な場合は、すでにキャッシュに入っていることが幸運です（両方のアクセスが順番に各コアにデータを送信し、それらを「共有」とマークする）、またはデータが存在しない場合は、MCがそれを持ってくるまで待ってから（一度）、ヒットの場合と同様に続行します。 しかし、一度例外として、1つ以上のコアがその行またはその一部に新しいデータを書き込む必要がある場合です。その場合、モディファイアは所有権（RFO）の読み取り要求を発行し、ラインの共有を防止し、他のコアのすべてのコピーを無効にします。そうしないと、キャッシュの一貫性または整合性が失われる危険性があります失効したデータを使用するか、間違ったメモリ順序を知覚する）。これは、並列アルゴリズムにおける競合状態として知られ、複雑なロック/フェンシングメカニズムの理由です。再び、これは実際のRAMアクセスと直交しており、ラストレベルのキャッシュアクセスにも同様に適用できることに注意してください。