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

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

在过去的 50 年里，计算机系统的性能和功能取得了巨大的发展。这在超大规模集成（VLSI）技术的帮助下成为可能。VLSI技术允许在单个芯片上容纳大量组件并提高时钟速率。因此，一次可以并行执行更多操作。

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

为什么采用并行架构？

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

应用趋势

随着硬件能力的进步，对高性能应用程序的需求也随之增加，这反过来又对计算机架构的发展提出了要求。

在微处理器时代之前，高性能计算机系统是通过奇异的电路技术和机器组织来获得的，这使得它们价格昂贵。现在，高性能的计算机系统是通过使用多个处理器来获得的，并且最重要和要求最高的应用程序被编写为并行程序。因此，为了获得更高的性能，需要开发并行架构和并行应用程序。

要提高应用程序的性能，加速是要考虑的关键因素。p 个处理器上的加速定义为 -

$$加速(p \ 处理器)\equiv\frac{性能(p \ 处理器)}{性能(1 \ 处理器)}$$

对于单个固定问题，

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

科学与工程计算

并行架构在科学计算（如物理、化学、生物学、天文学等）和工程应用（如油藏建模、气流分析、燃烧效率等）中已变得不可或缺。在几乎所有的应用中，都对计算输出的可视化有巨大的需求，从而需要开发并行计算以提高计算速度。

商业计算

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

技术趋势

随着技术和架构的发展，对高性能应用程序的开发有强烈的需求。实验表明，并行计算机的工作速度比最先进的单处理器要快得多。而且，在技术和成本的限制内，可以开发并行计算机。

这里使用的主要技术是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 级别而不是内存系统上组合的。

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

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

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

收敛

硬件和软件的发展已经淡化了共享内存和消息传递阵营之间的清晰界限。消息传递和共享地址空间代表两种不同的编程模型；每个都为共享、同步和通信提供了透明的范例。然而，基本的机器结构已经趋向于一个共同的组织。

数据并行处理

另一类重要的并行机有不同的名称：处理器阵列、数据并行架构和单指令多数据机。该编程模型的主要特征是可以对大型常规数据结构（如数组或矩阵）的每个元素并行执行操作。

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

基本设计问题

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

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

通信抽象

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

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

编程模型要求

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

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

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

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

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

计算机发展里程碑- 计算机的发展有两个主要阶段 -机械部分或机电部分。现代计算机是在电子元件引入后发展起来的。电子计算机中的高迁移率电子取代了机械计算机中的操作部件。对于信息传输，几乎以光速传播的电信号取代了机械齿轮或杠杆。
现代计算机的要素-现代计算机系统由计算机硬件、指令集、应用程序、系统软件和用户界面组成。

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

计算机体系结构的演变- 在过去的四十年中，计算机体系结构经历了革命性的变化。我们从冯诺依曼架构开始，现在我们有了多计算机和多处理器。
计算机系统的性能- 计算机系统的性能取决于机器能力和程序Behave。机器能力可以通过更好的硬件技术、先进的架构特性和高效的资源管理来提高。程序Behave是不可预测的，因为它取决于应用程序和运行时条件

多处理器和多计算机

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

多处理器
多电脑

共享内存多计算机

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

统一内存访问 (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 芯片实现的芯片面积 (A) 来计算该算法的空间复杂度。如果 T 是执行算法所需的时间（延迟），则 AT 给出通过芯片（或 I/O）处理的总位数的上限。对于某些计算，存在一个下界 f(s)，使得

AT ² >= O (f(s))

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

建筑发展轨迹

并行计算机的演变我沿着以下轨道传播 -

多处理器轨道
- 多处理器轨道
- 多机轨道
多数据轨
- 矢量轨道
- SIMD轨道
多线程跟踪
- 多线程轨道
- 数据流轨迹

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

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

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

并行系统中的处理器

在 80 年代，一种称为Transputer的专用处理器很流行用于制造多计算机。晶片机由一个核心处理器、一个小型 SRAM 存储器、一个 DRAM 主存储器接口和四个通信通道组成，全部位于单个芯片上。为了进行并行计算机通信，通道被连接起来形成晶片机网络。但其计算能力不足，无法满足并行应用日益增长的需求。RISC处理器的发展解决了这个问题，而且价格便宜。

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

高性能处理器

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

传统 RISC 的特点是 -

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

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

许多现代微处理器使用超级流水线方法。在超级流水线中，为了提高时钟频率，减少了流水线级内完成的工作并增加了流水线级的数量。

超大指令字 (VLIW) 处理器

这些源自水平微编程和超标量处理。VLIW 处理器中的指令非常大。单个指令内的操作并行执行，并转发到适当的功能单元执行。因此，在获取 VLIW 指令后，对其操作进行解码。然后，操作被分派到并行执行的功能单元。

矢量处理器

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

缓存

高速缓存是高性能微处理器的重要元素。每18个月后，微处理器的速度就会增加两倍，但用于主存的DRAM芯片却无法与这个速度竞争。因此，引入高速缓存来弥合处理器和内存之间的速度差距。高速缓存是一种快速且小型的 SRAM 存储器。现代处理器中应用了更多的缓存，例如转换后备缓冲区 (TLB) 缓存、指令和数据缓存等。

直接映射缓存

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

全关联缓存

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

组关联缓存

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

缓存策略

除了映射机制之外，缓存还需要一系列策略来指定在某些事件的情况下应该发生什么。在（设置）关联高速缓存的情况下，高速缓存必须确定哪个高速缓存块将被进入高速缓存的新块替换。

一些著名的替代策略是 -

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

多处理器和多计算机

我们将在本章中讨论多处理器和多计算机。

多处理器系统互连

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

分层总线系统

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

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

交叉开关和多端口存储器

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

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

多级和组合网络

多级网络或多级互连网络是一类高速计算机网络，主要由网络一端的处理元件和另一端的存储元件组成，并通过交换元件连接。

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

多电脑

多计算机是分布式内存 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 系统就是为了克服这一困难而设计的。它将多计算机变成网络环境中具有多用户访问的应用服务器。

消息传递机制

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

消息路由方案

在采用存储转发路由方案的多计算机中，数据包是信息传输的最小单位。在虫洞路由网络中，数据包被进一步划分为 flits。数据包长度由路由方案和网络实现决定，而 flit 长度则受网络规模影响。

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

在虫洞路由中，从源节点到目的节点的传输是通过一系列路由器完成的。同一数据包的所有微片以流水线方式以不可分离的顺序传输。在这种情况下，只有 header flit 知道数据包要去哪里。

死锁和虚拟通道

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

当所有通道都被消息占用并且循环中没有通道被释放时，就会出现死锁情况。为了避免这种情况，必须遵循避免死锁的方案。

缓存一致性和同步

在本章中，我们将讨论缓存一致性协议来应对多缓存不一致问题。

缓存一致性问题

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

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

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

一般来说，不一致问题有三个来源 -

共享可写数据
进程迁移
输入/输出活动

史努比总线协议

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

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

缓存事件和操作

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

读取未命中- 当处理器想要读取一个块但该块不在缓存中时，就会发生读取未命中。这将启动总线读取操作。如果不存在脏副本，则具有一致副本的主存储器向请求高速缓冲存储器提供副本。如果远程高速缓冲存储器中存在脏副本，则该高速缓冲存储器将限制主存储器并将副本发送到请求高速缓冲存储器。在这两种情况下，缓存副本都会在读取未命中后进入有效状态。
Write-hit - 如果副本处于脏或保留状态，则写入在本地完成，并且新状态是脏的。如果新状态有效，则写入无效命令将广播到所有缓存，使它们的副本无效。当共享内存被写透时，结果状态在第一次写入后被保留。
Write-miss - 如果处理器无法写入本地缓存，则副本必须来自主内存或带有脏块的远程缓存。这是通过发送读取无效命令来完成的，该命令将使所有缓存副本无效。然后本地副本会更新为脏状态。
读命中- 读命中始终在本地缓存中执行，不会导致状态转换或使用窥探总线进行失效。
块替换- 当副本脏时，将通过块替换方法将其写回主存储器。但是，当副本处于有效或保留或无效状态时，不会进行替换。

基于目录的协议

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

在基于目录的协议系统中，要共享的数据被放置在一个公共目录中，该目录保持缓存之间的一致性。在这里，目录充当过滤器，处理器在其中请求许可将条目从主存储器加载到其高速缓存存储器。如果某个条目发生更改，则目录会更新该条目或使包含该条目的其他缓存失效。

硬件同步机制

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

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

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

当处理器包含本地高速缓冲存储器时，维持高速缓存一致性是多处理器系统中的一个问题。该系统中很容易出现不同缓存之间数据不一致的情况。

主要关注领域是 -

共享可写数据
进程迁移
输入/输出活动

共享可写数据

当两个处理器（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 设备被添加到总线上。一开始，两个缓存都包含数据元素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（Cache Coherent NUMA）。

仅高速缓存内存架构 (COMA)

COMA 机器与 NUMA 机器类似，唯一的区别是 COMA 机器的主存储器充当直接映射或组关联缓存。数据块根据其地址散列到 DRAM 缓存中的某个位置。远程获取的数据实际上存储在本地主存储器中。而且，数据块没有固定的归属位置，它们可以在整个系统中自由移动。

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

COMA 与 CC-NUMA

以下是 COMA 和 CC-NUMA 之间的差异。

COMA 往往比 CC-NUMA 更灵活，因为 COMA 透明地支持数据迁移和复制，而不需要操作系统。
COMA 机器的构建昂贵且复杂，因为它们需要非标准内存管理硬件，并且一致性协议更难实现。
COMA 中的远程访问通常比 CC-NUMA 中的远程访问慢，因为需要遍历树形网络来查找数据。

硬件软件权衡

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

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

宽松的内存一致性模型

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

系统规格

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

以下是使用程序顺序放宽的几个规范模型 -

放宽写入到读取程序顺序- 此类模型允许硬件抑制第一级高速缓存中错过的写入操作的延迟。当写入未命中位于写入缓冲区中并且对其他处理器不可见时，处理器可以完成在其高速缓存存储器中命中的读取，甚至在其高速缓存存储器中未命中的单个读取。
放宽写入到读取和写入到写入的程序顺序- 允许写入绕过先前未完成的写入到各个位置，从而可以在更新主内存之前将多个写入合并到写入缓冲区中。因此，多个写入未命中会重叠并且变得乱序可见。其动机是进一步最小化写入延迟对处理器中断时间的影响，并通过使新数据值对其他处理器可见来提高处理器之间的通信效率。
放宽所有程序顺序- 默认情况下，除了进程内的数据和控制依赖性之外，不保证任何程序顺序。因此，好处是多个读取请求可以同时处理，并且按程序顺序可以被稍后的写入绕过，并且它们本身可以无序完成，从而允许我们隐藏读取延迟。这种类型的模型对于动态调度的处理器特别有用，它可以继续过去对其他内存引用的读取未命中。它们允许进行许多重新排序，甚至消除由编译器优化完成的访问。

编程接口

编程接口假定在同步操作之间根本不必维护程序顺序。确保所有同步操作都被明确标记或识别。运行时库或编译器将这些同步操作转换为系统规范所需的适当的保序操作。

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

翻译机制

在大多数微处理器中，将标签转换为顺序维护机制相当于在标记为同步的每个操作之前和/或之后插入合适的内存屏障指令。它将保存带有单独加载/存储的指令，指示要执行的顺序并避免额外的指令。然而，由于操作通常不频繁，这并不是大多数微处理器迄今为止所采取的方式。

克服容量限制

我们已经讨论了仅在处理器高速缓冲存储器中提供硬件自动复制和一致性的系统。处理器高速缓存无需首先将其复制到本地主存储器中，而是根据引用直接复制远程分配的数据。

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

三级缓存

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

仅高速缓存内存架构 (COMA)

在 COMA 机器中，整个主内存中的每个内存块都有一个与其链接的硬件标签。不存在始终保证为内存块分配空间的固定节点。数据动态迁移到访问/吸引它们的节点的主存储器或在主存储器中复制。当访问远程块时，它会被复制到吸引内存中并进入高速缓存，并由硬件在两个位置保持一致。数据块可以驻留在任何吸引存储器中并且可以容易地从一个存储器移动到另一个存储器。

降低硬件成本

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

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

对并行软件的影响

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

互联网络设计

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

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

组织架构

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

链路- 链路是一根或多根光纤或电线的电缆，每一端都有一个连接器连接到交换机或网络接口端口。这样，一端发送模拟信号，另一端接收模拟信号，得到原始的数字信息流。
开关- 开关由一组输入和输出端口、连接所有输入到所有输出的内部“交叉开关”、内部缓冲和控制逻辑组成，以在每个时间点实现输入-输出连接。通常，输入端口的数量等于输出端口的数量。
网络接口- 网络接口的Behave与交换机节点完全不同，并且可以通过特殊链路进行连接。网络接口格式化数据包并构建路由和控制信息。与开关相比，它可能具有输入和输出缓冲。它可以执行端到端错误检查和流量控制。因此，其成本受到处理复杂性、存储容量和端口数量的影响。

互联网络

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

直接连接网络- 直接网络在相邻节点之间具有点对点连接。这些网络是静态的，这意味着点对点连接是固定的。直接网络的一些例子是环、网和立方体。
间接连接网络- 间接网络没有固定的邻居。通信拓扑可以根据应用需求动态改变。间接网络可以细分为三部分：总线网络、多级网络和交叉开关。
- 总线网络- 总线网络由许多连接了许多资源的位线组成。当总线对数据和地址使用相同的物理线时，数据线和地址线是时间复用的。当总线上连接有多个总线主控器时，需要仲裁器。
- 多级网络- 多级网络由多级交换机组成。它由“axb”开关组成，这些开关使用特定的级间连接模式（ISC）进行连接。小型 2x2 开关元件是许多多级网络的常见选择。阶段的数量决定了网络的延迟。通过选择不同的级间连接模式，可以创建各种类型的多级网络。
- 纵横开关- 纵横开关包含简单开关元件的矩阵，可以打开和关闭以创建或断开连接。打开矩阵中的开关元件，可以在处理器和存储器之间建立连接。交叉开关是非阻塞的，即所有通信排列都可以无阻塞地执行。

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

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

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

路由

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

路由机制

算术、基于源的端口选择和查表是高速交换机根据数据包标头中的信息确定输出通道的三种机制。所有这些机制都比传统 LAN 和 WAN 路由器中实现的一般路由计算更简单。在并行计算机网络中，交换机需要在每个周期中对其所有输入做出路由决策，因此该机制需要简单且快速。

确定性路由

如果消息所采用的路由完全由其源和目的地确定，而不是由网络中的其他流量确定，则路由算法是确定性的。如果路由算法仅选择到达目的地的最短路径，则它是最小路径，否则它是非最小路径。

僵局自由

死锁可能发生在多种情况下。当两个节点尝试向彼此发送数据并且每个节点在任一节点接收之前开始发送时，可能会发生“正面”死锁。当网络中存在多个消息竞争资源时，就会发生另一种死锁情况。

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

开关设计

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

港口

引脚总数实际上是输入和输出端口总数乘以通道宽度。由于芯片周长与面积相比增长缓慢，开关往往受到引脚限制。

内部数据路径

数据路径是每个输入端口组和每个输出端口之间的连接。一般称为内横杆。非阻塞交叉开关是指每个输入端口可以同时以任何排列连接到不同输出的交叉开关。

通道缓冲器

交换机内缓冲存储器的组织对交换机性能有重要影响。传统的路由器和交换机往往在交换机结构外部配备大型 SRAM 或 DRAM 缓冲区，而在 VLSI 交换机中，缓冲区位于交换机内部，并且与数据路径和控制部分采用相同的芯片预算。随着芯片尺寸和密度的增加，可以使用更多的缓冲，网络设计人员也有更多的选择，但缓冲空间仍然是首选，其组织也很重要。

流量控制

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

流量控制问题出现在所有网络和许多级别。但并行计算机网络与局域网和广域网有本质上的不同。在并行计算机中，网络流量需要与总线上的流量一样准确地传递，并且在非常小的时间尺度上存在大量并行流。

延迟容忍度

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

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

延迟通常随着机器的大小而增加，因为更多的节点意味着相对于计算而言更多的通信、用于一般通信的网络中的更多跳跃以及可能更多的争用。硬件设计的主要目标是减少数据访问的延迟，同时保持高、可扩展的带宽。

延迟容忍概述

通过查看机器中的资源及其利用方式，可以最好地了解如何处理延迟容忍度。从处理器的角度来看，通信