并行与分布式系统架构深度解析

### 并行与分布式系统架构深度解析 #### 1. 引言 在当今计算机领域，并行性已贯穿计算机架构的各个层面。多处理器系统主要由处理器、内存层次结构和互连网络这三个关键部分构成。然而，这三个部分的发展历程大相径庭，将它们整合为一个多处理器系统需要新的解决方案，以确保它们的性能相互匹配。 处理器的发展最为显著。如今，所有处理器均为超标量处理器，能够在每个时钟周期并行执行多条指令。时钟频率的稳步提升，既得益于技术的进步，也得益于流水线技术的广泛应用。但处理器的开发成本高昂且生命周期短暂，因此大多数多处理器制造商都选择采用标准处理器，而非自行研发。 内存方面，DRAM 内存的容量迅速增长，但访问时间的下降幅度却十分有限。以一个 300 - MHz 的 4 路超标量处理器为例，在 50 - ns 的 DRAM 访问时间内，它可以执行约一百条指令。为了缓解 DRAM 访问时间带来的影响，速度更快但容量较小的 SRAM 内存被用作缓存。即便如此，处理器与内存之间的性能差距仍在不断扩大，如今需要多级缓存：一级缓存位于处理器芯片内部，二级缓存位于芯片外部的特定电路板上，未来甚至可能需要三级缓存。因此，未来几年对内存层次结构的研究亟待加强。 从实现角度来看，一块尺寸合理的印刷电路板（如 PC 主板）可以通过共享总线连接 2 个或 4 个（很快将达到 8 个）带有二级缓存的处理器。通过监听机制，可以简单而高效地解决缓存数据的一致性问题。或许，多芯片模块将取代印刷电路板，但这并不会改变系统的模块化特性。那么，如何将这些电路板集群连接起来，以构建更强大的多处理器系统呢？ 近年来，多数解决方案将“中央”内存置于集群中，并通过网络连接这些集群，如 IBM - SP2 使用 Delta 网络，Cray 使用环形网络等。这种方法旨在实现可扩展性，同时也是由于内存带宽不足以同时为所有处理器提供数据。然而，这种方式导致机器成本高昂，许多用户难以承受。而且，由于处理器之间通过消息进行通信，编程难度较大，且通信效率难以控制。部分系统配备了额外的硬件，使得物理上分布的内存可以被视为逻辑上共享的内存。在这类系统中，程序员只需面对一个内存空间，由软件（编译器或操作系统）负责程序和数据的最佳分配。这种内存空间的视图在工作站网络中迅速得到应用，但仅通过软件实现。此类网络具有极高的潜在性能，值得深入挖掘。 不过，对于程序员而言，不能忽视通信介质的物理特性。以当今最强大的处理器为例，每纳秒执行一条指令，而在同一时间内，电信号或光信号仅能传播 20 厘米。因此，由于机器之间的距离，通信时间相对于处理器的周期时间可能变得过长。例如，在 100 米的距离上，单比特的往返时间约为 1 微秒，在此期间处理器可以执行 1000 条指令。预计在未来 5 年，通信时间将保持不变，但处理器执行的指令数量将达到 10000 条，届时软件例程可能不再是数据传输延迟的主要原因。 为了给这些多处理器系统提供数据，输入/输出（I/O）设备也至关重要，主要包括磁盘和网络接口。I/O 设备在逻辑上位于内存层次结构的末端，拥有自己的总线（I/O 总线），并通过桥接器与内存总线相连。大多数情况下，通信采用直接内存访问（DMA）模式。过去，I/O 设备常常被忽视，但随着处理器与 I/O 设备之间性能差距的不断扩大，如今对 I/O 设备的研究日益受到重视。磁盘的发展虽然显著，但与 DRAM 内存类似，主要体现在容量和价格方面，而非性能。处理器性能每年增长 50%，而磁盘访问时间每年仅改善 7%。随着互联网使用的急剧增加，出现了许多计算需求较少但处理大量数据的新应用，这些应用与传统的科学代码在性能评估方面存在很大差异。 #### 2. 超标量处理器 ##### 2.1 简介 从硬件角度来看，RISC 处理器的重大改进在于广泛采用流水线技术，以利用并行性，实现接近每个周期执行一条指令的速率。而超标量处理器同样使用流水线，但它的主要特点是能够并行执行多条指令。 这一能力得益于多个功能单元（算术逻辑单元，ALUs）的存在以及能够在同一周期处理多条指令的流水线。拥有多个功能单元的想法并非新鲜事物，例如 CDC6600 和 IBM360/91 就配备了多个功能单元，但它们的流水线设计仅能在每个周期处理一条指令。因此，这些处理器设置多个功能单元的目的是为了容忍功能单元的延迟，以接近每个周期执行一条指令的速率。 超标量处理器的目标是突破每个周期执行一条指令的限制。其性能由每个周期执行的指令数量来衡量，而非每条指令所需的周期数。超标量处理器的设计峰值速率为每个周期执行 d 条指令，d 即为处理器的度，也就是每个周期能够完成执行并从处理器中退出的并行指令数量。当然，超标量处理器的目标是尽可能接近这个峰值性能。 ##### 2.2 乱序超标量处理器的架构 与 RISC 处理器类似，超标量处理器使用流水线来获取、解码和执行指令，但每个阶段都能并行处理多条指令。典型的流水线包括获取、解码、发布、执行和退出等多个阶段。通常，处理器的度是指每个周期能够退出的指令数量。在解码阶段，这个数量通常与度相同，但在其他阶段可能会有所不同，以补偿超过一个周期的延迟（例如在获取阶段发生缓存缺失，或者指令需要多个周期才能执行完毕）。 例如，可能会有六条指令并行执行，而获取和解码阶段仅能并行处理四条指令。因此，在各个阶段之间需要缓冲区来存储无法立即进入下一阶段的指令。 在大多数超标量处理器中，指令的执行顺序与程序顺序不同。这种乱序执行方式能够更好地利用功能单元，从而实现更高的并行性。假设有一系列指令，第二条指令的操作数已知，而第一条指令由于产生其操作数的指令执行延迟较长尚未完成，那么乱序执行机制会让第二条指令先执行。处理器中需要包含一种机制，用于检测指令的操作数是否准备就绪，以确定该指令是否可以执行。这种方法类似于数据流执行方式，但仅考虑已经获取并解码的指令。 为了保证执行结果的正确性，在指令退出时需要恢复程序顺序。常见的做法是使用一种结构，在指令解码后将其入队，执行完成后按相同顺序出队。 然而，超标量处理器在利用并行性方面存在一些限制： - **处理器架构方面**：包括处理器的度、功能单元的数量和类型、缓冲区的大小等。其中，处理器的度和重排序缓冲区的大小是主要的限制因素。重排序缓冲区与处理器的度密切相关，它存储着处理器已知的指令，并用于恢复指令的执行顺序。 - **程序依赖方面**：这部分将在后续详细讨论。 此外，指令缓冲区用于存储等待执行的指令，这些指令可能是因为操作数未知或功能单元繁忙而等待。指令缓冲区的实现方式有多种，例如可以是一个大的缓冲区（如 PentiumPro），也可以根据指令类型划分为多个子缓冲区（如 MIPS R10000、HP PA - 8000），或者分布在各个功能单元中（如 PowerPC604）。在最后一种情况下，每个缓冲区条目通常被称为保留站。每个周期，这些条目会检查其操作数是否准备就绪，如果就绪，则该指令成为可执行的候选指令，由仲裁器根据一定的策略（通常优先选择最旧的指令）选择要执行的指令。 功能单元的数量和类型也是限制因素，需要谨慎选择。另外，从缓存中获取指令也存在限制，平均每个周期需要获取 d 条指令，但由于所需指令可能跨越两个缓存行，而每个周期只能访问一个缓存行，因此需要引入缓冲区来补偿获取指令数量不足的周期，并可能需要实现一种机制来克服只能访问一个缓存行的限制。 ##### 2.3 克服依赖关系带来的限制 并行性的一个重要约束是指令之间的依赖关系，这些依赖关系可分为编程模型导致的控制依赖和真依赖，以及执行模型导致的反依赖和输出依赖。 - **依赖关系的定义** - **控制依赖**：程序编译后会生成静态程序，但根据输入数据集的不同，会执行不同的指令序列。这是因为程序中存在条件分支，这些分支控制着指令的执行流程。通常，在没有控制指令时，程序会顺序执行下一条指令（程序计数器递增）；当执行控制指令时，程序计数器会更新。因此，分支之后的所有指令都依赖于该分支，因为它们的执行与否取决于分支的结果。 - **数据依赖** - **真依赖**：当一条指令的操作数是另一条指令的结果时，就存在真依赖。这种依赖关系是编程模型固有的。 - **输出依赖**：当两条指令将结果写入同一位置（寄存器或内存）时，会产生输出依赖。 - **反依赖**：如果一条较旧的指令读取某个位置的数据，而另一条指令向该位置写入数据，则会产生反依赖。 - **克服控制依赖** - **分支预测**：控制依赖如果不加以处理，会导致严重的性能损失。因为处理器需要知道分支的结果才能获取分支之后的指令，这在标量处理器中就已经存在问题，而在超标量处理器中更为严重。由于超标量处理器每个阶段会处理多条指令，如果在获取和执行分支之间有 s 个阶段，那么至少 s x d 条指令会被顺序获取，并且在分支结果确定后，很多指令（如无条件分支或已执行的条件分支之后的指令）可能会被丢弃。 为了克服这个问题，需要尽早预测分支的结果，