一次只能有一个CPU访问RAM吗？

Question

我目前正在尝试使用多个内核进行编程.我想用C++/Python/Java编写/实现并行矩阵乘法(我猜Java将是最简单的).

但是我自己无法回答的一个问题是RAM访问如何与多个CPU协同工作.

我的想法

我们有两个矩阵A和B.我们想要计算C = A*B:

当n,m或p很大时,并行执行只会更快.所以假设n,m和p> = 10,000.为简单起见,假设n = m = p = 10,000 = 10 ^ 4.

我们知道我们可以计算每个$ c_ {i,j} $而不用查看C的其他条目.所以我们可以并行计算每个c_ {i,j}:

但是所有c_ {1,i}(i\in 1,...,p)都需要A的第一行.由于A是一个10 ^ 8双精度数组,它需要800 MB.这肯定比CPU缓存大.但是一行(80kB)将适合CPU缓存.所以我想将每一行C分配给一个CPU(一旦CPU空闲)就是个好主意.所以这个CPU至少会在其缓存中有A并从中受益.

我的问题

如何管理不同内核(在普通的英特尔笔记本电脑上)的RAM访问？

我想必须有一个"控制器",一次可以独占访问一个CPU.这个控制器有一个特殊的名字吗？

偶然地,两个或更多CPU可能需要相同的信息.他们能同时得到它吗？RAM访问是否是矩阵乘法问题的瓶颈？

如果您知道一些介绍多核编程的好书(用C++/Python/Java编写),请让我知道.

Answer 1

您应该以缓存友好的方式将并行化矩阵乘法的问题（有很多方法 - 搜索“平铺”。这是 Berkeley 的一个很好的解释）与多个核心如何共享对某些资源的访问的问题分开，例如共享缓存和内存。第一个是指如何避免缓存抖动并实现数据的有效重用（在给定的缓存层次结构上），后者指的是内存带宽利用率。确实，两者是相连的，但它们大多是相互排斥的，因为良好的缓存会减少您的出站带宽（这对于性能和功耗来说当然是理想的）。但有时，在数据不可重用或算法无法修改以适应缓存的情况下，这是无法完成的。在这些情况下，内存带宽可能会成为您的瓶颈，不同的内核必须尽可能地共享它。

大多数现代 CPU 都有多个核心共享最后一级缓存（我不确定某些智能手机细分市场是否属于这种情况，但对于笔记本/台式机/服务器来说这通常适用）。反过来，该缓存与内存控制器进行通信（内存控制器曾经位于另一个称为北桥的芯片上，但几年前已集成到大多数 CPU 中以实现更快的访问）。通过内存控制器，整个 CPU 可以与 DRAM 通信并告诉它要获取什么。MC 通常足够聪明，可以组合访问，以便只需要最少的时间和精力来获取（请记住，从 DRAM 获取“页面”是一项漫长的任务，通常需要首先逐出读出放大器中缓冲的当前页面） ）。

请注意，这种结构意味着 MC 不必分别与多个内核通信，它只需将数据提取到最后一级缓存。内核也不需要直接与内存控制器通信，因为访问会通过最后一级缓存进行过滤（少数例外，例如将经过它的不可缓存访问以及具有另一个控制器的 IO 访问）。除了它们自己的私有缓存之外，所有核心都将共享该缓存存储。

现在关于共享的说明 - 如果 2 个（或更多）核心同时需要相同的数据，那么你很幸运 - 要么它已经在缓存中（在这种情况下，将通过将数据副本发送到每个核心来依次服务两个访问） ，并将它们标记为“共享”），或者如果数据不存在，则两者都会等到 MC 可以带它（一次），然后像命中情况一样继续。然而，有一个例外是一个或多个核心需要将新数据写入该行或其一部分。在这种情况下，修改器将发出所有权读取请求 (RFO)，这将阻止共享该行并使其他核心中的所有副本无效，否则您将面临失去缓存一致性或一致性的风险（因为一个核心可能会使用过时的数据或感知到不正确的内存顺序）。这在并行算法中被称为竞争条件，也是复杂锁定/防护机制的原因。再次注意，这与实际 RAM 访问正交，并且可能同样适用于最后一级缓存访问。