确定性执行技术 - 首页-中国计算机学会信息网

卢　凯　周　旭国防科学技术大学

确定性执行技术

多核为人们带来了额外的计算资源，使计算性能得到成倍提升，但也由此产生了编写并行程序困难、可靠性低等问题。本文主要关注多核并行程序的不确定性问题及其对程序调试带来的挑战。

多核调试的困境——“Bug不见了”

根据程序b u g 传播模型[1]，一个bug 从产生到被用户发现一般经历三个阶段，分别是错误原因(root cause)、错误传播(propa-gation)和错误显现(bug)。bug 的传播过程如图1所示，错误在刚产生阶段一般不会立即显现，而会随着程序的执行传播一段时间。根据bug 特性的不同，传播路径的长短也有差异。有些bug 传播的路径较短，有些则较长，还有一些会一直传播而不被用户察觉。当用户察觉到bug 时，就到了bug 的显现阶段。这时一般表现为系统崩溃、计算结果错误等等。

程序调试就是要找到引起

关键词：程序调试　多核

bug 的原因并修复bug 。因此，相对于bug 的传播过程而言，程序调试是一个逆向过程，即从bug 显现阶段出发，顺着bug 的传播路径找到引起bug 的根源。由于bug 传播路径的影响，一般很难一次调试成功，往往需要多次运行程序，通过设置断点等方式对错误路径进行标记，逐步找出问题的根源。但这只限于串行程序。

这种调试方式对并行程序却是无效的。因为并行程序存在由不可控因素引发的不确定性。其不确定性主要是：程序在给定的输入条件下多次运行，执行流程和结果可能不一致。例如，在图2所示的例子中，若两个线程对共享变量x 的交织访问顺序不同，就可能造成程序最终的执行结果不同。多核并行程序的不确定性是由共享内存的体系结构所决定的。在多核平台上，线程是独立执行的，但是所有的线程却能同时访问主存。这就有可能产生访存冲突，引起不确定性。总之，引起多核并行程序不确定性的条件有两个：一是不确定的线

程交织顺序，二是线程间的访存冲突。由于线程执行速度是随着系统变化而变化的，因此难以避免线程交织；并且与一般的输入相比，线程交织是一种额外的、隐式的、不可控的因素，因此更加难以追踪或者控制它。访存冲突在多核平台上也是不可避免的：由于线程是合作完成一件任务，因此它们之间就要交换信息，而共享内存是最简单高效的通信通道。可以说，不确定的线程交织和访存冲突都是多核平台

图2　线程交织访问共享变量导致的不确定性

图1　经典的bug 传播模型

中与生俱来的特性，这也赋予了并行程序不确定的性质。

由于不确定性的存在，调试变得非常困难。当bug出现时，需要根据现场信息追踪引起bug 的原因。当现场信息不足时，需要重新执行程序来获取bug传播路径上更为详细的信息。但问题往往是，当我们在相同的输入下重新运行程序时，由于不可知的原因，程序执行了一个与上次不同的路径，结果是“bug不见了”，调试就会陷入困境。并行程序的bug就像是被不确定性这个魔咒隐藏起来的宝藏一样，我们费尽千辛万苦寻找宝藏的埋藏地，并且在路上做上了详细的标记，而当我们再回去拿铲子准备挖宝藏的时候，却发现原先做的标记已经不见了，宝藏也不翼而飞。这种忽隐忽现、时有时无的特性使并行程序调试变得无踪可觅，完全靠运气。

这种不确定性不仅限制了程序调试，同时对程序测试、容错等方面也产生了不利的影响。为了解决这些问题，一种新型的确定性并行技术开始在学术界流行并且逐渐成为热点[2, 3]。

确定性并行技术——并行程序调试的突破确定性并行技术的目的：保证并行程序在相同的输入下，总是能产生相同的程序执行流程和取得相同的结果。确定性并行技术能够完全复现bug，实现对并行程序调试困境的突破，并且能

同时对程序测试、容错等提供有

力支撑。目前，确定性并行技术

的主流途径是使用运行时控制的

方法解决线程交织和访存冲突的

问题，实现确定性的并行环境。

轮流执行法

既然不确定性是由不可控的

线程交织引起的，让线程串行执

行就能实现确定性，那我们就采

用这种方法。这也是保证确定性

并行最简单的方法。这一方法最

早在文献[4]中提出。该方法先预

定义一个线程执行顺序，线程按

照这种顺序各执行N条指令，然

后以这种顺序继续执行，直到程

序结束。但这种方法完全牺牲了

并行性，使并行程序退化成了串

行程序的效率。文献[4]在这种简

单方法的基础上增加了程序并行

度，实现了第一个可用的确定性

并行系统——DMP。DMP将线

程的执行代码分成无冲突的和有

冲突两部分，并基于一个假设：

大部分的线程执行代码之间是没

有访存冲突的。即线程各自访问

不同的内存，不会引发不确定

合并本地修改：通信

图3　确定性线程交织顺序

图4　基于弱内存一致性的确定性并行技术

性。因此，当线程之间无访存冲突时，就可以并行执行；一旦线程之间发生了访存冲突，则转入串行执行，解决访存冲突。如图3所示，这种方法的关键是如何动态地检测访存冲突。

我们基于文献[4]提出了一种提高程序并行度的方法[5]。文献[4]的方法是在线程遇到访存冲突后就强制线程进入串行阶段，直到所有线程完成当前一轮执行的配额（每轮N条指令）为止。而我们认为：在串行阶段执行的N-P（P为并行阶段完成的指令数）条指令中，并不是所有的指令都会与其他线程发生访存冲突。极端的情况是，第P+1条指令（第一条串行指令）发生了访

存冲突，而剩余的N-P-1条指令均可以与其他线程并行。基于这个观察，我们提出了全并行的确定性技术，即不通过串行执行来解决访存冲突，而是在发生访存冲突时，根据线程对内存块的请求情况，重新分配线程访问内存块的权限。这就使得许多串行阶段执行的代码可以并行执行，极大地减少了程序的串行时间，从而提升了程序的并行度。

无冲突访存法

另一种保证确定性的方法是从访存冲突的角度出发解决问题。我们注意到并行程序不确定性的两个条件：一是不确定的线程交织顺序，二是访存冲突。如果线程之间完全没有访存冲突，即使线程交织顺序是不确定的，也依然可以保证程序的确定性。

依据这种思路，文献[6,7]都将线

程的共享内存进行了分离，即为

每个线程创建共享变量的本地副

本，这样线程访问的共享变量实

际上是本地变量，互相之间完全

不冲突，也不会引起不确定性。

为了实现原有线程之间通过共享

内存的通信，它们会每隔一段时

间做一次全局线程同步，并将所

有线程对本地变量的修改提交到

共享变量，在下一阶段重新从共

享变量中创建本地副本。如图4

所示。为了保证确定性，必须注

意两个问题：一是进行全局同步

的点必须是确定的，文献[6]每

隔N条指令进行一次全局同步。

而文献[7]在线程遇到同步语句

时进行一次全局同步；二是在

将多个本地变量的修改提交到

一个共享变量中时，可能会发

生修改冲突。解决冲突通常需

要设置线程优先级，优先级高

的线程可以覆盖优先级低的线

程对变量的修改。

上述两种方法虽然可以实现

并行技术的确定性，但是仍然比较

粗糙。为此，我们提出了一种不

用全局同步的确定性并行技术[8]。

首先，访存冲突依然是通过将共

享变量分离成线程本地变量来解

决，但是在实现隔离环境下的线

程通信时，我们并没有采用粗糙

的全局通信方式，而是采用了按

需通信的方式：通信只在需要同

步的两个或几个线程之间发生。

程序原有的线程同步本身会产

生一些线程和线程之间的时序关

系，通常被称为happens-before关

系[9]。这种时序关系恰好能和线

序结构与数据流一致。

程内部的时序关系构成一个半序结构。利用这种程序固有的时序关系就可实现线程通信，即数据沿着happens-before关系从时序较早的代码流向时序较晚的代码。如图5所示。

确定性编程模型

上面介绍的确定性方法都是通过控制线程来实现的。这些方法试图不改变现有的多线程模型，不对原有程序和用户的编程习惯产生影响。另外一些确定性并行技术则试图通过改变现有的并行编程模型来实现。例如，文献[10]提出了一种diverge&merge 的编程模型，在这种模型下用户必须定义子线程何时从主线程中分离出一部分数据进行计算，何时将计算结果合并到主线程。文献[11]则鼓励用户编写串行程序，然后通过特殊的标记将部分函数调用并行化。运行时系统动态实现这部分代码的并行运行，但必须保证并行的结果和原始程序中定义的串行语义完全一致。文献[12~14]则采用了消息通信方式来解决程序的不确定问题。目前较为流行的函数式语言(func-tional language)也是实现确定性并行的一种新编程模型。函数式语言本身就定义了一种程序的确定性执行流程，即程序执行就像数学中的函数一样，能将确定的输入映射为确定的输出。然而，这种方法的最大问题是性能和编程模型的普适性问题。发展趋势

多核并行给程序调试带来了

前所未有的困境，而确定性并行

技术是突破这种困境的钥匙。目

前学术界提出了很多确定性并行

技术，除了前面提到的运行时控

制的方法和采用新型编程模型的

方法之外，还有一些如静态验证

的方法等等。从目前的发展趋势

来看，运行时控制依然是主流，

随着技术的发展，如果新型的编

程模型在未来被人们普遍接受，

那么这些采用新型模型的方法也

许会逐渐发展起来。尤其是像

Java或者函数式语言这种介于操

作系统和用户程序之间的运行时

系统，其本身就对线程拥有强大

的控制能力，再加上新的语义限

制，实现一个高效的、跨平台的

确定性系统也许会更加容易。■

卢　凯

CCF会员。国防科学

技术大学研究员。主

要研究方向为大规模

并行处理、系统软件

技术。

kailu@https://www.wendangku.net/doc/5c840462.html,

参考文献

[1] J.-C. L a p r i e, D e p e n d a b l e

computing: concepts, limits,

c h a l l e n g e s,i n t h e25t h

International Conference on

Fault-tolerant Computing, 1995

[2] R. L. Bocchino Jr, V. S. Adve,

S. V. A d v e, a n d M. S n i r,

Parallel programming must

be deterministic by default,

in Proceedings of the First

USENIX conference on Hot

topics in parallelism, 2009, 4-4

[3] E. A. Lee, The problem with

threads, Computer, vol. 39,

33~42, 2006

[4] D. J o s e p h, L. B r a n d o n, C.

L u i s, a n d O. M a r k, D M P:

deterministic shared memory

multiprocessing, presented

at the Proceeding of the 14th

international conference on

A r c h i t e c t u r a l s u p p o r t f o r

programming languages and

operating systems, Washington,

DC, USA, 2009

[5] X. Zhou, K. Lu, X. Wang, and

X. Li, Exploiting parallelism

i n d e t e r m i n i s t i c s h a r e d

memory multiprocessing, J.

Parallel Distrib. Comput.,

72(2012)716~727, 2012

[6] B. Tom, A. Owen, D. Joseph,

C. Luis, and G. Dan, CoreDet:

a compiler and runtime system

for deterministic multithreaded

execution, presented at the

Proceedings of the fifteenth

e d i t i o n o

f A S P L O S o n

A r c h i t e c t u r a l s u p p o r t f o r

programming languages and

operating systems, Pittsburgh,

Pennsylvania, USA, 2010

[7] T. Liu, C. Curtsinger, and E. D.

Berger, DTHREADS: Efficient

Deterministic Multithreading, in

Proceedings of the 22nd ACM 周　旭

国防科学技术大学计

算机学院博士生。主

要研究方向为高可靠

并行计算、并行程序

调试技术。

zhouxunudt@https://www.wendangku.net/doc/5c840462.html,

Symposium on Operating Systems Principles, 2011

[8] X. Z. Kai Lu, Xiaoping Wang,

Wenzhe Zhang, Gen Li, RaceFree: An Efficient Multi-Threading M o d e l f o r D e t e r m i n i s m, i n PPoPP, Shenzhen, China, 2013 [9] L. Lamport, Time, clocks, and the

ordering of events in a distributed system, Communications of the ACM, vol. 21, 558~565, 1978 [10] A. Amittai, W. Shu-Chun, H.

Sen, and F. Bryan, Efficient system-enforced deterministic parallelism, presented at the Proceedings of the 9th USENIX conference on Operating systems design and implementation, Vancouver, BC, Canada, 2010 [11] E. D. Berger, T. Yang, T. Liu,

and G. Novark, Grace: Safe multithreaded programming for C/C++, in OOPSLA, 2009, 81~96 [12] S. A. Edwards and O. Tardieu,

SHIM: A deterministic model for heterogeneous embeded systems, Transactions on VLSI Systems, 854~867, 2006

[13] S. A. Edwards, N. Vasudevan,

and O. Tardieu, Programming shared memory multiprocessors with deterministic message-

passing concurrency: Compiling SHIM to Pthreads, in DATE, March 2008

[14] O. Tardieu and S. A. Edwards,

Scheduling-independent threads and exceptions in SHIM, in

E M S O

F T,O c t o b e r2006,

142~151