基于進程投機并行的運行時系統(tǒng)設計與優(yōu)化

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

?

基于進程投機并行的運行時系統(tǒng)設計與優(yōu)化

劉 雷1,2，李 晶1,2，陳 莉1，馮曉兵1

(1. 中國科學院計算技術研究所，北京 100190；2. 中國科學院大學，北京 100190)

投機并行化是解決遺留串行代碼并行化的重要技術，但以往投機并行化運行時系統(tǒng)面臨著諸多的性能問題，如任務分配不均衡、通信頻繁、沖突代價高，以及進程啟動/結束頻繁而導致開銷過高等。為此，提出一種基于進程實現(xiàn)的投機并行化運行時系統(tǒng)。采用隱式單程序多數(shù)據(jù)的并行任務劃分和執(zhí)行模式，通過實現(xiàn)重用進程的投機任務調度策略和委托正確性檢查技術，降低投機進程啟動/結束和通信的開銷，提高投機進程的利用率，同時利用守護進程與投機進程協(xié)同執(zhí)行的方式，確保在投機進程出現(xiàn)異常情況時程序也能正確執(zhí)行。實驗結果表明，該基于進程實現(xiàn)的投機運行時系統(tǒng)比同類型系統(tǒng)的性能提高231%。

軟件投機并行；基于進程投機并行；運行時并行；委托正確性檢查；并行任務劃分

1 概述

多核處理器結構已經(jīng)成為當今的主流硬件結構，但如何對遺留的串行軟件進行并行化改造，是計算機產業(yè)界和研究界面臨的巨大挑戰(zhàn)。投機并行化方法利用運行時分析技術，可以更精確地了解程序特征信息，從而獲得比傳統(tǒng)靜態(tài)分析方法更多的并行性，已經(jīng)成為近年來的研究熱點。

然而，投機并行化的產業(yè)化之路并不明朗。對于當今主流的基于線程的投機并行化方法，需要特殊的硬件支持來降低開銷[1]。Intel的研究表明[2]，基于線程的投機并行化在考慮實際開銷的情況下，并行化后的性能加速才有18.18%。如此低的性能提升，導致目前的硬件廠家都沒有實現(xiàn)對線程投機并行化的硬件支持。而純軟件的投機并行化系統(tǒng)不僅運行時開銷比較大，而且為了支持投機過程中對程序狀態(tài)的備份，線程還極易出現(xiàn)死鎖、數(shù)據(jù)沖突、ABA等諸多難于調試的問題，導致其實現(xiàn)難度非常大。

相較而言，利用進程可以更容易地實現(xiàn)軟件投機并行化系統(tǒng)，進程間天然的地址獨立性可以很好地解決投機所需的存儲空間維護難題，能夠自動實現(xiàn)變量的私有化和副本化。同時，由于子進程的虛存地址和父進程的虛地址是一致的，可以很容易地實現(xiàn)訪存的正確性檢測機制。此外，該方法也特別適合于發(fā)掘更粗粒度的并行性。最近已經(jīng)有很多的研究機構采用基于進程或類似的方法來開發(fā)投機并行化系統(tǒng)[3-5]。

但是目前軟件投機并行化系統(tǒng)的運行時開銷還很大，從而影響了該技術的推廣。例如，文獻[3]提出基于進程的投機并行系統(tǒng)BOP，它創(chuàng)建的投機進程執(zhí)行一次任務后就馬上退出，在下次投機階段開始時又要再創(chuàng)建新的進程來執(zhí)行，頻繁的進程啟動、注銷導致了很大的運行時開銷。當投機執(zhí)行失敗時，BOP會殺死所有的投機進程，從頭串行執(zhí)行，因而白白浪費了很多的執(zhí)行時間。此外，投機任務間的負載不平衡問題也很嚴重。

采用線程實現(xiàn)的投機并行化系統(tǒng)，盡管開銷相對小，但其運行時系統(tǒng)依然有很多需要優(yōu)化的地方。如文獻[6-9]的投機并行化方法，用主線程來維護系統(tǒng)的正確性，在進入投機循環(huán)時，主線程將迭代任務分配給各投機線程，各投機線程在執(zhí)行完成后按序將結果提交給主線程進行正確性驗證[9]。當驗證通過時，主線程讀入相應結果，并繼續(xù)往下檢測其他投機結果。而如果發(fā)現(xiàn)沖突，主線程則舍棄當前結果，重新執(zhí)行。盡管通過線程池技術，該方法并沒有頻繁的線程啟動/結束開銷，但由于主線程是按序執(zhí)行的，且只會在新的循環(huán)迭代時才將任務賦給投機線程，使得投機線程每執(zhí)行完一次任務，它都需等待較長時間才能獲得下次任務。這種運行時實現(xiàn)機制同樣會導致較大的線程間同步等待開銷，還是會影響程序的并行化性能。文獻[10]在線程投機并行系統(tǒng)中提出了值預測的方法減少同步開銷，但是優(yōu)化能力有限，還帶來了額外的硬件開銷。

目前的軟件投機并行化系統(tǒng)為了保證按序提交數(shù)據(jù)及進行正確性檢測，投機任務間需要很大的進程(線程)啟動或調度開銷，以及數(shù)據(jù)通信和同步開銷等[11-12]。因此，現(xiàn)有投機并行系統(tǒng)的運行時方法都存在任務分配不平衡、沖突代價高和通信開銷大的問題。這些問題對基于進程實現(xiàn)的投機并行化系統(tǒng)更為突出，由于進程的創(chuàng)建、進程間通信的開銷和調度開銷較線程方式大得多，如何降低這些開銷也就成為了基于進程實現(xiàn)投機并行的關鍵技術。因此，本文提出一種新型的基于進程的投機任務調度策略，并對該運行時系統(tǒng)的設計理念和算法實現(xiàn)加以闡述。

2 基于進程的軟件投機并行化方法

2.1 基本概念和定義

定義1(任務) 任務是一個指令序列，對應于算法或程序的某個邏輯部分。它是投機并行執(zhí)行調度的最小單位，投機并行化的第一步就是將問題分解為多個任務。

定義2(執(zhí)行單元UE) UE是并發(fā)執(zhí)行任務的實體，任務通過分配到一個UE上執(zhí)行，如進程或線程。

定義3(任務間時序關系) 投機并行化將代碼劃分為串行執(zhí)行區(qū)域和并行執(zhí)行區(qū)域，并行執(zhí)行區(qū)域的任務將采用投機的方式與其他任務并發(fā)執(zhí)行。為了保證投機執(zhí)行的正確性，除了要對不同任務的訪存進行跟蹤外，還要明確任務間原有的時序關系。若任務t在串行執(zhí)行語義中是在任務t之前執(zhí)行的，則稱t先于t執(zhí)行，記為t<t。

定義4(訪存沖突) 對于2個不同的任務t和t，如果存在一個存儲單元，任務t和t都有對的訪存操作，只要有一個任務對進行寫操作，則稱2個任務間存在著訪問沖突。假設任務t在串行執(zhí)行時先于t執(zhí)行，即t<t，則稱任務t依賴于任務t，記為tδt。

2.2 進程投機并行化的執(zhí)行過程

投機并行化技術采用冒險的猜測執(zhí)行方式去發(fā)掘并行性，并利用沖突檢測和回退機制來保證正確性。

當程序執(zhí)行到投機并行區(qū)域時，投機系統(tǒng)先保存當前的狀態(tài)，然后啟動執(zhí)行單元并行的運行目標任務。當各投機的執(zhí)行單元完成后，再進行正確性驗證，如果沒有沖突發(fā)生，則收集各執(zhí)行單元的執(zhí)行結果，程序繼續(xù)運行后續(xù)代碼；否則恢復之前的程序狀態(tài)，并將程序指針回退到投機前位置，重新以串行的方式執(zhí)行程序。投機任務并行執(zhí)行的流程如圖1所示，實箭頭表示控制流，虛箭頭表示執(zhí)行的任務。

圖1 投機并行化原理

投機并行化的正確性驗證機制主要負責檢測投機過程中是否存在任務間的沖突，驗證過程分為3步：

(1)各投機執(zhí)行單元在并行過程中記錄讀寫信息。

(2)投機任務完成后，需要將所收集到的信息提交給其他投機執(zhí)行單元。

(3)進行投機任務間的沖突檢測。

導致投機失敗的沖突包括：

(1)狀態(tài)無法恢復的系統(tǒng)調用，這類調用往往影響系統(tǒng)共享資源的使用或直接修改系統(tǒng)狀態(tài)，如內存分配與釋放、文件的讀/寫、進程的創(chuàng)建。

(2)違反訪存的線性一致性，如果2個任務t和t，存在著依賴關系tδt，若在并行調度的過程中能夠保證不會出現(xiàn)違反依賴tδt的情況，即對于存在訪存沖突的任務在串行執(zhí)行時t<t，要求并行調度算法同樣滿足t<t。則稱該調度關系滿足線性一致性要求。否則，說明存在線性一致性 沖突。

(3)異常，在投機并行執(zhí)行過程中可能出現(xiàn)未知的程序行為，導致異常發(fā)生，包括除數(shù)為0、死鎖、死循環(huán)等情況。傳統(tǒng)的投機系統(tǒng)很難判斷和處理這類異常沖突。

2.3 進程投機的任務劃分和ISPMD執(zhí)行機制

傳統(tǒng)的基于線程的投機并行化方法，只能對連續(xù)執(zhí)行的代碼段進行投機并行化，為了支持更多類型的并行性，實現(xiàn)了一種稱為隱式單程序多數(shù)據(jù)(Implicit SPMD, ISPMD)的并行任務劃分和執(zhí)行模式。

將每個并行任務分成需維護串行執(zhí)行語義的代碼區(qū)域和可能并行執(zhí)行的代碼區(qū)域(PPR)2種類型。并行執(zhí)行過程采用SPMD的方式，即每個投機進程都會執(zhí)行需維護串行執(zhí)行語義的代碼，而僅屬于本次投機任務的進程才執(zhí)行可能并行執(zhí)行區(qū)域內的代碼。

算法1ISPMD任務劃分和執(zhí)行舉例 1: SUP_parallel_start();2: while(condition){3: P;4: SUP_task();{5: Q;6: }7: R;8: }9: SUP_parallel_finish();

例如算法1所示的循環(huán)，對該while循環(huán)的代碼進行并行化，同時要求滿足代碼和串行執(zhí)行，并發(fā)執(zhí)行。則采用ISPMD任務執(zhí)行模型，當?shù)趥€進程串行執(zhí)行完11…P1R1P后，就可以開始執(zhí)行投機并行任務Q。假設循環(huán)共有次迭代，采用ISPMD劃分方式，執(zhí)行投機并行化的正確性須滿足以下條件：

(1)各迭代的任務間無訪存沖突，即無QδQ，0≤，≤。

(2)各迭代的任務Q與其后續(xù)的任務RP+1R+1…PR間無訪存訪存沖突，即無?，0≤≤，QδR∪QδP+1∪QδR+1∪…∪QδP∪QδR成立。

定理對于算法1的并行任務劃分方式，上述2個條件是使用ISPMD方法進行投機并行化的正確性必要保證。

證明：假設是循環(huán)所有迭代的個數(shù)，根據(jù)ISPMD的任務調度規(guī)則可知，在投機并行過程中，并發(fā)執(zhí)行的投機任務Q前，已經(jīng)得到任務11…P1R1P的執(zhí)行結果，因此它們之間的訪存沖突可以忽略檢測，即不會出現(xiàn)PδQ，≤，或RδQ，0≤<≤。由于原始的程序執(zhí)行序是1<1<1<…<P<Q<R…，如果存在QδQ，0≤<≤，則該執(zhí)行結果肯定是錯的；如果存在QδR，≤，或QδP，0≤<≤時，結果也肯定是錯誤的。因此，定理成立。

3 運行時系統(tǒng)的實現(xiàn)方法

3.1 投機并行化的任務分配和調度函數(shù)的實現(xiàn)

要實現(xiàn)ISPMD執(zhí)行方式，如果采用傳統(tǒng)的進程投機并行技術，則當每次遇到可能并行執(zhí)行代碼區(qū)域時，都會創(chuàng)建一個新的進程。這種頻繁的進程創(chuàng)建開銷都是非常巨大的，而且當投機并行過程中沒有沖突發(fā)生時，這種開銷是完全沒有必要的。

為了解決這個問題，本文提出了進程重用的概念，利用冗余計算技術和隱式任務派分等技術實現(xiàn)類似線程池的進程調度方法。采用進程重用方法的投機執(zhí)行方式如圖2所示。各投機進程間沒有直接的消息通信，也沒有同步等開銷。

圖2 進程重用的調度方式

3.2 投機執(zhí)行正確性保證機制的實現(xiàn)

對于傳統(tǒng)的投機并行化實現(xiàn)技術，為了驗證本次投機執(zhí)行的正確性，投機進程需要對相關變量的讀寫信息進行記錄，同時等待前次的投機任務完成，以獲取其寫記錄信息來進行驗證。并在自己通過正確性驗證后將該記錄傳遞給下一個投機進程。因此，導致進程間的通信十分頻繁，同步開銷非常大。

為此，本文提出并實現(xiàn)了一種稱為委托正確性檢查的方法，將正確性驗證等操作轉移到一個專門的進程，即守護進程(manager)中進行，進而使得投機進程可以無需等待正確性驗證的結果而直接執(zhí)行后續(xù)迭代。守護進程在對各投機進程提交的數(shù)據(jù)進行驗證時會自動保證檢測的順序性，即各個任務的驗證順序應與其串行執(zhí)行的順序保持 一致。

此外，為了解決投機并行系統(tǒng)在發(fā)生異常時可能造成的崩潰問題，本文設計的守護進程不僅進行投機并行進程的正確性檢測工作，還會在空閑時以串行的方式執(zhí)行可能投機代碼段。這樣能夠保證即使投機進程出現(xiàn)異常情況，原始的程序執(zhí)行也不會受到影響。

投機進程執(zhí)行完任務后，會將讀寫信息和相應修改的數(shù)據(jù)提交到進程間共享空間中。守護進程先判斷是否有投機任務執(zhí)行結束并提交數(shù)據(jù)，如果有則進行正確性驗證，如果沒有發(fā)現(xiàn)沖突，那么守護進程更新程序狀態(tài)，然后跳到投機任務之后的代碼繼續(xù)執(zhí)行。如果有錯誤或者沒有投機任務提交，則守護進程串行執(zhí)行代碼。投機進程執(zhí)行的算法如下所示：

算法2投機進程的實現(xiàn)算法 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 實驗結果與分析

為了驗證本文投機并行化運行時系統(tǒng)的有效性，與經(jīng)典的進程級投機并行化系統(tǒng)BOP和采用OpenMP版本的并行程序進行對比。

測試平臺選擇4′4 AMD 4核2.5 GHz Opteron 8380 CPU，32 GB內存服務器，串行和OpenMP編譯器都為Gcc4.4。

測試用例共6個，其中5個選自SPEC標準測試程序集。測試例子Art選自SPEC2000，是一個神經(jīng)網(wǎng)絡訓練程序。Bzip2選擇SPEC2000，是一個比較經(jīng)典的數(shù)據(jù)壓縮程序。Hmmer選自SPEC2006，是計算生物學中的一個多重序列比對統(tǒng)計模型分析程序。Parser選自SPEC2000，是一個英語語法的解析程序。Sjeng 選自SPEC CPU2006，國際象棋程序。QT-cluster(Quality threshold)是一個經(jīng)典的聚類算法，通過判斷聚類直徑是否超過預設的閾值來進行分類。

實驗結果如圖3所示，其中，SUP是本文的投機并行化系統(tǒng)，圖3顯示在8個工作進程的情況下，本文的進程投機并行化系統(tǒng)的性能加速比明顯好于BOP，幾何平均性能加速比是BOP的2.31倍。事實上，本文系統(tǒng)的性能加速比甚至不比基于線程實現(xiàn)的OpenMP版本差。由于有些程序存在數(shù)據(jù)依賴，用OpenMP很難并行化，因此沒有相應的OpenMP版本數(shù)據(jù)。

圖3 性能加速比的對比(8進程)

5 結束語

基于進程的投機并行化技術是近幾年的研究熱點，本文提出一種投機并行的運行時系統(tǒng)，對進程重用、委托檢查技術進行了介紹，這些技術有效地解決了以往投機并行化運行時系統(tǒng)運行時開銷過大的問題。本文方法由于正確性驗證與串行狀態(tài)維護的需要，守護進程占用了一個核的計算資源。下一步工作將研究如何在保證正確性的情況下，充分利用守護進程來執(zhí)行投機任務，從而進一步提高性能。

[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] 柯傳樂. 進程投機并行的運行時系統(tǒng)研究[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－)，男，助理研究員、博士，主研方向：并行編譯，編譯優(yōu)化；李 晶，博士研究生；陳 莉，副研究員；馮曉兵，研究員。

2012-11-15

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

10.3969/j.issn.1000-3428.2014.03.020