parallel-processing - 一次只能有一个 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

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

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

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

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