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

?

基于進(jìn)程投機(jī)并行的運(yùn)行時(shí)系統(tǒng)設(shè)計(jì)與優(yōu)化

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

(1. 中國(guó)科學(xué)院計(jì)算技術(shù)研究所，北京 100190；2. 中國(guó)科學(xué)院大學(xué)，北京 100190)

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

軟件投機(jī)并行；基于進(jìn)程投機(jī)并行；運(yùn)行時(shí)并行；委托正確性檢查；并行任務(wù)劃分

1 概述

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

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

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

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

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

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

2 基于進(jìn)程的軟件投機(jī)并行化方法

2.1 基本概念和定義

定義1(任務(wù)) 任務(wù)是一個(gè)指令序列，對(duì)應(yīng)于算法或程序的某個(gè)邏輯部分。它是投機(jī)并行執(zhí)行調(diào)度的最小單位，投機(jī)并行化的第一步就是將問(wèn)題分解為多個(gè)任務(wù)。

定義2(執(zhí)行單元UE) UE是并發(fā)執(zhí)行任務(wù)的實(shí)體，任務(wù)通過(guò)分配到一個(gè)UE上執(zhí)行，如進(jìn)程或線程。

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

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

2.2 進(jìn)程投機(jī)并行化的執(zhí)行過(guò)程

投機(jī)并行化技術(shù)采用冒險(xiǎn)的猜測(cè)執(zhí)行方式去發(fā)掘并行性，并利用沖突檢測(cè)和回退機(jī)制來(lái)保證正確性。

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

圖1 投機(jī)并行化原理

投機(jī)并行化的正確性驗(yàn)證機(jī)制主要負(fù)責(zé)檢測(cè)投機(jī)過(guò)程中是否存在任務(wù)間的沖突，驗(yàn)證過(guò)程分為3步：

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

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

(3)進(jìn)行投機(jī)任務(wù)間的沖突檢測(cè)。

導(dǎo)致投機(jī)失敗的沖突包括：

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

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

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

2.3 進(jìn)程投機(jī)的任務(wù)劃分和ISPMD執(zhí)行機(jī)制

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

將每個(gè)并行任務(wù)分成需維護(hù)串行執(zhí)行語(yǔ)義的代碼區(qū)域和可能并行執(zhí)行的代碼區(qū)域(PPR)2種類型。并行執(zhí)行過(guò)程采用SPMD的方式，即每個(gè)投機(jī)進(jìn)程都會(huì)執(zhí)行需維護(hù)串行執(zhí)行語(yǔ)義的代碼，而僅屬于本次投機(jī)任務(wù)的進(jìn)程才執(zhí)行可能并行執(zhí)行區(qū)域內(nèi)的代碼。

算法1ISPMD任務(wù)劃分和執(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)，對(duì)該while循環(huán)的代碼進(jìn)行并行化，同時(shí)要求滿足代碼和串行執(zhí)行，并發(fā)執(zhí)行。則采用ISPMD任務(wù)執(zhí)行模型，當(dāng)?shù)趥€(gè)進(jìn)程串行執(zhí)行完11…P1R1P后，就可以開(kāi)始執(zhí)行投機(jī)并行任務(wù)Q。假設(shè)循環(huán)共有次迭代，采用ISPMD劃分方式，執(zhí)行投機(jī)并行化的正確性須滿足以下條件：

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

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

定理對(duì)于算法1的并行任務(wù)劃分方式，上述2個(gè)條件是使用ISPMD方法進(jìn)行投機(jī)并行化的正確性必要保證。

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

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

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

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

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

圖2 進(jìn)程重用的調(diào)度方式

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

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

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

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

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

算法2投機(jī)進(jìn)程的實(shí)現(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 實(shí)驗(yàn)結(jié)果與分析

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

測(cè)試平臺(tái)選擇4′4 AMD 4核2.5 GHz Opteron 8380 CPU，32 GB內(nèi)存服務(wù)器，串行和OpenMP編譯器都為Gcc4.4。

測(cè)試用例共6個(gè)，其中5個(gè)選自SPEC標(biāo)準(zhǔn)測(cè)試程序集。測(cè)試?yán)覣rt選自SPEC2000，是一個(gè)神經(jīng)網(wǎng)絡(luò)訓(xùn)練程序。Bzip2選擇SPEC2000，是一個(gè)比較經(jīng)典的數(shù)據(jù)壓縮程序。Hmmer選自SPEC2006，是計(jì)算生物學(xué)中的一個(gè)多重序列比對(duì)統(tǒng)計(jì)模型分析程序。Parser選自SPEC2000，是一個(gè)英語(yǔ)語(yǔ)法的解析程序。Sjeng 選自SPEC CPU2006，國(guó)際象棋程序。QT-cluster(Quality threshold)是一個(gè)經(jīng)典的聚類算法，通過(guò)判斷聚類直徑是否超過(guò)預(yù)設(shè)的閾值來(lái)進(jìn)行分類。

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

圖3 性能加速比的對(duì)比(8進(jìn)程)

5 結(jié)束語(yǔ)

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

[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ī)并行化方法[J].計(jì)算機(jī)應(yīng)用研究, 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] 柯傳樂(lè). 進(jìn)程投機(jī)并行的運(yùn)行時(shí)系統(tǒng)研究[D]. 北京: 中國(guó)科學(xué)院計(jì)算技術(shù)研究所, 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

國(guó)家“863”計(jì)劃基金資助項(xiàng)目(2012AA010902)；國(guó)家“973”計(jì)劃基金資助項(xiàng)目(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