并行计算机体系结构 - 快速指南

---

---

并行计算机体系结构 - 介绍

在过去的50年中，计算机系统的性能和能力有了巨大的发展。这得益于超大规模集成电路 (VLSI) 技术。VLSI技术允许在单个芯片上容纳大量组件并提高时钟频率。因此，可以同时并行执行更多操作。

并行处理也与数据局部性和数据通信相关。并行计算机体系结构是在任何时间点，在技术和成本限制内，组织所有资源以最大限度地提高性能和可编程性的一种方法。

为什么选择并行架构？

并行计算机体系结构通过使用越来越多的处理器，为计算机系统的发展增添了新的维度。原则上，利用大量处理器实现的性能高于给定时间点单个处理器的性能。

应用趋势

随着硬件容量的提高，对高性能应用程序的需求也随之增加，这反过来又推动了计算机体系结构的发展。

在微处理器时代之前，高性能计算机系统是通过特殊的电路技术和机器组织获得的，这使得它们非常昂贵。现在，高性能计算机系统是通过使用多个处理器获得的，大多数重要和需求量大的应用程序都被编写为并行程序。因此，为了获得更高的性能，需要同时开发并行架构和并行应用程序。

为了提高应用程序的性能，**加速比**是一个关键因素。p个处理器的**加速比**定义为：

$$Speedup(p \ 个处理器)\equiv\frac{Performance(p \ 个处理器)}{Performance(1 \ 个处理器)}$$

对于单个固定问题，

$$计算机系统的性能 = \frac{1}{完成问题所需的时间}$$ $$固定问题的加速比(p \ 个处理器) =\frac{Time(1 \ 个处理器)}{Time(p \ 个处理器)}$$

科学和工程计算

并行架构已成为科学计算（如物理、化学、生物、天文学等）和工程应用（如油藏模拟、气流分析、燃烧效率等）不可或缺的一部分。在几乎所有应用中，对计算输出的可视化都有巨大的需求，这导致了对并行计算发展的需求，以提高计算速度。

商业计算

在商业计算（如视频、图形、数据库、OLTP等）中，也需要高速计算机在指定时间内处理海量数据。桌面使用多线程程序，这几乎类似于并行程序。这反过来也需要开发并行架构。

技术趋势

随着技术和体系结构的发展，对高性能应用程序的需求越来越强烈。实验表明，并行计算机的工作速度远快于最先进的单处理器。此外，并行计算机可以在技术和成本限制内开发。

这里使用的主要技术是VLSI技术。因此，现在可以在相同面积内安装越来越多的晶体管、门和电路。随着基本VLSI特征尺寸的减小，时钟频率也与其成比例地提高，而晶体管数量则按平方增长。同时使用许多晶体管（并行性）可以预期比提高时钟频率获得更好的性能。

技术趋势表明，基本的单芯片构建块将提供越来越大的容量。因此，在单个芯片上放置多个处理器的可能性增加了。

架构趋势

技术发展决定了什么才是可行的；体系结构将技术的潜力转化为性能和能力。并行性和局部性是两种方法，其中更大的资源量和更多晶体管可以提高性能。然而，这两种方法竞争相同的资源。当多个操作并行执行时，执行程序所需的周期数减少了。

但是，需要资源来支持每个并发活动。还需要资源来分配本地存储。通过使用资源来利用一定程度的并行性和一定程度的局部性，可以实现最佳性能。

通常，计算机体系结构的历史被划分为四个世代，它们具有以下基本技术：

• 真空管
• 晶体管
• 集成电路
• VLSI

直到1985年，这一时期都由位级并行性的增长主导。4位微处理器之后是8位、16位等等。为了减少执行完整的32位操作所需的周期数，数据路径的宽度加倍了。后来，引入了64位操作。

指令级并行性的增长主导了80年代中期到90年代中期。RISC方法表明，对指令处理步骤进行流水线处理很简单，因此平均而言，几乎每个周期都会执行一条指令。编译器技术的进步使指令流水线效率更高。

在80年代中期，基于微处理器的计算机包括：

• 一个整数处理单元
• 一个浮点单元
• 一个缓存控制器
• 用于缓存数据的SRAM
• 标签存储

随着芯片容量的增加，所有这些组件都被合并到单个芯片中。因此，单个芯片包含用于整数运算、浮点运算、内存运算和分支运算的独立硬件。除了对单个指令进行流水线处理外，它还一次获取多条指令，并在可能的情况下将它们并行发送到不同的功能单元。这种指令级并行性称为超标量执行。

并行架构的融合

并行机已经开发出几种不同的架构。在本节中，我们将讨论不同的并行计算机体系结构及其融合的性质。

通信架构

并行架构通过通信架构增强了传统计算机体系结构的概念。计算机体系结构定义了关键的抽象（如用户-系统边界和硬件-软件边界）和组织结构，而通信体系结构定义了基本的通信和同步操作。它还解决了组织结构。

编程模型是顶层。应用程序是用编程模型编写的。并行编程模型包括：

• 共享地址空间
• 消息传递
• 数据并行编程

共享地址编程就像使用公告板一样，在那里可以通过在特定位置发布信息与一个人或多个人进行沟通，而这个位置由所有其他人共享。个体活动通过记录谁在执行什么任务来协调。

消息传递就像电话或信件一样，其中特定接收者从特定发送者接收信息。

数据并行编程是一种有组织的合作形式。在这里，几个人同时对数据集的各个元素执行操作，并全局共享信息。

共享内存

共享内存多处理器是最重要的并行机器类别之一。它在多编程工作负载上提供更好的吞吐量，并支持并行程序。

在这种情况下，所有计算机系统都允许处理器和一组I/O控制器通过某种硬件互连访问一组内存模块。通过添加内存模块来增加内存容量，并通过向I/O控制器添加设备或添加额外的I/O控制器来增加I/O容量。可以通过等待更快的处理器可用或添加更多处理器来提高处理能力。

所有资源都围绕一个中央内存总线组织。通过总线访问机制，任何处理器都可以访问系统中的任何物理地址。由于所有处理器到所有内存位置的距离相等，因此所有处理器对内存位置的访问时间或延迟相同。这称为对称多处理器。

消息传递架构

消息传递架构也是一类重要的并行机器。它提供作为显式I/O操作的处理器间通信。在这种情况下，通信在I/O级别组合，而不是在内存系统中。

在消息传递架构中，用户通信通过使用执行许多更低级别操作的操作系统或库调用来执行，其中包括实际的通信操作。结果，在编程模型和物理硬件级别的通信操作之间存在距离。

发送和接收是消息传递系统中最常见的用户级通信操作。发送指定本地数据缓冲区（要传输的数据）和接收远程处理器。接收指定发送进程和放置传输数据的本地数据缓冲区。在发送操作中，将标识符或标签附加到消息，并且接收操作指定匹配规则，例如来自特定处理器的特定标签或来自任何处理器的任何标签。

发送和匹配接收的组合完成内存到内存的复制。每一端都指定其本地数据地址和成对的同步事件。

融合

硬件和软件的发展模糊了共享内存和消息传递阵营之间的界限。消息传递和共享地址空间代表了两种不同的编程模型；每个模型都提供了一种透明的共享、同步和通信范例。但是，基本的机器结构已经融合成一个共同的组织。

数据并行处理

另一类重要的并行机被称为处理器阵列、数据并行架构和单指令多数据 (SIMD) 机。该编程模型的主要特点是可以在大型规则数据结构（如数组或矩阵）的每个元素上并行执行操作。

数据并行编程语言通常通过查看一组进程（每个处理器一个）的局部地址空间来实现，这些空间形成一个明确的全局空间。由于所有处理器都一起通信，并且对所有操作都有全局视图，因此可以使用共享地址空间或消息传递。

基本设计问题

仅开发编程模型并不能提高计算机的效率，仅开发硬件也无法做到这一点。然而，计算机体系结构的发展可以改变计算机的性能。我们可以通过关注程序如何使用机器以及提供了哪些基本技术来理解设计问题。

在本节中，我们将讨论通信抽象和编程模型的基本要求。

通信抽象

通信抽象是编程模型和系统实现之间主要的接口。它就像指令集一样，提供了一个平台，使相同的程序可以在许多实现上正确运行。此级别的操作必须简单。

通信抽象就像硬件和软件之间的契约，允许彼此灵活改进，而不会影响工作。

编程模型要求

并行程序有一个或多个线程操作数据。并行编程模型定义了线程可以命名哪些数据，可以对命名数据执行哪些操作，以及操作遵循哪个顺序。

为了确认程序之间的依赖关系得到强制执行，并行程序必须协调其线程的活动。

并行计算机体系结构 - 模型

并行处理已发展成为现代计算机中的一项有效技术，以满足现实应用中对更高性能、更低成本和更准确结果的需求。由于多程序设计、多处理或多计算机的实践，当今计算机中的并发事件很常见。

现代计算机拥有强大而广泛的软件包。要分析计算机性能的发展，首先必须了解硬件和软件的基本发展。

• 计算机发展里程碑 - 计算机发展有两个主要阶段：机械或机电部件。现代计算机是在引入电子元件后发展起来的。电子计算机中高迁移率的电子取代了机械计算机中的操作部件。对于信息传输，以接近光速传播的电信号取代了机械齿轮或杠杆。

• 现代计算机的组成元素 - 现代计算机系统由计算机硬件、指令集、应用程序、系统软件和用户界面组成。

计算问题分为数值计算、逻辑推理和事务处理。一些复杂的问题可能需要所有三种处理模式的组合。

• 计算机体系结构的演变 - 在过去的四十年中，计算机体系结构经历了革命性的变化。我们从冯·诺依曼体系结构开始，现在有了多计算机和多处理器。

• 计算机系统的性能 - 计算机系统的性能取决于机器能力和程序行为。机器能力可以通过更好的硬件技术、先进的体系结构特性和高效的资源管理来提高。程序行为是不可预测的，因为它取决于应用程序和运行时条件。

多处理器和多计算机

在本节中，我们将讨论两种类型的并行计算机：

• 多处理器
• 多计算机

共享内存多计算机

三种最常见的共享内存多处理器模型是：

统一内存访问 (UMA)

在此模型中，所有处理器都统一共享物理内存。所有处理器对所有内存字的访问时间都相同。每个处理器可能都有一个私有缓存内存。外围设备也遵循相同的规则。

当所有处理器都能平等地访问所有外围设备时，该系统称为对称多处理器。当只有一个或少数处理器可以访问外围设备时，该系统称为非对称多处理器。

非统一内存访问 (NUMA)

在 NUMA 多处理器模型中，访问时间随内存字的位置而变化。在这里，共享内存在所有处理器之间物理分布，称为局部内存。所有局部内存的集合构成一个全局地址空间，所有处理器都可以访问该空间。

仅缓存内存体系结构 (COMA)

COMA 模型是 NUMA 模型的特例。在这里，所有分布式主内存都转换为缓存内存。

• 分布式内存多计算机 - 分布式内存多计算机系统由多个计算机（称为节点）组成，这些计算机通过消息传递网络互连。每个节点充当具有处理器、局部内存和有时是 I/O 设备的自主计算机。在这种情况下，所有局部内存都是私有的，只有本地处理器可以访问。这就是为什么传统机器被称为无远程内存访问 (NORMA) 机器的原因。

多向量和 SIMD 计算机

在本节中，我们将讨论用于向量处理和数据并行的超级计算机和并行处理器。

向量超级计算机

在向量计算机中，向量处理器作为可选功能附加到标量处理器。主机计算机首先将程序和数据加载到主内存中。然后，标量控制单元解码所有指令。如果解码的指令是标量操作或程序操作，则标量处理器使用标量功能流水线执行这些操作。

另一方面，如果解码的指令是向量操作，则指令将被发送到向量控制单元。

SIMD 超级计算机

在 SIMD 计算机中，'N' 个处理器连接到一个控制单元，并且所有处理器都有各自的内存单元。所有处理器都通过互连网络连接。

PRAM 和 VLSI 模型

理想模型为开发并行算法提供了一个合适的框架，无需考虑物理约束或实现细节。

可以强制执行这些模型以获得并行计算机上的理论性能界限，或者在制造芯片之前评估芯片面积和运行时间的 VLSI 复杂性。

并行随机存取机

Sheperdson 和 Sturgis (1963) 将传统的单处理器计算机建模为随机存取机 (RAM)。Fortune 和 Wyllie (1978) 开发了一种并行随机存取机 (PRAM) 模型，用于对具有零内存访问开销和同步的理想化并行计算机进行建模。

一个 N 处理器 PRAM 有一个共享内存单元。此共享内存可以集中或分布在处理器之间。这些处理器在同步读内存、写内存和计算周期上运行。因此，这些模型指定了如何处理并发读写操作。

以下是可能的内存更新操作：

• 独占读取 (ER) - 在此方法中，在每个周期中，只有一个处理器允许从任何内存位置读取。

• 独占写入 (EW) - 在此方法中，允许至少一个处理器一次写入内存位置。

• 并发读取 (CR) - 它允许多个处理器在同一周期内从同一内存位置读取相同的信息。

• 并发写入 (CW) - 它允许同时写入同一内存位置。为了避免写冲突，设置了一些策略。

VLSI 复杂度模型

并行计算机使用 VLSI 芯片制造处理器阵列、内存阵列和大型交换网络。

如今，VLSI 技术是二维的。VLSI 芯片的大小与该芯片中可用的存储（内存）空间量成正比。

我们可以通过该算法的 VLSI 芯片实现的芯片面积 (A) 来计算算法的空间复杂度。如果 T 是执行算法所需的时间（延迟），则 A.T 给出了通过芯片处理的总位数的上限 (或 I/O)。对于某些计算，存在一个下限 f(s)，使得

A.T² >= O (f(s))

其中 A=芯片面积，T=时间

体系结构发展轨迹

并行计算机的演变沿着以下轨迹发展：

• 多处理器轨迹
  • 多处理器轨迹
  • 多计算机轨迹
• 多数据轨迹
  • 向量轨迹
  • SIMD 轨迹
• 多线程轨迹
  • 多线程轨迹
  • 数据流轨迹

在多处理器轨迹中，假设不同的线程在不同的处理器上并发执行，并通过共享内存（多处理器轨迹）或消息传递（多计算机轨迹）系统进行通信。

在多数据轨迹中，假设相同的代码在海量数据上执行。这是通过对一系列数据元素执行相同的指令（向量轨迹）或通过对相似的数据集执行相同的指令序列（SIMD 轨迹）来完成的。

在多线程轨迹中，假设在同一处理器上交错执行各种线程以隐藏在不同处理器上执行的线程之间的同步延迟。线程交错可以是粗略的（多线程轨迹）或精细的（数据流轨迹）。

并行系统中的处理器

在 80 年代，一种名为Transputer的专用处理器很流行，用于制造多计算机。Transputer 由一个核心处理器、一个小 SRAM 内存、一个 DRAM 主内存接口和四个通信通道组成，所有这些都集成在一个芯片上。为了进行并行计算机通信，通道被连接起来形成一个 Transputer 网络。但它缺乏计算能力，因此无法满足并行应用程序日益增长的需求。这个问题通过开发 RISC 处理器得到了解决，而且价格也很便宜。

现代并行计算机使用微处理器，这些微处理器在多个级别上使用并行性，例如指令级并行性和数据级并行性。

高性能处理器

RISC 和 RISCy 处理器主导着当今的并行计算机市场。

传统 RISC 的特点是：

• 寻址模式少。
• 指令格式固定，通常为 32 位或 64 位。
• 具有专门的加载/存储指令，用于将数据从内存加载到寄存器，并将数据从寄存器存储到内存。
• 算术运算始终在寄存器上执行。
• 使用流水线技术。

如今大多数微处理器都是超标量处理器，即在并行计算机中使用多个指令流水线。因此，超标量处理器可以同时执行多条指令。超标量处理器的效率取决于应用程序中可用的指令级并行性 (ILP)。为了保持流水线满负荷运行，硬件级别上的指令执行顺序与程序顺序不同。

许多现代微处理器使用 *超流水线* 技术。在 *超流水线* 中，为了提高时钟频率，减少流水线每个阶段的工作量，并增加流水线阶段的数量。

超长指令字 (VLIW) 处理器

这些处理器源于水平微程序设计和超标量处理。VLIW 处理器中的指令非常长。单条指令内的操作并行执行，并转发到相应的功能单元执行。因此，在获取 VLIW 指令后，对其操作进行解码。然后将操作调度到功能单元，在其中并行执行。

向量处理器

向量处理器是通用微处理器的协处理器。向量处理器通常是寄存器-寄存器或内存-内存类型的。向量指令被获取和解码，然后对操作数向量的每个元素执行特定操作，而在普通处理器中，向量操作需要代码中的循环结构。为了提高效率，向量处理器将多个向量操作链接在一起，即一个向量操作的结果作为另一个操作数转发。

缓存

缓存是高性能微处理器的重要组成部分。每 18 个月，微处理器的速度就会翻倍，但主内存的 DRAM 芯片无法与之匹敌。因此，引入缓存来弥合处理器和内存之间的速度差距。缓存是一种快速的小型 SRAM 内存。现代处理器中应用了更多缓存，例如转换旁路缓冲区 (TLB) 缓存、指令缓存和数据缓存等。

直接映射缓存

在直接映射缓存中，使用“模”函数将主内存中的地址一对一映射到缓存位置。由于相同的缓存条目可以映射多个主内存块，因此处理器必须能够确定缓存中的数据块是否为实际需要的数据块。此标识通过将标签与缓存块一起存储来完成。

全相联缓存

全相联映射允许将缓存块放置在缓存中的任何位置。通过使用某种替换策略，缓存确定存储缓存块的缓存条目。全相联缓存具有灵活的映射，可以最大限度地减少缓存条目冲突。由于全相联实现成本高昂，因此从未大规模使用。

组相联缓存

组相联映射是直接映射和全相联映射的组合。在这种情况下，缓存条目被细分为缓存组。与直接映射一样，内存块到缓存组的映射是固定的。但在缓存组内，内存块以全相联方式映射。

缓存策略

除了映射机制之外，缓存还需要一系列策略来指定在某些事件发生时应该发生什么。对于（组）相联缓存，缓存必须确定哪个缓存块应该被进入缓存的新块替换。

一些众所周知的替换策略包括：

• 先进先出 (FIFO)
• 最近最少使用 (LRU)

多处理器和多计算机

本章将讨论多处理器和多计算机。

多处理器系统互连

并行处理需要使用高效的系统互连来实现输入/输出和外围设备、多处理器和共享内存之间的快速通信。

分层总线系统

分层总线系统由连接计算机中各种系统和子系统/组件的总线层次结构组成。每个总线由许多信号线、控制线和电源线组成。本地总线、背板总线和 I/O 总线等不同总线用于执行不同的互连功能。

本地总线是在印刷电路板上实现的总线。背板总线是一个印刷电路，在其上使用许多连接器来插入功能板。连接输入/输出设备到计算机系统的总线称为 I/O 总线。

交叉开关和多端口内存

交换网络在输入和输出之间提供动态互连。小型或中型系统主要使用交叉开关网络。如果可以解决延迟增加的问题，多级网络可以扩展到更大的系统。

交叉开关和多端口内存组织都是单级网络。虽然单级网络的构建成本较低，但可能需要多次才能建立某些连接。多级网络具有多个交换盒阶段。这些网络应该能够将任何输入连接到任何输出。

多级网络和组合网络

多级网络或多级互连网络是一类高速计算机网络，主要由网络一端的处理单元和另一端的内存单元以及连接它们的交换单元组成。

这些网络用于构建更大的多处理器系统。这包括 Omega 网络、蝴蝶网络等等。

多计算机

多计算机是分布式内存 MIMD 架构。下图显示了多计算机的概念模型。

多计算机是消息传递机，它应用分组交换方法来交换数据。在这里，每个处理器都有一个私有内存，但没有全局地址空间，因为处理器只能访问其自己的本地内存。因此，通信不是透明的：程序员必须在其代码中显式地放置通信原语。

没有全局可访问的内存是多计算机的一个缺点。这可以通过使用以下两种方案来解决：

• 虚拟共享内存 (VSM)
• 共享虚拟内存 (SVM)

在这些方案中，应用程序程序员假定一个大的全局可寻址共享内存。如果需要，应用程序进行的内存引用将转换为消息传递范例。

虚拟共享内存 (VSM)

VSM 是硬件实现。因此，操作系统的虚拟内存系统透明地实现于 VSM 之上。因此，操作系统认为它正在一台具有共享内存的机器上运行。

共享虚拟内存 (SVM)

SVM 是操作系统级别的软件实现，并得到处理器内存管理单元 (MMU) 的硬件支持。在这里，共享的单元是操作系统内存页。

如果处理器寻址特定内存位置，MMU 将确定与内存访问关联的内存页是否在本地内存中。如果该页不在内存中，在普通的计算机系统中，它将由操作系统从磁盘交换进来。但在 SVM 中，操作系统从拥有该特定页的远程节点获取该页。

三代多计算机

在本节中，我们将讨论三代多计算机。

过去的設計選擇

在选择处理器技术时，多计算机设计者选择低成本的中粒度处理器作为构建块。大多数并行计算机都是使用标准的现成微处理器构建的。为多计算机选择分布式内存，而不是使用共享内存，这将限制可扩展性。每个处理器都有它自己的本地内存单元。

对于互连方案，多计算机具有消息传递、点对点直接网络，而不是地址交换网络。对于控制策略，多计算机的设计者选择异步 MIMD、MPMD 和 SMPD 操作。加州理工学院的 Cosmic Cube (Seitz, 1983) 是第一代多计算机的先驱。

当前和未来的发展

下一代计算机从使用全局共享虚拟内存的中粒度到细粒度多计算机发展而来。第二代多计算机目前仍在使用。但是，使用更好的处理器（如 i386、i860 等），第二代计算机得到了很大的发展。

第三代计算机是下一代计算机，其中将使用 VLSI 实现的节点。每个节点可能具有一个 14-MIPS 处理器、20-Mbytes/s 路由通道和 16 KB 的 RAM 集成在一个芯片上。

英特尔 Paragon 系统

以前，使用同构节点来制造超立方体多计算机，因为所有功能都由主机提供。因此，这限制了 I/O 带宽。因此，为了有效地或以高吞吐量解决大型问题，这些计算机无法使用。英特尔 Paragon 系统旨在克服这一困难。它将多计算机变成了具有网络环境中多用户访问的应用程序服务器。

消息传递机制

多计算机网络中的消息传递机制需要特殊的硬件和软件支持。在本节中，我们将讨论一些方案。

消息路由方案

在使用存储转发路由方案的多计算机中，数据包是最小的信息传输单元。在 wormhole 路由网络中，数据包进一步细分为 flit。数据包长度由路由方案和网络实现确定，而 flit 长度受网络大小的影响。

在 **存储转发路由** 中，数据包是信息传输的基本单元。在这种情况下，每个节点使用数据包缓冲区。数据包通过一系列中间节点从源节点传输到目标节点。延迟与源节点和目标节点之间的距离成正比。

在 **wormhole 路由** 中，从源节点到目标节点的传输是通过一系列路由器完成的。同一数据包的所有 flit 以不可分割的序列以流水线方式传输。在这种情况下，只有报头 flit 知道数据包的去向。

死锁和虚拟通道

虚拟通道是两个节点之间的逻辑链路。它由源节点和接收节点中的 flit 缓冲区以及它们之间的物理通道构成。当为一对分配物理通道时，一个源缓冲区与一个接收缓冲区配对以形成虚拟通道。

当所有信道都被消息占用，并且循环中没有任何信道被释放时，就会发生死锁情况。为避免这种情况，必须遵循死锁避免方案。

缓存一致性和同步

本章将讨论用于应对多缓存不一致问题的缓存一致性协议。

缓存一致性问题

在多处理器系统中，数据不一致可能发生在内存层次结构的相邻级别之间或同一级别内。例如，缓存和主内存可能拥有同一对象的副本不一致。

由于多个处理器并行且独立地运行，多个缓存可能拥有同一内存块的不同副本，这就产生了**缓存一致性问题**。**缓存一致性方案**通过维护每个缓存数据块的统一状态来帮助避免此问题。

设 X 为共享数据的元素，已被两个处理器 P1 和 P2 引用。一开始，X 的三个副本是一致的。如果处理器 P1 将新的数据 X1 写入缓存，使用**直写策略**，则相同的副本将立即写入共享内存。在这种情况下，缓存内存和主内存之间会发生不一致。当使用**写回策略**时，只有当缓存中修改后的数据被替换或失效时，主内存才会被更新。

一般来说，有不一致性问题的三个来源：

• 共享可写数据
• 进程迁移
• I/O 活动

窥探总线协议

窥探协议通过基于总线的内存系统实现缓存内存和共享内存之间的数据一致性。**写无效**和**写更新**策略用于维护缓存一致性。

在这种情况下，我们有三个处理器 P1、P2 和 P3，它们的本地缓存内存和共享内存中都有数据元素“X”的一致副本（图 a）。处理器 P1 使用**写无效协议**将其缓存内存中的 X 写入 X1。因此，所有其他副本都通过总线失效。它用“I”表示（图 b）。失效的块也称为**脏块**，即它们不应该被使用。**写更新协议**通过总线更新所有缓存副本。使用**写回缓存**，内存副本也会更新（图 c）。

缓存事件和操作

在执行内存访问和失效命令时，会发生以下事件和操作：

• **读未命中** - 当处理器想要读取一个块，而该块不在缓存中时，就会发生读未命中。这会启动**总线读取**操作。如果不存在脏副本，则拥有一致副本的主内存会向请求缓存内存提供副本。如果在远程缓存内存中存在脏副本，则该缓存将限制主内存并向请求缓存内存发送副本。在这两种情况下，缓存副本在读未命中后将进入有效状态。

• **写命中** - 如果副本处于脏状态或**保留**状态，则在本地进行写入，新状态为脏状态。如果新状态有效，则将广播写无效命令到所有缓存，使它们的副本失效。当共享内存被直写时，在此第一次写入后，结果状态为保留。

• **写未命中** - 如果处理器无法写入本地缓存内存，则副本必须来自主内存或具有脏块的远程缓存内存。这是通过发送**读无效**命令来完成的，该命令将使所有缓存副本失效。然后，本地副本将更新为脏状态。

• **读命中** - 读命中始终在本地缓存内存中执行，不会导致状态转换或使用窥探总线进行失效。

• **块替换** - 当副本为脏副本时，将通过块替换方法将其写回主内存。但是，当副本处于有效、保留或无效状态时，不会发生替换。

基于目录的协议

通过使用多级网络构建具有数百个处理器的较大多处理器，需要修改窥探缓存协议以适应网络功能。由于在多级网络中执行广播非常昂贵，因此一致性命令仅发送到保留块副本的那些缓存。这就是为网络连接的多处理器开发基于目录的协议的原因。

在基于目录的协议系统中，要共享的数据被放置在一个公共目录中，该目录维护缓存之间的一致性。在这里，目录充当过滤器，处理器请求许可将条目从主内存加载到其缓存内存中。如果更改了条目，目录会更新它或使具有该条目的其他缓存失效。

硬件同步机制

同步是一种特殊的通信形式，其中，信息不是数据控制，而是在驻留在相同或不同处理器中的通信进程之间交换。

多处理器系统使用硬件机制来实现低级同步操作。大多数多处理器都具有硬件机制来强制执行原子操作，例如内存读、写或读-修改-写操作，以实现一些同步原语。除了原子内存操作之外，还有一些处理器间中断用于同步目的。

共享内存机中的缓存一致性

当处理器包含本地缓存内存时，在多处理器系统中维护缓存一致性是一个问题。在这个系统中，不同缓存之间的数据不一致很容易发生。

主要关注的领域是：

• 共享可写数据
• 进程迁移
• I/O 活动

共享可写数据

当两个处理器（P1 和 P2）在其本地缓存中具有相同的数据元素（X），并且一个进程（P1）写入数据元素（X）时，由于 P1 的缓存是直写本地缓存，主内存也会更新。现在，当 P2 尝试读取数据元素（X）时，它找不到 X，因为 P2 缓存中的数据元素已过时。

进程迁移

在第一阶段，P1 的缓存具有数据元素 X，而 P2 没有任何内容。P2 上的一个进程首先写入 X，然后迁移到 P1。现在，进程开始读取数据元素 X，但是由于处理器 P1 拥有过时的数据，因此进程无法读取它。因此，P1 上的一个进程写入数据元素 X，然后迁移到 P2。迁移后，P2 上的一个进程开始读取数据元素 X，但它在主内存中发现 X 的过时版本。

I/O 活动

如图所示，I/O 设备添加到双处理器多处理器体系结构中的总线。一开始，两个缓存都包含数据元素 X。当 I/O 设备接收到新的元素 X 时，它会将新元素直接存储到主内存中。现在，当 P1 或 P2（假设为 P1）尝试读取元素 X 时，它会获得过时的副本。因此，P1 写入元素 X。现在，如果 I/O 设备尝试传输 X，它会获得过时的副本。

统一内存访问 (UMA)

统一内存访问 (UMA) 体系结构意味着共享内存对于系统中的所有处理器都是相同的。常用的 UMA 机器类别（通常用于（文件）服务器）是所谓的对称多处理器 (SMP)。在 SMP 中，所有系统资源（如内存、磁盘、其他 I/O 设备等）都可由处理器以统一的方式访问。

非统一内存访问 (NUMA)

在 NUMA 体系结构中，有多个具有内部间接/共享网络的 SMP 集群，它们连接在可扩展的消息传递网络中。因此，NUMA 体系结构在逻辑上是共享的，在物理上是分布式内存体系结构。

在 NUMA 机器中，处理器的缓存控制器确定内存引用是本地于 SMP 的内存还是远程的。为了减少远程内存访问的数量，NUMA 体系结构通常应用可以缓存远程数据的缓存处理器。但是，当涉及缓存时，需要维护缓存一致性。因此，这些系统也称为 CC-NUMA（缓存一致性 NUMA）。

仅缓存内存体系结构 (COMA)

COMA 机器类似于 NUMA 机器，唯一的区别是 COMA 机器的主内存充当直接映射或组相联缓存。数据块根据其地址被哈希到 DRAM 缓存中的一个位置。远程获取的数据实际上存储在本地主内存中。此外，数据块没有固定的主位置，它们可以自由地在系统中移动。

COMA 体系结构大多具有分层消息传递网络。此类树中的交换机包含一个目录，其数据元素作为其子树。由于数据没有主位置，因此必须显式搜索它。这意味着远程访问需要沿着树中的交换机进行遍历以搜索其目录中所需的数据。因此，如果网络中的交换机从其子树接收到对相同数据的多个请求，它会将它们组合成一个单一请求，然后将其发送到交换机的父节点。当请求的数据返回时，交换机会将其多个副本向下发送到其子树。

COMA 与 CC-NUMA 的比较

以下是 COMA 和 CC-NUMA 之间的区别。

• COMA 往往比 CC-NUMA 更灵活，因为 COMA 透明地支持数据的迁移和复制，而无需操作系统。

• COMA 机器构建起来昂贵且复杂，因为它们需要非标准的内存管理硬件，并且一致性协议更难实现。

• COMA 中的远程访问通常比 CC-NUMA 中的远程访问慢，因为需要遍历树网络才能找到数据。

硬件软件权衡

有很多方法可以降低硬件成本。一种方法是将通信辅助和网络更松散地集成到处理节点中，并增加通信延迟和占用率。

另一种方法是在软件而非硬件中提供自动复制和一致性。后者在主内存中提供复制和一致性，并且可以以各种粒度执行。它允许使用现成的商品部件作为节点和互连，从而最大限度地降低硬件成本。但这给程序员带来了实现良好性能的压力。

宽松的内存一致性模型

共享地址空间的内存一致性模型定义了内存操作在相同或不同位置上的执行顺序的约束。实际上，任何支持共享地址空间命名模型的系统层都必须具有内存一致性模型，其中包括程序员接口、用户系统接口和硬件软件接口。与该层交互的软件必须了解其自身的内存一致性模型。

系统规格

体系结构的系统规范指定内存操作的排序和重新排序，以及实际可以从中获得多少性能。

以下是使用程序顺序中的放松的一些规范模型：

• 放松写-读程序顺序 - 此类模型允许硬件抑制一级缓存内存中错过的写操作的延迟。当写未命中在写缓冲区中并且对其他处理器不可见时，处理器可以完成在其缓存内存中命中的读操作，甚至可以完成在其缓存内存中未命中的单个读操作。

• 放松写-读和写-写程序顺序 - 允许写绕过先前对各种位置的未完成写操作，可以让多个写操作在更新主内存之前合并到写缓冲区中。因此，多个写未命中可以重叠并无序地可见。其动机是进一步最大限度地减少写延迟对处理器中断时间的影响，并通过使新的数据值对其他处理器可见来提高处理器之间的通信效率。

• 放松所有程序顺序 - 默认情况下，除了进程内的数据和控制依赖性之外，没有任何程序顺序得到保证。因此，其好处是多个读取请求可以同时处于未完成状态，并且程序顺序可以被后面的写入绕过，并且它们本身可以无序完成，从而允许我们隐藏读取延迟。这类模型对于动态调度处理器特别有用，动态调度处理器可以继续进行读取未命中以进行其他内存引用。它们允许许多重新排序，甚至消除编译器优化所做的访问。

编程接口

编程接口假设在同步操作之间不需要维护任何程序顺序。确保所有同步操作都明确标记或识别为同步操作。运行时库或编译器将这些同步操作转换为系统规范要求的合适的顺序保持操作。

然后，系统确保顺序一致的执行，即使它可能以任何它想要的方式重新排序同步操作之间的操作，也不会破坏对进程内某个位置的依赖关系。这允许编译器在同步点之间拥有足够的灵活性来进行它想要的重新排序，并且还允许处理器执行其内存模型允许的尽可能多的重新排序。在程序员接口处，一致性模型至少应与硬件接口的一致性模型一样弱，但不一定是相同的。

转换机制

在大多数微处理器中，将标签转换为顺序保持机制相当于在标记为同步的每个操作之前和/或之后插入合适的内存屏障指令。它将节省指示要强制执行哪些排序的单个加载/存储指令，并避免额外的指令。但是，由于这些操作通常很少见，因此这不是大多数微处理器迄今为止采用的方式。

克服容量限制

我们已经讨论了仅在处理器缓存内存中提供硬件自动复制和一致性的系统。处理器缓存在本地主内存中复制之前，会在引用时直接复制远程分配的数据。

这些系统的一个问题是本地复制的范围仅限于硬件缓存。如果一个块从缓存内存中被替换，当它再次需要时，它必须从远程内存中获取。本节中讨论的系统的主要目的是解决复制容量问题，但仍以缓存块的细粒度在硬件中提供一致性以提高效率。

三级缓存

为了解决复制容量问题，一种方法是使用大型但速度较慢的远程访问缓存。当机器的节点本身是小规模多处理器并且可以简单地为了性能而变大时，这对于功能性是必要的。它还将保存已从本地处理器缓存内存中替换的已复制远程块。

仅缓存内存架构 (COMA)

在 COMA 机器中，整个主内存中的每个内存块都带有与其关联的硬件标签。没有固定的节点可以始终保证为内存块分配空间。数据会动态迁移到访问/吸引它们的节点的主内存中，或在其中复制。当访问远程块时，它会在吸引内存中复制并引入缓存，并由硬件保持两者的状态一致。数据块可能驻留在任何吸引内存中，并且可以轻松地从一个内存移动到另一个内存。

降低硬件成本

降低成本意味着将一些专用硬件的功能转移到现有硬件上运行的软件。软件比在硬件缓存中更容易管理主内存中的复制和一致性。低成本方法往往在主内存中提供复制和一致性。为了有效地控制一致性，辅助的其他功能组件都可以从硬件专用化和集成中受益。

研究工作旨在通过不同的方法降低成本，例如通过在专用硬件中执行访问控制，但将其他活动分配给软件和商品硬件。另一种方法是在软件中执行访问控制，并旨在在没有专用硬件支持的商品节点和网络上分配一致的共享地址空间抽象。

对并行软件的影响

宽松的内存一致性模型需要并行程序将所需的冲突访问标记为同步点。编程语言提供支持将某些变量标记为同步，然后编译器会将其转换为合适的顺序保持指令。为了限制编译器自身对共享内存访问的重新排序，编译器本身可以使用标签。

互连网络设计

并行机器中的互连网络将信息从任何源节点传输到任何所需的目的地节点。此任务应以尽可能小的延迟完成。它应该允许大量此类传输同时发生。此外，与机器其余部分的成本相比，它应该便宜。

网络由链路和交换机组成，这有助于将信息从源节点发送到目标节点。网络由其拓扑、路由算法、交换策略和流量控制机制指定。

组织结构

互连网络由以下三个基本组件组成：

• 链路 - 链路是一根或多根光纤或电线的电缆，两端各有一个连接器，连接到交换机或网络接口端口。通过它，模拟信号从一端传输，在另一端接收以获得原始数字信息流。

• 交换机 - 交换机由一组输入和输出端口、连接所有输入到所有输出的内部“交叉开关”、内部缓冲区和控制逻辑组成，以在每个时间点实现输入-输出连接。通常，输入端口的数量等于输出端口的数量。

• 网络接口 - 网络接口的行为与交换机节点大相径庭，并且可能通过专用链路连接。网络接口格式化数据包并构建路由和控制信息。与交换机相比，它可能有输入和输出缓冲区。它可以执行端到端错误检查和流量控制。因此，其成本受其处理复杂性、存储容量和端口数量的影响。

互连网络

互连网络由交换元件组成。拓扑是连接单个交换机到其他元件（如处理器、内存和其他交换机）的模式。网络允许在并行系统中的处理器之间交换数据。

• 直接连接网络 - 直接网络在相邻节点之间具有点对点连接。这些网络是静态的，这意味着点对点连接是固定的。直接网络的一些示例包括环、网格和多维立方体。

• 间接连接网络 - 间接网络没有固定的邻居。通信拓扑可以根据应用程序的需求动态更改。间接网络可以细分为三个部分：总线网络、多级网络和交叉开关。

  • 总线网络 - 总线网络由许多位线组成，许多资源连接到这些位线上。当总线使用相同的物理线路传输数据和地址时，数据线和地址线是时间复用的。当多个总线主控连接到总线时，需要仲裁器。

  • 多级网络 - 多级网络由多个交换机级组成。它由“axb”交换机组成，这些交换机使用特定的级间连接模式 (ISC) 连接。小型 2x2 交换元件是许多多级网络的常见选择。阶段数决定网络的延迟。通过选择不同的级间连接模式，可以创建各种类型的多级网络。

  • 交叉开关 - 交叉开关包含一个简单的交换元件矩阵，可以打开和关闭以建立或断开连接。打开矩阵中的交换元件，就可以在处理器和内存之间建立连接。交叉开关是非阻塞的，即所有通信排列都可以在不阻塞的情况下执行。

评估网络拓扑中的设计权衡

如果主要关注的是路由距离，则必须最大化维度并构建超立方体。在存储转发路由中，假设交换机的度数和链路的数量不是重要的成本因素，并且链路的数量或交换机的度数是主要的成本，则必须最小化维度并构建网格。

在每个网络的最坏情况流量模式下，最好使用高维网络，其中所有路径都很短。在每个节点仅与一两个附近的邻居通信的模式中，最好使用低维网络，因为实际上只使用少数维度。

路由

网络的路由算法确定从源到目标的可能路径中哪条用作路由，以及如何确定每个特定数据包遵循的路由。维度顺序路由限制了合法路径的集合，以便从每个源到每个目标都只有一条路由。通过首先在高阶维度上走正确的距离，然后是下一个维度，依此类推获得。

路由机制

高速交换机使用算术运算、基于源端口的选择和查找表这三种机制来根据数据包头中的信息确定输出信道。所有这些机制都比传统局域网和广域网路由器中实现的通用路由计算更简单。在并行计算机网络中，交换机需要在每个周期内为所有输入做出路由决策，因此该机制需要简单快捷。

确定性路由

如果消息所走的路由完全由其源和目标决定，而不受网络中其他流量的影响，则路由算法是确定性的。如果路由算法只选择到达目的地的最短路径，则它是最小化的，否则是非最小化的。

无死锁

死锁可能发生在各种情况下。当两个节点尝试相互发送数据，并且每个节点都在另一个节点接收之前开始发送时，可能会发生“对头”死锁。另一种死锁的情况是，当多个消息竞争网络中的资源时。

证明网络无死锁的基本技术是清除由于消息通过网络移动而可能发生在信道之间的依赖关系，并证明整个信道依赖图中没有循环；因此，没有可能导致死锁的流量模式。常用的方法是对信道资源进行编号，以便所有路由都遵循特定的递增或递减序列，从而避免出现依赖循环。

交换机设计

网络的设计取决于交换机的设计以及交换机的连接方式。交换机的度数、其内部路由机制及其内部缓冲决定了可以支持哪些拓扑以及可以实现哪些路由算法。与计算机系统的任何其他硬件组件一样，网络交换机包含数据路径、控制和存储。

端口

引脚总数实际上是输入和输出端口总数乘以信道宽度。由于芯片的周长比面积增长缓慢，交换机往往受引脚限制。

内部数据路径

数据路径是每组输入端口与每个输出端口之间的连接。它通常被称为内部交叉开关。非阻塞交叉开关是指每个输入端口可以同时连接到任何排列中的不同输出的交叉开关。

信道缓冲区

交换机内缓冲存储的组织对交换机性能有重要影响。传统的路由器和交换机倾向于在交换机结构外部具有大型 SRAM 或 DRAM 缓冲区，而在 VLSI 交换机中，缓冲区位于交换机内部，并与数据路径和控制部分占用相同的硅片预算。随着芯片尺寸和密度的增加，可用的缓冲区更多，网络设计师拥有更多选择，但缓冲区资源仍然是重要的选择，其组织方式也很重要。

流量控制

当网络中的多个数据流尝试同时使用相同的共享网络资源时，必须采取一些措施来控制这些流。如果我们不想丢失任何数据，则必须阻塞某些流，而其他流则继续进行。

流量控制的问题存在于所有网络和许多层次。但它在并行计算机网络中的性质与在局域网和广域网中的性质有质的区别。在并行计算机中，网络流量需要像通过总线上的流量一样精确地传递，并且在非常短的时间尺度上存在大量并行流。

延迟容忍

微处理器速度每十年增长十倍以上，但商品内存（DRAM）的速度仅翻倍，即访问时间减半。因此，以处理器时钟周期表示的内存访问延迟在10年内增长了六倍。多处理器加剧了这个问题。

在基于总线的系统中，在处理器和内存之间建立高带宽总线往往会增加从内存获取数据的延迟。当内存物理分布时，网络和网络接口的延迟会添加到访问节点上本地内存的延迟中。

延迟通常随着机器规模的增长而增长，因为更多的节点意味着相对于计算而言更多的通信，更普遍的通信需要更多网络跳转，并且可能存在更多争用。硬件设计的目标是减少数据访问延迟，同时保持高可扩展带宽。

延迟容忍概述

最好通过查看机器中的资源以及如何利用它们来了解如何处理延迟容忍。从处理器的角度来看，从一个节点到另一个节点的通信架构可以看作是一个流水线。流水线的阶段包括源和目标处的网络接口，以及沿途的网络链路和交换机。根据体系结构如何管理通信，通信辅助、本地内存/缓存系统和主处理器中也存在阶段。

在基线通信结构中的利用率问题是，在给定时间处理器或通信架构处于繁忙状态，并且在通信流水线中，只有一个阶段在繁忙状态，因为正在传输的单个字从源到目标移动。延迟容忍的目标是尽可能多地重叠这些资源的使用。

显式消息传递中的延迟容忍

消息传递中的实际数据传输通常由发送方发起，使用发送操作。接收操作本身并不促使数据进行通信，而是将数据从传入缓冲区复制到应用程序地址空间。接收方发起的通信是通过向作为数据源的进程发出请求消息来完成的。然后，该进程通过另一个发送操作将数据发送回。

同步发送操作的通信延迟等于将消息中的所有数据传送到目的地所需的时间，以及接收处理的时间，以及返回确认的时间。同步接收操作的延迟是其处理开销；这包括将数据复制到应用程序，以及如果数据尚未到达则会产生额外的延迟。我们希望隐藏这些延迟，如果可能的话，还要隐藏两端的开销。

共享地址空间中的延迟容忍

基线通信是通过共享地址空间中的读写操作进行的。为方便起见，它被称为读写通信。接收方发起的通信是通过读取操作完成的，读取操作会导致访问另一个处理器的内存或缓存中的数据。如果没有共享数据的缓存，则可以通过写入分配在远程内存中的数据来完成发送方发起的通信。

使用缓存一致性，写入的效果更复杂：写入导致发送方或接收方发起的通信取决于缓存一致性协议。无论是接收方发起还是发送方发起，在硬件支持的读写共享地址空间中的通信都是自然细粒度的，这使得容忍延迟非常重要。

共享地址空间中的块数据传输

在共享地址空间中，无论是通过硬件还是软件，数据合并和块传输的启动都可以在用户程序中显式执行，也可以由系统透明地执行。显式块传输是通过在用户程序中执行类似于发送的命令来启动的。发送命令由通信辅助解释，该通信辅助以流水线方式将数据从源节点传输到目标节点。在目标节点，通信辅助从网络接口中提取数据字并将它们存储在指定位置。

与发送-接收消息传递有两个主要区别，这两个区别都源于发送进程可以直接指定程序数据结构，数据将在目标位置放置，因为这些位置位于共享地址空间。

在共享地址空间中处理长延迟事件

如果内存操作是非阻塞的，则处理器可以继续执行其他指令。对于写入，如果写入放入写入缓冲区，并且处理器继续执行，而缓冲区负责向内存系统发出写入并根据需要跟踪其完成，则通常很容易实现这一点。区别在于，与写入不同，读取通常紧随其后的是需要读取返回的值的指令。

共享地址空间中的预通信

预通信是一种已在商用微处理器中广泛采用的技术，其重要性在未来可能会增加。预取指令不会替换数据的实际读取，如果要通过重叠来达到隐藏延迟的目的，则预取指令本身必须是非阻塞的。

在这种情况下，由于共享数据没有缓存，因此预取的数据被带入称为预取缓冲区的特殊硬件结构中。当在下次迭代中将单词实际读取到寄存器中时，它从预取缓冲区的头部读取，而不是从内存读取。如果要隐藏的延迟远大于计算单个循环迭代所需的时间，我们将预取多个迭代，并且预取缓冲区中可能同时存在多个字。

共享地址空间中的多线程

就隐藏不同类型的延迟而言，硬件支持的多线程也许是最通用的技术。它具有以下概念上的优势：

• 它不需要特殊的软件分析或支持。

• 由于它是动态调用的，因此它可以像处理可预测情况一样好地处理不可预测的情况，例如缓存冲突等。

• 与预取一样，它不会更改内存一致性模型，因为它不会重新排序线程内的访问。

• 虽然之前的技术针对的是隐藏内存访问延迟，但多线程可以同样轻松地隐藏任何长延迟事件的延迟，只要可以在运行时检测到该事件即可。这包括同步和指令延迟。

随着延迟与处理器速度相比越来越长，这种趋势可能会在未来发生变化。此外，随着更复杂的微处理器已经提供了可以扩展用于多线程的方法，以及正在开发新的多线程技术以将多线程与指令级并行结合起来，这种趋势在未来肯定会发生一些变化。