README.md

二、并行计算平台

从传统的逻辑角度来看，顺序计算机包括一个通过数据路径连接到处理器的存储器。处理器、内存和数据路径这三个组成部分都是计算机系统整体处理速度的瓶颈。多年来，一些架构创新解决了这些瓶颈问题。其中最重要的创新之一就是处理单元、数据路径和内存单元的多重性。这种多重性要么对程序员完全隐藏（如隐式并行），要么以不同形式暴露给程序员。在本章中，我们将概述与并行处理相关的重要架构概念。目的是为程序员提供足够详细的信息，使他们能够在各种平台上编写高效的代码。我们开发了成本模型和抽象概念，用于量化各种并行算法的性能，并找出各种编程结构导致的瓶颈。

在讨论并行平台时，我们首先要概述串行和隐式并行架构。这是因为通常可以通过简单的程序转换来重新设计代码，从而实现显著的速度提升（2 到 5 倍的未优化速度）。对次优串行代码进行并行化往往会带来不可靠的速度提升和误导运行时间的不良后果。因此，我们主张在尝试并行化之前先优化代码的串行性能。正如我们将在本章中展示的，串行优化和并行优化的任务往往具有非常相似的特点。在讨论了串行和隐式并行架构之后，我们将在本章的其余部分讨论并行平台的组织、算法的底层成本模型以及可移植算法设计的平台抽象。希望直接了解并行架构的读者可以跳过第 2.1 和 2.2 节。

2.1 隐式并行 - 微处理器架构的趋势

在过去的十年中，微处理器技术在时钟速度方面取得了显著的进步，但同时也暴露出其他各种性能瓶颈。为了缓解这些瓶颈，微处理器设计人员探索了其他途径，以实现具有成本效益的性能提升。在本节中，我们将概述其中的一些趋势，以便了解它们的局限性以及对算法和代码开发的影响。本节的目的不是全面介绍处理器架构。参考书目中提到的几篇优秀文章都涉及这一主题。

• 2.1.1 流水线和超标量
• 2.1.2 超长指令字处理器

2.2 内存系统性能的限制

计算机程序的有效运行不仅取决于处理器的速度，还取决于内存系统向处理器提供数据的能力。在逻辑层面上，内存系统（可能由多级缓存组成）接收一个内存字的请求，并在 $1$ 纳秒后返回一个大小为 b 的数据块，其中包含所请求的字。这里的 $l$ 指的是内存的延迟时间。数据从内存传送到处理器的速度决定了内存系统的带宽。

• 2.2.1 利用缓存改善有效内存延迟
• 2.2.2 内存带宽的影响
• 2.2.3 隐藏内存延迟的其他方法
• 2.2.4 多线程与预取的权衡

2.3 并行计算平台的逻辑架构

在前面的章节中，我们指出了影响串行或隐式并行程序性能的各种因素。当前微处理器的峰值性能和可持续性能之间的差距越来越大，内存系统性能的影响，以及许多问题的分布式性质，都是并行化的主要动机。现在，我们将从高层次介绍并行计算平台的要素，这些要素对于面向性能和可移植的并行编程至关重要。为了便于我们讨论并行平台，我们首先探讨了基于并行平台的逻辑组织和物理组织的两部分。逻辑组织指的是程序员对平台的看法，而物理组织指的是平台的实际硬件组织。从程序员的角度来看，并行计算的两个关键组成部分是表达并行任务的方法和指定这些任务之间交互的机制。前者有时也被称为控制结构，后者则被称为通信模型。

• 2.3.1 并行平台的控制结构
• 2.3.2 并行平台的通信模式

2.4 并行平台的物理架构

在本节中，我们将讨论并行机的物理架构。我们将从理想架构开始，概述与实现这一模型相关的实际困难，并讨论一些传统架构。

• 2.4.1 理想并行计算机的结构
• 2.4.2 并行计算机互连网络
• 2.4.3 网络拓扑
• 2.4.4 评估静态互连网络
• 2.4.5 评估动态互连网络
• 2.4.6 多处理器系统的缓存一致性

2.5 并行计算中的通信开销

并行程序执行过程中的主要开销之一来自处理元件之间的信息通信。通信成本取决于多种特性，包括编程模型语义、网络拓扑结构、数据处理和路由选择，以及相关的软件协议。这些问题是我们在此讨论的重点。

• 2.5.1 并行计算中的消息传递开销
• 2.5.2 并行计算中的内存共享开销

2.6 互联网络中的路由机制

将信息路由到目的地的高效算法对并行计算机的性能至关重要。路由机制决定了信息通过网络从源节点到达目的节点的路径。它将信息的源节点和目的节点作为输入。它还可以使用网络状态信息。它返回一条或多条从源节点到目的节点的网络路径。

2.7 进程到处理器的映射技术及其影响

正如我们在第 2.5.1 节中所讨论的，程序员通常无法控制逻辑进程如何映射到网络中的物理节点。因此，即使通信模式本身并不拥塞，也可能造成网络拥塞。下面我们举例说明：

• 2.7.1 图的映射技术
• 2.7.2 成本与性能的平衡