计算机体系结构——多处理机系统_旋转锁 栅栏 计算机系统

一、概述

1.1 重要概念

粗粒度和细粒度的多线程

1） 粗粒度多线程：通过线程间的切换部分隐藏了代价较高、时延较长的阻塞带来的吞吐率的损失。
优点：大大减少了线程间切换的次数，并且不减慢每个独立线程的执行。
缺点：不能有效减少吞吐率。

2） 细粒度多线程：每条指令之间都能进行程序切换，从而消除了完全空闲的流出槽，导致多个线程交替执行。
优点：能够隐藏由任何或长或短的阻塞带来的吞吐率的损失。
缺点：减慢了每个独立线程的执行。这是因为即使没有任何阻塞，线程也会被其他线程的指令插入执行而导致延迟。

3） 同时多线程：一个时钟周期内调度多条指令使用流出槽。
优点：同时实现指令级和线程级并行。
缺点：实际中一些因素，如活跃线程个数、缓冲大小限制、可并行指令以及从多个线程中取出指令的能力等，仍将限制流出槽的利用率。

评估指标

通信延迟

通信延迟＝发送开销＋跨越时间＋传输延迟＋接收开销

跨越时间

数字信号从发送方的线路端传送到接收方的线路端所经过的时间。

传输时间

全部的消息量除以线路带宽。

多处理机的架构

根据多处理机系统中处理器个数的多少可将多处理机的类型分为
第一类为集中式共享存储器结构；
第二类为分布式存储器结构；
每一类代表了一种存储器的结构和互连策略。

二、分布式存储器多处理机系统

处理器的规模较大，存储器分布到各个处理器上，而非采用集中式。系统中每个结点包含了处理器、存储器、I／O以及互连网络接口。

2.1 分布式存储器架构的特征

将存储器分布到各结点有两个优点：
第一，如果大多数的访问是针对本结点的局部存储器，则可降低对存储器和互连网络的带宽要求。
第二，对局部存储器的访问延迟低。
分布式存储器结构最主要的缺点：
处理器之间的通信较为复杂，且各处理器之间访问延迟较大。

2.2 地址空间的组织方案

共享地址空间的机器

可利用load和store指令中的地址隐含地进行数据通信，因而可称为共享存储器机器。

(1) 与常用的集中式多处理机使用的通信机制兼容。
(2) 当处理器通信方式复杂或程序执行动态变化时，易于编程；同时在简化编译器设计方面占有优势。
(3) 当通信数据较小时，通信开销较低，带宽利用较好。
(4) 通过硬件控制的Cache减少了远程通信的频度，减少了通信延迟以及对共享数据的访问冲突。

多个地址空间的机器

根据简单的网络协议，通过传递消息来请求某些服务或传输数据，从而完成通信。因而这种机器常称为消息传递机器。

三、集中式存储的多处理机系统

由几个到几十个处理器构成的MIMD机器。各处理器通过大容量的Cache和总线互连，共享一个单独的物理存储器。又称为对称式共享存储器结构机器或者UMA机器。

支持对共享数据和私有数据的Cache缓存的优势

私有数据缓冲在Cache中降低了平均访存时间和对存储器带宽的要求，使程序的行为类似于单机。共享数据的Cache缓存可降低访存时间和对存储器带宽的要求，还可减少多个处理器同时读共享数据所产生的冲突。

四、多处理机间的数据一致性

4.1 多处理机存储系统一致性的特征

若一个存储系统满足以下三点，则称该存储系统是一致的。
(1) 处理器P对X单元进行一次写之后又对X单元进行读，读和写之间没有其他处理器对X单元进行写，则读的返回值总是写进的值。
(2) 一个处理器对X单元进行写之后，另一处理器对X单元进行读，读和写之间无其他写，则读X单元的返回值应为写进的值。
(3) 对同一单元的写是顺序化的，即任意两个处理器对同一单元的两次写，从所有处理器看来顺序都应是相同的。

一致性（coherency）和连贯性（consistency）

如果对某个数据项的任何读操作均可得到其最新写入的值，则认为这个存储系统是一致的。定义包括两个方面：
1）返回给读操作的是什么值，即coherency(一致性)；
2）什么时候才能将已写入的值返回给读操作，即consistency(连贯性)。
一致性和连贯性是互补的，一致性定义了对同一个存储器地址进行的读写操作行为，而连贯性定义了关于访问其他存储地址的读写操作

多处理机的写直达和写回cache的区别

写直达 Cache 与写回式 Cache 最大的区别在于，本地处理器不需要读取另一个处理器脏Cache 块。从而在写直达协议中不再提供硬件在读失效或写失效时将被替换的块的强制写回主存，也不再访问其他 Cache 拷贝而中断处理器访问。主存在 CPU 每次写 Cache 块时都会更新，所以在处理器产生读失效后就会直接访问主存，从主存中读取到正确的值。

在写直达 Cache中，有效的 Cache 块都与主存保持一致。

cache写作废和写更新策略

决定了在多处理机系统中某数据组织方式下实现cache一致性的准则。

写作废协议

在一个处理器写某个数据项之前保证它对该数据项有唯一的访问权。

写更新协议

当一个处理器写某数据项时，通过广播使其他Cache中所有对应的该数据项副本进行更新。

多处理机中的cache问题

伪共享（False sharing）

伪共享参考[^1]

4.2 跟踪共享数据状态的技术

决定了多处理机间数据交换的组织方式。

4.2.1 目录协议

用一种专用的存储器所记录的数据结构，它记录着可以进入Cache的每个数据块的访问状态、该块在各个处理器的共享状态以及是否修改过等信息。
在每个节点增加了目录存储器用于存放目录。存储器的每一块在目录中对应有一项，每个目录项主要有“状态”和“位向量”两个内容。“状态”描述目录对应存储块的当前情况，“位向量”共有N位，每一位对应一个处理机是否在Cache中有该块的副本。当处理器对某一块进行写操作时，根据位向量通知具有相应副本的处理器进行失效等操作

目录的特征

目录是一种专用的存储器所记录的数据结构，记录着可以进入Cache的每个数据块的访问状态，详见下一节。

宿主结点（home节点）：存放有存储器块和对应地址目录项的节点。

目录承担了一致性协议操作的主要功能：

发往一个目录的消息会产生两种不同类型的操作

更新目录状态
发送消息（从而能够）满足请求服务

目录项可能接收到三种不同的请求

读失效、写失效、数据写回

实现方式

在每个节点增加了目录存储器用于存放目录，cache的每一块在目录中对应有一项；
每一个目录项主要包含的状态：

1. 目录对应存储块当前状态：有无该块，块是否共享还是独占写状态

• 是否共享（shared）
  在一个或多个处理器上有这个块的拷贝，且主存中的值是最新值（所以Cache均相同）
• 未缓冲
  所有处理器的Cache都没有此块的拷贝。
• 修改位
  仅有一个处理器上有此块的拷贝，且已对此块进行了写操作，而主存的拷贝仍是旧的，这个处理器称为该块的拥有者。

2. 位向量，共有N（处理器的个数）位，每一位对应于一个处理器的局部Cache，用于指出该Cache中有无该存储块的拷贝。
   当此块被共享时，每个位指出与之对应的处理器是否有此块的拷贝；当此块为专有时，可根据位向量来寻找此块的拥有者

CPU请求时块的状态变化

1）当一个块处于未缓冲状态，对此块发出的请求及处理操作为：
读失效：将存储器数据送往请求方处理器，且本处理器成为此块的唯一共享节点，本块状态转为共享。
写失效：将存储器数据送往请求方处理器，此块成为调整为modified。
2）当一个块处于共享状态，mem中的数据是其当前最新值，对此块发出的请求及处理操作为：
读失效：将存储器数据送往请求方处理器，并将其纳入共享集合（在位向量中标记）。
写失效：将数据送往请求方处理器，对共享集合中所有的处理器发送写作废消息，且将共享集合置为仅含有此处理器，本块状态变为modified
3）当一个块处于modified状态，且本块最新值保存在共享集合指出的拥有者处理器中，对此块发出的请求及处理操作为：
读失效：将“取数据”消息发往拥有者处理器，使该块的状态变为共享，并将数据送回目录结点写入存储器，进而把该数据返送请求方处理器，将请求方处理器加入共享集合。
写失效：本块将有一个新的拥有者
数据写回：拥有者处理器的Cache要替换此块时必须将其写回，从而使存储器中有最新拷贝（宿主结点实际上成为拥有者），此块成为非共享，共享集合为空。

4.2.2 监听协议

移步链接：多处理机系统的cache一致性——监听协议

五、多处理机间的同步

5.1 多处理机实现同步的方法

软件方法

1）旋转锁：是指处理器环绕一个锁不停地旋转而请求获得该锁，当锁的占用时间很少以及加锁过程延迟很低时可以采用旋转锁。
2）软件排队锁：可以排队记录等待的进程，当锁释放时发送出一个已确定的等待进程。软件实现主要是采用记录等待进程的排队数组进行排队。
3）组合树：是多个请求在局部结合起来形成树的一种分级结构，局部组合的分枝数量大大小于总的分枝数量，因此组合树降低冲突的原因是将大冲突化解成为并行的多个小冲突。

硬件方法

1）硬件排队锁：可以排队记录等待的进程，当锁释放时发送出一个已确定的等待进程。硬件实现一般是在基于目录的机器上，通过硬件向量等方式来进行排队和同步控制。
2）硬件原语：用硬件实现，能够以原子方式自动读出和修改存储单元。

5.2 原子操作

理解原子操作首先需要理解原子交换的概念，原子交换是将一个存储单元的值和一个寄存器的值进行交换，且交换是不可分的。通常这个存储单元可以称为同步锁，假设0代表锁可用，1代表锁不可用；交换后可以表示存储单元的锁被寄存器所对应的进程占用。

原子操作有很多种实现方式：

测试并置（test_and_set）

可以一条指令完成。
先测试一个值，如果符合条件则修改其值。（存储单元里对应的锁是0，读出来（测试）发现是0（满足条件），空闲，就占用这个锁；然后+1，修改其值）。

fetch and increment

可以一条指令完成。
返回存储单元的值并自动增加该值（读出来0自动加1）

lr和sc指令

两条指令完成。
先链取，再条件存——成功返回1，失败返回0，从第二条指令的返回值可以判断该指令对的执行是否成功，即如果取回来是0，则其他线程仍在占用，本线程占用失败；如果返回值是1 ，表示本线程占用成功。

实现多处理机的旋转锁

指处理器环绕一个锁不停地旋转而请求获得该锁。处理器环绕一个锁不停地旋转（测试）而请求获得该锁。当锁的占用时间很少以及加锁过程延迟很低时可采用旋转锁。
只要敢占这个锁，同步锁在这里同步的处理机进程数量很多的时候，自旋锁阻塞处理器，在循环中等待锁被释放，旋转锁开销会很大

栅栏同步

并行循环程序中一个常用的同步操作。
栅栏强制所有到达该栅栏的进程进行等待，直到全部的进程到达栅栏，然后释放全部的进程，从而形成同步。
栅栏的典型实现是用两个旋转锁：一个用来记录到达栅栏的进程数，另一个用来封锁进程直至最后一个进程到达栅栏。

标准栅栏同步时间

忽略读写锁的时间。N 个处理器中的每一个都需要 C 个周期来锁住与栅栏相关的计数器并修改它的值，然后释放锁。考虑最坏的情况，所有 N 个处理器都要对计数器加锁并修改它的值。
当存在排队锁提高栅栏的性能的情况下，由于锁只能顺序访问计数器，在同一时间只能有一个处理器修改计数器的值，所以共需要花 NC 个时钟周期使得所有的处理器都到达栅栏。
若不存在排队锁，则N个处理器争用时，时间为NC，N-1个处理器争用时，时间为(N-1)C，以此类推，则总的时间为NC + (N − 1)C + (N − 2)C + ⋯ + 2C + C，即NC(N + 1)/2。

k 元组合树栅栏同步时间

k 元组合树是多个请求在局部结合起来形成树的一种分级结构，局部组合的分枝数量大大小于总分枝数量，因此组合树降低冲突的原因是将大冲突化解成为并行的多个小冲突。变量 k表示扇入数目。树中每个结点组合 k 个进程，提供一个单独的计数器和锁，因而在每个结点有k 个进程进行竞争，当第 k 个进程到达树中对应结点时则开始进行父结点，然后递增父结点的计数器，当父结点计数器到达 k 时，置 release 标志。每个结点计数器在最后一个进程到达时被初始化。所需时间为：

参考文献

1. 知乎：伪共享（False Sharing）
2. 软件学报：片上多核处理器Cache一致性协议优化研究综述