并行计算机架构：流量控制与缓存层次结构解析

# 并行计算机架构：流量控制与缓存层次结构解析 ## 1. 网络流量控制机制 在网络中，多个消息可能同时传输并尝试使用相同的网络链路，这会引发问题。当这种情况发生时，部分消息传输必须被阻塞，而其他消息则可以继续传输。用于协调网络中并发消息传输的技术被称为流量控制机制。这种技术在各种网络中都很重要，包括局域网和广域网，像 TCP 这样的流行协议就包含了复杂的流量控制机制，以获得较高的有效网络带宽。 ### 1.1 链路级流量控制 链路级流量控制考虑的是网络中单个链路上的消息或数据包传输。假设链路连接两个交换机 A 和 B，数据包要从 A 传输到 B。 - 如果 A 和 B 之间的链路空闲，数据包可以从 A 的输出端口传输到 B 的输入端口，然后转发到 B 的合适输出端口。 - 如果 B 繁忙，其输入端口可能没有足够的缓冲区空间来存储来自 A 的数据包。此时，数据包必须留在 A 的输出缓冲区，直到 B 的输入缓冲区有足够空间。这可能会给 A 之前的交换机带来反向压力，导致网络拥塞的风险。 链路级流量控制机制的思路是，如果接收交换机的输入缓冲区空间不足，它会向发送交换机提供反馈，以阻止额外数据包的传输。这种反馈会在网络中迅速向后传播，直到到达原始发送节点。然后，发送方可以降低传输速率，以避免进一步的数据包延迟。 ### 1.2 端到端流量控制 链路级流量控制有助于减少拥塞，但反馈传播可能太慢，在到达原始发送方时网络可能已经拥塞。端到端流量控制直接向原始发送方提供反馈，可能会导致更快的反应。例如，TCP 协议使用的窗口机制就是一种实现方式。通过这种机制，发送方可以了解接收方的可用缓冲区空间，并调整发送的数据包数量，以避免缓冲区溢出。 下面是链路级和端到端流量控制的流程对比： | 流量控制类型 | 反馈方式 | 反应速度 | 作用范围 | | ---- | ---- | ---- | ---- | | 链路级流量控制 | 接收交换机向发送交换机反馈 | 可能较慢 | 单个链路 | | 端到端流量控制 | 直接向原始发送方反馈 | 较快 | 整个网络路径 | mermaid 流程图展示链路级流量控制过程： ```mermaid graph LR A[发送交换机 A] -->|数据包传输| B[接收交换机 B] B -->|缓冲区不足反馈| A A -->|降低传输速率| B ``` ## 2. 缓存与内存层次结构 在过去几十年的硬件发展中，处理器周期时间和主内存访问时间之间的差距越来越大。这主要是因为处理器时钟频率大幅提高，而内存访问时间却没有显著降低。 ### 2.1 内存访问时间分析 主内存基于 DRAM（动态随机存取存储器）构建。对于时钟频率为 3 GHz 的典型处理器，其周期时间为 0.33 ns，而内存访问时间根据使用的 DRAM 芯片不同，需要 60 到 210 个机器周期。 缓存使用 SRAM（静态随机存取存储器）芯片构建，SRAM 芯片比 DRAM 快得多，但单位面积容量较小且成本更高。2022 年，不同级别的缓存和主内存的典型访问时间如下： | 存储类型 | 访问时间 | | ---- | ---- | | L1 缓存 | 约 1 ns | | L2 缓存 | 3 - 10 ns | | L3 缓存 | 10 - 20 ns | | DRAM 主内存 | 50 - 70 ns | 如果应用程序的工作空间大于主内存容量，部分工作空间必须存储在磁盘（磁盘或 SSD）上。但访问磁盘比访问主内存要慢得多，磁盘的典型访问时间在 10 到 20 ms 之间，对于典型的 CPU 频率，这相当于 3000 万到 1 亿个机器周期。因此，将应用程序数据存储在磁盘上会显著减慢程序的执行时间。 ### 2.2 内存层次结构 最简单的内存层次结构是在处理器和主内存之间使用单个缓存（一级缓存，L1 缓存）。缓存包含主内存中数据的子集，并使用替换策略将新数据从主内存带入缓存，替换不再访问的数据元素。如今，每个处理器通常使用两级或三级缓存，包括一个小而快的 L1 缓存和更大但较慢的 L2 和 L3 缓存。 对于多处理器系统，每个处理器使用单独的本地缓存，这会带来保持所有处理器对共享地址空间的一致视图的问题，即缓存一致性问题。对于具有共享地址空间的多处理器，内存层次结构的顶层是所有处理器都可以访问的共享地址空间。 内存层次结构的设计对并行程序的执行时间有很大影响，内存访问应该进行排序，以尽可能高效地使用给定的内存层次结构。以下是一个简单的内存层次结构示意图： ```mermaid graph LR P[处理器] -->|访问| L1[L1 缓存] L1 -->|数据交换| L2[L2 缓存] L2 -->|数据交换| L3[L3 缓存] L3 -->|数据交换| MM[主内存] MM -->|数据交换| D[磁盘] ``` ## 3. 缓存的特性 缓存是处理器和主内存之间的小型但快速的存储器，由 SRAM 构建。典型的访问时间为 0.5 - 2.5 ns，而 DRAM 的访问时间为 50 - 70 ns。 ### 3.1 缓存基本工作原理 缓存包含主内存中数据的副本，数据以块为单位在缓存和主内存之间移动，这些数据块称为缓存块或缓存行。缓存控制由单独的缓存控制器执行，与处理器解耦。 在程序执行期间，处理器指定要读取或写入的内