Chapter 05 : Thread-Level Parallelism¶

约 5821 个字 10 张图片预计阅读时间 29 分钟

Introduction¶

在本章，我们主要探索的是线程级并行（Thread-Level Parallelism, TLP）；而 TLP 利用到了 MIMD（Multiple Instructions，Multiple Data）

多处理器（Multiprocessor）由一组紧密耦合的处理器构成，这些处理器受操作系统控制，并通过一个共享的地址空间来共享内存（不一定只有一块物理内存）。多处理器通过以下两个不同的软件模型来利用 TLP：

并行处理（Parallel Processing）：一组在单任务上协作的紧密耦合的线程的执行
请求级并行（Request-Level Parallelism）：来自一名或多名用户的多个相对独立的进程的执行
- 运行在多个处理器上的单一应用程序会利用请求级并行，例如数据库响应查询，或者通过多个独立运行的应用程序（后者通常被称为多道程序设计，Multiprogramming）

多处理器既包含具有多个核心的单芯片系统，即所谓的多核（Multicore），也涵盖由多个芯片组成的计算机，其中每个芯片通常也是一个多核单元

Multiprocessor Architecture¶

现有的共享内存的多处理器，根据其内存组织的不同划分为以下两大类：

对称/共享内存多处理器（Symmetric/Shared-Memory Multiprocessors，SMP)，或集中式（Centralized）共享内存多处理器
- 具有小到中等数量的核心，通常为 32 个或更少
- 对于这种核心数量较少的多处理器，里面的这些处理器可以共享一个所有处理器都有平等访问权的单一集中式内存，因此称为“对称”
- 大多数现有的多核都属于 SMP
- SMP 有时也被称为统一内存访问（Uniform Memory Access，UMA）多处理器，这是因为所有处理器对内存的访问延迟是均等的，即便内存被划分为多个分区亦是如此
- 某些多核处理器对最外层高速缓存的访问是非均匀的，这种结构被称为非均匀高速缓存访问（Nonuniform Cache Access，NUCA），因此即便它们拥有单一主内存，也并非真正的 SMP
- 下图展示了集中式共享内存多处理器的基本结构：
分布式共享内存（Distributed Shared memory, DSM)
- 在由多个多核芯片构成的多处理器系统中，每个多核芯片通常配备独立的内存单元，因此这类系统的内存采用分布式组织而非集中式组织
- 许多分布式内存设计能实现对本地内存的快速访问，而远程内存访问速度则显著下降
- 在此类架构中，程序员和软件系统需明确区分本地与远程内存访问操作，但通常无需关注各远程存储节点间的具体分布情况
- 为支持更多的处理器数量，内存必须是分布组织而非集中组织；否则内存系统将以增大访问延迟的代价来满足更多处理器的带宽需求
- 由于上述问题，SMP 随处理器数量的增加会逐渐丧失优势，因此绝大多数超大规模多处理器系统都采用了分布式内存组织
- 下图展示了分布式共享内存多处理器的基本结构：
- DSM 多处理器也被称为非均匀内存访问架构（Nonuniform Memory Access，NUMA），因为数据访问时间取决于数据字在内存中的物理位置
- DSM 的主要缺点是处理器间的数据通信机制变得更为复杂，且需要软件层面付出更多努力才能充分利用所增加的内存带宽优势
Hurdles of Parallel Processing¶

多处理器系统的设计面临着许多挑战，主要包括以下几个方面：

程序中有限的并行能力
相对高昂的通信开销，或者说并行处理器中远程访问的高延迟问题
- 在现有的共享内存的多处理器中，不同核心间的数据传输可能耗费 35 至 50 个时钟周期
- 而跨芯片的核心间通信则需 100 到 300 甚至更多时钟周期（针对大规模多处理器）
- 具体时长取决于通信机制、互连网络类型以及多处理器的规模

它们对应的具体解决方法为：

对于应用程序并行能力不足的问题，主要需从软件层面着手：
- 一方面采用能提供更优并行性能的新算法
- 另一方面依靠软件系统，最大化处理器完整配置下的有效执行时间
对于降低远距离延迟的影响，我们可以：
- 通过硬件机制（如缓存共享数据）或软件手段（如重构数据结构使访问本地化）来减少远程访问次数
- 借助多线程技术或预取策略来尝试掩盖延迟

Centralized Shared-Memory¶

集中式共享内存多处理器含有多个较大、多级的高速缓存来减少内存带宽的需求。对称的共享内存机器通常支持对共享数据和私有数据的缓存，其中：

私有数据（Private Data）仅被一个处理器使用
- 当私有数据被缓存时，其存储位置会迁移至高速缓存中，从而降低平均访问时间以及所需的内存带宽
共享数据（Shared Data）则能被多个处理器共同访问
- 对于共享数据的缓存处理，其值可能被复制到多个高速缓存中。除了缩短访问延迟和减少内存带宽需求外，这种复制还能缓解多处理器同时读取同一共享数据项时可能产生的竞争问题
- 然而，共享数据的缓存也带来了新的挑战——高速缓存的一致性（Coherence）问题

Cache Coherence Problem¶

高速缓存一致性问题指的是由于两个不同的处理器对内存的视图是通过各自的高速缓存建立的，因此这些处理器最终可能看到同一内存位置下的不同值（这可能是由于一个处理器修改了该内存位置的值，而另一个处理器并未更新其高速缓存中的值所致，本质上来源于我们同时拥有由主存定义的全局状态和由各处理器核心私有的独立缓存所定义的局部状态）

我们定义，如果一个内存系统对任何数据项的读取都能返回该数据项最近被写入的值，我们就可以说这个内存系统是一致的，这一定义实际包括了内存系统行为的两个方面：

一致性（Coherence）：规定了读操作可以返回哪些值
连贯性（Consistency）：决定了写操作的值何时能被读操作返回

当满足以下条件时，我们称内存系统具有一致性：

处理器 P 对位置 X 的写入操作后紧跟着 P 对 X 的读取操作，且在该写入与读取之间没有其他处理器对 X 进行写入时，该读取总是返回由 P 所写入的值
- 该性质保留了程序顺序，而且该性质即使在单处理器中也依然成立
当一个处理器对位置 X 的读取操作发生在另一个处理器对 X 的写入操作之后，只要读写之间有足够的时间间隔 , 且在两次访问之间没有其他对 X 的写入发生，该读取将返回被写入的值
- 该性质定义了内存一致性的核心含义：若某个处理器能持续读取到过时的数据值，那么显然可以判定该内存处在不一致的状态
写串行化（Write Serialization）：针对同一位置的写操作是可串行的（Serialized）。也就是说，任何两个处理器对该位置的两次写操作，在所有处理器看来，都遵循相同的顺序。例如，若先后向某位置写入值 1 和 2，所有处理器都不可能先读到 2 再读到 1

尽管上述三个性质已足以确保一致性，但连贯性同样至关重要，比如：我们无法要求对 X 的读取操作能立即获取其他处理器对 X 所写入的（最新）值，因为此时写入的数据甚至可能尚未离开原来的处理器

一致性与连贯性互为补充：

一致性规定了针对同一内存地址读写操作的行为
连贯性定义了涉及不同内存地址访问时的读写行为

Cache Coherence Protocols¶

在多处理器内运行的程序中，同一数据的多份拷贝通常会同时存在于各级高速缓存中。在一致性的多处理器中，高速缓存提供了共享数据的迁移（Migration）与复制（Replication）的双重功能

迁移：数据项可透明地转移至本地高速缓存并被使用。这既降低了访问远程分配的共享数据的延迟，又缓解了共享内存的带宽压力
复制：有效减少了读取共享数据时的访问延迟和资源争用

由此可见，实现高效的迁移与复制对提升共享数据访问的性能而言至关重要。因此，多处理器引入硬件级协议来维护高速缓存的一致性。这个协议被称为高速缓存一致性协议（Cache Coherence Protocols），其实现核心在于追踪数据块的共享状态。每个缓存块的状态通过与之关联的状态位来维护（类似于单处理器高速缓存中的有效位和脏位）。根据具体实现技术的不同，可以将协议分为以下两类：

基于目录（Directory Based）：特定物理内存块的共享状态被保存在一个称为目录（Directory）的位置
监听（Snooping）：每个持有物理内存块数据拷贝的高速缓存均可追踪该块的共享状态

Snooping Coherence Protocols¶

要维持高速缓存一致性要求，有写无效协议（Write Invalidate Protocol）和写更新（Write Update）/写广播（Write Broadcast）协议两种方法

Write Invalidate Protocols¶

写无效协议确保处理器在写入数据项前拥有对该项的独占访问权

独占访问能保证执行写入操作时不存在任何其他可读或可写的副本：该项数据的所有其他高速缓存的拷贝均会被置为无效状态
当读取操作发生时，高速缓存未命中，这迫使系统必须获取数据的新副本
对于写入操作，我们要求执行写入的处理器拥有独占访问权限，防止其他任何处理器同时进行写入
- 若存在两个处理器试图同时写入同一数据的情况，其中一方将获胜，导致另一方的数据拷贝失效；另一方若要完成其写入操作，就必须获取包含最新更新值的数据新拷贝
执行无效指令时，处理器只需获取总线控制权，并将待失效的地址通过总线广播出去。
所有处理器持续监听总线上的地址信号：若发现总线上出现的地址出现在自己的高速缓存中，则立即将对应的高速缓存数据标记为无效
在高速缓存失效时：
- 在写穿式（Write-Through）高速缓存中，查找数据项的当前值较为简单，因为所有已写入的数据都会立即发送至内存，从中总能获取到数据项的最新值
- 对于写回式（Write-Back）高速缓存而言，确定最新数据值的难度更大，因为数据项的最新值可能存在于私有高速缓存而非共享高速缓存或主存中，不过我们可以对高速缓存失效和写入操作采用相同的监听机制：
  - 每个处理器都会监听共享总线上传输的所有地址
  - 当某处理器发现自己持有目标缓存块的脏拷贝时，会将该缓存块作为读请求的响应内容返回，并终止对主存（或三级高速缓存）的访问

Example

我们通过为每个核中集成一个有限状态控制器来实现监听式一致性协议。该控制器响应来自核内处理器及总线（或其他广播媒介）的请求，改变选定高速缓存块的状态，同时利用总线访问数据或使其失效。我们规定协议包含三种状态：

无效（Invalid）
共享（Shared）：表示私有高速缓存中的块可能被多个核共享
修改（Modified）：表明某个块已在私有高速缓存中被更新；并且该状态意味着该块具有独占性

下表展示了由核产生的请求（上半部分）以及来自总线的请求（下半部分）与高速缓存一致性的关系：

当总线上出现无效请求或写失效时，所有私有高速缓存中存有该缓存块拷贝的核都会将其置为无效。对于写回式高速缓存的写失效情况，若该块仅存在于一个私有高速缓存，且处于独占状态，那么该缓存还需执行写回操作；否则可直接从共享高速缓存或主存读取数据

下图展示了采用写无效协议和写回式高速缓存的单个私有高速缓存块的有限状态转换图：

任何有效的高速缓存块要么处于一个或多个私有高速缓存的共享状态，要么严格位于单一高速缓存的独占状态
任何向独占状态的转换（这是处理器写入块的必要条件）都要求在总线上发出无效或写失效信号，这将导致所有本地高速缓存将该块置为无效状态
此外，若其他本地高速缓存曾以独占状态持有该块（变脏了），则该高速缓存会执行写回操作，从而提供包含目标地址的数据块
最后，当总线出现针对独占状态块的读失效时，持有该独占拷贝的本地高速缓存会将其状态变更为共享状态

Write Update / Broadcast Protocols¶

写更新 / 写广播协议：在写入数据项时更新该数据项的所有缓存拷贝

由于写更新协议必须向所有共享缓存行广播写入操作，因而会消耗更多的带宽

MSI Extensions¶

先前描述的一致性协议是一种简单的三状态协议，通常以其状态的首字母来指代，因此被称为 MSI（Modified，Shared，Invalid）协议。我们可以基于这一基础协议进行扩展，通过增加额外状态和事务来优化特定行为，从而可能提升性能表现。其中，最常见的两种扩展是：

MESI 协议：增加了独占（Exclusive）状态，形成四种状态：修改（Modified）、独占（Exclusive）、共享（Shared）和无效（Invalid）
- 独占状态表示缓存块仅存在于单一高速缓存中，且未被修改
- 若某个块处于独占状态，对其进行写入时无需产生失效信号，从而优化了同一高速缓存先读取后写入该数据块的场景
- 当然，当对处于独占状态的块的读失效发生时，必须将该块转为共享状态以维持一致性
- 添加独占状态的好处在于：当同一个核再次写入处于独占状态的数据块时，既不需要获取总线访问权，也不需生成失效信号，因为系统明确知晓该数据块仅存在于本地的这个高速缓存中；处理器只需将其状态改为已修改即可实现更新
- 通过将一致性状态位编码为独占状态位、并用脏位标识修改情况即可轻松实现该状态的扩展应用
MOESI 协议：在 MESI 协议的基础上增加了拥有（Owned）状态，用于表示相关缓存块由该高速缓存持有，且主存中的拷贝已过时
- 在 MSI 和 MESI 协议中，当尝试共享处于修改状态的缓存块时，在原高速缓存和新的共享高速缓存中，该块的状态都会转变为共享状态，且必须将其写回主存
- 而在 MOESI 协议中，原高速缓存的修改状态可以直接转换为拥有状态而无需立即写入内存。其他新的共享该块的高速缓存则保持共享状态；而仅由原高速缓存持有的拥有状态表明主存拷贝已失效，且指定高速缓存是所有者
- 当发生失效时，所有者必须提供该数据块（因为主存未更新）；若被替换，则需将其写回主存
MESIF 协议：在 MESI 协议的基础上增加了转发（Forward）状态，表示哪个共享处理器（在具有相同共享状态数据块的处理器之间）应该响应请求
- 为行的最新请求者分配 Forward 状态

Increase Snoop Bandwidth¶

随着多处理器中处理器数量的增加，或每个处理器的内存需求增长，系统中任何集中式资源都可能成为瓶颈，监听式高速缓存的带宽就是其一，因为每个高速缓存都必须检查每一次的失效情况，而增加互连带宽只会将问题转嫁给高速缓存。下面给出一些增加监听带宽的技术：

复制标签位（Tags），实现带宽倍增
如果多核处理器共享最外层的高速缓存，那么可采用分布式的高速缓存——每个处理器分管部分内存区域，并处理对应地址空间的监听请求
- 鉴于 L3 承担着过滤监听请求的功能，L3 必须具备包容性（Inclusive）
可在最外层的共享高速缓存层（如 L3）设置一个目录
- 同样地，L3 必须保持包容性
- 引入目录结构后，无需广播至所有 L2 缓存，仅需查询目录指向的可能持有数据块拷贝的特定 L2 即可
- 与前一种方法类似，其关联的目录条目亦可以分布式存储

下图展示的就是一个采用分布式高速缓存系统的多核处理器：

Coherence Miss¶

在计组课程中，我们知道单处理器的失效率可以被分解为三个 C：容量（Capacity）、强制（Compulsory）和冲突（Conflict）。它们既揭示了应用程序行为特征，也为高速缓存的设计优化提供了方向。同理，由处理器间通信引发的失效（通常称为一致性失效，Coherence Misses）也可归因于两个因素：

真共享失效（True Sharing Misses）：
- 在基于无效的协议中，处理器首次写入共享缓存块时会触发无效操作，以确立对该块的所有权
- 此外，当其他处理器尝试读取该缓存块中被修改的数据字时，会发生失效并导致相应块的传输
- 上述两类失效均被归类为真共享缺失，因为它们直接源于处理器间的数据共享行为
伪共享失效（False Sharing Misses）：
- 在基于无效的一致性算法中，每个缓存块仅有一个有效位；当某个块因其中某些数据字被写入而被无效化（随后使用便引发失效）时，便会出现了伪共享
- 若接收无效化的处理器实际使用了被写入的字，则该引用属于真共享引用，此时无论块有多大都会引发失效
- 然而，若被写入字与读取字不同，且无效化并未传递新值，仅造成额外缓存失效时，即为伪共享失效
- 此时虽然块是被共享的，但高速缓存中并无实际共享的数据字；若块大小为单个字数据，则此失效不会发生

Example

Answer

Distributed Shared Memory¶

分布式共享内存添加目录至每个节点（单个多核处理器，或在内部实现一致性的小型处理器集合），每个目录会记录每个可能被缓存的块的状态信息，包括哪些高速缓存（或高速缓存组）拥有该块的副本、数据是否是脏的（已被修改）等，当高速缓存失效时不需要执行一致性协议的广播操作，其示意图如下：

Directory-based Cache Coherence Protocol¶

目录协议必须实现两个核心操作：处理读失效和处理对共享且干净的高速缓存块的写入。

为实现这些功能，目录需要追踪每个高速缓存块的状态。具体有以下几类状态：

共享：一个或多个节点缓存了该数据块，且内存中的数值与所有缓存副本保持同步更新
未缓存（Uncached）：没有任何节点持有该缓存块的副本
已修改（Modified）：只有一个节点持有该数据块副本，且已执行过写操作，因此内存中的对应副本失效；此时该处理器被称为此数据块的所有者（Owner）

下图展示了节点间传递的各类消息：

本地节点（Local Node）是发起请求的节点，家节点（Home Node）则是存储着目标地址对应内存位置及目录条目的节点。
物理地址空间采用静态分布方式，因此总能确定哪个节点存有特定的物理地址的内存和目录信息（例如高位比特可表示节点编号，低位比特则表示该节点内存中的偏移量）
当家节点同时作为本地节点时仍需访问目录，因为数据副本可能存在于被称为远程节点（Remote Node）的第三方节点中
- 远程节点是拥有高速缓存块副本的节点（无论该副本处在独占状态还是共享状态）
- 远程节点可能与本地节点或家节点相同，此时处理器间消息可替换为处理器内消息，其他机制保持不变