基于進程投機并行的運行時系統設計與優化

劉 雷，李 晶，陳 莉，馮曉兵

?

基于進程投機并行的運行時系統設計與優化

劉 雷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