HL-TLS：支持熱點的線程級猜測編譯實現(xiàn)

金 躍，李春強，尚云海，盧永江

（浙江大學(xué)超大規(guī)模集成電路設(shè)計研究所，杭州310027）

HL-TLS：支持熱點的線程級猜測編譯實現(xiàn)

金 躍，李春強，尚云海，盧永江

（浙江大學(xué)超大規(guī)模集成電路設(shè)計研究所，杭州310027）

猜測并行化編譯，即線程級猜測（TLS）編譯，可將原來順序運行的程序并行化。但由于猜測數(shù)據(jù)的不確定性引起的數(shù)據(jù)管理開銷過大，以及猜測線程失敗引起的線程回滾開銷，使得并行后的執(zhí)行性能較低。針對上述問題，提出一種HL-TLS并行化編譯優(yōu)化框架。HL-TLS能有效地標記并行化的循環(huán)體為熱點循環(huán)體，采用對最高層次熱點循環(huán)體進行更激進的并行化的方式提高性能，而對非熱點循環(huán)體采用保守的順序執(zhí)行以減少開銷。實驗結(jié)果表明，使用HL-TLS編譯優(yōu)化框架，實驗程序的執(zhí)行效率可以提高20%。

并行計算；多線程；猜測執(zhí)行；線程級猜測并行；熱點循環(huán)；動態(tài)轉(zhuǎn)換執(zhí)行機制

1 概述

循環(huán)體的并行化是當(dāng)今多核系統(tǒng)中提升計算機性能的一個編譯研究熱點。線程級猜測（Thread Level Speculation，TLS）技術(shù)能有效提高并行化效率。TLS技術(shù)在假設(shè)不存在數(shù)據(jù)依賴的條件下，延后檢查數(shù)據(jù)沖突，積極地對程序進行并行化，從而提高程序執(zhí)行的性能。使用硬件TLS技術(shù)［1-3］，雖然取得較好的效果，但是往往代價昂貴，并且設(shè)計復(fù)雜。軟件TLS編譯技術(shù)［4-6］相比硬件來說，有更好的可擴展性，但存在資源開銷大的問題，如猜測線程間通信的開銷、猜測數(shù)據(jù)管理一致性的開銷等，特別是當(dāng)猜測線程執(zhí)行時如果檢測到數(shù)據(jù)沖突發(fā)生，往往需要將整個線程回滾（Rollback）［6］到安全點，整個程序才能繼續(xù)保持數(shù)據(jù)一致性。當(dāng)猜測錯誤達到一定比例時，線程回滾形成的CPU資源浪費會導(dǎo)致TLS猜測并行化執(zhí)行時間比順序執(zhí)行時間更長。

HL-TLS（Hot Loops-TLS）并行編譯優(yōu)化框架編譯出的程序在執(zhí)行時，編譯時插入的樁代碼能有效地標記可以并行化執(zhí)行的熱點循環(huán)體，并對循環(huán)體的并行化執(zhí)行方式進行動態(tài)轉(zhuǎn)換，轉(zhuǎn)換后的熱點循環(huán)體執(zhí)行方式根據(jù)熱點程度不同分為多個層次。在HL-TLS并行編譯優(yōu)化框架中，第一層次熱點循環(huán)體先采用順序提交的TLS并行化執(zhí)行方式；TLS并行化執(zhí)行過程中，如果回滾次數(shù)低于一定程度，則此循環(huán)體被標記為第二層次熱點循環(huán)體，被動態(tài)轉(zhuǎn)換為激進的直接提交（In-Place）［7-9］的TLS執(zhí)行方式，從而進一步提升性能；對于TLS執(zhí)行中回滾次數(shù)高于一定程度的循環(huán)體，將被標記為非熱點循環(huán)體，被動態(tài)轉(zhuǎn)換為順序執(zhí)行，從而避免開銷過大而產(chǎn)生TLS執(zhí)行效率低于順序執(zhí)行的情況。

針對TLS編譯技術(shù)的上述問題，本文提出HL-TLS編譯優(yōu)化框架，在TLS編譯技術(shù)的基礎(chǔ)上，引入熱點循環(huán)體（Hot Loops，HL）的概念來解決現(xiàn)有TLS編譯技術(shù)因線程回滾過多導(dǎo)致資源開銷過大的問題，并對熱點循環(huán)體采用更為激進的并行化執(zhí)行策略，從而提高程序性能。

2 相關(guān)研究

LRPD test［10］系統(tǒng)地實現(xiàn)了軟件TLS并行化技術(shù)。在LRPD test中，數(shù)據(jù)依賴在線程執(zhí)行的最后檢測，相比同步并行化技術(shù)（synchronization parallel）減少了等待和執(zhí)行時檢查的時間，從而提高了性能。此后RLRPD test［11］基于LRPD test做了改進，并使用了sliding w indow策略，從而控制了線程間通信的開銷。

文獻［12-13］針對循環(huán)體進行TLS研究。其中文獻［12］實現(xiàn)了代價驅(qū)動的編譯器框架，其使用代價描述決定了哪些可以被TLS并行，而哪些不適合。

本文的HL-TLS框架不同于上文提到的框架。首先，HL-TLS是一個全新的概念，以上文章都沒有針對HL-TLS進行研究。其次，雖然HL-TLS和文獻［12］中的cost-driven compiler一樣是代價驅(qū)動的，但是后者是靜態(tài)計算代價，而在HL-TLS是動態(tài)計算并決定的。但是以上文獻都沒有提到動態(tài)轉(zhuǎn)換執(zhí)行機制的技術(shù)。

文獻［14-15］實現(xiàn)了編譯器輔助TLS并行化，提高了編程效率，但是對性能并沒有改進。

文獻［16］總結(jié)了TLS并行技術(shù)，并從生命周期的角度提出新的分類方法，但是并未提出新的框架，也并未提高性能。

與本文框架最為接近的是文獻［6-7］。文獻［7］提出了一個輕量級的TLS軟件并行框架，并驗證了性能提升和可行性。文獻［6］對文獻［7］進行改進，在數(shù)據(jù)管理上采用新的數(shù)據(jù)結(jié)構(gòu)以節(jié)省緩存開銷。本文HL-TLS框架的不同之處在于：（1）采用了新框架，并提出了TLS熱點循環(huán)體的概念，針對TLS最高層次的熱點循環(huán)體，可以采用激進的直接提交的TLS策略，進一步提升程序性能；（2）本文采用了執(zhí)行機制動態(tài)轉(zhuǎn)換，程序?qū)⑹褂米钸m合的執(zhí)行方式，從而最大程度上保證程序的性能提升。

3 TLS編譯技術(shù)

TLS編譯技術(shù)，是一種并行化計算編譯技術(shù)。當(dāng)程序在編譯時不確定是否存在數(shù)據(jù)依賴關(guān)系時，編譯器往往保守地認為存在數(shù)據(jù)依賴關(guān)系，從而阻礙了程序的并行化編譯。但是運用TLS編譯技術(shù)，可以先假設(shè)程序中不存在數(shù)據(jù)沖突，將程序并行化編譯以提高性能，而將數(shù)據(jù)沖突檢測延后。

為了解決數(shù)據(jù)沖突的問題，TLS編譯技術(shù)對猜測線程產(chǎn)生的數(shù)據(jù)進行了一定管理，管理方法采用2種方式［6］：

（1）每個猜測線程產(chǎn)生的數(shù)據(jù)采用專門的緩存（Buffer）管理，不直接寫到內(nèi)存（M emory）；在猜測線程的提交（Comm it）階段，再將最終數(shù)據(jù)從緩存中提交到內(nèi)存中。這種方式稱為順序提交（Serial-Comm it）。

（2）每個猜測線程產(chǎn)生的數(shù)據(jù)直接寫到內(nèi)存（M emory），寫入前的內(nèi)存數(shù)據(jù)備份到專門的緩存（Buffer）中；在猜測線程的提交（Comm it）階段，如果檢測到數(shù)據(jù)沖突，則內(nèi)存中的數(shù)據(jù)被取消，采用備份在緩存中的原數(shù)據(jù)進行恢復(fù)。這種方式稱為直接提交（In-Place Comm it）。

直接提交相對順序提交而言，是一種激進的數(shù)據(jù)管理方法。直接提交假設(shè)猜測線程產(chǎn)生的猜測數(shù)據(jù)是正確的，且不存在將數(shù)據(jù)從緩存中提交到內(nèi)存的階段，因此如果程序中存在的數(shù)據(jù)沖突較少時，即回滾次數(shù)相對較小時，則采用直接提交將比順序提交可以獲得更好的性能。但是一旦數(shù)據(jù)沖突超過一定比例，直接提交方式的內(nèi)存恢復(fù)的開銷將引起性能急劇下降，并抵消并行化帶來的性能提升，因而此時性能比順序提交要差。另外，在TLS編譯技術(shù)中，當(dāng)程序執(zhí)行時沖突比例超過一定閾值時，TLS并行不管采用直接提交或是順序提交，其執(zhí)行時間將會超過順序執(zhí)行時間。傳統(tǒng)的TLS編譯技術(shù)一般假設(shè)程序中存在一定比例的數(shù)據(jù)沖突，因此使用的數(shù)據(jù)管理方式往往是比較保守的順序提交方式。

圖1（a）展示了一個循環(huán)體。假設(shè)只有在執(zhí)行時才知道數(shù)組成員間的依賴關(guān)系，則為了保證程序的正確性，這段程序只能順序執(zhí)行，如圖1（b）所示。但是如果運用TLS編譯技術(shù)，則可以將這段程序并行化執(zhí)行。剛開始猜測線程執(zhí)行時形成的數(shù)據(jù)，稱為猜測數(shù)據(jù)，因為并沒有檢驗其數(shù)據(jù)一致性，所以猜測數(shù)據(jù)是不安全的；當(dāng)猜測線程執(zhí)行完畢，如果沒有檢測到數(shù)據(jù)沖突，則該猜測線程產(chǎn)生的數(shù)據(jù)是安全的，此猜測線程產(chǎn)生的猜測數(shù)據(jù)被確認寫入內(nèi)存，這個過程稱為提交；如果檢測到數(shù)據(jù)沖突，線程需要撤銷（Squash）到安全狀態(tài)，并進行回滾操作，以保障數(shù)據(jù)一致性，這個過程稱為撤銷并回滾。

如圖1（c）中所示，線程1對arrary［3］進行寫操作，線程3對array［3］進行讀操作，而且讀操作發(fā)生在寫操作前，即RAW（Read-A fter-W rite）沖突，則線程3必須回滾到安全點重新執(zhí)行。

圖1 線程猜測循環(huán)過程

綜上所述，猜測線程的生命周期包括了空閑、猜測化執(zhí)行、提交或檢測到?jīng)_突進行撤銷并回滾等階段，如圖2所示。

圖2 線程猜測的生命周期

4 HL-TLS框架

本文在TLS編譯技術(shù)的基礎(chǔ)上提出了HL-TLS并行化編譯框架：標記能有效并行化的循環(huán)體為熱點循環(huán)體（HL），采用對最高層次的熱點循環(huán)體進行更激進的并行化的方式提高性能，而對非熱點循環(huán)體采用保守的執(zhí)行方式以減少開銷。

HL-TLS編譯出的程序，除循環(huán)體的線程化部分外，還包含2個重要部件：熱點循環(huán)體判斷部件和執(zhí)行機制動態(tài)轉(zhuǎn)換部件。

熱點循環(huán)體判斷部件的任務(wù)是尋找符合熱點條件的循環(huán)體。熱點循環(huán)體判斷部件將會使用如下3個條件：

（1）循環(huán)體所在的函數(shù)被調(diào)用多次，超過HL-TLS定義的臨界調(diào)用次數(shù)——N-HOT-CALL；循環(huán)體順序執(zhí)行時，所用的時間超過HL-TLS定義的臨界執(zhí)行時間——T-HOT-EXE。

（2）循環(huán)體TLS執(zhí)行后，沖突比例不超過HL-TLS定義的臨界沖突比例1——P-ROLLBACK1。

（3）循環(huán)體TLS執(zhí)行后，沖突比例超過HL-TLS定義的臨界沖突比例1——P-ROLLBACK1，但不超過HL-TLS定義的臨界沖突比例2——P-ROLLBACK2。

執(zhí)行機制動態(tài)轉(zhuǎn)換部件的任務(wù)是根據(jù)以上條件決定的循環(huán)體熱點程度選擇該循環(huán)體的執(zhí)行方式：順序執(zhí)行、順序提交的TLS并行化執(zhí)行和直接提交的TLS并行化執(zhí)行。

循環(huán)體在程序執(zhí)行初期均為非熱點循環(huán)體，采用保守的順序執(zhí)行；當(dāng)符合熱點條件1時，HL-TLS將其標記為第一層次熱點循環(huán)體，循環(huán)體將采用順序提交的TLS并行化執(zhí)行；到達下次執(zhí)行前，將根據(jù)是否符合熱點條件2來決定是否轉(zhuǎn)換為激進的直接提交的TLS并行化執(zhí)行，如果沖突比例小于P-ROLLBACK1，則HL-TLS將其標記為第二層次熱點循環(huán)體，采用激進的直接提交的TLS并行化執(zhí)行此循環(huán)體，以提高執(zhí)行效率；如果沖突比例大于P-ROLLBACK 1但是小于P-ROLLBACK2，即滿足熱點條件3，此循環(huán)體仍然作為第一層次熱點采用順序提交的TLS并行化執(zhí)行；如果沖突比例超過P-ROLLBACK 2，過多的數(shù)據(jù)沖突造成的回滾操作將浪費大量CPU資源，判定此循環(huán)體不適合TLS并行化，HL-TLS將其標記為非熱點循環(huán)體，此后執(zhí)行將轉(zhuǎn)為保守的順序執(zhí)行方式。

4.1 熱點判斷

如前文所述，熱點判斷的條件有3點。循環(huán)體滿足條件1或者條件3時，為第一層次熱點循環(huán)體，將采用順序提交的TLS方式執(zhí)行；循環(huán)體滿足條件2時，為第二層次，即最高層次熱點循環(huán)體，將采用激進的直接提交的TLS方式執(zhí)行，以提高程序性能。如果3個條件皆不滿足或者TLS執(zhí)行后發(fā)現(xiàn)沖突比例超過了P-ROLLBACK 2時，此循環(huán)體將被標記為非熱點循環(huán)體，其后續(xù)的執(zhí)行方式將使用順序執(zhí)行。使用各個條件來判斷熱點循環(huán)體的原因如下：

（1）不滿足條件1：如果循環(huán)體所在的函數(shù)沒有被多次調(diào)用（調(diào)用次數(shù)小于N-HOT-CALL），循環(huán)體并行化的意義不大，繼續(xù)延續(xù)順序執(zhí)行。如果循環(huán)體的單次執(zhí)行時間很短（小于T-HOT-EXE），則可以判定將來并行化帶來的性能提升將被創(chuàng)建線程的開銷所抵消，循環(huán)體不能被判定為熱點循環(huán)體，將繼續(xù)延續(xù)順序執(zhí)行；

（2）不滿足條件2或者條件3：如果沖突比例過高（HL-TLS中定義為大于P-ROLLBACK 2），則數(shù)據(jù)沖突而回滾整個線程造成的開銷將抵消并行帶來的優(yōu)勢，甚至超過了帶來的優(yōu)勢，即TLS并行化執(zhí)行時間超過順序執(zhí)行時間的情況。

（3）區(qū)分第一層次和第二層次熱點循環(huán)體：如前文所述，如果回滾比例在一定范圍內(nèi)（HL-TLS中定義為小于P-ROLLBACK1），則直接提交的TLS并行執(zhí)行方式可以獲得比順序提交的TLS并行執(zhí)行方式更快的執(zhí)行速度。第二層次熱點循環(huán)體采用的是直接提交的TLS并行執(zhí)行，其回滾比例小于P-ROLLBACK1；第一層次熱點循環(huán)體采用的是順序提交的TLS并行執(zhí)行，其回滾比例大于P-ROLLBACK 1但小于P-ROLLBACK 2。當(dāng)回滾比例大于P-ROLLBACK2，此循環(huán)體為非熱點循環(huán)體。

熱點機制的算法實現(xiàn)如下：

判定為熱點循環(huán)體的優(yōu)勢在于，下一次執(zhí)行此循環(huán)體時，將根據(jù)循環(huán)體為第一層次或第二層次熱點循環(huán)體的信息，來選擇下一次執(zhí)行方式。如果此循環(huán)體被判定為第一層次熱點循環(huán)體，則說明此循環(huán)體滿足了順序提交的TLS并行化執(zhí)行的前提條件，下次執(zhí)行則會采用順序提交的TLS并行化執(zhí)行。如果此循環(huán)體被判定為第二層次熱點，則說明此循環(huán)體用TLS來并行化將有極大可能給程序帶來性能的提升，此時，可以采用更加激進的策略去TLS并行這段程序塊，即采用直接提交的數(shù)據(jù)管理機制。

相反，如果這段循環(huán)體沒有被判定為第一層或第二層次熱點循環(huán)體，則此循環(huán)體為非熱點循環(huán)體，只能夠保守地對它進行順序執(zhí)行。在這種情況下，通常是因為程序執(zhí)行時遇到了過多的沖突，此時如果仍然采用TLS并行化策略，將會導(dǎo)致開銷（沖突檢測開銷、回滾開銷）帶來的性能下降大過并行化帶來的性能提升。此時，相比較現(xiàn)行其他的TLS策略，HL-TLS編譯優(yōu)化框架有利于避免這種情況的發(fā)生從而大大減少了不必要的開銷。

使用到的宏、數(shù)據(jù)結(jié)構(gòu)和函數(shù)接口如表1所示。

表1 熱點判斷部件用到的結(jié)構(gòu)體以及函數(shù)接口

4.2 執(zhí)行機制動態(tài)轉(zhuǎn)換

從上節(jié)可知，執(zhí)行機制的動態(tài)轉(zhuǎn)換依賴于熱點判斷部件。對于循環(huán)體運用什么方式的執(zhí)行機制，是由熱點判斷部件決定的。這種動態(tài)的執(zhí)行方式的轉(zhuǎn)化，解決了因TLS并行帶來的并行性能低于順序執(zhí)行性能的問題；并且因更加激進的TLS策略的應(yīng)用，一定程度上提高了程序的性能。如圖3所示，在HL-TLS框架中的動態(tài)轉(zhuǎn)換執(zhí)行機制分為下面2個方面：

（1）發(fā)生在循環(huán)體多次調(diào)用之間。根據(jù)熱點判斷部件，可以知道循環(huán)體是否被判定為第一層或第二層次熱點循環(huán)體。如果循環(huán)體是第一層次熱點循環(huán)體，則下次執(zhí)行循環(huán)體時，將用TLS并行化機制；如果循環(huán)體是第二層次循環(huán)體，則使用更加激進的直接提交的TLS并行化執(zhí)行策略；否則，此循環(huán)體將使用保守的順序化執(zhí)行機制。

（2）發(fā)生在循環(huán)體執(zhí)行時。如前文所述，多次執(zhí)行循環(huán)體時，會根據(jù)前幾次的執(zhí)行情況，來指導(dǎo)下一次執(zhí)行。不僅如此，在循環(huán)體執(zhí)行的時候，也會根據(jù)循環(huán)體內(nèi)部前幾次循環(huán)執(zhí)行后的數(shù)據(jù)沖突情況，來指導(dǎo)循環(huán)體剩下部分的執(zhí)行。如果前幾次循環(huán)出現(xiàn)沖突，那么在剩下的循環(huán)體中，出現(xiàn)沖突的可能性就會大大增加。所以，在前幾次循環(huán)中，數(shù)據(jù)沖突出現(xiàn)一定的比例之后，就會轉(zhuǎn)而用順序或同步并行的方法去執(zhí)行剩下的部分。

圖3 動態(tài)轉(zhuǎn)換執(zhí)行機制

4.3 程序執(zhí)行流程

運用HL-TLS框架時，編譯器對源代碼中每個可以TLS并行化執(zhí)行的循環(huán)體前插入一段熱點判斷和執(zhí)行機制動態(tài)轉(zhuǎn)換的代碼，并對其進行并行化編譯，程序執(zhí)行時，通過HL-TLS的熱點判斷和執(zhí)行機制動態(tài)轉(zhuǎn)換部件，進行第一層次、第二層次熱點的判斷，并轉(zhuǎn)換到最適合此循環(huán)體的執(zhí)行方式執(zhí)行。

（1）順序執(zhí)行程序，跟蹤循環(huán)體是否滿足熱點條件1；

（2）如果不滿足條件1，則此循環(huán)體被判定為非熱點循環(huán)體，循環(huán)體繼續(xù)采用順序執(zhí)行；

（3）如果滿足條件1，則此循環(huán)體被判定為第一層次熱點循環(huán)體，循環(huán)體的下次執(zhí)行方式為順序提交的TLS并行，TLS執(zhí)行后判斷是否滿足熱點條件2或者3；

（4）如果滿足熱點條件2，則此循環(huán)體被判定為第二層次熱點循環(huán)體，此后循環(huán)體的猜測并行化執(zhí)行將采用更為激進的直接提交的TLS執(zhí)行方式；

（5）如果不滿足條件2，但滿足條件3，則此循環(huán)體延續(xù)為第一層次熱點循環(huán)體，此后的執(zhí)行方式為順序提交的TLS執(zhí)行；

（6）如果既不滿足條件2，也不滿足條件3，則此循環(huán)體將被判定為非熱點循環(huán)體，此后的執(zhí)行方式為保守地順序執(zhí)行。

循環(huán)體執(zhí)行的流程如圖4所示。

圖4 HL-TLS執(zhí)行流程

在HL-TLS框架中，熱點判斷部件以及執(zhí)行機制動態(tài)轉(zhuǎn)換的采用，有效減少了因回滾引起的開銷，解決了因開銷過大而引起的性能降低的問題；而被標記為第二層次熱點之后，采用更為激進的直接提交的TLS方式執(zhí)行循環(huán)體，在一定程度上提高了其執(zhí)行的性能。

5 性能比較與分析

將HL-TLS和SpLSC［7］做性能比較。SpLSC是一個輕量級的TLS編譯框架，是目前相對實用且性能表現(xiàn)比較好的實現(xiàn)框架。SpLSC假設(shè)程序中會存在一定的沖突比例，采用順序提交的TLS執(zhí)行方式，且其執(zhí)行方式在程序執(zhí)行時不可改變。相比較SpLSC來說，HL-TLS引進了熱點循環(huán)體的概念和分析，并運用了執(zhí)行機制的動態(tài)轉(zhuǎn)換，且主要在以下2個方面對SpLSC體現(xiàn)了優(yōu)勢：

（1）引進熱點循環(huán)體判斷，能有效減少不必要的開銷，特別是避免因回滾過多引起的TLS并行性能比順序性能還低的問題；

（2）對于最終判定為第二層次熱點的循環(huán)體，HL-TLS將采用更加激進的方案進行TLS并行，所以在一定程度上能提高加速比。

實驗所用的處理器為Intel Xeon 8核處理器，頻率3.47 GHz，cache大小為12 288 KB。所用的編譯器為gcc-4.6.3，使用-O2選項。實驗采用的測試用例來自以下3個benchmark：SciM ark2，BYTEmark和JOlden。實驗結(jié)果如表2所示，SpLSC和HL-TLS加速比皆為和順序執(zhí)行相比較的結(jié)果。

表2 測試用例實驗結(jié)果

如表2所示，4核上的HL-TLS執(zhí)行速度平均要比順序執(zhí)行提高了79.7%，比SpLSC提高了19.8%。其中NNFW性能提升較為明顯，比SpLSC提升了將近40%。

8核上的HL-TLS執(zhí)行速度平均要比順序執(zhí)行提高了152.3%，比SpLSC提高了20.0%。其中SparseM ult性能提升較為明顯，比SpLSC提升了將近40%。而在IDEA Dekey中性能略微下降了0.8%。

從實驗結(jié)果中可以看到，除了IDEA Dekey在8核HL-TLS比SpLSC要慢，HL-TLS的性能均有所提升，不管是在4核還是8核上，執(zhí)行速度平均要比SpLSC提高了20%。HL-TLS性能有所提升的主要原因是HL-TLS在執(zhí)行時識別了循環(huán)體熱點層次，其后最高層次熱點循環(huán)體將采用更加激進的直接提交的數(shù)據(jù)管理方案進行TLS并行，因此得到了更多的性能提升。

IDEA Dekey在8核中，HL-TLS執(zhí)行速度比SpLSC低0.9%。分析運行結(jié)果發(fā)現(xiàn)，IDEA Dekey運行時猜測線程產(chǎn)生的數(shù)據(jù)有較高的比例是猜測錯誤的，因此IDEA Dekey適合使用順序提交的TLS并行方式。在IDEA Dekey中，HL-TLS沒有體現(xiàn)出對SpLSC的優(yōu)勢，HL-TLS熱點判斷模塊產(chǎn)生的額外開銷導(dǎo)致了性能略微有所下降。

除了動態(tài)地采用直接提交的TLS并行策略提升性能，HL-TLS還將動態(tài)地識別那些不適合TLS并行化的循環(huán)體轉(zhuǎn)換為保守地順序執(zhí)行。如表3所示，在EM 3D中，HL-TLS是SpLSC性能的2倍左右。其中，SpLSC性能明顯低于順序執(zhí)行，且不到順序執(zhí)行的50%。而HL-TLS性能接近于順序執(zhí)行。SpLCS引起的回滾數(shù)量為：20（4核）、60（8核）。例如，循環(huán)體進行TLS并行執(zhí)行時如果數(shù)據(jù)沖突過多此時線程撤銷并回滾的開銷已經(jīng)抵消了并行化帶來的優(yōu)勢，HL-TLS將采用順序執(zhí)行，從而避免了如SpLSC的性能明顯下降的問題。

表3 SpLSC中開銷過大的情況

因此，從總體上看，無論循環(huán)體猜測并行執(zhí)行時回滾次數(shù)多少，HL-TLS都體現(xiàn)出了對SpLSC的優(yōu)勢。

6 結(jié)束語

本文提出一種新的TLS編譯框架HL-TLS。該框架有效解決了現(xiàn)有TLS編譯技術(shù)中猜測并行執(zhí)行回滾開銷過大、性能提高有限的問題。HL-TLS對第二層次的熱點循環(huán)體采用更加激進的TLS并行化策略，從而進一步提高了并行執(zhí)行的性能。而針對回滾過多影響性能、甚至導(dǎo)致并行性能低于順序執(zhí)行的情況，HL-TLS能夠加以識別并動態(tài)轉(zhuǎn)換執(zhí)行機制，從而避免此種問題的發(fā)生。實驗結(jié)果表明，HL-TLS在一定程度上提高了程序的性能，并且解決了開銷過大的問題。下一步的研究方向是在HOT機制中加入同步并行的HOT判斷，并在動態(tài)轉(zhuǎn)換執(zhí)行機制中進行同步并行方案，實現(xiàn)順序、同步并行、順序提交TLS并行和直接提交TLS并行執(zhí)行方式的動態(tài)轉(zhuǎn)換，從而進一步挖掘程序的并行化能力。

［1］ Steffan JG，Colohan C G，Zhai A，et al.A Scalable Approach for Thread Level Speculation［C］//Proceedings of the 27th Annual International Sym posium on Computing Architecture.New York，USA：ACM Press，2000：1-12.

［2］ 賴 鑫，劉 聰，王志英.支持線程級猜測的存儲體系結(jié)構(gòu)設(shè)計［J］.計算機工程，2012，38（24）：228-234.

［3］ Krishnan V，Torrellas J.A Chip-multiprocessor Architecture with Speculative Multithreading［J］.IEEE Transactions on Computings，1999，48（9）：866-880.

［4］ Cintra M，Llanos D R.Toward Efficient and Robust Software Speculative Parallelization on Multiprocessors［C］//Proceedings of the 9th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming.New York，USA：ACM Press，2003：13-24.

［5］ Liu W，Tuck J，Ceze L，et al.POSH：A TLS Compiler that Exploits Program Structure［C］//Proceedings of the 11th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming.New York，USA：ACM Press，2006：158-167.

［6］ Yiapanis P，Rosas-Ham D，Brow n G，et al.Optimizing Software Runtime Systems for Speculative Parallelization［J］.ACM Transactions on Architecture and Code Optimization，2013，9（4）：39-51.

［7］ Oancea C E，Mycroft A.Software Thread-level Speculation：An Optimistic Library Implementation［C］//Proceedings of the 1st International Workshop on Multicore Software Engineering.New York，USA：ACM Press，2008：23-32.

［8］ Oancea C E，Mycroft A.A Lightweight In-place Implementation for Software Thread-level Speculation［C］// Proceedings of the 21st Annual Symposium on Parallelism in Algorithm s and Architectures.New York，USA：ACM Press，2009：223-232.

［9］ Oancea C E，Mycroft A.Set-congruence Dynamic Analysis for Thread-level Speculation［M］.Berlin，Germany：Springer-Verlag，2008：156-171.

［10］ Rauchwerger L，Padua D.The LRPD Test：Speculative Run-time Parallelization of Loops with Privatization and Reduction Parallelization［C］//Proceedings of ACM SIGPLAN'95.New York，USA：ACM Press，1995：218-232.

［11］ Dang F，Yu H，Rauchwerger L.The R-LRPD Test：Speculative Parallelization of Partially Parallel Loops，TX77843-3112［R］.College Station，USA：Texas A&M University，2001.

［12］ Du Zhaohui，Lim Chu Cheow，Li Xiaofeng，et al.A Cost-driven Compilation Framework for Speculative Parallelization of Sequential Program s［C］//Proceedings of ACM SIGPLAN'04.New York，USA：ACM Press，2004：71-81.

［13］ Dubey P K，O'Brien K，O'Brien K M，et al.Singleprogram Speculative Multithreading（SPSM）Architecture［C］//Proceedings of PACT'95.Manchester，UK：［s.n.］，1995：109-121.

［14］ Xiang Lingxiang，Scott M L.Compiler Aided Manual Speculation for High Performance Concurrent Data Structures［C］//Proceedings of the 18th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming.New York，USA：ACM Press，2013：47-56.

［15］ A ldea S，Estebanez A，Llanos D R，et al.A New GCC Plugin-based Compiler Pass to Add Support for Thread level Speculation into OpenMP［C］//Proceedings of EPP'14.Porto，Portugal：Springer International Publishing，2014：234-245.

［16］ 郭 輝，王 瓊，沈 立，等.多核平臺上的線程級猜測執(zhí)行綜述［J］.計算機科學(xué)，2014，41（1）：16-21.

編輯索書志

HL-TLS：Com piling Implementation of Thread Level Speculation Supporting Hot Spot

JIN Yue，LI Chunqiang，SHANG Yunhai，LU Yongjiang
（Institute of VLSIDesign，Zhejiang University，Hangzhou 310027，China）

Thread Level Speculation（TLS）compiling can effectively improve the parallel efficiency.But the overheads，caused by the management of the speculative data and the failure of speculative thread's rollback，decreases the improvement of the parallel performance.Aiming at the too big overhead of data management and thread rollback，the Hot Loops-TLS（HL-TLS）framework is proposed.HL-TLS marks the loops which can be efficiently paralleled as HL，using a more eager parallel way on HL to improve performance，while using conservative sequence way on non-HL to reduce the overheads.Experimental result shows that HL-TLS im proves 20%performance.

parallel computing；multi-thread；speculative execution；Thread Level Speculation（TLS）parallel；Hot Loops（HL）；dynamic transformation execution mechanism

金 躍，李春強，尚云海，等.HL-TLS：支持熱點的線程級猜測編譯實現(xiàn)［J］.計算機工程，2015，41（11）：77-83.

英文引用格式：Jin Yue，Li Chunqiang，Shang Yunhai，et al.HL-TLS：Com piling Implementation of Thread Level Speculation Supporting Hot Spot［J］.Computer Engineering，2015，41（11）：77-83.

1000-3428（2015）11-0077-07

A

TP311

10.3969/j.issn.1000-3428.2015.11.014

國家自然科學(xué)基金資助項目（61204111）；“核高基”重大專項（2010ZX01030-001-001-006）。

金 躍（1990-），男，碩士研究生，主研方向：編譯器優(yōu)化，并行計算；李春強、尚云海，碩士；盧永江，副教授、博士。

2014-11-06

2014-12-07 E-m ail：xuyv@zju.edu.cn