并行计算机网络路由、交换与缓存机制解析

### 并行计算中的路由、交换、缓存与内存层次结构解析 #### 1. 路由与交换 在网络数据传输中，路由和交换是关键环节。其中，虫孔路由是一种常见的路由方式。在四个交换机上传输四个数据包时，可能会出现死锁情况。如图所示，每个数据包占用一个片缓冲（flit buffer），并请求下一个交换机的另一个片缓冲，但该缓冲已被其他数据包占用，导致没有数据包能传输到下一个交换机，从而形成死锁。不过，虫孔路由的优点是交换机的缓冲区可以较小，因为只需存储数据包的一小部分。 随着技术发展，如今交换机的缓冲区可以做得足够大，虚拟直通路由成为更常用的交换技术。通过使用合适的路由算法（如维度有序路由）或虚拟通道，可以避免死锁的危险。 网络中还存在一个普遍问题，即多个消息可能同时传输并试图同时使用相同的网络链路。为解决此问题，需要流量控制机制来协调并发消息传输。流量控制机制在各种网络中都很重要，对于并行计算机网络尤为关键，因为它们必须能够快速可靠地传输大量消息，消息丢失可能导致并行程序出错。 流量控制机制通常旨在避免网络拥塞，以保证消息的快速传输。链路级流量控制机制是其中一个重要方面，它考虑网络单个链路上的消息或数据包传输。假设一个数据包要从交换机 A 传输到交换机 B，如果 A 和 B 之间的链路空闲，数据包可以从 A 的输出端口传输到 B 的输入端口，再转发到 B 的合适输出端口；但如果 B 繁忙，可能没有足够的缓冲区空间存储来自 A 的数据包，此时数据包必须留在 A 的输出缓冲区，直到 B 的输入缓冲区有足够空间。这可能会对 A 之前的交换机产生反向压力，导致网络拥塞。链路级流量控制机制的思路是，当接收交换机的输入缓冲区空间不足时，向发送交换机提供反馈，以防止额外数据包的传输，该反馈会在网络中快速反向传播，直到到达原始发送节点，发送节点可以降低传输速率以避免数据包延迟。 然而，链路级流量控制可能反馈传播速度过慢，在到达原始发送者时网络可能已经拥塞。端到端流量控制直接向原始发送者提供反馈，可能会导致更快的反应，如 TCP 协议使用的窗口机制，发送者可以根据接收者的可用缓冲区空间调整发送的数据包数量，以避免缓冲区溢出。 #### 2. 缓存与内存层次结构 在过去几十年的硬件发展中，处理器周期时间和主内存访问时间之间的差距不断增大。主内存基于动态随机存取存储器（DRAM）构建，典型的 DRAM 芯片内存访问时间在 20 - 70 纳秒之间，而 3 GHz 的处理器周期时间仅为 0.33 纳秒，这意味着主内存访问需要 60 - 200 个周期。为了有效利用处理器周期，通常使用内存层次结构，它由多个不同大小和访问时间的内存级别组成。只有层次结构顶部的主内存使用 DRAM，其他级别使用静态随机存取存储器（SRAM），这些内存通常被称为缓存。SRAM 比 DRAM 快得多，但单位面积容量较小且成本更高。使用内存层次结构的目标是从快速内存中访问大部分数据，仅从慢速主内存中访问一小部分数据，从而实现较小的平均内存访问时间。 最简单的内存层次结构是在处理器和主内存之间使用单个缓存（一级缓存，L1 缓存）。缓存包含主内存中数据的子集，并使用替换策略将新数据从主内存带入缓存，替换不再访问的数据元素，目标是将当前最常用的数据元素保留在缓存中。如今，每个处理器通常使用两级或三级缓存，包括小而快的 L1 缓存和更大但较慢的 L2 和 L3 缓存。 在多处理器系统中，每个处理器使用单独的本地缓存时，会出现缓存一致性问题，即必须确保每个处理器访问数据元素时总是访问到最新写入的数据值。对于具有共享地址空间的多处理器，内存层次结构的顶层是所有处理器都可以访问的共享地址空间。内存层次结构的设计会对并行程序的执行时间产生重大影响，因此应合理安排内存访问顺序，以尽可能高效地使用给定的内存层次结构。 缓存是位于处理器和主内存之间的小而快速的内存，由 SRAM 构建。典型的缓存访问时间为 0.5 - 2.5 纳秒，而 DRAM 的访问时间为 50 - 70 纳秒。数据在缓存和主内存之间以块为单位传输，这些块称为缓存块或缓存行，其大小对于给定架构是固定的，在程序执行期间不能更改。 缓存控制由单独的缓存控制器执行，与处理器解耦。在程序执行期间，处理器通过机器程序的加载和存储操作指定要读取或写入的内存地址，并将这些地址转发给内存系统，然后等待相应的值返回或写入。处理器独立于内存系统的组织指定内存地址，不需要了解内存系统的架构。缓存控制器接收到处理器的内存访问请求后，会检查指定的内存地址是否属于当前存储在缓存中的缓存行。如果是，则发生缓存命中，请求的字将从缓存中传递给处理器；如果不是，则发生缓存未命中，缓存行首先从主内存复制到缓存中，然后请求的字再传递给处理器，这个延迟时间称为未命中惩罚。由于主内存访问时间明显长于缓存访问时间，缓存未命中会导致操作数传递延迟，因此应尽量减少缓存未命中的数量。 缓存控制器的具体行为对处理器是隐藏的，处理器会观察到一些内存访问比其他访问花费更长时间，导致操作数传递延迟。在延迟期间，处理器可以执行与延迟操作数无关的其他操作，还可以使用操作数预取等技术支持预期的操作数加载，以便执行其他独立操作。 程序的缓存未命中数量可能对程序的运行时间产生重大影响。如果许多内存访问导致缓存未命中，处理器可能经常需要等待操作数，程序执行可能会很慢。由于缓存管理由硬件实现，程序员不能直接指定在程序执行的哪个时刻哪些数据应驻留在缓存中，但程序中内存访问的顺序会对运行时间产生很大影响，重新排序内存访问可能会显著减少程序执行时间。在这种情况下，内存访问的局部性常被用来描述程序的内存访问特征，可以分为空间局部性和时间局部性： - **空间局部性**：如果程序在执行过程中连续时间点经常访问相邻地址的内存位置，则该程序的内存访问具有高空间局部性。对于具有高空间局部性的程序，在访问一个内存位置后，通常会很快访问同一缓存行中的一个或多个其他内存位置。在这种情况下，加载一个缓存块后，可以从该缓存块中加载后续的几个内存位置，从而避免昂贵的缓存未命中。使用包含多个内存字的缓存块是基于大多数程序具有空间局部性的假设，即加载一个缓存块后，在该缓存块被替换之前会访问其中的多个内存字。 - **时间局部性**：如果程序在执行过程中连续时间点经常多次访问同一内存位置，则该程序的内存访问具有高时间局部性。对于具有高时间局部性的程序，在将一个缓存块加载到缓存后，通常会在该缓存块被替换之前多次访问其中的内存字。 对于空间局部性小的程序，加载一个缓存块后，可能只访问其中一个内存字就被另一个缓存块替换；对于时间局部性小的程序，加载一个缓存块后，对应的内存位置可能只被访问一次就被替换。为了提高程序的时间或空间局部性，已经提出了许多程序转换方法。 缓存有几个重要特征，包括缓存大小、内存块到缓存块的映射、替换算法和写回策略，下面将详细介绍前两个特征。 - **缓存大小**：在使用相同硬件技术的情