国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

基于性能預(yù)測的推測多線程循環(huán)選擇方法

2014-06-02 01:37趙銀亮李玉祥馮博琴武萬杰
電子與信息學(xué)報 2014年11期
關(guān)鍵詞:剖析線程指令

劉 斌 趙銀亮 韓 博 李玉祥 吉 爍 馮博琴 武萬杰

?

基于性能預(yù)測的推測多線程循環(huán)選擇方法

劉 斌 趙銀亮*韓 博 李玉祥 吉 爍 馮博琴 武萬杰

(西安交通大學(xué)計算機(jī)科學(xué)與技術(shù)系 西安 710049)

線程級推測(Thread-Level Speculation, TLS)是多核上一種加速串行程序的線程級自動并行化技術(shù)。循環(huán)具有規(guī)則的結(jié)構(gòu)并在運行時占有大量的執(zhí)行時間,因此循環(huán)是挖掘并行性的理想對象。然而,選擇哪些循環(huán)并行才能提高程序的加速比是一個很難決定的問題。為了解決該問題,該文提出一種基于性能預(yù)測的循環(huán)選擇方法。基于輸入訓(xùn)練集獲取程序預(yù)執(zhí)行的剖析信息,同時結(jié)合各種推測因素,構(gòu)建了循環(huán)結(jié)構(gòu)的性能預(yù)測模型。預(yù)測結(jié)果定量評估了循環(huán)推測并行的加速比并決定該循環(huán)在運行時是否適合并行。實驗結(jié)果表明,該文提出的方法能有效地預(yù)測循環(huán)并行時所蘊含的并行性,并依據(jù)預(yù)測結(jié)果準(zhǔn)確地選擇具有并行收益的循環(huán)推測并行,最終Olden基準(zhǔn)測試集加速比性能平均提升了12.34%。

并行處理;線程級推測;循環(huán)選擇;性能預(yù)測

1 引言

隨著半導(dǎo)體按照摩爾定律的發(fā)展,處理器進(jìn)入了多核時代,如何有效利用豐富的核資源成為當(dāng)前研究的熱點。當(dāng)指令級并行在挖掘并行性方面遇到了瓶頸,線程級并行(Thread-Level Parallelism, TLP)逐漸成為更佳的選擇,尤其適合于片上多處理器(Chip MultiProcessor, CMP)[1]。為了提升程序在CMP上的性能,大量非規(guī)則程序需要重構(gòu)以便適合在多核上并行執(zhí)行,從而提高程序的加速比性能。線程級推測(Thread-Level Speculation, TLS)作為線程級并行的一種重要方法,允許多個線程激進(jìn)地并行執(zhí)行以提高程序的加速比,較為典型的代表有Multiscalar[2], Hydra[3], POSH[4], Mitosis[5], DOMORE[6], SEED[7], DOE[8]和Prophet[9]。

循環(huán)具有規(guī)則的結(jié)構(gòu)并且在程序執(zhí)行時占有大量的時間,因此循環(huán)成為并行執(zhí)行最理想的對象。目前,大量的研究關(guān)注循環(huán)并且從循環(huán)中提取多線程[10]。文獻(xiàn)[11]結(jié)合數(shù)據(jù)和控制依賴提出一種誤推測代價模型,并基于該模型對循環(huán)進(jìn)行性能評估,然后對循環(huán)進(jìn)行改造并選擇合適的循環(huán)并行執(zhí)行。與本文類似文獻(xiàn)[11]也選擇了具有收益的循環(huán)并行。與本文不同的是該方法僅考慮數(shù)據(jù)和控制依賴構(gòu)建模型,而本文方法考慮了多種推測因素。文獻(xiàn)[12]為Java語言提出一種動態(tài)循環(huán)選擇框架??蚣懿捎糜布\行系統(tǒng)提取依賴時間和推測狀態(tài)等信息評估了循環(huán)的加速比性能。與本文相似的是對循環(huán)評估了循環(huán)的加速比并反向指導(dǎo)線程劃分。不同之處在于該框架研究的是面向?qū)ο蟮腏ava程序,而本文研究的是非規(guī)則C語言程序,這兩者程序的特征不同所引起的推測開銷也就不同。文獻(xiàn)[13]采用專家經(jīng)驗手工并行化了SPEC2000基準(zhǔn)測試集。文獻(xiàn)[13]的研究工作非常耗時,容易發(fā)生錯誤,而本文的研究工作是一種自動并行化的技術(shù)。

本文提出一種基于性能預(yù)測的循環(huán)選擇方法?;谳斎胗?xùn)練集多次預(yù)執(zhí)行程序獲取反映程序行為的剖析信息。綜合考慮剖析信息和影響推測并行的各種因素,構(gòu)建了循環(huán)推測并行時的性能預(yù)測模型,模型的預(yù)測結(jié)果決定了該循環(huán)是否進(jìn)行推測并行。本文基于Prophet編譯器實現(xiàn)了性能預(yù)測模型。使用Olden基準(zhǔn)測試集進(jìn)行了性能測試,并與傳統(tǒng)方法進(jìn)行了比較和分析。實驗結(jié)果表明本文提出的預(yù)測模型能有效地預(yù)測循環(huán)中所蘊含的并行性,并準(zhǔn)確地選擇有收益的循環(huán)推測并行,最終Olden基準(zhǔn)測試集加速比性能平均提升了12.34%。

2 執(zhí)行模型

TLS將串行程序在多核上并行執(zhí)行以提高程序的加速比,執(zhí)行模型如圖1所示,串行程序被一系列的線程激發(fā)點-準(zhǔn)控制無關(guān)點(Spawning Point- Control Quasi-Independent Points, SP-CQIPs)指令對映射成多線程程序。同時按照串行語義順序,在每一時刻只有一個線程提交數(shù)據(jù)到內(nèi)存,該線程被稱為確定線程,而其他線程為推測線程。每個推測線程由串行程序代碼片段及預(yù)計算片段組成。預(yù)計算片段是由編譯器根據(jù)切片技術(shù)生成的一小段代碼,用來預(yù)測推測線程使用的live-ins(推測線程使用但并非由該線程定義的變量值)。如圖1(a)所示,如果忽略SP-CQIPs指令對,推測多線程程序就轉(zhuǎn)換成串行程序;如圖1(b)所示,當(dāng)程序執(zhí)行到確定線程1中的SP時,如果有閑置核資源,將激發(fā)一個新推測線程2;當(dāng)確定線程1執(zhí)行到CQIP將驗證直接后繼線程2在預(yù)計算片段中使用的live-ins。若驗證正確,則確定線程1提交執(zhí)行結(jié)果,將核資源釋放,該核可以執(zhí)行其他的線程。然后將確定執(zhí)行的權(quán)限傳遞給直接后繼線程;若驗證失敗則會導(dǎo)致推測執(zhí)行失敗。當(dāng)出現(xiàn)驗證失敗時,則撤銷推測線程2,跳過預(yù)計算片段,串行執(zhí)行此直接后繼線程2,如圖1(c)所示;當(dāng)出現(xiàn)讀后寫(Read After Write, RAW)依賴違規(guī)時,如圖1(d)所示,則在當(dāng)前的狀態(tài)下重新啟動該線程。

3 性能預(yù)測模型

3.1 基本思想

在循環(huán)級并行中,現(xiàn)有的方法大多都采用靜態(tài)、定性的方法進(jìn)行性能評估。在本文中,結(jié)合程序的剖析信息和各種推測因素,提出一種定量預(yù)測并行性能的循環(huán)選擇方法。首先,基于輸入訓(xùn)練集獲取程序在預(yù)執(zhí)行時的剖析信息并以注釋的形式添加到對應(yīng)的SUIF中間文件(SUIF-IR)中。然后,綜合剖析信息和推測因素,構(gòu)建了一種性能預(yù)測模型。該模型力圖更加精確地預(yù)測程序行為和定量地評估各種推測因素對加速比性能的影響,并利用預(yù)測結(jié)果評判推測執(zhí)行性能的好壞程度,最終決定是否在程序運行時并行該循環(huán)。

3.2 剖析信息

程序剖析是通過收集程序過去運行時的信息,進(jìn)而動態(tài)調(diào)整程序?qū)淼膱?zhí)行。理論上講,如果編譯器能預(yù)測出精確的程序行為,它能產(chǎn)生出任何平臺下并行性能最好的代碼。然而實際上,編譯器僅能獲取部分精確的程序行為。為了提高程序行為的精確性,本文開發(fā)了Profiler剖析器,分析了程序集的輸入特征,根據(jù)輸入特征構(gòu)造了基準(zhǔn)程序的輸入訓(xùn)練集。通過多次預(yù)執(zhí)行程序捕獲了程序運行時的剖析信息,為性能預(yù)測模型的構(gòu)建提供了更為精確的程序行為。

Profiler的工作流程如圖2所示,當(dāng)一個程序指令被執(zhí)行時,首先判斷指令的類型,當(dāng)指令為循環(huán)指令時,記錄當(dāng)前循環(huán)的迭代次數(shù)和動態(tài)指令數(shù)。那么循環(huán)的平均動態(tài)指令數(shù)為L= (L-1×(-1)+)/,其中L-1為上一次循環(huán)執(zhí)行時的平均動態(tài)指令數(shù)。通過多次預(yù)執(zhí)行程序,求其平均值可獲取循環(huán)部分的剖析信息并以注釋的形式標(biāo)注在對應(yīng)的SUIF-IR文件中。

圖1 推測多線程執(zhí)行模型

圖2 程序剖析器

3.3 推測并行影響因素

線程粒度、數(shù)據(jù)依賴、線程分發(fā)和激發(fā)距離是影響循環(huán)并行性能的關(guān)鍵影響因素。一般來說這些因素被綜合考慮決定并行性能的好壞。

(1)線程粒度(thread size)是指一個線程的動態(tài)指令數(shù)。線程分發(fā)、線程啟動與重啟、線程沖突和線程間的通信會引起推測并行開銷,所以線程粒度大小是影響推測性能的關(guān)鍵因素。線程粒度過小,推測執(zhí)行中的各種開銷將會抵消掉推測并行所帶來的收益。線程粒度過大,線程間過多的控制和數(shù)據(jù)依賴將會導(dǎo)致線程沖突的概率增大,進(jìn)而增加推測并行時的開銷。

(2)數(shù)據(jù)依賴(data dependence)是指子線程中的指令引用了父線程中定義的變量。數(shù)據(jù)依賴距離通常用來刻畫線程間依賴的程度。數(shù)據(jù)依賴距離是指線程推測并行時子線程執(zhí)行時需要等待的指令數(shù)直到它所需要的數(shù)據(jù)被父線程產(chǎn)生。如果數(shù)據(jù)依賴距離過小子線程中需要的值還未由父線程產(chǎn)生,會引發(fā)額外的推測代價。

(3)線程分發(fā)(thread dispatch)是指當(dāng)激發(fā)一個新的線程時,需要分發(fā)一個處理器單元執(zhí)行該線程。線程分發(fā)需要復(fù)制父線程堆棧的參數(shù)和寄存器里的數(shù)值,這需要占用一定的開銷。

(4)激發(fā)距離是指在父線程中定義的SP點到子線程開始CQIP點之間動態(tài)指令數(shù)。如果激發(fā)距離過長,子線程執(zhí)行過程中使用的變量還未產(chǎn)生,將會導(dǎo)致數(shù)據(jù)推測失敗。如果激發(fā)距離過小,推測執(zhí)行所引起的各種開銷將抵消掉推測并行所獲得的收益。

3.4 性能預(yù)測

圖3 循環(huán)激發(fā)示意圖

圖4 推測執(zhí)行的加速效果

由式(2),式(6)和式(7)最終得到循環(huán)推測并行時預(yù)期加速比為

4 實驗結(jié)果和性能分析

本文基于SUIF/MACHSUIF[14]開發(fā)了Prophet編譯器[15],并在編譯器中實現(xiàn)了性能預(yù)測的循環(huán)選擇方法。同時在Prophet模擬器[9]中驗證了方法的有效性,Prophet模擬器是基于Tomasulo[16]算法實現(xiàn)的超標(biāo)量流水線4核處理器。最后選用了Olden 基準(zhǔn)程序集[17]中的子集測試了本文提出的評估方法。

4.1 剖析信息統(tǒng)計

通過分析Olden程序集的輸入特征,程序的輸入?yún)?shù)個數(shù)不同但都為整型。根據(jù)均勻分布隨機(jī)函數(shù)構(gòu)造了程序的訓(xùn)練輸入集,采用漸進(jìn)式預(yù)執(zhí)行來獲取程序的剖析信息。隨著程序預(yù)執(zhí)行次數(shù)的增加,程序的剖析信息在程序某次執(zhí)行之后趨于穩(wěn)定。本文希望在穩(wěn)定點之后停止預(yù)執(zhí)行,最終每個程序的預(yù)執(zhí)行次數(shù)如表1所示,剖析信息統(tǒng)計如圖6(a)所示。從圖6(a)可以看出程序預(yù)執(zhí)行后所獲取的剖析信息,其中橫軸代表了循環(huán)的平均迭代次數(shù),縱軸代表了循環(huán)平均迭代體大小。圖6(b)為圖6(a)左下角局域放大圖,從中可以看出Olden中89.16%的循環(huán)具有中小規(guī)模。同時,7.23%的循環(huán)是比較大的循環(huán)體。從表1可以看出,每個程序預(yù)執(zhí)行次數(shù)各不相同,程序mst的執(zhí)行次數(shù)最多,高達(dá)1098次,而程序bh僅執(zhí)行了106次。經(jīng)過分析,主要原因是每個程序本身的特征不同,從而導(dǎo)致循環(huán)剖析信息達(dá)到穩(wěn)定狀態(tài)時所執(zhí)行的次數(shù)也就不同。

表1 Olden基準(zhǔn)測試集剖析信息統(tǒng)計

圖6 Olden基準(zhǔn)測試集循環(huán)剖析信息

理論上講,預(yù)執(zhí)行次數(shù)越多,所構(gòu)建的預(yù)測模型也就越準(zhǔn)確。然而,由于時間的限制,再多的預(yù)執(zhí)行也無法覆蓋所有的執(zhí)行路徑。這種情況說明剖析方法在實現(xiàn)過程中,剖析信息有可能不夠完全精確。然而,隨著預(yù)執(zhí)行次數(shù)的不斷增加,這些輸入的剖析信息會變得更為精確,從而不斷提高預(yù)測模型的精確程度。

4.2 加速比性能比較

圖7給出了基于傳統(tǒng)方法[18]和本文改進(jìn)方法加速比性能的實驗數(shù)據(jù)。實驗結(jié)果顯示,大多數(shù)Olden基準(zhǔn)測試集的加速比性能都有一定程度的提升。特別是程序em3d, health和bh性能提升較為顯著,而程序mst和tsp 的加速比性能未發(fā)生改變。為了定量分析,定義性能增長率為

圖7 加速比性能比較

表2統(tǒng)計了Olden測試集基于傳統(tǒng)的方法和改進(jìn)的方法在Prophet模擬器中產(chǎn)生的動態(tài)信息及性能增長率。由表2中的最右列可以看出,與傳統(tǒng)的方法相比,本文提出的方法使Olden基準(zhǔn)測試集的增長率變化范圍由0到107.61%,其平均增長率可達(dá)12.34%。實驗數(shù)據(jù)顯示,本文的改進(jìn)方法能充分地挖掘程序中的并行性同時獲得了更好的性能改善。此外,表2和表3分別統(tǒng)計了Prophet系統(tǒng)產(chǎn)生的動態(tài)線程統(tǒng)計信息。

程序em3d性能提升高達(dá)107.61%,原因在于程序em3d中循環(huán)蘊含的并行性較大,同時本文采用性能預(yù)測方法并行了8個具有并行收益的循環(huán),而傳統(tǒng)方法僅依靠啟發(fā)式并行了4個外層循環(huán)(表2)。實驗數(shù)據(jù)表明改進(jìn)方法從程序em3d中激發(fā)出的線程數(shù)目是傳統(tǒng)方法的2.41倍,同時改進(jìn)方法保證了程序em3d激發(fā)成功率也有一定程度的提高,最終本文方法允許更多的推測線程參與并行從而提高了加速比性能。程序bh包含83個循環(huán),是循環(huán)數(shù)最多的程序。傳統(tǒng)方法僅并行了30個外層循環(huán),本文方法選取具有并行收益的69個循環(huán)并行執(zhí)行,并行的循環(huán)數(shù)量占循環(huán)總數(shù)的83.13%而傳統(tǒng)方法僅占36.14%(表2)。改進(jìn)方法雖然導(dǎo)致線程執(zhí)行的成功率下降,但并行更多的循環(huán)使成功激發(fā)的線程數(shù)目卻增加了,因此性能提升了3.16%。由表2中數(shù)據(jù)可以看出,程序health和power 執(zhí)行行為與程序bh相似。本文方法為這兩個程序分別選取了9個和13個具有并行收益的循環(huán)推測并行。雖然激發(fā)成功率都降低了(表2),但成功激發(fā)的線程數(shù)目增加了,其加速比性能各自提升了6.39%和0.93%。實驗結(jié)果表明本文方法能激發(fā)更多的推測線程參與并行從而提高程序的加速比性能。

程序voronoi有18個循環(huán)體,但循環(huán)較小同時蘊含的并行有限。由表2可見,相比傳統(tǒng)方法,雖然本文方法并行循環(huán)數(shù)增加了1個,但程序voronoi成功激發(fā)的線程數(shù)目與傳統(tǒng)方法幾乎相近,所以性能提升了,但提升的程度較為有限。程序mst和tsp加速比性能沒有發(fā)生任何變化。對于程序mst,由表2可見,循環(huán)體數(shù)有12個,傳統(tǒng)方法和本文的改進(jìn)方法都選取了6個循環(huán)并行。雖然并行的循環(huán)數(shù)相同,但本文改進(jìn)方法選擇了具有并行收益的循環(huán)和傳統(tǒng)方法所選擇的最外層循環(huán)并不相同,最終導(dǎo)致成功激發(fā)的線程數(shù)目相差不大。同樣,針對程序tsp,改進(jìn)方法選取了5個循環(huán)并行化。由表2中可見,雖然激發(fā)的線程數(shù)目增加了,但是相應(yīng)的線程激發(fā)的成功率卻降低了,結(jié)果顯示成功激發(fā)的線程數(shù)目和傳統(tǒng)方法激發(fā)的線程數(shù)基本一樣,由此可見,加速比性能不僅與線程數(shù)目相關(guān)而且還與每個線程對并行性能的貢獻(xiàn)相關(guān)。最終由于本文方法所獲取的收益與傳統(tǒng)方法所獲取的收益一致導(dǎo)致性能未發(fā)生變化。因此程序mst和tsp的加速比性能保持了原來的性能。

表2 Olden基準(zhǔn)測試集動態(tài)信息統(tǒng)計

表3 Olden基準(zhǔn)測試集線程信息統(tǒng)計

改進(jìn)方法線程粒度平均值與方差均小于傳統(tǒng)方法(表3),說明Olden基準(zhǔn)測試集更適合細(xì)粒度并行。同時,改進(jìn)方法產(chǎn)生的Live-ins變量比傳統(tǒng)方法要多。實驗結(jié)果表明本文方法有效的減少了推測并行時的開銷,提升了有效工作時間比例,從而提高了程序的加速比性能。

5 結(jié)束語

該文提出和驗證了一種基于性能預(yù)測的循環(huán)選擇方法。該文主要創(chuàng)新在于:(1)基于程序的輸入訓(xùn)練集獲取了程序預(yù)執(zhí)行的剖析信息,相比靜態(tài)分析方法更加精確地預(yù)測了程序執(zhí)行行為。(2)研究了影響線程級推測的關(guān)鍵因素。(3)提出一種性能預(yù)測模型。基于性能預(yù)測Olden基準(zhǔn)測試集加速比性能平均提升了12.34%。實驗表明,該文提出的性能預(yù)測方法能夠有效地評估循環(huán)推測并行時所蘊含的并行性,并依據(jù)評估結(jié)果選擇具有并行收益的循環(huán)推測并行從而提高程序的加速比性能。

[1] Yang L and Zhai A. Dynamically dispatching speculative threads to improve sequential execution[J]., 2012, 9(3): 13:1-13:31.

[2] Vijaykumar T N and Sohi G S. Task selection for a multiscalar processor[C]. Proceedings of the 31st Annual ACM/IEEE International Symposium on Microarchitecture, Dallas, 1998: 81-92.

[3] Hammond L, Hubbert B A, Siu M,The stanford hydra cmp[J]., 2000, 20(2): 71-84.

[4] Liu W, Tuck J, Ceze L,POSH: a TLS compiler that exploits program structure[C]. Proceedings of the 8th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, New York, 2006: 158-167.

[5] Madriles C, García-Qui?ones C, Sánchez J,Mitosis: a speculative multithreaded processor based on precomputation slices[J]., 2008, 19(7): 914-925.

[6] Jialu H, Jablin T B, Beard S R,Automatically exploiting cross-invocation parallelism using runtime information[C]. Proceedings of the 2013 IEEE/ACM International Symposium on Code Generation and Optimization, Shenzhen, 2013: 1-11.

[7] Gao L, Li L, Xue J,SEED: a statically greedy and dynamically adaptive approach for speculative loop execution[J]., 2013, 62(5): 1004-1016.

[8] Sharafeddine M, Jothi K, and Akkary H. Disjoint out-of-order execution processor[J]., 2012, 9(3): 19:1-19:32.

[9] 宋少龍, 趙銀亮, 馮博琴, 等. 支持推測多線程的擴(kuò)展多核模擬器Prophet+[J]. 西安交通大學(xué)學(xué)報, 2010, 44(10): 13-17.

Song Shao-long, Zhao Yin-liang, Feng Bo-qin,Prophet+: an extended multicore simulator for speculative multithreading[J]., 2010, 44(10): 13-17.

[10] Wang S Y, Yew P C, and Zhai A. Code transformations for enhancing the performance of speculatively parallel threads[J]., 2012, 21(2): 1-23,

[11] Du Z H, Lim C C, Li X F,A cost-driven compilation framework for speculative parallelization of sequential programs[J]., 2004, 39(6): 71-81.

[12] Chen M and Olukotun K. TEST: a tracer for extracting speculative threads[C]. Proceedings of the 2003 International Symposium on Code Generation and Optimization, San Francisco, 2003: 301-312.

[13] Prabhu M K and Olukotun K. Exposing speculative thread parallelism in SPEC2000[C]. Proceedings of the 10th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, Chicago, 2005: 142-152.

[14] Smith M D and Holloway G. An introduction to machine suif and its portable libraries for analysis and optimization[OL]. http://www.eecs.harvard.edu/hube/software/nci/overview. html, 2013.

[15] Chen Z, Zhao Y L, Pan X Y,.. An Overview of Prophet[M]. Berlin: German, Springer, 2009: 396-407.

[16] Hennessy J L and Patterson D A. Computer Architecture: A Quantitative Approach [M]. Amsterdam, Elsevier, 2012: 176-183.

[17] Carlisle M C, and Rogers A. Software caching and computation migration in olden[J]., 1996, 38(2): 248-255.

[18] Pan X Y, Zhao Y L, Chen Z,A thread partitioning method for speculative multithreading[C]. Proceedings of the 8th International Conference on Scalable Computing and Communications,Piscataway, 2009: 285-290.

劉 斌: 男,1981年生,博士生,研究方向為并行計算與機(jī)器學(xué)習(xí).

趙銀亮: 男,1960年生,教授,博士生導(dǎo)師,研究方向為程序語言與編譯系統(tǒng)、大數(shù)據(jù)并行處理及挖掘.

韓 博: 男,1975年生,高級工程師,研究領(lǐng)域為軟件編程方法學(xué)、信息管理學(xué).

A Loop Selection Approach Based on Performance Prediction for Speculative Multithreading

Liu Bin Zhao Yin-liang Han Bo Li Yu-xiang Ji Shuo Feng Bo-qin Wu Wan-jie

(,’,’710049,)

Thread-Level Speculation (TLS) is a thread-level automatic parallelization technique to accelerate sequential programs on multi-core. Loops are usually regular structures and programs spent significant amounts of time executing them, thus loops are ideal candidates for exploiting the parallelism of programs. However, it is difficult to decide which set of loops should be parallelized to improve overall program performance. In order to solve the problem, this paper proposes a loop selection approach based on performance prediction. Basing on the input training set, the paper gathers profiling information during program pre-execution. Combining profiling information associated with the program and various speculative execution factors, the paper establishes a performance prediction model for loops. Then, based on the result of prediction, the paper can quantitatively estimate the speedup of loops and decide which loops should be parallelized on runtime. The experimental results show that the proposed approach effectively predicts the parallelism of loops when speculative execution and accurately selects beneficial loops for speculative parallelization according to the predicted results, finally Olden benchmarks reach 12.34% speedup performance improvement on average speedup.

Parallel processing; Thread-Level Speculation (TLS); Loop selection; Performance prediction

TP314

A

1009-5896(2014)11-2768-07

10.3724/SP.J.1146.2013.01879

趙銀亮 zhaoy@mail.xjtu.edu.cn

2013-12-02收到,2014-03-21改回

國家自然科學(xué)基金(61173040),國家“863”計劃項目(2012AA011003)和博士學(xué)科點專項科研基金(20130201110012)資助課題

猜你喜歡
剖析線程指令
基于C#線程實驗探究
一元一次方程錯解剖析
剖析高考數(shù)列創(chuàng)新題
基于國產(chǎn)化環(huán)境的線程池模型研究與實現(xiàn)
“幾何圖形初步”錯解剖析
ARINC661顯控指令快速驗證方法
集合中的錯解剖析
淺談linux多線程協(xié)作
殺毒軟件中指令虛擬機(jī)的脆弱性分析
中斷與跳轉(zhuǎn)操作對指令串的影響