多核并行体系结构-投机同步

文中内容来源于我这学期某门课程的presentation, 这里把ppt和讲稿稍作修改发出来留存下~

内容主要是包括这篇论文:

论文: Speculative synchronization: applying thread-level speculation to explicitly parallel applications

为什么需要投机同步

同步屏障(Barrier), 锁(Lock)和标志(Flag)是程序员编写并行程序广泛使用的几类操作, 主要目的是使并行线程之间不发生竞争.

简单回顾一下屏障, 锁和标志位的含义:

• 锁相信大家都很清楚了, 这里主要回顾一下屏障和标志

• 同步屏障是多对多的同步, 在所有线程到达屏障之前, 任何先到达屏障的线程都必须等待, 为了实现屏障, 需要一个临界区来实现对线程数量的统计. 同步屏障 wiki

• 而标志是指一对多的同步, 消费者接收到生产者对flag的置位之前将保持等待, 由于只有一个生产者, 故读写flag并不需要临界区的支持

大多数程序员为了并行程序的稳定性和安全性, 在同步操作的时候会显得过于保守, 即使有些竞争可能并不发生, 或者发生的概率非常小, 程序员也会进行加锁或者是设置屏障.

典型的场景:

• 难以分析的指针访问
• 概率很小的哈希碰撞

保守的同步策略将带来较大的性能损失, 因此我们希望引入一种硬件设计, 能让线程投机地跨越锁, 标志和屏障, 来继续执行之后的代码, 如果发生冲突, 再将线程回滚.

借鉴线程级投机的思想

线程级投机主要通过提取串行程序中的并行性来进行投机, 其主要的思路是通过对线程进行排序, 一个线程在保证与前序线程无冲突的情况下提交该线程的状态.

投机同步借鉴了很多在线程级投机的思想, 比如使用每个处理器的私有缓存保存投机数据, 始终维持安全线程的执行, 跟踪检测访存冲突和回滚等.

在线程级投机中, 安全线程的定义是序号最小的线程(即最早开始执行的线程), 而在投机同步中, 不对线程进行排序, 对安全线程的定义如下

• 对于锁而言, 安全线程是锁的持有者
• 对于屏障而言, 安全线程是未到达屏障的线程
• 对于标志而言, 安全线程是标志的置位者

同时提出了一种叫投机同步单元(简称SSU)的硬件, 用于从处理器卸载对一个同步变量的操作, 以让线程投机的执行下去.

文中方案一些特性

投机同步的核心思路其实在于希望用尽量简单的硬件方案实现较大的性能提升

• 简化的硬件设计方案: 和TLS不同
  • 投机同步不需要保证线程的顺序
  • 没有多版本的支持, 不仅检测RAW(写后读)冲突, 对于名称冲突WAW(写后写), WAR(读后写)等冲突也直接回滚投机线程
  • 没有伪共享的支持, 硬件设计都是对一个缓存行(cache line)的操作
  • 对于不同的同步方式具有统一的硬件支持
• 类似于OpenMP, 文中利用m4宏设计了一种高层的抽象, 能够让程序员像使用常规同步一样使用投机同步
• 和传统同步方案保证兼容

右图展示了常规同步的m4宏和投机同步的m4宏的区别, 这个在后文将详细说明, 这里可以看到加粗的部分是SSU提供的接口

m4: 是一个通用的宏处理器, 是POSIX标准下的一部分

OpenMP利用pragma预处理指令, 实现并行接口的抽象

投机锁的例子

首先讲一讲投机锁和投机屏障的例子, 用图先给大家一个概念, 然后我们再详细的介绍投机同步的硬件结构以及一些实现细节

这时我们可以先不去思考如何进行冲突检测, 投机锁的获取和释放这些问题, 先简单的理解一下这个方案的思路

在文章的剩余部分都将用黑色圆圈表示安全线程, 用红色圆圈表示投机线程, 同时用横杠表示同步点

首先介绍一下投机锁的例子, 图中的 Acquire 和 Release 分别表示锁的获取和释放。

• 首先是所有线程都未进入临界区, 均为安全线程

• 然后线程A首先获得锁并成为安全线程, 进入临界区

• 之后线程B、E投机地进入临界区, 由于线程A已经获取了锁, 所以B, E是投机线程

• 由于线程C、D尚未进入临界区，故C、D也是安全的

• 然后线程E首先退出临界区，但此时线程E仍然可能和未退出临界区的安全线程A发生冲突，故在安全线程A退出临界区之前，线程E不能提交。

• 当安全线程A退出临界区时，就可以将投机线程E提交了

• 同时由于A释放锁, 投机线程B和C将争夺锁, 假设投机线程B得到锁，将由投机状态变为安全状态

这个大概就是整个投机锁的全过程

投机屏障的例子

下面是投机屏障的例子，由于有了投机锁的概念，投机屏障相对容易理解

• 首先当所有线程都未到达屏障的时，所有线程都处于安全状态

• 之后线程C投机地跨过屏障

• 之后线程A投机地跨过屏障

• 只有当最后一个线程到达屏障时，才可以提交所有的投机线程

SSU硬件结构

介绍完了两个例子后, 我们来说说它们的硬件是如何设计和实现的

实现投机同步需要在常规体系结构上引入一个叫做投机同步单元 (Speculative Synchronization Unit, SSU)的模块

SSU存在于共享内存的多处理器的每个处理器私有的缓存结构上，一般就是L1 Cache和L2 Cache

SSU的作用是从处理器上卸载对一个同步变量的操作，让处理器可以向前投机执行代码

SSU的组成包括:

1. 扩展的缓存控制器

2. 在L1 cache上增加一个额外的缓存行, 该缓存行只能由ssu写入, 其他来自本地和远程的请求可以访问, 主要功能为:

   1. 保存同步变量

   2. 增加状态位"Acquire"和"Release", 当ssu获取到一个来自cpu的同步变量时, 这两个位将被置位

      （当投机线程退出临界区时，Release位将被清除。当SSU空闲时(即ssu释放了同步变量时)，Acquire位将被清除。）

3. 为每一个缓存行(L1 + L2)增加一位"投机位(Speculative bit)", 标志该缓存行是否是正在被投机写入或者读取

对于32KB的L1 Cache和 1MB的L2 Cache， SSU大约需要一共2KB的存储空间。

SSU-投机锁请求

下面介绍一下在发生投机同步的时候, SSU是如何工作的

首先是投机的锁请求

该行为发生在已经有一个进入临界区的安全线程, 然后另一个线程投机的进入临界区的时刻

文中使用的锁获取原语是T&T&S （test and test and set)，右图展示了使用该原语进行锁获取的汇编代码, 也完全可以换成其他的原语。

当处理器执行到锁请求时，我们分CPU侧和SSU侧的行为进行讨论

首先是CPU侧：

• CPU首先将锁的地址发送给SSU
• 然后保存当前寄存器的状态 (checkpoint)
• 然后继续投机地进入临界区，执行临界区的代码

然后是SSU侧：

• SSU首先将Acquire位和Release位置位
• 将CPU提供的锁变量提取到额外的缓存行(L1 Cache) 中
• 然后SSU开启Test循环自旋，不断地尝试获取锁
• 一旦Acquire位被置位，将CPU投机访存的部分置投机位

这里需要注意的是，为了保证缓存行的安全副本，在第一次投机访问缓存脏行的时候，必须将该缓存行写回主存。

SSU-投机锁获取

投机锁获取的行为发生在一个安全线程退出临界区，SSU获取到锁变量并成为安全线程的时候。

在此之前，SSU一直在锁变量上自旋，当发现锁变量被释放时，SSU检查当前的Release位的状态，如果是置位状态，则认为当前投机线程仍然在临界区执行。

此时SSU将通过T&S获取到锁, 然后将清除缓存行上所有的投机位，提交缓存值，该线程成为安全线程，并且SSU变为空闲状态。

之后的锁变量的释放操作就是常规的同步操作，由CPU完成。

SSU-投机锁释放

投机锁释放的行为发生在投机线程先于安全线程退出临界区，然后才是安全线程退出临界区之后的时候。

此时SSU的Release位应该是清空的状态，表示投机线程已经退出了临界区

这时与投机锁获取的不同之处在于, 线程将直接跳过通过T&S锁获取的操作, 直接提交投机线程, SSU变为空闲状态

SSU-冲突处理和回滚

底层的缓存一致性协议会检测访问冲突, 比如收到外部的invalid或者对脏行的read时, 故文中主要讨论SSU如何处理这些冲突

• 我们将未标记投机位的缓存行称为安全行, 将标记了投机位的缓存行称为投机行
• 当安全行接受到外部消息时, 就按照缓存一致性协议正常处理
• 当投机行接受到外部消息时:
  • 发出者可能是投机线程, 也可能是安全线程, 无论如何, 我们都将直接回滚接收线程 (由于设计上并没有为线程定义任何的顺序, 故所有对投机行的一致性消息都认为是冲突)
  • 回滚的策略具体按如下步骤:
    • 首先将所有被投机位标记的脏行重新失效化处理, ( 如果缓存行不脏的话就无需失效缓存行)
    • 清除所有的投机行的投机位
    • SSU强制让CPU恢复寄存器的检查点状态

这样就可以让线程快速回滚到进入临界区前的状态

SSU-缓存溢出

当缓存不够需要发生缓存行替换时

投机行永远不会被换出到主存

• 因为首先不论是投机读还是投机写, 投机行都记录了过去的访问历史, 将用于可能的冲突检测
• 如果是投机写(标记为脏)则更不能替换, 因为数据本身都不安全了

所以替换时首先会选择安全行进行替换

如果找不到安全行替换, 则该投机线程将暂停, 直到该线程成为安全线程, 即SSU拿到锁, 或者是发生冲突该线程回滚

由于安全线程没有投机行, 因此缓存未命中时, 直接按照传统的缓存替换策略进行替换即可

对多重锁和嵌套锁的支持

在投机执行的时候, 可能会碰到两种情况

• 第一种是投机线程已经执行完上一个临界区, 并即将进入下一个临界区, 而安全线程还停留在上一个临界区的情况, 即多重锁
• 第二种是投机线程未退出临界区, 但是在临界区内部将获取另一把锁的情况, 即嵌套锁

文中首先提供了一个程序接口, 可以暴露SSU的状态, 这时程序员可以选择自旋等待SSU变为空闲来手动处理这种情况

如果采用第一种策略, 程序的性能不能得到完全的发挥, 另一种策略, 我们可以分情况讨论:

• 如果获取的是不同的锁, 我们可以简单的将第二把锁视为投机的变量, 因为对锁的操作本质上也是读写操作, 然后可以用完全一致的冲突处理策略来进行冲突检测, 如果出现其他线程对锁变量的获取操作, 那么直接回滚该投机线程
• 如果获取的是同一把锁, 则不能与前一个方式一致, 这时又可以分为两种情况:
  • 如果投机线程已经退出了之前的临界区, 则直接合并两个临界区, 意味着Release位在第一个临界区退出时被清除, 然后在第二个临界区又被置位, 但是CPU无需为第二个临界区设置检查点, 如果发生冲突就直接回滚到第一个检查点上
  • 如果投机线程还没有退出之前的临界区, 这时投机线程只能等待其变为安全线程, 然后继续执行, 或者是等待本线程发生冲突并且回滚

投机标志

下面介绍一下投机标志和投机屏障, 投机标志可以直接由投机锁衍生而来, 而投机屏障又可以由投机标志衍生而来

观察左图投机标志的情景可以看到其和"投机锁释放"的情形十分相似，仅仅是将锁变量改变成了Flag

二者的共同之处在于都只需要在一个变量上进行自旋，当该变量达到某个值后（对于锁而言是检测到了cpu释放锁，对于flag而言是检测到了flag被设置为pass值），直接将投机线程提交。

投机屏障

由于同步屏障的本质就是锁 + 标志

故投机屏障可以由传统锁 + 投机标志实现

文中讨论的屏障实现方式是最常见的翻转感应集中式屏障 (这里不具体介绍各种屏障的实现, 可以参考《并行多核计算机体系结构基础》)（比如为什么代码中的local_f不改为一个特定的值, 而是采用翻转 -> 特定的值会导致死锁）

补充: 翻转感应集中式栅障

在屏障的临界区中需要让SSU空闲，因为对锁的获取和对count的更新必然导致投机线程发生冲突

所以这里的实现需要显式暴露SSU的状态，这个在后文的代码实现中会讲到

对软件接口(宏)的介绍

类似于OpenMP, 文中利用m4宏设计了一种高层的抽象, 能够让程序员像使用常规同步一样使用投机同步

首先是ssu_lock的实现, 该实现对应投机锁的实现, 传入锁地址, 然后如果返回值为1表示ssu接受请求, 为0表示该请求失败, 在对应的宏实现中, 当ssu拒绝请求时, 该加锁即以常规的锁实现

然后是ssu_spin(addr, value)其中addr表示flag的地址, 而value表示对应的pass值, 该操作对应投机标志的实现

然后是ssu_idle()的实现, 在上一页ppt中我们提到需要显式暴露ssu的状态, 才能让程序在投机屏障的临界区中避免必然失败的投机, ssu_idle将提供这个接口, 该操作可以暴露ssu的当前状态, 对应的SS_EXPOSE宏实现表示自旋等待ssu的空闲, 然后下面的投机屏障中在进入临界区之前使用了这个SS_EXPOSE宏, 表示程序将等待SSU结束投机才进入对count变量更新的临界区