基于进程投机并行的运行时系统设计与优化

刘 雷，李 晶，陈 莉，冯晓兵



基于进程投机并行的运行时系统设计与优化

刘 雷1,2，李 晶1,2，陈 莉1，冯晓兵1

(1. 中国科学院计算技术研究所，北京 100190；2. 中国科学院大学，北京 100190)

投机并行化是解决遗留串行代码并行化的重要技术，但以往投机并行化运行时系统面临着诸多的性能问题，如任务分配不均衡、通信频繁、冲突代价高，以及进程启动/结束频繁而导致开销过高等。为此，提出一种基于进程实现的投机并行化运行时系统。采用隐式单程序多数据的并行任务划分和执行模式，通过实现重用进程的投机任务调度策略和委托正确性检查技术，降低投机进程启动/结束和通信的开销，提高投机进程的利用率，同时利用守护进程与投机进程协同执行的方式，确保在投机进程出现异常情况时程序也能正确执行。实验结果表明，该基于进程实现的投机运行时系统比同类型系统的性能提高231%。

软件投机并行；基于进程投机并行；运行时并行；委托正确性检查；并行任务划分

1 概述

多核处理器结构已经成为当今的主流硬件结构，但如何对遗留的串行软件进行并行化改造，是计算机产业界和研究界面临的巨大挑战。投机并行化方法利用运行时分析技术，可以更精确地了解程序特征信息，从而获得比传统静态分析方法更多的并行性，已经成为近年来的研究热点。

然而，投机并行化的产业化之路并不明朗。对于当今主流的基于线程的投机并行化方法，需要特殊的硬件支持来降低开销[1]。Intel的研究表明[2]，基于线程的投机并行化在考虑实际开销的情况下，并行化后的性能加速才有18.18%。如此低的性能提升，导致目前的硬件厂家都没有实现对线程投机并行化的硬件支持。而纯软件的投机并行化系统不仅运行时开销比较大，而且为了支持投机过程中对程序状态的备份，线程还极易出现死锁、数据冲突、ABA等诸多难于调试的问题，导致其实现难度非常大。

相较而言，利用进程可以更容易地实现软件投机并行化系统，进程间天然的地址独立性可以很好地解决投机所需的存储空间维护难题，能够自动实现变量的私有化和副本化。同时，由于子进程的虚存地址和父进程的虚地址是一致的，可以很容易地实现访存的正确性检测机制。此外，该方法也特别适合于发掘更粗粒度的并行性。最近已经有很多的研究机构采用基于进程或类似的方法来开发投机并行化系统[3-5]。

但是目前软件投机并行化系统的运行时开销还很大，从而影响了该技术的推广。例如，文献[3]提出基于进程的投机并行系统BOP，它创建的投机进程执行一次任务后就马上退出，在下次投机阶段开始时又要再创建新的进程来执行，频繁的进程启动、注销导致了很大的运行时开销。当投机执行失败时，BOP会杀死所有的投机进程，从头串行执行，因而白白浪费了很多的执行时间。此外，投机任务间的负载不平衡问题也很严重。

采用线程实现的投机并行化系统，尽管开销相对小，但其运行时系统依然有很多需要优化的地方。如文献[6-9]的投机并行化方法，用主线程来维护系统的正确性，在进入投机循环时，主线程将迭代任务分配给各投机线程，各投机线程在执行完成后按序将结果提交给主线程进行正确性验证[9]。当验证通过时，主线程读入相应结果，并继续往下检测其他投机结果。而如果发现冲突，主线程则舍弃当前结果，重新执行。尽管通过线程池技术，该方法并没有频繁的线程启动/结束开销，但由于主线程是按序执行的，且只会在新的循环迭代时才将任务赋给投机线程，使得投机线程每执行完一次任务，它都需等待较长时间才能获得下次任务。这种运行时实现机制同样会导致较大的线程间同步等待开销，还是会影响程序的并行化性能。文献[10]在线程投机并行系统中提出了值预测的方法减少同步开销，但是优化能力有限，还带来了额外的硬件开销。

目前的软件投机并行化系统为了保证按序提交数据及进行正确性检测，投机任务间需要很大的进程(线程)启动或调度开销，以及数据通信和同步开销等[11-12]。因此，现有投机并行系统的运行时方法都存在任务分配不平衡、冲突代价高和通信开销大的问题。这些问题对基于进程实现的投机并行化系统更为突出，由于进程的创建、进程间通信的开销和调度开销较线程方式大得多，如何降低这些开销也就成为了基于进程实现投机并行的关键技术。因此，本文提出一种新型的基于进程的投机任务调度策略，并对该运行时系统的设计理念和算法实现加以阐述。

2 基于进程的软件投机并行化方法

2.1 基本概念和定义

定义1(任务) 任务是一个指令序列，对应于算法或程序的某个逻辑部分。它是投机并行执行调度的最小单位，投机并行化的第一步就是将问题分解为多个任务。

定义2(执行单元UE) UE是并发执行任务的实体，任务通过分配到一个UE上执行，如进程或线程。

定义3(任务间时序关系) 投机并行化将代码划分为串行执行区域和并行执行区域，并行执行区域的任务将采用投机的方式与其他任务并发执行。为了保证投机执行的正确性，除了要对不同任务的访存进行跟踪外，还要明确任务间原有的时序关系。若任务t在串行执行语义中是在任务t之前执行的，则称t先于t执行，记为t<t。

定义4(访存冲突) 对于2个不同的任务t和t，如果存在一个存储单元，任务t和t都有对的访存操作，只要有一个任务对进行写操作，则称2个任务间存在着访问冲突。假设任务t在串行执行时先于t执行，即t<t，则称任务t依赖于任务t，记为tδt。

2.2 进程投机并行化的执行过程

投机并行化技术采用冒险的猜测执行方式去发掘并行性，并利用冲突检测和回退机制来保证正确性。

当程序执行到投机并行区域时，投机系统先保存当前的状态，然后启动执行单元并行的运行目标任务。当各投机的执行单元完成后，再进行正确性验证，如果没有冲突发生，则收集各执行单元的执行结果，程序继续运行后续代码；否则恢复之前的程序状态，并将程序指针回退到投机前位置，重新以串行的方式执行程序。投机任务并行执行的流程如图1所示，实箭头表示控制流，虚箭头表示执行的任务。

图1 投机并行化原理

投机并行化的正确性验证机制主要负责检测投机过程中是否存在任务间的冲突，验证过程分为3步：

(1)各投机执行单元在并行过程中记录读写信息。

(2)投机任务完成后，需要将所收集到的信息提交给其他投机执行单元。

(3)进行投机任务间的冲突检测。

导致投机失败的冲突包括：

(1)状态无法恢复的系统调用，这类调用往往影响系统共享资源的使用或直接修改系统状态，如内存分配与释放、文件的读/写、进程的创建。

(2)违反访存的线性一致性，如果2个任务t和t，存在着依赖关系tδt，若在并行调度的过程中能够保证不会出现违反依赖tδt的情况，即对于存在访存冲突的任务在串行执行时t<t，要求并行调度算法同样满足t<t。则称该调度关系满足线性一致性要求。否则，说明存在线性一致性 冲突。

(3)异常，在投机并行执行过程中可能出现未知的程序行为，导致异常发生，包括除数为0、死锁、死循环等情况。传统的投机系统很难判断和处理这类异常冲突。

2.3 进程投机的任务划分和ISPMD执行机制

传统的基于线程的投机并行化方法，只能对连续执行的代码段进行投机并行化，为了支持更多类型的并行性，实现了一种称为隐式单程序多数据(Implicit SPMD, ISPMD)的并行任务划分和执行模式。

将每个并行任务分成需维护串行执行语义的代码区域和可能并行执行的代码区域(PPR)2种类型。并行执行过程采用SPMD的方式，即每个投机进程都会执行需维护串行执行语义的代码，而仅属于本次投机任务的进程才执行可能并行执行区域内的代码。

算法1ISPMD任务划分和执行举例 1: SUP_parallel_start();2: while(condition){3: P;4: SUP_task();{5: Q;6: }7: R;8: }9: SUP_parallel_finish();

例如算法1所示的循环，对该while循环的代码进行并行化，同时要求满足代码和串行执行，并发执行。则采用ISPMD任务执行模型，当第个进程串行执行完11…P1R1P后，就可以开始执行投机并行任务Q。假设循环共有次迭代，采用ISPMD划分方式，执行投机并行化的正确性须满足以下条件：

(1)各迭代的任务间无访存冲突，即无QδQ，0≤，≤。

(2)各迭代的任务Q与其后续的任务RP+1R+1…PR间无访存访存冲突，即无∂，0≤≤，QδR∪QδP+1∪QδR+1∪…∪QδP∪QδR成立。

定理对于算法1的并行任务划分方式，上述2个条件是使用ISPMD方法进行投机并行化的正确性必要保证。

证明：假设是循环所有迭代的个数，根据ISPMD的任务调度规则可知，在投机并行过程中，并发执行的投机任务Q前，已经得到任务11…P1R1P的执行结果，因此它们之间的访存冲突可以忽略检测，即不会出现PδQ，≤，或RδQ，0≤<≤。由于原始的程序执行序是1<1<1<…<P<Q<R…，如果存在QδQ，0≤<≤，则该执行结果肯定是错的；如果存在QδR，≤，或QδP，0≤<≤时，结果也肯定是错误的。因此，定理成立。

3 运行时系统的实现方法

3.1 投机并行化的任务分配和调度函数的实现

要实现ISPMD执行方式，如果采用传统的进程投机并行技术，则当每次遇到可能并行执行代码区域时，都会创建一个新的进程。这种频繁的进程创建开销都是非常巨大的，而且当投机并行过程中没有冲突发生时，这种开销是完全没有必要的。

为了解决这个问题，本文提出了进程重用的概念，利用冗余计算技术和隐式任务派分等技术实现类似线程池的进程调度方法。采用进程重用方法的投机执行方式如图2所示。各投机进程间没有直接的消息通信，也没有同步等开销。

图2 进程重用的调度方式

3.2 投机执行正确性保证机制的实现

对于传统的投机并行化实现技术，为了验证本次投机执行的正确性，投机进程需要对相关变量的读写信息进行记录，同时等待前次的投机任务完成，以获取其写记录信息来进行验证。并在自己通过正确性验证后将该记录传递给下一个投机进程。因此，导致进程间的通信十分频繁，同步开销非常大。

为此，本文提出并实现了一种称为委托正确性检查的方法，将正确性验证等操作转移到一个专门的进程，即守护进程(manager)中进行，进而使得投机进程可以无需等待正确性验证的结果而直接执行后续迭代。守护进程在对各投机进程提交的数据进行验证时会自动保证检测的顺序性，即各个任务的验证顺序应与其串行执行的顺序保持 一致。

此外，为了解决投机并行系统在发生异常时可能造成的崩溃问题，本文设计的守护进程不仅进行投机并行进程的正确性检测工作，还会在空闲时以串行的方式执行可能投机代码段。这样能够保证即使投机进程出现异常情况，原始的程序执行也不会受到影响。

投机进程执行完任务后，会将读写信息和相应修改的数据提交到进程间共享空间中。守护进程先判断是否有投机任务执行结束并提交数据，如果有则进行正确性验证，如果没有发现冲突，那么守护进程更新程序状态，然后跳到投机任务之后的代码继续执行。如果有错误或者没有投机任务提交，则守护进程串行执行代码。投机进程执行的算法如下所示：

算法2投机进程的实现算法 1: while (! finish speculation){2: My_task= get_task( );3: if (++cur_task==ma_task){4: Execute (my_task);5: Checkin_data( my_task);6: Commit_task(my_task);7: }else {8: Patial_execute(++cur_task);9： }10: }

4 实验结果与分析

为了验证本文投机并行化运行时系统的有效性，与经典的进程级投机并行化系统BOP和采用OpenMP版本的并行程序进行对比。

测试平台选择4´4 AMD 4核2.5 GHz Opteron 8380 CPU，32 GB内存服务器，串行和OpenMP编译器都为Gcc4.4。

测试用例共6个，其中5个选自SPEC标准测试程序集。测试例子Art选自SPEC2000，是一个神经网络训练程序。Bzip2选择SPEC2000，是一个比较经典的数据压缩程序。Hmmer选自SPEC2006，是计算生物学中的一个多重序列比对统计模型分析程序。Parser选自SPEC2000，是一个英语语法的解析程序。Sjeng 选自SPEC CPU2006，国际象棋程序。QT-cluster(Quality threshold)是一个经典的聚类算法，通过判断聚类直径是否超过预设的阈值来进行分类。

实验结果如图3所示，其中，SUP是本文的投机并行化系统，图3显示在8个工作进程的情况下，本文的进程投机并行化系统的性能加速比明显好于BOP，几何平均性能加速比是BOP的2.31倍。事实上，本文系统的性能加速比甚至不比基于线程实现的OpenMP版本差。由于有些程序存在数据依赖，用OpenMP很难并行化，因此没有相应的OpenMP版本数据。

图3 性能加速比的对比(8进程)

5 结束语

基于进程的投机并行化技术是近几年的研究热点，本文提出一种投机并行的运行时系统，对进程重用、委托检查技术进行了介绍，这些技术有效地解决了以往投机并行化运行时系统运行时开销过大的问题。本文方法由于正确性验证与串行状态维护的需要，守护进程占用了一个核的计算资源。下一步工作将研究如何在保证正确性的情况下，充分利用守护进程来执行投机任务，从而进一步提高性能。

[1] Steffan J G, Colohan C, Zhai A, et al. The STAMPede Appro- ach to Thread-level Speculation[J]. ACM Transactions on Computer Systems, 2005, 23(3): 253-300.

[2] Kejariwal A, Tian Xinmin, Li Wei, et al. On the Performance Potential of Different Types of Speculative Thread-level Parallelism[C]//Proc. of the 20th Annual International Conference on Supercomputing. New York, USA: ACM Press, 2006: 24.

[3] Ding Chen, Shen Xipeng, Kelsey K, et al. Software Behavior Oriented Parallelization[C]//Proc. of ACM SIGPLAN Conference on Programming Language Design and Implementation. New York, USA: ACM Press, 2007: 223-234.

[4] Ke Chuanle, Liu Lei, Zhang Chao, et al. Safe Parallel Pro- gramming Using Dynamic Dependence Hints[C]//Proc. of ACM International Conference on Object Oriented Program- ming Systems Languages and Applications. New York, USA: ACM Press, 2011: 243-258.

[5] Berger E D, Yang Ting, Liu Tongping, et al. Grace: Safe Multithreaded Programming for C/C++[C]//Proc. of the 24th ACM SIGPLAN Conference on Object Oriented Program- ming Systems Languages and Applications. New York, USA: ACM Press, 2009: 81-96.

[6] Tian Chen, Lin Changhui, Feng Min, et al. Enhanced Specu- lative Parallelization via Incremental Recovery[C]//Proc. of the 16th ACM Symposium on Principles and Practice of Parallel Programming. New York, USA: ACM Press, 2011: 189-200.

[7] 李 莹, 孙煦雪, 袁新宇, 等. 基于交互信息的投机并行化方法[J].计算机应用研究, 2010, 27(6): 2123-2126, 2139.

[8] Cintra M H, Llanos D R. Design Space Exploration of a Software Speculative Parallelization Scheme[J]. IEEE Transactions on Parallel and Distributed Systems, 2005, 16(6): 562-576.

[9] Bernstein A J. Analysis of Programs for Parallel Processing[J]. IEEE Transactions on Electronic Computers, 1966, 15(5): 757-763.

[10] Zhai A, Steffan J G, Colohan C B, et al. Compiler and Hardware Support for Reducing the Synchronization of Speculative Threads[J]. ACM Transactions on Architecture and Code Optimization, 2008, 5(1): 1-33.

[11] Feng Min, Gupta R, Hu Yi. SpiceC: Scalable Parallelism via Implicit Copying and Explicit Commit[C]//Proceedings. of the 16th ACM Symposium on Principles and Practice of Parallel Programming. New York, USA: ACM Press, 2011: 69-80.

[12] 柯传乐. 进程投机并行的运行时系统研究[D]. 北京: 中国科学院计算技术研究所, 2012.

编辑 任吉慧

Design and Optimization on Runtime System of Process-based Speculative Parallelization

LIU Lei1,2, LI Jing1,2, CHEN Li1, FENG Xiao-bing1

(1. Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China; 2. University of Chinese Academy of Sciences, Beijing 100190, China)

Speculative parallelization is an important technique for solving the problem of parallelizing the legacy codes. However, the original runtime systems of speculative parallelization are confronted with serious performance problems, such as load unbalance, frequent communication, high conflict costs and frequent process creation/destruction overheads. This paper proposes a process-based speculative runtime system, using Implicit Single Program Multiple Data(ISPMD) method to partition and execute tasks in parallel, and implement a reused-process and delegated correctness checking method to reduce the overheads of frequent creation/destruction of speculative processes or the communication between them, which can improve the utilization of speculative processes. Besides, through a method that speculative tasks cooperate with manager task, the system can ensure the correct execution, even in the presence of exceptions with speculative processes. According to experimental results, the process-based speculative runtime system achieves 231% speedup improvement compared with other process-based speculative parallel systems.

software speculative parallelization; process-based speculative parallelization; runtime parallelization; delegated correctness checking; partitioning of parallel tasks

1000-3428(2014)03-0099-04

A

TP311.5

国家“863”计划基金资助项目(2012AA010902)；国家“973”计划基金资助项目(2011CB302504)。

刘 雷(1980－)，男，助理研究员、博士，主研方向：并行编译，编译优化；李 晶，博士研究生；陈 莉，副研究员；冯晓兵，研究员。

2012-11-15

2013-04-16 E-mail：liulei@ict.ac.cn

10.3969/j.issn.1000-3428.2014.03.020