基于交互信息的投機并行化方法

摘 要:針對投機并行化中如何權(quán)衡策略并確定合適的執(zhí)行模型來獲取理想性能的問題，提出了一種基于交互信息的投機并行化方法，利用交互信息來確定投機并行化的執(zhí)行模型，建立相關(guān)評價模型，并著重從線程抽取創(chuàng)建角度提出了相應(yīng)的策略及對應(yīng)的性能評價。通過實驗表明，基于交互信息進行“按需”并行化，可以達到所需的性能要求。

關(guān)鍵詞:投機多線程; 線程抽取創(chuàng)建; 執(zhí)行模型; 并行化

中圖分類號:TP314文獻標(biāo)志碼:A

文章編號:1001-3695(2010)06-2123-04

doi:10.3969/j.issn.1001-3695.2010.06.037

Interactionbased speculative threadlevel parallelization

LI Ying， SUN Xuxue， YUAN Xinyu， XU Yingcheng

(College of Computer Science Technology， Zhejiang University， Hangzhou 310027， China)

Abstract:Aiming at the problem about how to trade off between different policies and execution models to get ideal performance in the exploration of speculative threadlevel parallelism， this paper proposed an interactionbased method to exploit speculative thread level parallelism. This solution used interactive information to set up the execution model and evaluation model， especially from the view of thread extraction and spawning. The experimental results show that on demand parallelization based on interactive information can achieve the performance goal.

Key words:speculative multithreading; thread extraction and thread spawn; execution model; parallelization

在并行編譯中，當(dāng)存在大量模糊依賴時，傳統(tǒng)并行編譯器不得不采用保守的策略來保證程序執(zhí)行的正確性，這大大限制了串行程序可以挖掘的并發(fā)程度。為解決這些問題，研究人員提出了投機并行化[1]，它將串行程序轉(zhuǎn)換成多個投機執(zhí)行的并行線程，并在運行時檢查數(shù)據(jù)依賴。

投機并行化系統(tǒng)可以由純軟件實現(xiàn)[2，3]，也可以由硬件支持[4~7]或軟硬件相結(jié)合[8~10]來完成。其主要任務(wù)包括多線程抽取和多線程的投機執(zhí)行。投機并行化中的開銷有多種來源，找到最優(yōu)的程序分解來獲得性能最優(yōu)是一個NP完全問題[11]，不同的執(zhí)行模型及實現(xiàn)機制會涉及不同的性能考慮，也會產(chǎn)生不同的開銷代價。如何在各種策略中進行權(quán)衡，確定合適的執(zhí)行模型以及建立對應(yīng)的開銷模型和性能評估，使用投機并行化來獲取理想性能，這就是本文研究的問題域。

1 交互式投機并行化

1.1 概述

本文使用的方法是結(jié)合交互式和投機并行化，利用與用戶交互獲取的信息來確定投機并行化的執(zhí)行模型，建立相關(guān)評價模型，“按需”并行化來達到性能要求。

本文使用軟硬件相結(jié)合來實現(xiàn)投機并行化系統(tǒng)，其框架結(jié)構(gòu)如圖1所示。多線程抽取主要由靜態(tài)時刻編譯系統(tǒng)支持，包括對串行程序進行劃分、多線程識別標(biāo)記、進行程序變換和編譯優(yōu)化、生成多線程并行化代碼，而多線程執(zhí)行由運行時系統(tǒng)支持，包括多線程產(chǎn)生、多線程提交，使用值預(yù)測、調(diào)度及同步等技術(shù)來進行性能優(yōu)化;通過硬件支持來實現(xiàn)對內(nèi)存一致性的維護，包括檢測數(shù)據(jù)依賴沖突、投機運行狀態(tài)和投機數(shù)據(jù)的緩存、誤投機的回滾和恢復(fù)等。

投機多線程并行化中存在的性能和開銷評估對象主要有并行粒度、負載、內(nèi)存、時間和實現(xiàn)復(fù)雜度五個方面，詳細的性能和開銷考慮點如表1所示。

本文的主要貢獻在于:a)提出交互方式進行投機多線程并行化，充分挖掘性能與執(zhí)行模型及投機策略間的對應(yīng)關(guān)聯(lián)，以達到所需的性能要求;b)從線程抽取創(chuàng)建角度提出了相應(yīng)的策略及對應(yīng)的性能評價，提供交互工具來確定策略設(shè)計。

表1 投機多線程并行化的性能評估

評估對象優(yōu)質(zhì)性能考慮點開銷代價考慮點

并行粒度粗細粒度結(jié)合，并行性充分挖掘并行性挖掘不充分，粒度不符合需要

負載負載均衡負載不平衡

內(nèi)存

內(nèi)存沖突數(shù)量少內(nèi)存沖突多

內(nèi)存一致性高內(nèi)存不一致

投機緩沖區(qū)有效使用投機緩沖區(qū)低效使用

緩存局部性高缺乏緩存局部性

時間

誤投機時線程擠壓重啟時間少誤投機時線程擠壓重啟時間開銷

降低投機緩沖區(qū)溢出率及溢出帶來的時間開銷投機緩沖區(qū)溢出的時間開銷

線程間通信花費時間少線程間通信的時間開銷

線程分派和提交花費時間少線程分派和提交產(chǎn)生的時間開銷

線程同步開銷少線程同步產(chǎn)生的時間開銷

并行代碼指令執(zhí)行時間開銷少代碼并行執(zhí)行的時間開銷，包括load、store指令延遲的開銷

運行時值預(yù)測、調(diào)度、預(yù)取等優(yōu)化技術(shù)的時間開銷少運行時值預(yù)測、調(diào)度、預(yù)取等優(yōu)化措施產(chǎn)生的時間開銷

線程新建的時間開銷少線程創(chuàng)建啟動帶來的時間開銷

依賴沖突檢測時間開銷少依賴沖突檢測的時間開銷

復(fù)雜度軟硬件實現(xiàn)復(fù)雜度可接受軟硬件實現(xiàn)復(fù)雜度高

1.2 “按需”投機并行化

1.2.1 基于交互信息的執(zhí)行模型

在投機并行化系統(tǒng)中，編程人員通過可視化交互工具輸入相關(guān)機制設(shè)計和策略選擇信息。根據(jù)這些交互信息，可變的投機多線程并行化執(zhí)行模型經(jīng)過類實例化過程成為確定的執(zhí)行模型。本文提供的可變的投機多線程執(zhí)行模型包括線程抽取創(chuàng)建策略、線程執(zhí)行策略、程序變換與調(diào)優(yōu)機制以及內(nèi)存一致性維護機制，如圖2所示。其中，程序變換工具集提供了多種編譯優(yōu)化技術(shù)，如循環(huán)展開、迭代聚合等，可由程序員定制，在線程抽取時選用以對程序進行變換優(yōu)化;投機并行調(diào)優(yōu)工具集提供了值預(yù)測、預(yù)取、強制同步、線程調(diào)度及輔助線程等機制，可由程序員定制啟用，在多線程投機執(zhí)行時進行相關(guān)優(yōu)化來達到性能目的;內(nèi)存一致性維護機制主要涉及內(nèi)存依賴沖突檢測機制和緩沖投機狀態(tài)、投機數(shù)據(jù)的策略設(shè)計，其中包括投機緩沖區(qū)大小等的設(shè)置。

為了更清晰地進行本階段的研究，即主要在線程抽取創(chuàng)建策略的設(shè)計與對應(yīng)性能評價模型的探索空間中進行研究，本文對研究模型進行一定的簡化，限定其中部分可變量因素。該研究執(zhí)行模型使用硬件來檢測內(nèi)存依賴沖突并對投機狀態(tài)和數(shù)據(jù)進行緩沖，維護內(nèi)存的一致性，默認采用循環(huán)展開和迭代聚合的程序變換技術(shù)以及值預(yù)測機制，線程執(zhí)行中采用順序提交，而將線程抽取創(chuàng)建作為可變量。下面分別對線程抽取創(chuàng)建及其對應(yīng)的性能評價模型進行建模研究。

1.2.2 線程的抽取與創(chuàng)建

線程抽取創(chuàng)建機制包括投機線程抽取對象的選擇、投機線程創(chuàng)建順序和創(chuàng)建點。線程抽取創(chuàng)建機制決定投機線程的大小及程序劃分的結(jié)果，影響執(zhí)行時間開銷和內(nèi)存開銷，與投機成功率及誤投機產(chǎn)生的開銷相關(guān)聯(lián)。

線程抽取包括循環(huán)的選擇和非循環(huán)部分的劃分。抽取創(chuàng)建策略決定了投機線程執(zhí)行的代碼以及其開始執(zhí)行的時間，主要涉及兩個點的選定，即創(chuàng)建點SP(spawning point，表示新投機線程創(chuàng)建點)和控制準(zhǔn)獨立點CQIP(control quasiindependent point，表示新創(chuàng)建的投機線程開始執(zhí)行點)[12]。如圖3所示的投機多線程創(chuàng)建和運行中，標(biāo)志了SP和CQIP的位置。線程n照常執(zhí)行指令流，直到到達一個創(chuàng)建點;在這個創(chuàng)建點，處理器標(biāo)志一條在未來很有可能執(zhí)行的指令(即指定控制準(zhǔn)獨立點CQIP)。接著，線程n+1創(chuàng)建一個投機新線程并在CQIP開始執(zhí)行，而線程n繼續(xù)執(zhí)行指令直到線程的匯合點，即CQIP。運行時刻硬件會進行依賴檢測，若檢測到內(nèi)存依賴沖突，則投機線程將被擠壓銷毀(squash)。

有效地選定指令作為創(chuàng)建點和控制準(zhǔn)獨立點來組成創(chuàng)建對(spawning pairs)才能提高線程級并行度，充分挖掘程序的并行性。線程抽取的對象主要有循環(huán)連續(xù)體，循環(huán)迭代，函數(shù)、過程/方法連續(xù)體和基本塊。針對這些對象選擇合適的SP和CQIP，使得運行時訪問SP后到達CQIP的概率非常高，以此作為有效選擇創(chuàng)建對的首要標(biāo)準(zhǔn)[12]。將循環(huán)迭代(loop iteration)作為投機多線程抽取的對象，是因為在不考慮跳轉(zhuǎn)結(jié)果的情況下，一個循環(huán)迭代開始后，下一個迭代極其有可能還在循環(huán)體中，即迭代會再次被執(zhí)行。與循環(huán)迭代相關(guān)的線程創(chuàng)建機制叫做循環(huán)迭代創(chuàng)建策略，這種策略默認將循環(huán)中靜態(tài)順序的第一條指令作為SP和CQIP。另一個高可預(yù)測性的控制流點是循環(huán)連續(xù)體(loop continuation)，將其作為投機多線程抽取對象，是因為在不考慮循環(huán)中的控制流結(jié)果的情況下，開始循環(huán)后，結(jié)束循環(huán)的后向跳轉(zhuǎn)(backward branch)指令后面的一條指令極其有可能被執(zhí)行。與循環(huán)連續(xù)體相關(guān)的線程創(chuàng)建機制叫做循環(huán)連續(xù)體創(chuàng)建策略，這種策略默認將循環(huán)中靜態(tài)順序的第一條指令作為SP，結(jié)束循環(huán)的后向跳轉(zhuǎn)的下一條指令作為CQIP。除以上所述外，子過程連續(xù)體(subroutine continuation)也可作為線程抽取的考慮對象，是因為在不考慮過程中路徑的情況下，過程調(diào)用返回后的下一條指令極其有可能被執(zhí)行。與子過程連續(xù)體相關(guān)的線程創(chuàng)建機制叫做子過程連續(xù)體創(chuàng)建策略，這種策略默認將子過程調(diào)用作為SP，子過程調(diào)用后的下一條指令作為CQIP。每次在一個過程調(diào)用指令執(zhí)行時就創(chuàng)建一個投機線程，并在調(diào)用后的下一條指令處開始執(zhí)行。

為了清晰描述幾種線程抽取對象及其標(biāo)志，現(xiàn)規(guī)定如下符號規(guī)則:

 definition of;  instance of;  equivalence of

其中:AB表示A是B的定義，AB表示A是B的一個實例，AB表示A與B等價。

線程抽取對象可形式化描述為:應(yīng)用程序中的過程由路徑組成，{p|pRP}routine。程序中的路徑是一個由節(jié)點鏈、路徑類型、長度和概率組成的四元組(X，τ〈?〉，λ，ρ)P。其中X是一組節(jié)點，每個節(jié)點可以是基本塊或循環(huán)體或調(diào)用，list(n)∧n{BB|Δl|Δc}X;τ〈?〉是模板路徑類型，可以是循環(huán)路徑類型τl{continue|break|exit}，或過程路徑類型τr{return|exit}。將路徑類型具體化后，就可得到循環(huán)路徑apply(P，τl)LP或過程路徑apply(P，τr)RP。一組循環(huán)路徑即構(gòu)成循環(huán)實例list(LP)φl，而一條過程路徑就是一個過程實例RPφc。循環(huán)實例和過程實例分別可構(gòu)成循環(huán)實例環(huán)行鏈和過程實例環(huán)行鏈cList(φ〈?〉)B，apply(B，φc)Bc，apply(B，φl)Bl。對于循環(huán)節(jié)點，它是由循環(huán)實例環(huán)行鏈、指向鏈?zhǔn)讓嵗闹羔槨⒀h(huán)計數(shù)及長度來表征(Bl，θ，t，λ)Δl。對于過程節(jié)點，它是由過程實例環(huán)行鏈、指針及長度來表征(Bc，θ，λ)Δc。根據(jù)控制流圖提供的信息，對一個程序進行遍歷，生成路徑和相關(guān)節(jié)點，同時分析可識別出循環(huán)連續(xù)體、循環(huán)迭代和過程連續(xù)體。循環(huán)迭代作為線程抽取對象時，要考慮一類循環(huán)節(jié)點，其循環(huán)實例環(huán)行鏈中的元素的路徑類型τlcontinue。循環(huán)連續(xù)體作為線程抽取對象時，要考慮那些循環(huán)實例環(huán)行鏈中元素的路徑類型為τlbreak的循環(huán)節(jié)點;過程連續(xù)體作為線程抽取對象時，要考慮那些過程實例環(huán)行鏈中元素的路徑類型τrreturn的過程節(jié)點。

分析出線程抽取對象后，需要計算和確定SP和CQIP。SP的選擇可以選在線程開始時，對于循環(huán)和調(diào)用而言分別對應(yīng)于循環(huán)主體開始和函數(shù)調(diào)用之前。文獻[13]就是采用這種策略:對于循環(huán)，SP位于循環(huán)主體的開始，每一個循環(huán)迭代將下一個迭代創(chuàng)建為投機線程;對于函數(shù)調(diào)用，SP位于函數(shù)調(diào)用之前，非投機線程執(zhí)行函數(shù)體，而從函數(shù)后續(xù)體創(chuàng)建投機線程。這種選擇策略能夠最大化處理器利用率，減少空閑時間，但會導(dǎo)致投機線程產(chǎn)生太早，不能充分考慮運行時信息，而且線程過早產(chǎn)生，導(dǎo)致沒有空閑可用的處理器可供分配。另一種SP的選擇是在線程中任意點可創(chuàng)建，具有較大靈活性，這種將創(chuàng)建投機線程延遲的方法可以充分利用運行時信息，直至能夠解析一個特定跳轉(zhuǎn)或數(shù)據(jù)依賴時才創(chuàng)建，能夠提高投機成功概率，缺點是可能會導(dǎo)致處理器空閑時間過大。確定了SP后，需要選擇CQIP。除了上文提到的高概率可達點標(biāo)準(zhǔn)外，還需考慮SP和CQIP間的距離大小，需要保持合適的距離以維持線程的大小在限定范圍內(nèi)。線程粒度太小將不能充分挖掘程序并行性，導(dǎo)致過度的線程初始化開銷;而大線程將會導(dǎo)致工作負載不均衡、投機數(shù)據(jù)和狀態(tài)緩沖區(qū)過大以及誤投機后的恢復(fù)開銷大。另外，應(yīng)該選擇合適的CQIP，使得其后面的指令與之前的指令存在較少依賴關(guān)系，即使存在依賴關(guān)系，其依賴關(guān)系中的數(shù)值應(yīng)該可預(yù)測。標(biāo)志CQIP的標(biāo)準(zhǔn)，就是保證SP和CQIP間的指令與CQIP后面的指令盡可能相互獨立無依賴[12]。

本方法提供可視化交互工具，通過用戶交互來獲取線程抽取創(chuàng)建機制中參數(shù)的相關(guān)信息，如投機線程抽取對象、投機線程創(chuàng)建點、投機線程粒度選擇等。根據(jù)這些信息，投機多線程并行化執(zhí)行模型采用如下所述的線程抽取創(chuàng)建的算法來確定SP和CQIP，從而確定線程抽取創(chuàng)建策略。

Input:cfgcontrol flow information.

Output: list(pr)where pair(snode， cnode)pr.

Declaration

choice extobjp

where p∈(P({LI，LC，SC})-)

LI: loopIteration;

LC:loopContinuation;

SC:subrouinteContinuation

choice point{firstAtOnce， delay}

suggestion grain{coarse， fine， mid}

node sp

nodeList cCandi

float prob

Process

phasel: interact with programmer， instantiate extObj， point， grain and prob(especially considering those branches)

phase 2:

one traversal and mark to generate list(Δl) and list(Δc);

case loopIteration∈extObj

compute(list(Δl)， τl， continue);

case loopContinuation∈extObj

compute(list(Δl)，τl， break);

case subrouinte Continuation∈extObj

compute(list(Δc)， τc， return);

end

function compute(list(Δ〈?〉) li， τ〈?〉t， type ty)

foreach elem in li

if(t==ty){

sp←analyzeSP(elem， point);

cCandi←analyzeCandi(sp);

pr←(sp， refine(cCandi));

add pr to output list;

}

完成SP和CQIP的計算后，就確定了一組需要創(chuàng)建的投機線程的序列。一個投機多線程執(zhí)行模型可以支持順序或亂序創(chuàng)建投機線程。如果允許亂序創(chuàng)建，則線程不需要按程序順序進行創(chuàng)建，對于兩段順序執(zhí)行中相隔較遠的代碼，可以在其交叉的代碼區(qū)創(chuàng)建線程之前并行執(zhí)行。文獻[13]采用的投機多線程協(xié)議就是采用亂序創(chuàng)建，同時在創(chuàng)建一個克隆線程時傳遞寄存器狀態(tài)。亂序創(chuàng)建投機線程挖掘了更多的任務(wù)級并行性，但也可能導(dǎo)致死鎖或系統(tǒng)開銷過大等問題。為了防止亂序創(chuàng)建中可能出現(xiàn)的死鎖情況，投機多線程處理器需要對一些線程采取搶占機制;同時，投機執(zhí)行模型中的亂序創(chuàng)建的深度應(yīng)該是有限的。例如，亂序深度為1的情況下，一個線程被創(chuàng)建后至多一個前驅(qū)線程可以被創(chuàng)建，當(dāng)前驅(qū)線程隨后被創(chuàng)建而導(dǎo)致當(dāng)前線程被搶占，處理器必須保存至多一個線程的狀態(tài)。

本機制中，程序員可通過可視化交互工具來輸入創(chuàng)建次序的選擇以及支持亂序創(chuàng)建時的亂序深度，以此來確定運行時刻投機線程的創(chuàng)建策略。

2 實驗結(jié)果與分析

本文通過用戶交互信息來確定投機多線程執(zhí)行模型，其運行時刻總的時間開銷可建模為

T∞=max(Ti-s)+Tdisp/comm(P+1)/2+

max(Ti-ei=1..p)+Tf×fail+To×overflow+Tpred

其中:Ti-s是第i個線程的創(chuàng)建時間;Ti-e是第i個線程的主體代碼指令執(zhí)行時間;fail是投機失敗的概率;To是投機緩沖區(qū)溢出的時間開銷;overflow是投機緩沖區(qū)溢出的概率;Tpred是運行時值預(yù)測產(chǎn)生的時間開銷。

投機多線程并行化方案的加速比為

speedUp=∑numi=1TiT∞

其中:Ti是線程i原始執(zhí)行的時間。

圖4所示為投機線程創(chuàng)建機制設(shè)定的一個應(yīng)用場景。本文的實驗環(huán)境使用SESC模擬器[14]模擬支持投機多線程的4核體系環(huán)境。圖5~7從加速比的性能需求角度顯示了投機線程創(chuàng)建機制中不同策略的選擇所產(chǎn)生的影響。其中，圖5為選擇不同的投機線程創(chuàng)建順序時的性能結(jié)果;圖6為選擇不同的投機線程抽取對象時的性能結(jié)果;圖7為選擇不同的投機線程粒度大小時的性能結(jié)果。圖8是投機線程亂序創(chuàng)建的系統(tǒng)開銷。

3 相關(guān)工作

近年來有不少研究從軟件和硬件角度來支持投機并行化[10，15，16]，這些框架采用了不同的執(zhí)行模型來進行投機并行化。對于投機執(zhí)行模型中的線程抽取創(chuàng)建策略，Bhowmik等人[17]在SUIFMACHSUIF平臺上設(shè)計了一個投機多線程框架，使用基于依賴的任務(wù)選擇算法設(shè)計線程創(chuàng)建策略來進行投機并行化，他們使用基于簡單啟發(fā)式的靜態(tài)編譯分析來選取投機線程。除了靜態(tài)編譯優(yōu)化方法，另外一些研究[11，12，16]使用評測(profiling)來識別好的線程劃分以進行投機執(zhí)行。文獻[11]通過評測運行時執(zhí)行次數(shù)選取線程的方法來避免靜態(tài)分解評估準(zhǔn)確性的問題，同時在評測時刻實現(xiàn)分解來避免動態(tài)分解開銷。對于線程抽取對象，循環(huán)迭代是程序中創(chuàng)建線程最明顯的部分，很多投機多線程的研究都專注于循環(huán)迭代[16，18，19]，也有針對子程序結(jié)構(gòu)開發(fā)線程級并行性[20]。Du Zhaohui等人[19]提出了一個開銷驅(qū)動的編譯框架，靜態(tài)確定哪個循環(huán)可以并行化，他們從控制流圖和數(shù)據(jù)依賴圖中計算開銷圖，并評估誤投機的概率。文獻[20]總結(jié)出使用循環(huán)迭代創(chuàng)建策略、增量值預(yù)測器以及一個無限連接體系結(jié)構(gòu)的設(shè)計，對于挖掘投機線程級并行性是非常有效的。對于投機執(zhí)行模型中的線程提交策略，文獻[3]通過實驗驗證了串行提交會成為性能瓶頸，而部分提交和并行提交能有效降低開銷。對于投機并行化中內(nèi)存一致性的維護，文獻[2]提出了一種激進的滑動窗口機制，同時在投機并行化框架中實現(xiàn)了利用規(guī)約同步約束對投機存儲操作進行數(shù)據(jù)依賴沖突檢測。

4 結(jié)束語

本文提出了基于交互信息的投機并行化方法，利用交互信息確定投機執(zhí)行模型，并將線程抽取創(chuàng)建作為可變因素對線程抽取創(chuàng)建策略及其對應(yīng)的性能評價模型進行了研究。

在未來研究中，筆者將繼續(xù)探索投機并行化執(zhí)行模型，并從以下幾方面對當(dāng)前工作進行擴展和改進:

a)目前設(shè)計的方法對開發(fā)人員有一定投機執(zhí)行的背景要求，在未來的工作中，將設(shè)計更為通用簡便的交互方式，將投機并行化的性能需求和執(zhí)行策略映射為更明晰的表達方式，為普通使用者提供友好的交互支持。

b)將線程提交機制以及程序變換與調(diào)優(yōu)作為可變因素，提供交互來支持更為靈活的投機執(zhí)行模型。

參考文獻:

[1]OPLINGER J T， HEINE D L， LAM M S. In search of speculative threadlevel parallelism[C]//Proc of the 8th International Conference on Parallel Architectures and Compilation Techniques. Washington DC: IEEE Computer Society， 1999: 303-313.

[2]CINTRA M， LLANOS D R. Toward efficient and robust software speculative parallelization on multiprocessors[C]//Proc of the 9th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. New York: ACM Press，2003: 13-24.

[3]CINTRA M， LLANOS D. Design space exploration of a software speculative parallelization scheme[J]. IEEE Trans on Parallel and Distributed Systems，2005， 16(6): 562-576.

[4]PRVULOVIC M， GARZARN M J， RAUCHWERGER L， et al. Removing architectural bottlenecks to the scalability of speculative parallelization[C]//Proc of the 28th Annual International Symposium on Computer Architecture. New York: ACM Press，2001: 204-215.

[5]SOHI G S， BREACH S E. VIJAYKUMAR T N. Multiscalar processors[C]//Proc of the 22nd Annual International Symposium on Computer Architecture. New York: ACM Press，1995: 414-425.

[6]TSAI J Y， HUANG Jian， AMLO C， et al. The superthreaded processor architecture[J]. IEEE Trans on Computers，1999， 48(9): 881-902.

[7]STEFFAN J G， COLOHAN C， ZHAI A， et al. The STAMPede approach to threadlevel speculation[J]. ACM Trans on Computer System，2005， 23(3): 253-300.

[8]CHEN M， OLUKOTUN K. TEST: a tracer for extracting speculative threads[C]//Proceedings of International Symposium on Code Generation and Optimization. Washington DC: IEEE Computer Society， 2003: 301-312.

[9]OOI C L， KIM W S， PACK I I， et al. Multiplex: unifying conventional and speculative threadlevel parallelism on a chip multiprocessor[C]//Proc of the 15th International Conference on Supercomputing. New York: ACM Press，2001: 368-380.

[10]OHSAWA T， TAKAGI M， KAWAHARA S， et al. Pinot: speculative multithreading processor architecture exploiting parallelism over a wide range of granularities[C]//Proc of the 38th Annual IEEE/ACM International Symposium on Microarchitecture. Washington DC: IEEE Computer Society， 2005: 81-92.

[11]JOHNSON T A， EIGENMANN R， VIJAYKUMAR T N. Speculative thread decomposition through empirical optimization[C]//Proc of the 12th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming.New York: ACM Press，2007: 205-214.

[12]MARCUELLO P， GONZLEZ A. Threadspawning schemes for speculative multithreading[C]//Proc of the 8th International Symposium on Highperformance Computer Architecture. Washington DC: IEEE Computer Society， 2002: 55-64.

[13]XEKALAKIS P， IOANNOU N， CINTRA M. Combining thread level speculation helper threads and runahead execution[C]//Proc of the 23rd International Conference on Supercomputing. New York: ACM Press，2009: 410-420.

[14]SACK P. SESC: SuperESCalar simulator [EB/OL]. (2004-12-20). http://iacoma.cs.uiue.edu/~pau/sack/sescdoc/sescdoc.pdf.

[15]MADRILES C， GARCAQUIONES C， NCHEZ J. Mitosis: a speculative multithreaded processor based on precomputation slices[J]. IEEE Trans on Parallel and Distributed Systems， 2008， 19(7): 914-925.

[16]LIU Wei， TUCK J， CEZE L， et al. POSH: a TLS compiler that exploits program structure[C]//Proc of the 11th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. New York:ACM Press，2006: 158-167.

[17]BHOWMIK A， FRANKLIN M. A general compiler framework for speculative multithreading[C]//Proc of the 14th Annual ACM Symposium on Parallel Algorithms and Architectures. New York: ACM Press， 2002: 99-108.

[18]劉圓，安虹，汪芳，等. 利用連續(xù)兩階段在線剖析優(yōu)化多線程推測執(zhí)行[J].小型微型計算機系統(tǒng)，2009，30(3):385-390.

[19]DU Zhaohui， LIM C C， LI Xiaofeng， et al. A costdriven compilation framework for speculative parallelization of sequential programs[C]//Proc of ACM SIGPLAN Conference on Programming Language Design and Implementation. New York: ACM Press， 2004: 71-81.

[20]安虹，王莉，王耀彬. 針對子程序結(jié)構(gòu)的線程級推測并行性分析[J].小型微型計算機系統(tǒng)，2009，30(2):230-235.