并行计算机架构 - 快速指南
并行计算机架构 - 简介
在过去的 50 年中，计算机系统的性能和功能取得了巨大的发展。这得益于超大规模集成 (VLSI) 技术。VLSI 技术允许在单个芯片上容纳大量组件，并提高时钟频率。因此，可以同时并行执行更多操作。
并行处理还与数据局部性和数据通信相关。并行计算机架构是一种组织所有资源的方法，以在技术和任何时间点的成本限制内最大限度地提高性能和可编程性。
为什么是并行架构?
并行计算机架构通过使用越来越多的处理器，为计算机系统的发展增加了一个新的维度。原则上，在给定时间点，使用大量处理器所实现的性能高于单个处理器的性能。
应用趋势
随着硬件容量的提高，对高性能应用程序的需求也随之增加，这反过来又对计算机体系结构的发展提出了要求。
在微处理器时代之前，高性能计算机系统是通过奇特的电路技术和机器组织获得的，这使得它们价格昂贵。现在，高性能计算机系统是通过使用多个处理器获得的，大多数重要和要求高的应用程序都是以并行程序的形式编写的。因此，为了获得更高的性能，需要开发并行体系结构和并行应用程序。
要提高应用程序的性能，加速是需要考虑的关键因素。 p 个处理器上的加速定义为 −
$$Speedup(p \ 处理器)\equiv\frac{Performance(p \ 处理器)}{Performance(1 \ 处理器)}$$对于单个固定问题，
$$performance \ of \ a \ computer \ system = \frac{1}{Time \ needed \ to \ complete \ the \ problem}$$ $$Speedup \ _{fixed \ problem} (p \ processors) =\frac{Time(1 \ processor)}{Time(p \ processor)}$$科学与工程计算
并行架构已成为科学计算(如物理、化学、生物、天文学等)和工程应用(如油藏建模、气流分析、燃烧效率等)中不可或缺的一部分。在几乎所有应用中，对计算输出可视化的需求都很大，因此需要开发并行计算来提高计算速度。
商业计算
在商业计算(如视频、图形、数据库、OLTP 等)中，也需要高速计算机在指定时间内处理大量数据。桌面使用多线程程序，这些程序几乎与并行程序类似。这反过来又需要开发并行架构。
技术趋势
随着技术和架构的发展，对高性能应用程序的开发需求强烈。实验表明，并行计算机的工作速度比单处理器的最高速度快得多。此外，并行计算机可以在技术和成本限制内开发。
这里使用的主要技术是 VLSI 技术。因此，如今越来越多的晶体管、门和电路可以安装在相同的区域内。随着基本 VLSI 特征尺寸的减小，时钟频率也成比例提高，而晶体管的数量则成平方增长。可以预期，同时使用多个晶体管(并行性)的性能要比增加时钟频率好得多。
技术趋势表明，基本的单芯片构建块将提供越来越大的容量。因此，在单个芯片上放置多个处理器的可能性增加了。
架构趋势
技术的发展决定了什么是可行的；架构将技术的潜力转化为性能和能力。并行性和局部性是两种方法，其中更大的资源量和更多的晶体管可以提高性能。然而，这两种方法争夺相同的资源。当多个操作并行执行时，执行程序所需的周期数会减少。
但是，需要资源来支持每个并发活动。还需要资源来分配本地存储。最佳性能是通过中间操作计划实现的，该计划使用资源来利用并行度和局部度。
一般来说，计算机体系结构的历史分为四代，具有以下基本技术 −
- 真空管
- 晶体管
- 集成电路
- VLSI
直到 1985 年，位级并行性的增长一直占据主导地位。4 位微处理器，然后是 8 位、16 位等等。为了减少执行完整 32 位操作所需的周期数，数据路径的宽度加倍。后来，引入了 64 位操作。
指令级并行性的增长在 80 年代中期到 90 年代中期占据主导地位。RISC 方法表明，将指令处理步骤流水线化很简单，因此平均而言，几乎每个周期都会执行一条指令。编译器技术的发展使指令流水线更加高效。
20 世纪 80 年代中期，基于微处理器的计算机由以下部分组成:
- 整数处理单元
- 浮点单元
- 缓存控制器
- 用于缓存数据的 SRAM
- 标签存储
随着芯片容量的增加，所有这些组件都合并到单个芯片中。因此，单个芯片由用于整数运算、浮点运算、内存操作和分支操作的独立硬件组成。除了流水线处理单个指令外，它还会一次获取多个指令，并尽可能将它们并行发送到不同的功能单元。这种指令级并行性称为超标量执行。
并行架构的融合
并行机器已经开发出几种不同的架构。在本节中，我们将讨论不同的并行计算机架构及其融合的性质。
通信架构
并行架构通过通信架构增强了计算机架构的传统概念。计算机架构定义了关键的抽象(如用户系统边界和硬件软件边界)和组织结构，而通信架构定义了基本的通信和同步操作。它还解决了组织结构问题。
编程模型是最顶层。应用程序是用编程模型编写的。并行编程模型包括 −
- 共享地址空间
- 消息传递
- 数据并行编程
共享地址编程就像使用公告板，一个人可以通过在特定位置发布信息与一个或多个人进行交流，该位置由所有其他个人共享。个人活动通过记录谁在做什么任务来协调。
消息传递就像电话或信件，特定接收者从特定发送者接收信息。
数据并行编程是一种有组织的合作形式。在这里，几个人同时对数据集的不同元素执行操作并在全球范围内共享信息。
共享内存
共享内存多处理器是并行机器中最重要的一类。它在多道程序工作负载上提供更好的吞吐量并支持并行程序。
在这种情况下，所有计算机系统都允许处理器和一组 I/O 控制器通过某种硬件互连访问一组内存模块。通过添加内存模块可以增加内存容量，通过向 I/O 控制器添加设备或添加额外的 I/O 控制器可以增加 I/O 容量。可以通过等待更快的处理器可用或添加更多处理器来增加处理能力。
所有资源都围绕中央内存总线组织。通过总线访问机制，任何处理器都可以访问系统中的任何物理地址。由于所有处理器与所有内存位置的距离相等，因此所有处理器在内存位置上的访问时间或延迟相同。这被称为对称多处理器。
消息传递架构
消息传递架构也是并行机器的重要类别。它以显式 I/O 操作的形式提供处理器之间的通信。在这种情况下，通信是在 I/O 级别而不是内存系统上组合的。
在消息传递架构中，用户通信通过使用操作系统或库调用来执行，这些调用执行许多较低级别的操作，其中包括实际的通信操作。因此，编程模型与物理硬件级别的通信操作之间存在距离。
发送和接收是消息传递系统中最常见的用户级通信操作。发送指定本地数据缓冲区(要传输)和接收远程处理器。接收指定发送进程和将放置传输数据的本地数据缓冲区。在发送操作中，标识符或标签附加到消息，接收操作指定匹配规则，如来自特定处理器的特定标签或来自任何处理器的任何标签。
发送和匹配接收的组合完成了内存到内存的复制。每一端都指定其本地数据地址和成对的同步事件。
融合
硬件和软件的发展已经淡化了共享内存和消息传递阵营之间的明确界限。消息传递和共享地址空间代表两种不同的编程模型；每种模型都为共享、同步和通信提供了透明的范例。然而，基本的机器结构已经向一个共同的组织融合。
数据并行处理
另一类重要的并行机被称为 − 处理器阵列、数据并行架构和单指令多数据机。编程模型的主要特点是可以对大型常规数据结构(如数组或矩阵)的每个元素并行执行操作。
数据并行编程语言通常通过查看一组进程(每个处理器一个进程)的本地地址空间来实施，从而形成一个显式全局空间。由于所有处理器都相互通信，并且存在所有操作的全局视图，因此可以使用共享地址空间或消息传递。
基本设计问题
仅开发编程模型无法提高计算机的效率，仅开发硬件也无法做到这一点。但是，计算机架构的发展可以改变计算机的性能。我们可以通过关注程序如何使用机器以及提供了哪些基本技术来理解设计问题。
在本节中，我们将讨论通信抽象和编程模型的基本要求。
通信抽象
通信抽象是编程模型和系统实现之间的主要接口。它就像指令集一样，提供了一个平台，以便同一个程序可以在许多实现上正确运行。这个级别的操作必须简单。
通信抽象就像硬件和软件之间的契约，它允许彼此灵活地改进而不影响工作。
编程模型要求
并行程序有一个或多个线程对数据进行操作。并行编程模型定义了线程可以命名哪些数据、可以对命名数据执行哪些操作以及操作遵循的顺序。
为了确认程序之间的依赖关系得到执行，并行程序必须协调其线程的活动。
并行计算机架构 - 模型
并行处理已成为现代计算机中的一项有效技术，可满足实际应用中对更高性能、更低成本和更准确结果的需求。由于多道程序设计、多处理或多计算的实践，并发事件在当今的计算机中很常见。
现代计算机具有强大而广泛的软件包。要分析计算机性能的发展，首先我们必须了解硬件和软件的基本发展。
计算机发展里程碑 −计算机的发展有两个主要阶段 - 机械或机电部件。现代计算机是在引入电子元件后发展起来的。电子计算机中的高迁移率电子取代了机械计算机中的操作部件。对于信息传输，几乎以光速传播的电信号取代了机械齿轮或杠杆。
现代计算机的要素 − 现代计算机系统由计算机硬件、指令集、应用程序、系统软件和用户界面组成。
计算问题分为数值计算、逻辑推理和事务处理。一些复杂的问题可能需要三种处理模式的结合。
计算机架构的演变 − 在过去的四十年里，计算机架构经历了革命性的变化。我们从冯·诺依曼架构开始，现在我们有了多计算机和多处理器。
计算机系统的性能 − 计算机系统的性能取决于机器能力和程序行为。机器能力可以通过更好的硬件技术、先进的架构特性和高效的资源管理来提高。程序行为不可预测，因为它取决于应用程序和运行时条件
多处理器和多计算机
在本节中，我们将讨论两种类型的并行计算机 −
- 多处理器
- 多计算机
共享内存多计算机
三种最常见的共享内存多处理器模型是 −
统一内存访问 (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.T2 >= O (f(s))
其中 A=芯片面积，T=时间
架构开发轨迹
我们沿着以下轨迹传播了并行计算机的演变 −
- 多处理器轨道
- 多处理器轨道
- 多计算机轨道
- 多数据轨道
- 矢量轨道
- SIMD 轨道
- 多线程轨道
- 多线程轨道
- 数据流轨道
在多处理器轨道中，假设不同的线程在不同的处理器上并发执行，并通过共享内存(多处理器轨道)或消息传递(多计算机轨道)系统进行通信。
在多数据轨道中，假设在海量数据上执行相同的代码。它是通过对一系列数据元素执行相同的指令(向量轨道)或对一组相似的数据执行相同的指令序列(SIMD 轨道)来实现的。
在多线程轨道中，假设在同一处理器上交错执行各种线程，以隐藏在不同处理器上执行的线程之间的同步延迟。线程交错可以是粗略的(多线程轨道)或精细的(数据流轨道)。
并行系统中的处理器
在 80 年代，一种用于制造多台计算机的专用处理器很受欢迎，称为Transputer。Transputer 由一个核心处理器、一个小型 SRAM 内存、一个 DRAM 主内存接口和四个通信通道组成，所有这些都在单个芯片上。为了进行并行计算机通信，通道被连接起来形成一个 Transputers 网络。但它缺乏计算能力，因此无法满足并行应用程序日益增长的需求。 RISC 处理器的开发解决了这个问题，而且它也很便宜。
现代并行计算机使用微处理器，它在多个级别使用并行性，如指令级并行性和数据级并行性。
高性能处理器
RISC 和 RISCy 处理器主导着当今的并行计算机市场。
传统 RISC 的特点是 −
- 寻址模式很少。
- 指令格式固定，通常为 32 位或 64 位。
- 有专用的加载/存储指令，用于将数据从内存加载到寄存器，并将数据从寄存器存储到内存。
- 算术运算始终在寄存器上执行。
- 使用流水线。
如今，大多数微处理器都是超标量的，即在并行计算机中使用多条指令流水线。因此，超标量处理器可以同时执行多条指令。超标量处理器的有效性取决于应用程序中可用的指令级并行性 (ILP) 的数量。为了保持流水线充满，硬件级别的指令以与程序顺序不同的顺序执行。
许多现代微处理器使用超级流水线方法。在超级流水线中，为了增加时钟频率，流水线阶段内完成的工作会减少，流水线阶段的数量会增加。
超大指令字 (VLIW) 处理器
这些处理器源自水平微编程和超标量处理。VLIW 处理器中的指令非常大。单个指令中的操作并行执行，并转发到适当的功能单元执行。因此，在获取 VLIW 指令后，其操作会被解码。然后，操作会被分派到功能单元，并在其中并行执行。
矢量处理器
矢量处理器是通用微处理器的协处理器。矢量处理器通常是寄存器-寄存器或内存-内存。获取和解码矢量指令，然后对操作数矢量的每个元素执行特定操作，而在普通处理器中，矢量操作需要代码中的循环结构。为了提高效率，矢量处理器将多个矢量运算链接在一起，即一个矢量运算的结果作为操作数转发到另一个矢量运算。
缓存
缓存是高性能微处理器的重要组成部分。每 18 个月后，微处理器的速度就会翻一番，但主存储器的 DRAM 芯片无法与这种速度相媲美。因此，引入了缓存来弥合处理器和内存之间的速度差距。缓存是一种快速而小的 SRAM 内存。现代处理器中应用了更多的缓存，如转换后备缓冲区 (TLB) 缓存、指令和数据缓存等。
直接映射缓存
在直接映射缓存中，使用"模数"函数将主存储器中的地址一对一映射到缓存位置。由于同一缓存条目可以映射多个主存储器块，因此处理器必须能够确定缓存中的数据块是否是实际需要的数据块。此识别通过将标签与缓存块一起存储来完成。
全关联缓存
全关联映射允许将缓存块放置在缓存中的任何位置。通过使用某种替换策略，缓存确定存储缓存块的缓存条目。全关联缓存具有灵活的映射，可最大限度地减少缓存条目冲突的数量。由于全关联实现成本高昂，因此从未大规模使用过。
组关联缓存
组关联映射是直接映射和全关联映射的组合。在这种情况下，缓存条目被细分为缓存集。与直接映射一样，缓存中内存块与集合的映射是固定的。但在缓存集合内，内存块以完全关联的方式映射。
缓存策略
除了映射机制，缓存还需要一系列策略来指定在发生某些事件时应该发生什么。对于(组)相联缓存，缓存必须确定哪个缓存块将被进入缓存的新块替换。
一些众所周知的替换策略是 −
- 先进先出 (FIFO)
- 最近最少使用 (LRU)
多处理器和多计算机
我们将在本章中讨论多处理器和多计算机。
多处理器系统互连
并行处理需要使用高效的系统互连，以便在输入/输出和外围设备、多处理器和共享内存之间实现快速通信。
分层总线系统
分层总线系统由连接计算机中各种系统和子系统/组件的总线层次结构组成。每条总线由多条信号线、控制线和电源线组成。不同的总线(如本地总线、背板总线和 I/O 总线)用于执行不同的互连功能。
本地总线是在印刷电路板上实现的总线。背板总线是一种印刷电路，上面有许多连接器用于插入功能板。将输入/输出设备连接到计算机系统的总线称为 I/O 总线。
交叉开关和多端口存储器
交换网络在输入和输出之间提供动态互连。小型或中型系统大多使用交叉开关网络。如果可以解决增加的延迟问题，则可以将多级网络扩展到更大的系统。
交叉开关和多端口存储器组织都是单级网络。虽然单级网络的构建成本较低，但可能需要多次传递才能建立某些连接。多级网络具有多级开关盒。这些网络应该能够将任何输入连接到任何输出。
多级和组合网络
多级网络或多级互连网络是一类高速计算机网络，主要由网络一端的处理元件和另一端的存储器元件组成，并通过交换元件连接。
这些网络用于构建更大的多处理器系统。其中包括 Omega 网络、Butterfly 网络等。
多计算机
多计算机是分布式内存 MIMD 架构。下图显示了多计算机的概念模型 −
多计算机是消息传递机器，它应用分组交换方法来交换数据。在这里，每个处理器都有一个私有内存，但没有全局地址空间，因为处理器只能访问自己的本地内存。因此，通信不透明:程序员必须明确地将通信原语放入他们的代码中。
没有全局可访问的内存是多计算机的一个缺点。可以使用以下两种方案解决这个问题 −
- 虚拟共享内存 (VSM)
- 共享虚拟内存 (SVM)
在这些方案中，应用程序员假设一个全局可寻址的大共享内存。如果需要，应用程序所做的内存引用将转换为消息传递范例。
虚拟共享内存 (VSM)
VSM 是一种硬件实现。因此，操作系统的虚拟内存系统是在 VSM 之上透明实现的。因此，操作系统认为它在具有共享内存的机器上运行。
共享虚拟内存 (SVM)
SVM 是操作系统级别的软件实现，由处理器的内存管理单元 (MMU) 提供硬件支持。这里，共享的单位是操作系统内存页面。
如果处理器寻址特定内存位置，MMU 会确定与内存访问相关的内存页面是否在本地内存中。如果页面不在内存中，在普通计算机系统中，操作系统会将其从磁盘换入。但在 SVM 中，操作系统会从拥有该特定页面的远程节点获取页面。
三代多计算机
在本节中，我们将讨论三代多计算机。
过去的设计选择
在选择处理器技术时，多计算机设计人员选择低成本的中粒度处理器作为构建块。大多数并行计算机都是用标准的现成微处理器构建的。多计算机选择分布式内存，而不是使用共享内存，这会限制可扩展性。每个处理器都有自己的本地内存单元。
对于互连方案，多计算机具有消息传递、点对点直接网络，而不是地址交换网络。对于控制策略，多计算机设计者选择异步 MIMD、MPMD 和 SMPD 操作。加州理工学院的宇宙立方体 (Seitz, 1983) 是第一代多计算机中的第一个。
现在和未来的发展
下一代计算机从中粒度多计算机发展到使用全局共享虚拟内存的细粒度多计算机。目前，第二代多计算机仍在使用。但是，使用 i386、i860 等更好的处理器，第二代计算机已经得到了很大的发展。
第三代计算机是下一代计算机，其中将使用 VLSI 实现的节点。每个节点可能在单个芯片上集成一个 14-MIPS 处理器、20-Mbytes/s 路由通道和 16 KB RAM。
Intel Paragon 系统
以前，同质节点用于制造超立方体多计算机，因为所有功能都交给了主机。因此，这限制了 I/O 带宽。因此，为了高效或高吞吐量地解决大规模问题，这些计算机无法使用。Intel Paragon 系统旨在克服这一困难。它将多计算机变成了网络环境中具有多用户访问的应用程序服务器。
消息传递机制
多计算机网络中的消息传递机制需要特殊的硬件和软件支持。在本节中，我们将讨论一些方案。
消息路由方案
在具有存储和转发路由方案的多计算机中，数据包是信息传输的最小单位。在虫洞路由网络中，数据包进一步划分为 flit。数据包长度由路由方案和网络实现决定，而 flit 长度受网络大小影响。
在存储和转发路由中，数据包是信息传输的基本单位。在这种情况下，每个节点都使用一个数据包缓冲区。数据包通过一系列中间节点从源节点传输到目标节点。延迟与源和目标之间的距离成正比。
在虫洞路由中，从源节点到目标节点的传输是通过一系列路由器完成的。同一数据包的所有 flit 以流水线方式以不可分割的顺序传输。在这种情况下，只有头部 flit 知道数据包要去哪里。
死锁和虚拟通道
虚拟通道是两个节点之间的逻辑链接。它由源节点和接收节点中的 flit 缓冲区以及它们之间的物理通道组成。当为一个对分配物理通道时，一个源缓冲区与一个接收缓冲区配对以形成虚拟通道。
当所有通道都被消息占用并且循环中没有一个通道被释放时，就会发生死锁情况。为了避免这种情况，必须遵循死锁避免方案。
缓存一致性和同步
在本章中，我们将讨论缓存一致性协议以应对多缓存不一致问题。
缓存一致性问题
在多处理器系统中，数据不一致可能发生在内存层次结构的相邻级别之间或同一级别内。例如，缓存和主内存可能具有同一对象的不一致副本。
由于多个处理器并行运行，并且多个独立的缓存可能拥有同一内存块的不同副本，因此会产生缓存一致性问题。缓存一致性方案通过为每个缓存的数据块维护统一的状态来帮助避免此问题。
假设 X 是共享数据的一个元素，已被两个处理器 P1 和 P2 引用。一开始，X 的三个副本是一致的。如果处理器 P1 使用直写策略将新数据 X1 写入缓存，则相同的副本将立即写入共享内存。在这种情况下，缓存和主内存之间就会出现不一致。当使用写回策略时，当缓存中修改的数据被替换或失效时，主内存将会更新。
一般来说，不一致问题的来源有三个 −
- 可写数据共享
- 进程迁移
- I/O 活动
Snoopy 总线协议
Snoopy 协议通过基于总线的内存系统实现高速缓存和共享内存之间的数据一致性。 写入无效和写入更新策略用于维护缓存一致性。
在这种情况下，我们有三个处理器 P1、P2 和 P3，它们在本地缓存和共享内存中都有数据元素"X"的一致副本(图 a)。处理器 P1 使用写入无效协议将 X1 写入其缓存中。因此，所有其他副本都通过总线失效。它用"I"表示(图 b)。无效块也称为脏，即不应使用它们。写入更新协议通过总线更新所有缓存副本。通过使用写回缓存，内存副本也会更新(图 c)。
缓存事件和操作
在执行内存访问和无效命令时会发生以下事件和操作 −
读取未命中 − 当处理器想要读取一个块并且它不在缓存中时，就会发生读取未命中。这会启动总线读取操作。如果不存在脏副本，则具有一致副本的主内存会向请求缓存内存提供副本。如果远程缓存内存中存在脏副本，则该缓存将限制主内存并向请求缓存内存发送副本。在这两种情况下，缓存副本在读取未命中后都将进入有效状态。
写入命中 − 如果副本处于脏或保留状态，则写入在本地完成，新状态为脏。如果新状态有效，则写入无效命令将广播到所有缓存，使其副本无效。当共享内存写入完毕后，在第一次写入后保留结果状态。
写入未命中 − 如果处理器无法在本地缓存内存中写入，则副本必须来自主内存或具有脏块的远程缓存内存。这是通过发送读取无效命令来完成的，该命令将使所有缓存副本无效。然后本地副本将更新为脏状态。
读命中 − 读命中始终在本地缓存中执行，不会引起状态转换或使用监听总线进行无效化。
块替换 − 当副本为脏时，将通过块替换方法将其写回到主内存。但是，当副本处于有效、保留或无效状态时，不会进行替换。
基于目录的协议
通过使用多级网络构建具有数百个处理器的大型多处理器，需要修改 snoopy 缓存协议以适应网络功能。在多级网络中执行广播非常昂贵，一致性命令仅发送给保留块副本的缓存。这就是为网络连接的多处理器开发基于目录的协议的原因。
在基于目录的协议系统中，要共享的数据放置在一个公共目录中，该目录可保持缓存之间的一致性。在这里，目录充当过滤器，处理器请求允许将条目从主存储器加载到其缓存存储器中。如果更改了条目，目录将更新它或使具有该条目的其他缓存无效。
硬件同步机制
同步是一种特殊的通信形式，其中不是数据控制，而是在驻留在相同或不同处理器中的通信进程之间交换信息。
多处理器系统使用硬件机制来实现低级同步操作。大多数多处理器都具有硬件机制来实施原子操作(例如内存读取、写入或读取-修改-写入操作)以实现一些同步原语。除了原子内存操作之外，一些处理器间中断也用于同步目的。
共享内存机器中的缓存一致性
当处理器包含本地缓存内存时，维护缓存一致性是多处理器系统中的一个问题。该系统中很容易出现不同缓存之间的数据不一致。
主要关注领域是 −
- 可写数据共享
- 进程迁移
- 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 机器中，处理器的缓存控制器确定内存引用是本地的还是远程的。为了减少远程内存访问的次数，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 机器中，整个主内存中的每个内存块都有一个与之关联的硬件标签。没有固定节点，始终可以保证为内存块分配空间。数据动态迁移到访问/吸引它们的节点的主内存中或在主内存中复制。当访问远程块时，它会在景点内存中复制并带入缓存，并由硬件在两个位置保持一致。数据块可以驻留在任何景点内存中，并且可以轻松地从一个景点移动到另一个景点。
降低硬件成本
降低成本意味着将专用硬件的某些功能转移到在现有硬件上运行的软件上。软件在主内存中管理复制和一致性比在硬件缓存中管理复制和一致性要容易得多。低成本方法往往在主内存中提供复制和一致性。为了有效地控制一致性，辅助的每个其他功能组件都可以从硬件专业化和集成中受益。
研究工作旨在通过不同的方法降低成本，例如通过在专用硬件中执行访问控制，但将其他活动分配给软件和商用硬件。另一种方法是在软件中执行访问控制，旨在在没有专用硬件支持的商用节点和网络上分配一致的共享地址空间抽象。
对并行软件的影响
宽松的内存一致性模型需要并行程序将所需的冲突访问标记为同步点。编程语言提供了将某些变量标记为同步的支持，然后编译器会将其转换为合适的保序指令。为了限制编译器对共享内存访问的重新排序，编译器可以自行使用标签。
互连网络设计
并行计算机中的互连网络将信息从任何源节点传输到任何所需的目标节点。此任务应尽可能以最小的延迟完成。它应允许大量此类传输同时进行。此外，与机器其余部分的成本相比，它应该便宜。
网络由链路和交换机组成，有助于将信息从源节点发送到目标节点。网络由其拓扑、路由算法、交换策略和流控制机制指定。
组织结构
互连网络由以下三个基本组件组成 −
链路 − 链路是一根或多根光纤或电线组成的电缆，两端各有一个连接器，连接到交换机或网络接口端口。通过它，模拟信号从一端传输，在另一端接收，以获得原始数字信息流。
交换机 − 交换机由一组输入和输出端口、将所有输入连接到所有输出的内部"交叉开关"、内部缓冲和控制逻辑组成，以在每个时间点实现输入输出连接。通常，输入端口的数量等于输出端口的数量。
网络接口 − 网络接口的行为与交换机节点完全不同，可以通过特殊链路连接。网络接口格式化数据包并构建路由和控制信息。与交换机相比，它可能具有输入和输出缓冲。它可以执行端到端错误检查和流量控制。因此，其成本受其处理复杂性、存储容量和端口数量的影响。
互连网络
互连网络由交换元件组成。拓扑是将各个交换机连接到其他元件(如处理器、内存和其他交换机)的模式。网络允许并行系统中的处理器之间交换数据。
直接连接网络 − 直接网络在相邻节点之间有点对点连接。这些网络是静态的，这意味着点对点连接是固定的。直接网络的一些示例是环、网状和立方体。
间接连接网络 − 间接网络没有固定的邻居。通信拓扑可以根据应用需求动态更改。间接网络可以细分为三个部分:总线网络、多级网络和交叉开关。
总线网络 − 总线网络由多条位线组成，这些位线上连接有多个资源。当总线使用相同的物理线路传输数据和地址时，数据和地址线是时分复用的。当有多个总线主控器连接到总线时，需要仲裁器。
多级网络 − 多级网络由多级开关组成。它由使用特定级间连接模式 (ISC) 连接的"axb"开关组成。小型 2x2 开关元件是许多多级网络的常见选择。级数决定了网络的延迟。通过选择不同的级间连接模式，可以创建各种类型的多级网络。
交叉开关 − 交叉开关包含一个简单开关元件矩阵，这些开关元件可以打开和关闭以建立或断开连接。打开矩阵中的开关元件，即可建立处理器与内存之间的连接。交叉开关是非阻塞的，也就是说，所有通信排列都可以无阻塞地执行。
评估网络拓扑中的设计权衡
如果主要关注的是路由距离，则必须最大化维度并构建超立方体。在存储转发路由中，假设交换机的度数和链接数不是重要的成本因素，而链接数或交换机度数是主要成本，则必须最小化维度并构建网格。
在每个网络的最坏情况下，流量模式最好是高维网络，其中所有路径都很短。在每个节点仅与一个或两个附近邻居通信的模式中，最好使用低维网络，因为实际上只使用了少数维度。
路由
网络的路由算法确定从源到目的地的可能路径中哪条用作路由，以及如何确定每个特定数据包所遵循的路由。维度顺序路由限制了合法路径集，以便从每个源到每个目的地只有一条路由。通过首先在高阶维度中行进正确的距离，然后是下一个维度，依此类推，获得该路径。
路由机制
算术、基于源的端口选择和表查找是高速交换机用来根据数据包头中的信息确定输出通道的三种机制。所有这些机制都比传统 LAN 和 WAN 路由器中实现的一般路由计算更简单。在并行计算机网络中，交换机需要在每个周期为其所有输入做出路由决策，因此该机制需要简单而快速。
确定性路由
如果消息所采用的路由完全由其源和目的地决定，而不是由网络中的其他流量决定，则路由算法是确定性的。如果路由算法仅选择通往目的地的最短路径，则它是最小的，否则它是非最小的。
无死锁
死锁可能发生在各种情况下。当两个节点尝试向对方发送数据并且每个节点在接收之前都开始发送时，可能会发生"正面"死锁。另一种死锁情况是，网络中有多条消息争夺资源。
证明网络无死锁的基本方法是清除由于消息在网络中移动而可能在通道之间发生的依赖关系，并表明整个通道依赖图中没有循环；因此不存在可能导致死锁的流量模式。实现此目的的常用方法是对通道资源进行编号，使所有路由都遵循特定的递增或递减顺序，这样就不会出现依赖循环。
交换机设计
网络的设计取决于交换机的设计以及交换机的连接方式。交换机的程度、其内部路由机制及其内部缓冲决定了可以支持哪些拓扑以及可以实现哪些路由算法。与计算机系统的任何其他硬件组件一样，网络交换机包含数据路径、控制和存储。
端口
引脚总数实际上是输入和输出端口总数乘以通道宽度。由于芯片的周长相对于面积增长缓慢，因此交换机的引脚数量往往有限。
内部数据路径
数据路径是每组输入端口和每个输出端口之间的连接。它通常被称为内部交叉开关。非阻塞交叉开关是指每个输入端口可以同时以任何排列方式连接到不同输出的交叉开关。
通道缓冲器
交换机内缓冲存储的组织对交换机性能有重要影响。传统路由器和交换机往往在交换结构外部具有大型 SRAM 或 DRAM 缓冲器，而在 VLSI 交换机中，缓冲位于交换机内部，并且来自与数据路径和控制部分相同的硅预算。随着芯片尺寸和密度的增加，可用的缓冲更多，网络设计人员有更多选择，但缓冲器空间仍然是首选，其组织也很重要。
流量控制
当网络中的多个数据流试图同时使用相同的共享网络资源时，必须采取一些措施来控制这些流。如果我们不想丢失任何数据，则必须阻止某些流，而让其他流继续传输。
流控制问题出现在所有网络和许多级别中。但并行计算机网络与局域网和广域网在性质上有所不同。在并行计算机中，网络流量需要像总线上的流量一样精确地传输，并且在非常小的时间尺度上存在大量并行流。
延迟容忍度
微处理器的速度每十年增加十倍以上，但商用内存(DRAM)的速度仅翻倍，即访问时间减半。因此，以处理器时钟周期计算的内存访问延迟在 10 年内增加了六倍。多处理器加剧了这个问题。
在基于总线的系统中，在处理器和内存之间建立高带宽总线往往会增加从内存获取数据的延迟。当内存在物理上分布时，网络和网络接口的延迟会添加到访问节点上的本地内存的延迟中。
延迟通常随着机器的大小而增加，因为更多的节点意味着相对于计算的更多通信、网络中用于一般通信的更多跳跃以及可能更多的争用。硬件设计的主要目标是减少数据访问的延迟，同时保持高可扩展带宽。
延迟容忍度概述
通过查看机器中的资源及其使用方式，可以最好地理解延迟容忍度的处理方式。从处理器的角度来看，从一个节点到另一个节点的通信架构可以看作是一条管道。管道的各个阶段包括源和目标处的网络接口，以及沿途的网络链路和交换机。根据架构如何管理通信，通信辅助、本地内存/缓存系统和主处理器中也存在各个阶段。
基线通信结构中的利用率问题是处理器或通信架构在给定时间内处于繁忙状态，而在通信管道中，每次只有一个阶段处于繁忙状态，因为传输的单个字从源传输到目标。延迟容忍度的目标是尽可能重叠使用这些资源。
显式消息传递中的延迟容忍度
消息传递中的实际数据传输通常由发送方发起，使用发送操作。接收操作本身并不促使数据被传送，而是将数据从传入缓冲区复制到应用程序地址空间。接收方发起的通信是通过向数据源进程发出请求消息来完成的。然后，该进程通过另一个发送将数据发送回去。
同步发送操作的通信延迟等于将消息中的所有数据传送到目的地所需的时间、接收处理的时间以及返回确认的时间。同步接收操作的延迟是其处理开销；其中包括将数据复制到应用程序中，以及如果数据尚未到达则产生的额外延迟。我们希望在两端隐藏这些延迟，包括开销(如果可能)。
共享地址空间中的延迟容忍度
基本通信是通过在共享地址空间中进行读写进行的。为方便起见，它被称为读写通信。接收方发起的通信是通过读取操作完成的，读取操作会导致访问另一个处理器的内存或缓存中的数据。如果没有共享数据的缓存，则发送方发起的通信可以通过写入分配在远程内存中的数据来完成。
对于缓存一致性，写入的影响更加复杂:写入导致发送方还是接收方发起的通信取决于缓存一致性协议。无论是接收方发起的还是发送方发起的，在硬件支持的读写共享地址空间中的通信自然都是细粒度的，这使得容忍延迟非常重要。
在共享地址空间中块数据传输
在共享地址空间中，无论是通过硬件还是软件，数据的合并和块传输的启动都可以在用户程序中明确完成，也可以由系统透明地完成。显式块传输是通过在用户程序中执行类似于发送的命令来启动的。发送命令由通信辅助解释，它以流水线方式将数据从源节点传输到目的地。在目的地，通信辅助从网络接口提取数据字并将其存储在指定位置。
与发送-接收消息传递有两个主要区别，这两个区别都源于这样一个事实:发送过程可以直接指定程序数据结构，数据将放置在目的地，因为这些位置位于共享地址空间中。
在共享地址空间中处理长延迟事件
如果内存操作是非阻塞的，处理器就可以处理内存操作以外的其他指令。对于写入，如果将写入放入写入缓冲区，处理器继续运行，而缓冲区负责将写入发送到内存系统并根据需要跟踪其完成情况，则这通常很容易实现。不同之处在于，与写入不同，读取通常很快就会跟上一条需要读取返回值的指令。
共享地址空间中的预通信
预通信是一种已经在商用微处理器中广泛采用的技术，其重要性在未来可能会增加。预取指令不会取代数据项的实际读取，并且预取指令本身必须是非阻塞的，如果它要实现通过重叠隐藏延迟的目标。
在这种情况下，由于共享数据未被缓存，预取的数据被带入一个称为预取缓冲区的特殊硬件结构。当字在下一次迭代中实际读入寄存器时，它是从预取缓冲区的头部读取的，而不是从内存中读取的。如果要隐藏的延迟比计算单次循环迭代的时间大得多，我们会提前预取几次迭代，并且预取缓冲区中一次可能会有多个字。
共享地址空间中的多线程
在隐藏不同类型的延迟方面，硬件支持的多线程可能是一种多功能技术。与其他方法相比，它具有以下概念优势 −
它不需要特殊的软件分析或支持。
由于它是动态调用的，因此它可以处理不可预测的情况，例如缓存冲突等，就像可预测的情况一样。
与预取一样，它不会改变内存一致性模型，因为它不会重新排序线程内的访问。
虽然以前的技术旨在隐藏内存访问延迟，但多线程可以同样轻松地隐藏任何长延迟事件的延迟，只要可以在运行时检测到该事件。这也包括同步和指令延迟。
这种趋势将来可能会改变，因为相对于处理器速度而言，延迟变得越来越长。此外，随着更复杂的微处理器已经提供可扩展用于多线程的方法，以及正在开发将多线程与指令级并行相结合的新多线程技术，这种趋势将来肯定会发生一些变化。
