剑客
关注科技互联网

[译] 详解如何在多核程序中实现同步扩展

高级同步方法能够提高多核软件的性能

Adam Morrison, 特拉维夫大学

为现代的多核处理器设计软件陷入了两难的境地。在传统的软件设计中,多个线程操作同一份数据,因其对共享数据更新的同步操作会使线程串行化,限制并发量,这会限制系统的可伸缩性。而对于分布式软件设计,多个线程并不共享任何可变数据,从而移除同步操作,提供更好的可伸缩性。然而分布式的设计使得一些本来由共享数据结构能轻易实现的功能变得相当困难,例如动态负载均衡、强一致性保证。分布式设计并非所有程序的良药。

共享可变数据结构的性能往往取决于使用的同步方法,要么是基于锁的,要么是无锁的。为了帮助读者做出明智的设计取舍,本文描述了一些高级的(同时也是务实的)同步方法,以期能将使用共享可变数据的设计的性能提升至对于大部分应用都能接受的水平。

共享可变数据的优缺点

为了了解设计多核软件中的困境,我们将考虑一个实际的问题:实现一个工作队列(work queue),该队列允许线程入队和出队一些工作项目——诸如待相应的事件,待处理的数据包等等。这里讨论的类似问题也对一般的多核软件设计有效。

集中式的共享队列

一个直观的工作队列设计方案(如图1a)是实现一个我们所熟知的基于链表的集中式FIFO(先进先出)队列数据结构。该数据结构支持常数数量级内存操作的入队和出队操作。并且能够轻易地实现动态负载均衡:由于所有的暂缓工作都被储存在了这个数据结构之中,空闲的线程能很容易地获取工作加以处理。为了使该数据结构线程安全,对队列链表头和链表尾的更新必须被同步,这不可避免的会限制可伸缩性。

[译] 详解如何在多核程序中实现同步扩展

使用锁来保护队列会序列化所有的操作:任何时刻仅有一个核心能够更新队列,其他核心则必须等到轮到它们。这最终产生出一个序列化瓶颈,并且很快的摧毁了性能。一个增强可伸缩性的可能性是将锁替换为无锁的同步,该方法使用原子指令来直接操作队列[1,11],故而能减少序列化的部分。(序列化依然是个问题,因为硬件的缓存一致机制亦会序列化这些更新同一个内存地址的原子指令)。在实践中,无锁同步机制往往不能够超过基于锁的同步,后文讲讨论其原因。

部分分布式队列

另一个工作队列设计通过分布的数据结构来寻求可伸缩性,该设计通过放弃集中式共享队列中的一些特性而提升并行量。譬如,图1b展示了一个每个核心使用一个SPMC(单生产者多消费者)队列的设计。每个核心仅将工作入队到自己的队列中去。而出队则能通过多种方式实现——通过遍历所有队列(通过随机地选择起点),直到找到一个包含工作的队列。

这个设计应该比集中式共享队列可伸缩性更好一些:因为不同核心的入队操作更新不同的队列,它们便可并发的运行。不同核心的出队操作也将选取不同的队列(假设所有的队列多有工作),所以这些操作也将并行执行。

这个设计所做的权衡是数据结构的一致性保证。具体来说,和集中式共享队列不同,分布式的设计并不保持程序中的因果关系。即使核心P1在核心P0将x0入队到其队列中之前将x1入队到自己的队列中,x1也有可能在x0之前出队。这样的设计弱化了数据结构本身所提供的一致性保证。

弱化的本质原因是由于在一个分布式的设计中,将本来由简单的集中式的设计所产生的各个核的数据合并成一个一致的视图这件事很困难(并且慢)。相反的,正如本例所示,分布式设计一般会弱化数据结构的一致性保证[5,8,14]。这种弱化的一致性保证是否能够被接受,取决于具体应用,但弄清这件事(推断能被接受的行为)使得使用这个数据结构变得复杂起来。

尽管各个核心SPMC队列的设计本质上有分布式特点,它却在工作量不均衡的时候产生了瓶颈。譬如说,如果只有一个核心产生任务,那么所有进行出队操作的核心都会竞争它的队列,从而使得这些核心的操作被序列化。

分布式队列

为了消除多个线程全部被同步,你可以尝试如图1c所示的设计,这个设计让每个核心都为系统里的其他核心维护一个SPSC(单生产者单消费者)队列,并将想让其他线程拿到的对象入队到这个队列里。和之前一样,这个设计弱化了队列的一致性保证。由于需要事先决定由哪个核心去拿到某一个对象,这个设计也同时让动态的负载均衡变得更加困难。

改进同步机制的动机

这里讨论的关键在于,我们需要权衡通过分布式方法设计队列数据结构获得的可伸缩性,和集中式共享队列所能提供的有用特性。不过,这里的权衡往往会因为集中式数据结构提供的难以接受的性能而无效,这将抵消该设计所带来的任何好处。本文主要强调糟糕性能的大部分原因是由于不充分的同步方法。本文探讨了能够提升集中式设计之性能的高级的同步方法,使得这些方法能够适更多的应用场景。有了这些方法在手,设计师们能够在架构自己系统之时做出更加明智的选择。

用代理方式使锁可伸缩

锁在本质上会序列化它所保护的临界区的操作。所以锁会限制伸缩性:有越多的核心,每个核心就需要等待更长的时间才能够执行进入临界区。故而当核心数超出一定数值时,等待的时间将会超过实际计算的时间。不过,通过更加有效地序列化手段,可伸缩性的上限能够被提升到较高的水平,在某些情况下,能够超越当前系统的程度。能够更高效地序列化的锁每秒能够支持更多的操作,故而能够在更多的核心下处理负荷。

更精确地讲,我们的目标是能够缩短计算的临界路径:由于数据依赖而需要被依次执行的指令的最长序列。当使用锁的时候,临街路径包含成功的获取锁,临界区的执行以及锁的释放。

作为一个展示低效的限制伸缩性的序列化操作实例,考虑出现在自旋锁中的声名狼藉的锁竞争问题。当许多核心同时尝试获取一个自旋锁的时候,它们让各自的缓存行在其间来回往复,这将拖慢锁的获取/释放。这会使得临街路径的长度增加,随着核心数的增加将导致性能崩溃[2]。

锁竞争有一个著名的解决方案,那就是通过可伸缩基于队列的锁的形式[2,10]。不同于让所有的等待线程争夺下一个获取锁的权利,基于队列锁的锁让等待线程排队,让上一个锁的释放来处理下一个等待线程的锁。这种传球的方式,仅仅会对每个获取锁/释放锁操作带来常量级别数量的缓存失效,这加速了锁的获取和释放,并且缩短了临界路径。如图2a所示,基于队列锁的临界路径仅仅包含一次锁的缓存行的交换(虚线箭头)。

[译] 详解如何在多核程序中实现同步扩展

基于锁的序列化能够再高效一些么?本节描述的代理同步方法能做到这一点:它消除了临界路径中绝大部分的锁获取和锁释放操作,且能提升临界区自身的执行速度。

代理。在代理锁机制中,拿到锁的核心就像一台服务器,执行所有等待该锁的核心想要执行的操作。代理方式从几个方面提升了伸缩性(图2b)。首先,该方法消除了原本等待线程们需要执行的锁获取和锁释放操作。其次,也将提升(临界区)操作的执行速度,这是因为数据都在服务器核心的缓存中而不需要从其他核心的缓存或是内存中转移过来。代理机制同时也给一种新的优化手段带来了可能,该手段通过利用数据结构的语义来让临界区执行的更快,正如下文所诉。

实现代理。通过让一个线程执行其他等待线程的操作从而加快序列化的速度的想法可以追溯到1999年Oyama等人的工作[13]。但当时他们的实现的额外开销掩盖了其好处。Hendler等人的flat combining算法则是第一个将该想法第一次高效实现的工作,也是第一个发觉该方法让基于被执行操作的语义的优化手段变得容易。

在flat combining算法中,所有要获取锁的线程都向一个共享的发布列表(publication list)中投递其想执行的操作(例如dequeue或者enqueue(x))。获取到锁的线程成为了服务器,剩下的线程则保持自旋等待,等待他们的操作被执行完成。服务器扫描发布列表,执行被挂起的请求,尔后在执行完成时释放锁。为了抵消向发布列表中添加记录的同步开销,线程会将发布记录留在列表中并在以后的操作中重用之。以后的工作借助于一个队列锁的队列来实现发布列表[4],并且通过利用一个专门的核心来承担服务器的职责而不是让线程们随机的成为服务器的方式来提升了操作的缓存局部性。

基于语义的优化。服务器线程拥有当前挂起操作的全局视图,这使其能够从两个方面来优化指令执行:

合并。 服务器能够合并多条操作从而减少对数据结构重复的访问。例如说,多个计数器加一操作能够被合并成一次加法操作。

• 消除。 Elimination . 相互的消除操作,比如计数器加一和减一,或者是从一个集合中添加以及删除同一个对象,这些都能在完全不修改数据结构的前提下被执行。

延迟代理。对于仅修改数据结构但不返回值的操作,例如enqueue(),代理能让完全消除指令序列化的优化手段变得可能。由于这些操作并不向调用核心返回任何相应,那么这些核心就不必等待服务器去执行这些操作,它们可以在发布列表中记录下请求的操作然后继续运行。若尔后核心执行了一个返回值依赖于该数据结构状态的操作,例如dequeue,那么它才会等待服务器执行完成所有之前的操作。但是直到这之前(在重更新的场景中很少发生),所有的操作都是异步被执行的。

该优化方式早期的实现依旧需要核心们在执行这些延迟的操作之时被同步,这是因为它需要向一个统一的(无锁的)队列中去记录操作[7]。Boyd-Wickizer等人[3],通过利用系统范围的同步时钟来实现了无需任何更新同步延迟代理。他们的OpLog程序库在每个核心的日志中记录下这些无需响应的更新操作的调用,以及其被调用的次数。读取这个数据结构的操作则作为服务器:它获取所有核心的日志的锁,根据时间戳的顺序来执行这些操作,尔后再读取数据结构的当前状态。OpLog因此提供了针对重更新少读取的数据结构(例如LRU缓存)的可伸缩的实现方式。

性能

为了展示代理的好处,我们将比较一个基于锁的工作队列和一个用代理实现的队列。基于锁队列的算法利用了Michael和Scott的two-lock队列[1]。该算法用不同的锁来保护对队列头的队列尾的更新,同步同一种类型的操作但允许入队出队并行地执行。基于队列的CLH锁(Craig, Landin和Hagerstein)被用来实现这个基于锁的算法。基于代理的队列则使用了Fatourou和Kallimanis的CC-Queue队列[4],该算法向基于锁算法的两把锁都添加了代理(故该方法有两个服务器运行:一个用于出队,一个用于入队)。

图3展示了基于锁的队列和基于代理的队列入队/出队的吞吐量比较(越高越好)。改基准测试模拟的是一个普遍的应用场景。每个核心重复地访问数据结构,执行一组入队出队操作,统计队列操作的吞吐量(即每秒总共的队列操作数)。为了模拟为了模拟真实应用场景下的工作量,一段“思考时间”被擦入到了每个队列操作之后。思考时间是均匀随机地从1至100纳秒中选择的,为的是模拟队列被频繁访问的高负载场景。测试使用了Fatourou和Kallimanis基准测试框架( https://github.com/nkallima/sim-universal-construction )的C语言实现,同时使用了一个伸缩性较好的内存分配器来减少malloc带来的瓶颈。没有实现任何基于语义的优化。

[译] 详解如何在多核程序中实现同步扩展

该基准测试(以及本文其他所有实验)是在Intel Xeon E7-4870 (Westmere EX)处理器上执行的。该处理器拥有十个2.40 GHz的核心,每个核心有两条硬件线程,总共20条硬件线程。

图3列出了吞吐量基准测试的结果,取10次实验平均数。基于锁的算法因为使用了两把锁,仅能伸缩至两个线程,且由于序列化而不能伸缩至超过两个现场的并发量。与之相反的,基于代理的算法却有较好的伸缩性,并且最终每秒执行了大概三千万条指令,这比基于锁算法的吞吐量高了超过3.5倍。

避免无锁式同步的失败CAS操作

无锁式同步(亦被称作非阻塞式同步)利用原子指令而不是锁来直接操作共享的数据。大部分无锁算法利用多核处理器上的CAS(Compare-And-Swap)指令(或者类似的指令)。一个CAS操作需要三个操作数:一个内存地址addr,一个旧值old以及一个新值new。该指令原子地将储存在addr中的数值从old更新至new,如果储存在addr中的值不等于old,那么CAS将不会更新内存而失败。

基于CAS操作的无锁算法利用CAS循环的模式来进行同步:一个核心读取共享状态,计算出新值,然后利用CAS来将共享内存更新至新值。若CAS指令成功了,那么这次的读取-计算-更新操作序列看上去就是成功了,若指令失败则该核心需要重试。图4列举了一个CAS循环的示例,该示例来自于Treiber的经典LIFO(后进先出)堆栈算法[15],是将一个节点链接到一个链表头结点上。许多基本数据结构的无锁式实现,例如队列、堆栈以及优先队列,都有着类似的思想,它们都利用某种原子指令来实现整个数据结构的更新操作。

[译] 详解如何在多核程序中实现同步扩展

当没有(或很少)竞争之时,原子指令(有时是多条)的使用可能使无锁式同步比基于锁的解决方案还要慢。而在高竞争之时,无锁式同步有效率更高的潜质,因为其消除了临界路径上锁获取以及锁释放的操作,仅留下了对数据结构的操作(图5a)。

[译] 详解如何在多核程序中实现同步扩展

另外,无锁式算法保证了某一操作总是能够完成,故而在高负荷下仍能表现优异,而基于锁的算法却可能由于操作系统优先抢占持锁的线程而停止。

在实践当中,无锁式算法可能无法实现这些性能期待。考虑一下,比如说Michael和Scott的无锁队列算法[11]。该算法利用链表实现了队列,利用CAS循环,对象从队列尾入队,从队列头出队(类似于图4的例子,不过基本思想比具体的细节重要得多)。尽管如此,正如图6a所示,无锁式算法无法伸缩至超过四个线程,最终性能低于two-lock队列算法。

[译] 详解如何在多核程序中实现同步扩展

这里较差性能的原因则是因为CAS失败:随着并发量增加,另一个CAS操作插入到一个核心的读取-计算-更新序列之间的几率也增加了,这会让该核心发生CAS失败。像这样失效的CAS操作向临界路径上累加了许多无用功。虽然这些失效的CAS操作并不更改内存,执行它们依旧需要获取该变量对应缓存列的排他访问。这让尔后获取该缓存列并成功更新的操作之时间延长(见图5b,在同一时间里,这里仅完成了两个操作,而图5a则是三个)。

为了消除CAS失效带来的性能损耗,图6b比较了CAS循环中(像图4那样)成功的CAS指令的吐吞量以及总共CAS操作的吞吐量(包括失效CAS操作)。可以观察到系统执行竞争激烈的原子指令最多能达到最终在数据结构中能观察到的速率的三倍。如果有方法能使所有的算子指令都能完成操作,便能够极大地提升性能。但由于CAS失效的固有性,我们如何才能做到这一点?

关键的观察在于x86架构支持几个总是成功的原子指令。其中一个是FAA(Fetch-And-Add),该指令原子地将整数累加到变量中,然后返回变量储存的旧值。下一节描述了一种基于FAA而不是CAS的无锁队列之设计。该算法被称作LCRQ(Linked Concurrent Ring Queue)[12],利用了FAA指令讲线程分布到队列中的对象上,从而让其能够快速且并行地入队出队。LCRQ一般执行一个FAA指令来获取自己在队列中的位置,从而提供了完全一致的行为。

LCRQ算法

本节展示了LCRQ算法的概要,对于详细的描述和评估,请参阅论文[12]。从概念上来讲,LCRQ能被看作下面这个简单却不切实际的队列算法(图7)的现实版实现。这个不切实际的算法用一个无限的数组Q来实现队列,Q有无限的头尾下标来标示Q中包含对象的部分。一开始,每个位置Q[i]都为空,且包含一个不能被入队的保留值⊥。头和尾的下标用FAA操作将线程分布到数组的各个元素中,并且在这些元素中用CAS实现同步。

[译] 详解如何在多核程序中实现同步扩展

一个enqueue(x)的操作包含一个通过向tail执行FAA得到的下标t。尔后enqueue用CAS操作原子地将x储存在Q[t],将Q[t]从⊥更新为x。如果CAS操作成功,那么enqueue操作完成,否则就重复此过程。

dequeue操作D则是通过向head执行FAA操作来获取一个下标h。该操作尝试原子地用CAS操作将Q[h]的内容从⊥替换为保留值⊤。当Q[h]包含一些x,满足x ≠ ⊥,则CAS操作失败,此时D返回x。否则的话,D将⊤成功地储存到数组中的事实保证了后续的enqueu操作尝试向Q[h]储存值会失败。如果tail ≤ h + 1(head的值在D的FAA操作后是h + 1), D尔后返回NULL(表明队列为空)。若D不能返回NULL,则重复此过程。

这个算法能被证明正确的实现了FIFO队列,但是它的两个主要缺陷限制了其实用性:使用了无限的数组,容易产生活锁(当入队操作线程不断地将⊤写入到出队线程将要访问的位置)。LCRQ算法解决了这些缺陷。

无限的数组首先被换成一个有R个元素的并发环形(循环数组)队列,缩写为CRQ。head和tail下标依然严格单调增加,不过此时下标与R取模后的数值指明了其指向的位置。由于现在有超多一个的入队线程和出队线程能够并发地访问一个元素,CRQ使用了更为复杂的基于CAS的协议来同步每个元素。这个协议让一个操作可以不必等待那些FAA返回较小下标的,指向同一个位置的其他操作的完成。

CRQ的关键性能特点是在公共的快速路径上,操作只包含一个FAA指令。LCRQ算法基于CRQ来阻止活锁问题,并处理CRQ填满的情况。LCRQ本质上是Michael和Scott的链表队列[11],这个队列里每个节点都是一个CRQ。被填满或者遭遇活锁的CRQ会更接近入队操作,然后添加一个新的CRQ到队列并在其上工作。LCRQ的大部分工作因此发生在各个CRQ里,让列表的头尾指针竞争(CAS失效)不再是个问题。

性能

本节比较了LCRQ和Michael和Scott的经典无锁队列[11],以及之前章节中提到的基于代理的队列。CAS失效的影响由LCRQ-CAS测试探究,这是用CAS循环实现FAA操作的一种LCRQ。

图8a为测试结果。在线程数超过两个时LCRQ超过了其他的队列技术,峰值吞吐量达到了将近四千万操作每秒,这即是每个操作1000指令周期。从八个线程开始,LCRQ超过了基于代理的队列1.4到1.5倍,超过了MS(Michael和Scott)队列三倍以上。LCRQ-CAS知道四个线程之前和LCRQ的性能一样,但那之后其性能便趋于稳定。随后,LCRQ-CAS由于CAS失效而表现出吞吐量“熔化”。类似的,MS队列的性能峰值点在两个线程处,并随着并发量增加而降低。

[译] 详解如何在多核程序中实现同步扩展

超额的工作能够显示出无锁算法在高负载时的优雅表现。在这些负载中,软件线程的数量超过了硬件支持的限度,从而迫使操作系统在线程间进行上下文切换。如果一个占有锁的线程被抢占了,基于锁的算法在该线程重新运行前是不能做任何事的。事实上,正如图8b显示的,当线程数超过20,基于锁的代理算法性能骤降15倍,而LCRQ和MS队列保持了它们的巅峰吞吐量。

结论

高级的同步方法能够提升共享可变数据结构的性能。同步依然有开销,当性能的需求非常严苛时(或者不需要集中式数据结构的特性),那么分布式的数据结构很有可能是正确的选择。对于其他多数情况,本文描述的方法能够帮助构建高性能软件。对这些方法的了解将有助于为多核机器设计软件。

引用

1. Al Bahra, S. 2013. Nonblocking algorithms and scalable multicore programming. Communications of the ACM 56(7): 50-61.

2. Boyd-Wickizer, S., Frans Kaashoek, M., Morris, R., Zeldovich, N. 2012. Non-scalable locks are dangerous. In Proceedings of the Ottawa Linux Symposium : 121-132.

3. Boyd-Wickizer, S., Frans Kaashoek, M., Morris, R., Zeldovich, N. 2014. OpLog: a library for scaling update-heavy data structures. Technical Report MIT-CSAIL-TR2014-019.

4. Fatourou, P., Kallimanis, N. D. 2012. Revisiting the combining synchronization technique. In Proceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming : 257- 266.

5. Haas, A., Lippautz, M., Henzinger, T. A., Payer, H., Sokolova, A., Kirsch, C. M., Sezgin, A. 2013. Distributed queues in shared memory: multicore performance and scalability through quantitative relaxation. In Proceedings of the ACM International Conference on Computing Frontiers: 17:1-17:9.

6. Hendler, D., Incze, I., Shavit, N., Tzafrir, M. 2010. Flat combining and the synchronization-parallelism tradeoff. In Proceedings of the 22nd ACM Symposium on Parallelism in Algorithms and Architectures : 355-364.

7. Klaftenegger, D., Sagonas, K., Winblad, K. 2014. Delegation locking libraries for improved performance of multithreaded programs. In Proceedings of the 20th International European Conference on Parallel and Distributed Computing : 572-583.

8. Kulkarni, M., Pingali, K., Walter, B., Ramanarayanan, G., Bala, K., Chew, L. P. 2007. Optimistic parallelism requires abstractions. In Proceedings of the 2007 ACM SIGPLAN Conference on Programming Language Design and Implementation : 211-222.

9. Lozi, J.-P., David, F., Thomas, G., Lawall, J., Muller, G. 2012. Remote core locking: migrating critical section execution to improve the performance of multithreaded applications. In Proceedings of the 2012 USENIX Annual Technical Conference : 65-76.

10. Mellor-Crummey, J. M., Scott, M. L. 1991. Algorithms for scalable synchronization on shared-memory multiprocessors. ACM Transactions on Computer Systems 9(1): 21-65 .

11. Michael, M. M., Scott, M. L. 1996. Simple, fast, and practical non-blocking and blocking concurrent queue algorithms. In Proceedings of the 15th Annual ACM Symposium on Principles of Distributed Computing : 267-275.

12. Morrison, A., Afek, Y. 2013. Fast concurrent queues for x86 processors. In Proceedings of the 18th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming : 103-112.

13. Oyama, Y., Taura, K., Yonezawa, A. 1999. Executing parallel programs with synchronization bottlenecks efficiently. In Proceedings of International Workshop on Parallel and Distributed Computing for Symbolic and Irregular Applications : 182-204.

14. Shavit, N. Data structures in the multicore age. 2011. Communications of the ACM 54(3): 76-84.

15. Treiber, R. K. 2006. Systems programming: coping with parallelism. Technical Report RJ5118, IBM Almaden Research Center.

Adam Morrison致力于让并行及分布式系统更加的易于使用而不会损耗其性能。他的研究兴趣包括计算机架构,系统软件以及分布式计算理论。他是以色列,特拉维夫大学,布拉瓦尼克计算机科学学院的助理教授。他在特拉维夫大学获取了计算机科学PhD学位,尔后在以色列理工学院花了三年时间作为博士后。他获得过IBM PhD奖学金以及因特尔和Deutsch奖。

相关文章:

Nonblocking Algorithms and Scalable Multicore Programming

– Samy Al Bahra

探索了一些基于锁同步以外的机制

Maximizing Power Efficiency with Asymmetric Multicore Systems

– Alexandra Fedorova, et al.

非对称多核系统承诺比传统对称处理器使用更少的能量。我们将如何开发软件才能尽可能多的利用其潜能?

Software and the Concurrency Revolution

– Herb Sutter and James Larus

利用多核处理器全部的能力需要软件行业新的工具和新的思想。

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址