parallel-processing - 一度に 1 つの CPU だけが RAM にアクセスできますか?

Question

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

しかし、私自身では答えられない 1 つの質問は、RAM アクセスが複数の CPU でどのように機能するかということです。

私の考え

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

並列実行は、n、m、または p が大きい場合にのみ高速になります。したがって、n、m、および p >= 10,000 とします。簡単にするために、n=m=p=10,000 = 10^4 とします。

C の他のエントリを見なくても、各 $c_{i,j}$ を計算できることがわかっています。したがって、すべての 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 アクセスはどのように管理されますか (通常の Intel ノートブック上)?

一度に1つのCPUに排他的にアクセスできる「コントローラー」が1つ必要だと思います。このコントローラーには特別な名前がありますか?

偶然にも、2 つ以上の CPU が同じ情報を必要とする場合があります。同時に取得できますか？RAM アクセスは行列乗算の問題のボトルネックですか?

また、マルチコア プログラミング (C++/Python/Java) を紹介する良い本があれば教えてください。

Answer 1

キャッシュに適した方法で行列乗算を並列化するという問題を分離する必要があります (そのための方法はたくさんあります - 「タイル化」を検索してください。ここに Berkeley からの素晴らしい説明があります))、複数のコアが共有キャッシュやメモリなどのリソースへのアクセスを共有する方法の問題から。前者はキャッシュのスラッシングを回避し、(特定のキャッシュ階層で) データの効果的な再利用を実現する方法を指し、後者はメモリ帯域幅の使用率を指します。2 つが接続されていることは事実ですが、適切なキャッシングはアウトバウンド帯域幅を削減するため、ほとんど相互に排他的です (もちろん、パフォーマンスと電力の両方にとって望ましいことです)。ただし、データが再利用できない場合や、キャッシュに収まるようにアルゴリズムを変更できない場合は、実行できないことがあります。このような場合、メモリ帯域幅がボトルネックになる可能性があり、別のコアが可能な限りそれを共有する必要があります。

最近のほとんどの CPU には、最終レベルのキャッシュを共有する複数のコアがあります (これが一部のスマートフォン セグメントに当てはまるかどうかはわかりませんが、ノートブック/デスクトップ/サーバーの場合、これは通常当てはまります)。次に、そのキャッシュはメモリコントローラーと通信します（以前はノースブリッジと呼ばれる別のチップ上にありましたが、数年前からアクセスを高速化するためにほとんどの CPU に統合されました）。メモリ コントローラーを介して、CPU 全体が DRAM と通信し、何をフェッチするかを伝えることができます。MC は通常、フェッチするのに最小限の時間と労力で済むようにアクセスを組み合わせるのに十分なほどスマートです (DRAM から「ページ」をフェッチするのは長いタスクであり、多くの場合、センス アンプにバッファされている現在のページを最初に追い出す必要があることに注意してください)。 ）。

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

共有についての注意 - 2 つ (またはそれ以上) のコアが同時に同じデータを必要とする場合、幸運です - それはすでにキャッシュに入っているか (この場合、両方のアクセスは、データのコピーを各コアに送信することによって順番に処理されます) 、およびそれらを「共有」としてマークする）、またはデータが存在しない場合は、MCが（1回）データを取得できるまで待機し、ヒットケースと同様に続行します. ただし、1 つ以上のコアがそのラインまたはその一部に新しいデータを書き込む必要がある場合は例外です。その場合、修飾子は所有権の読み取り要求 (RFO) を発行します。これにより、ラインの共有が妨げられ、他のコアのすべてのコピーが無効になります。そうしないと、キャッシュの一貫性または一貫性が失われるリスクがあります (1 つのコアが古いデータを使用するか、間違ったメモリ順序を認識します)。これは、並列アルゴリズムの競合状態として知られており、複雑なロック/フェンシング メカニズムの原因となっています。繰り返しますが、これは実際の RAM アクセスと直交しており、最終レベルのキャッシュ アクセスにも同様に適用される可能性があることに注意してください。