基于緩存行為特征的線程數(shù)據(jù)預(yù)取距離控制策略

黃 艷 張啟坤 段趙磊 古志民

1 引言

隨著片上多核處理器技術(shù)的快速發(fā)展，阻礙多核系統(tǒng)性能提升的“存儲(chǔ)墻”問(wèn)題進(jìn)一步突顯。目前，線程數(shù)據(jù)預(yù)取技術(shù)是隱藏存儲(chǔ)器訪問(wèn)延遲、提高多核系統(tǒng)性能的有效手段。

預(yù)取距離指數(shù)據(jù)預(yù)取技術(shù)中發(fā)出預(yù)取請(qǐng)求到預(yù)取數(shù)據(jù)被使用之間的執(zhí)行間隔。預(yù)取距離的大小直接決定了預(yù)取的有效性。一方面，為了讓預(yù)取數(shù)據(jù)在被使用前到達(dá)以便完全隱藏該數(shù)據(jù)的緩存失效延遲，預(yù)取距離應(yīng)該足夠大[1]；另一方面，為了避免預(yù)取數(shù)據(jù)到達(dá)的太早造成緩存污染，預(yù)取距離又不能過(guò)大[2]。

近年來(lái)，不少研究者[316]-利用幫助線程數(shù)據(jù)預(yù)取隱藏應(yīng)用程序中長(zhǎng)延遲取數(shù)指令的訪存延遲，其中多數(shù)采用特殊的線程間同步機(jī)制來(lái)控制預(yù)取距離。文獻(xiàn)[3]在程序執(zhí)行過(guò)程中使用特殊的硬件預(yù)測(cè)表預(yù)測(cè)最優(yōu)預(yù)取距離；文獻(xiàn)[4]通過(guò)關(guān)聯(lián)表評(píng)估連續(xù)兩次緩存失效事件的時(shí)間間隔，在一定預(yù)取距離范圍內(nèi)盡早發(fā)出預(yù)取請(qǐng)求；文獻(xiàn)[5]通過(guò)編譯器分析設(shè)置特定的采樣間隔，主線程在每個(gè)采樣間隔觸發(fā)一個(gè)幫助線程；文獻(xiàn)[6]通過(guò)預(yù)解碼（decode）檢測(cè)到長(zhǎng)延遲取數(shù)指令時(shí)觸發(fā)幫助線程；文獻(xiàn)[7]中幫助線程通過(guò)一個(gè)循環(huán)計(jì)數(shù)器與主線程進(jìn)行同步；文獻(xiàn)[8]使用信號(hào)量同步機(jī)制控制幫助線程的預(yù)取距離；文獻(xiàn)[9]通過(guò)增量改變預(yù)取距離的值找到較優(yōu)預(yù)取距離；文獻(xiàn)[10]在檢測(cè)到規(guī)律的只讀缺失模式時(shí)進(jìn)行數(shù)據(jù)預(yù)取。當(dāng)面向非規(guī)則數(shù)據(jù)密集應(yīng)用時(shí)，由于非規(guī)則數(shù)據(jù)訪問(wèn)間的相互依賴(lài)關(guān)系，這些方法難以實(shí)現(xiàn)對(duì)預(yù)取距離的有效控制，預(yù)取時(shí)效性難以得到保證。

本文提出一種基于緩存行為特征的有效預(yù)取距離控制策略。該方法的核心思想是：首先分析和預(yù)測(cè)熱點(diǎn)循環(huán)數(shù)據(jù)訪問(wèn)的緩存行為特征；然后，根據(jù)應(yīng)用程序熱點(diǎn)循環(huán)的緩存行為特征選取最大有效預(yù)取距離；最后，在預(yù)測(cè)的有效預(yù)取距離取值范圍內(nèi)通過(guò)實(shí)驗(yàn)測(cè)試選擇較優(yōu)預(yù)取距離取值。通過(guò)該策略控制線程數(shù)據(jù)預(yù)取距離能進(jìn)一步提高線程預(yù)取性能。

2 面向共享緩存的間隔預(yù)取策略（Skip-Pre fetching, SP）

指針應(yīng)用程序中的熱點(diǎn)數(shù)據(jù)通?？梢苑譃檠h(huán)依賴(lài)數(shù)據(jù)和非循環(huán)依賴(lài)數(shù)據(jù)。在 SP線程預(yù)取機(jī)制中，幫助線程通過(guò)忽略對(duì)部分非循環(huán)依賴(lài)數(shù)據(jù)的預(yù)取控制線程預(yù)取距離和平衡主線程與幫助線程。SP的基本思想：如果在幫助線程與主線程的并行執(zhí)行過(guò)程中，幫助線程的預(yù)取操作能與主線程的訪存操作或計(jì)算操作完全并行地執(zhí)行，互不干擾，且?guī)椭€程預(yù)取的數(shù)據(jù)都恰好被主線程需要，則主線程將獲得最大的性能收益。理論上，當(dāng)幫助線程的執(zhí)行延遲占熱點(diǎn)循環(huán)執(zhí)行總延遲的一半時(shí)，幫助線程與主線程達(dá)到最大程度的并行執(zhí)行，主線程的性能得到最大限度地提高。圖1抽象地說(shuō)明了這種理想狀況下的程序執(zhí)行流程。依據(jù)圖1 （a）所示，源程序熱點(diǎn)循環(huán)的單次循環(huán)延遲為（TFM＋TSM＋TC）。根據(jù)圖1（b），應(yīng)用線程預(yù)取機(jī)制后，通過(guò)合理地設(shè)置A_SKI與A_PRE的值（A_SKI即是預(yù)取距離），幫助線程的性能收益最大化時(shí)主程序熱點(diǎn)循環(huán)的單次循環(huán)延遲減少至原來(lái)的一半，即（TFM＋TSM＋TC）/2。

圖1 理想狀態(tài)下的線程預(yù)取

我們已有的研究結(jié)果表明，可以根據(jù)TFM，TSM和 TC三者間的關(guān)系確定 A_SKI與 A_PRE的關(guān)系。本文的研究工作即是在A_SKI與A_PRE關(guān)系確定的基礎(chǔ)上，通過(guò)分析應(yīng)用程序熱點(diǎn)數(shù)據(jù)的緩存行為特征，確定預(yù)取距離 A_SKI的有效取值范圍并通過(guò)實(shí)驗(yàn)選擇較優(yōu)的預(yù)取距離取值。

圖1中，TFM對(duì)應(yīng)于單次熱點(diǎn)循環(huán)中循環(huán)依賴(lài)數(shù)據(jù)的平均訪存延遲；TSM對(duì)應(yīng)于單次熱點(diǎn)循環(huán)中非循環(huán)依賴(lài)數(shù)據(jù)的平均訪存延遲；TC對(duì)應(yīng)于單次熱點(diǎn)循環(huán)中的平均計(jì)算延遲；A_SKI（預(yù)取距離）指幫助線程在執(zhí)行熱點(diǎn)循環(huán)時(shí)，不預(yù)取非循環(huán)依賴(lài)數(shù)據(jù)時(shí)連續(xù)執(zhí)行的循環(huán)次數(shù)；A_PRE（預(yù)取長(zhǎng)度）指幫助線程在執(zhí)行熱點(diǎn)循環(huán)時(shí)，預(yù)取非循環(huán)依賴(lài)數(shù)據(jù)時(shí)連續(xù)執(zhí)行的熱點(diǎn)循環(huán)次數(shù)。

3 基于緩存行為特征的線程預(yù)取距離控制策略

3.1 緩存行為特征分析

數(shù)據(jù)預(yù)取引發(fā)緩存污染的可能性與應(yīng)用程序的訪存特征及共享緩存的映射機(jī)制密切相關(guān)。對(duì)于片上多處理器中普遍使用的多路組相聯(lián)共享緩存來(lái)說(shuō)，執(zhí)行幫助線程數(shù)據(jù)預(yù)取時(shí)，如果一個(gè)應(yīng)用程序的熱點(diǎn)訪問(wèn)數(shù)據(jù)都集中映射到共享緩存的同一個(gè)緩存組中，則很容易引起緩存污染；反之，如果一個(gè)應(yīng)用程序的熱點(diǎn)循環(huán)訪問(wèn)數(shù)據(jù)極少映射到共享緩存的相同緩存組中，則不容易引起緩存污染。因此，通過(guò)分析應(yīng)用程序熱點(diǎn)數(shù)據(jù)訪問(wèn)流，識(shí)別出當(dāng)映射到同一個(gè)共享緩存組中的緩存行超過(guò)共享緩存的組相聯(lián)度時(shí)的熱點(diǎn)循環(huán)次數(shù)，可以預(yù)測(cè)在執(zhí)行數(shù)據(jù)預(yù)取時(shí)熱點(diǎn)循環(huán)何時(shí)會(huì)發(fā)生緩存污染。

這里把識(shí)別出的此特征定義為熱點(diǎn)循環(huán)對(duì)應(yīng)于共享緩存組的緩存相關(guān)度，并分析此特征與 SP預(yù)取策略中預(yù)取距離 A_SKI取值的關(guān)系。特別地，對(duì)本文中選擇的實(shí)驗(yàn)平臺(tái)Intel Core 2 Quad 6600處理器，其共享緩存的組相聯(lián)度是16。

定義 1 緩存相關(guān)度SA（L, Sx）： 假設(shè)對(duì)于CMP結(jié)構(gòu)中共享緩存（最低級(jí)）的組相聯(lián)度是C, Sx是該共享緩存中的某一個(gè)緩存組，包含C個(gè)緩存塊（B1, B2,…,BC）。對(duì)于訪存密集型程序中的熱點(diǎn)循環(huán)L，其循環(huán)次數(shù)是I。共享緩存采用的是LRU替換算法。假設(shè)在 L執(zhí)行到第 j（j＜I）次循環(huán)時(shí)，恰好 L中有C個(gè)數(shù)據(jù)塊映射到Sx中的C個(gè)緩存塊中。這里定義j為L(zhǎng)對(duì)應(yīng)于Sx的緩存相關(guān)度，記為SA（L,Sx）= j。圖2進(jìn)一步解釋了緩存相關(guān)度的定義。

圖 2 緩存相關(guān)度SA（L, Sx）=j 時(shí)的情況

熱點(diǎn)循環(huán)對(duì)應(yīng)于共享緩存組 Sx的緩存相關(guān)度表明熱點(diǎn)循環(huán)訪問(wèn)數(shù)據(jù)間的緩存相關(guān)性。例如，對(duì)于某個(gè)熱點(diǎn)循環(huán)，其對(duì)應(yīng)于共享緩存中緩存組Sx的緩存相關(guān)度為40，表明在應(yīng)用程序獨(dú)立運(yùn)行時(shí)，當(dāng)熱點(diǎn)循環(huán)執(zhí)行到第40次循環(huán)時(shí)，共享緩存組Sx中的熱點(diǎn)循環(huán)訪問(wèn)數(shù)據(jù)塊已經(jīng)達(dá)到飽和。當(dāng)再有熱點(diǎn)循環(huán)訪問(wèn)數(shù)據(jù)塊到達(dá)此緩存組時(shí)，將要進(jìn)行緩存替換。

定理1 假設(shè)熱點(diǎn)循環(huán)L對(duì)應(yīng)于共享緩存組Sx,SA（L, Sx）=j。應(yīng)用SP預(yù)取機(jī)制后，當(dāng)A_SKI +A_PRE ＞j時(shí)，幫助線程造成共享緩存污染的可能性增大。

證明 設(shè) A_SKI+ A_PRE=R，圖 3（a）說(shuō)明了A_SKI+A_PREj≤時(shí)Sx的數(shù)據(jù)駐入情況。如圖3（a）所示，A_SKI+A_PREj≤時(shí)，在主線程執(zhí)行A_SKI次循環(huán)，同時(shí)幫助線程執(zhí)行A_PRE次循環(huán)后，L的訪問(wèn)數(shù)據(jù)只占據(jù)Sx緩存組中C個(gè)緩存塊的一部分。當(dāng)熱點(diǎn)循環(huán) L的訪問(wèn)數(shù)據(jù)占用了 Sx緩存組中的全部C個(gè)緩存塊時(shí)，主線程早已執(zhí)行過(guò)第R次循環(huán)，此時(shí)幫助線程預(yù)取的數(shù)據(jù)也已被主線程訪問(wèn)過(guò)，因此，除非數(shù)據(jù)被重復(fù)訪問(wèn)，否則，新駐入的數(shù)據(jù)替換掉的都是無(wú)用數(shù)據(jù)，不存在緩存污染。

圖3（b）分析了A_SKI + A_PRE＞j時(shí) Sx的數(shù)據(jù)駐入情況。如圖 3（b）所示，在主線程執(zhí)行 N（N＜A_SKI）次循環(huán)，同時(shí)幫助線程執(zhí)行第 M（A_SKI＜M＜R）次循環(huán)時(shí)，熱點(diǎn)循環(huán)L的訪問(wèn)數(shù)據(jù)已經(jīng)占用了Sx緩存組中全部的C個(gè)緩存塊。所以當(dāng)L繼續(xù)執(zhí)行時(shí)，主線程將執(zhí)行第N+1次循環(huán)，而幫助線程將執(zhí)行第M+1次循環(huán)。此時(shí)主線程或幫助線程新駐入的訪問(wèn)數(shù)據(jù)將替換掉Sx緩存組中存儲(chǔ)的數(shù)據(jù)，如果替換掉的數(shù)據(jù)是幫助線程最近駐入的訪問(wèn)數(shù)據(jù)，因這些數(shù)據(jù)還沒(méi)有被主線程訪問(wèn)，從而造成緩存組Sx被污染。因此，當(dāng)A_SKI+A_PRE＞j時(shí)幫助線程造成共享緩存污染的可能性增大。 證畢

定理2 假設(shè)熱點(diǎn)循環(huán)L對(duì)應(yīng)于共享緩存組Sx,SA（L,Sx）=j。應(yīng)用 SP 預(yù)取機(jī)制時(shí)，當(dāng)預(yù)取距離A_SKI＜j/2時(shí)，幫助線程造成共享緩存污染的可能性比A_SKI ＞j/2小。

圖 3 基于緩存相關(guān)度和預(yù)取距離的緩存污染分析

證明 （1）當(dāng) A_SKI≤ A _PRE時(shí)，因A_SKI≤A_PRE，如果 A_SKI＞j/2，則 A_SKI+A_PRE＞j。根據(jù)圖 3和定理 1的證明過(guò)程，應(yīng)用SP預(yù)取機(jī)制后，A_SKI+A_PRE＞j時(shí)，幫助線程造成共享緩存污染的可能性增大。因此，A_SKI≤ A _PRE時(shí)，預(yù)取距離A_SKI＜j/2時(shí)，幫助線程造成共享緩存污染的可能性比A_SKI ＞j/2小。

（2）當(dāng) A_SKI＞A_PRE 時(shí)，因 A_SKI＞A_PRE，如果 A_SKI ＜j/2，則 A_SKI + A_PRE ＜j。根據(jù)圖3和定理1的證明過(guò)程，應(yīng)用SP預(yù)取機(jī)制后，A_SKI+A_PRE ＜j時(shí)，幫助線程造成共享緩存污染的可能性比A_SKI+A_PRE＞j時(shí)小。因此，A_SKI＞A_PRE時(shí)，預(yù)取距離A_SKI＜j/2時(shí)，幫助線程造成共享緩存污染的可能性比 A_SKI＞j/2小。 證畢

3.2 基于緩存行為特征的預(yù)取距離控制模型

預(yù)取距離的度量方式有多種，例如，預(yù)取指令與對(duì)應(yīng)取數(shù)指令執(zhí)行時(shí)間隔的CPU時(shí)鐘周期數(shù)、分支語(yǔ)句數(shù)、指令數(shù)、緩存失效事件數(shù)等都可以作為預(yù)取距離的度量標(biāo)準(zhǔn)[17]。SP預(yù)取機(jī)制中，幫助線程在每個(gè)循環(huán)中進(jìn)行預(yù)取操作時(shí)都跳過(guò) A_SKI次內(nèi)層循環(huán)，也就意味著幫助線程提前 A_SKI次循環(huán)發(fā)出預(yù)取請(qǐng)求。因此，SP中預(yù)取距離A_SKI就是指從發(fā)出預(yù)取請(qǐng)求到預(yù)取數(shù)據(jù)被使用時(shí)間隔的熱點(diǎn)循環(huán)次數(shù)。

3.2.1 基于緩存相關(guān)度的最大有效預(yù)取距離取值 定理2表明，本文在應(yīng)用SP預(yù)取機(jī)制時(shí)，應(yīng)設(shè)置預(yù)取距離 A_SKI＜SA（L, Sx）/2，即 A_SKI＜j/2，以便減少幫助線程引起的緩存污染。因此，為了減少整個(gè)共享緩存被污染的可能性，SP的預(yù)取距離A_SKI與熱點(diǎn)循環(huán)L對(duì)應(yīng)于共享緩存組Sx的緩存相關(guān)度應(yīng)該具有關(guān)系為

3.2.2 最小有效預(yù)取距離取值 在SP預(yù)取策略中為了保證數(shù)據(jù)預(yù)取的及時(shí)性，可以使用式（2）求得 SP預(yù)取的最小有效預(yù)取距離取值[18]：

這里平均訪存延遲指的是源測(cè)試程序中單次熱點(diǎn)循環(huán)的平均訪存延遲；而平均迭代延遲指的是應(yīng)用SP預(yù)取機(jī)制后，單次熱點(diǎn)循環(huán)的平均執(zhí)行延遲。在SP預(yù)取策略中，根據(jù)圖1，平均訪存延遲=TFM+TSM，理想情況下的平均迭代延遲=（TFM+TSM+TC）/2。則

特別地，當(dāng)TC相比于（TFM+TSM）可以忽略不計(jì)時(shí)，有效預(yù)取距離A_SKI最小為2次熱點(diǎn)循環(huán)；當(dāng)TC大于（TFM+TSM），有效預(yù)取距離A_SKI最小為0次熱點(diǎn)循環(huán)。

式（1）與式（3）為設(shè)置 SP 預(yù)取距離 A_SKI提供了直接依據(jù)。例如，熱點(diǎn)循環(huán)對(duì)應(yīng)于各共享緩存組的緩存相關(guān)度最小為 40，且 TC大于（TFM+TSM），為減少共享緩存污染和提高預(yù)取時(shí)效性，最大預(yù)取距離取值應(yīng)該設(shè)置為20，最小預(yù)取距離為0次熱點(diǎn)循環(huán)，SP預(yù)取距離A_SKI的較優(yōu)取值應(yīng)在0與20之間搜索。

4 實(shí)驗(yàn)結(jié)果與分析

為了得到 A_SKI預(yù)取距離的較優(yōu)取值，先分析應(yīng)用程序熱點(diǎn)循環(huán)對(duì)應(yīng)于共享緩存組的緩存相關(guān)度分布，并在此基礎(chǔ)上預(yù)測(cè) A_SKI預(yù)取的有效預(yù)取距離取值范圍；然后，通過(guò)實(shí)驗(yàn)測(cè)試結(jié)果確定SP對(duì)特定測(cè)試程序的較優(yōu)預(yù)取距離 A_SKI取值；最后，為幾個(gè)非規(guī)則數(shù)據(jù)密集應(yīng)用實(shí)現(xiàn)了 SP預(yù)取機(jī)制和傳統(tǒng)幫助線程數(shù)據(jù)預(yù)取機(jī)制，并通過(guò)對(duì)實(shí)驗(yàn)結(jié)果的比較分析，評(píng)估SP預(yù)取策略的性能和有效性。

4.1 實(shí)驗(yàn)背景

本文采用Intel Core 2 Quad 6600處理器作為實(shí)驗(yàn)平臺(tái)評(píng)估 SP預(yù)取策略對(duì)非規(guī)則數(shù)據(jù)密集應(yīng)用的性能影響。該處理器上有兩個(gè)L2 硬件預(yù)取裝置，ACL與DPL[19]，每個(gè)處理器上的兩個(gè)核動(dòng)態(tài)共享這兩個(gè)硬件預(yù)取裝置。共享緩存的大小為 4 MB，組相聯(lián)度是16。

從基準(zhǔn)測(cè)試程序包SPEC2006和Olden中選擇EM3D, MCF和MST作為測(cè)試對(duì)象。所有的測(cè)試程序都使用GCC 4.3編譯器進(jìn)行編譯，編譯選項(xiàng)為“-O2”。表1中顯示了這些測(cè)試程序的基本信息，包括輸入?yún)?shù)、熱點(diǎn)函數(shù)等信息。為了分析熱點(diǎn)循環(huán)訪問(wèn)數(shù)據(jù)的緩存相關(guān)度，表1中最后一列顯示了各測(cè)試程序的熱點(diǎn)循環(huán)的循環(huán)次數(shù)。如果此項(xiàng)數(shù)據(jù)是個(gè)具體數(shù)值，說(shuō)明對(duì)熱點(diǎn)函數(shù)的每次調(diào)用，外層循環(huán)次數(shù)始終是該數(shù)值。如果此項(xiàng)數(shù)據(jù)是一個(gè)數(shù)值區(qū)間，說(shuō)明對(duì)熱點(diǎn)函數(shù)的不同次調(diào)用，外層循環(huán)次數(shù)在此區(qū)間內(nèi)變化。

表1 熱點(diǎn)循環(huán)的循環(huán)次數(shù)

4.2 基于緩存相關(guān)度的SP有效預(yù)取距離取值結(jié)果

表2是各測(cè)試程序基于緩存相關(guān)度的SP有效預(yù)取距離取值結(jié)果。值得一提的是，本文中各程序的有效預(yù)取距離取值范圍只是一個(gè)比較粗略的界限，旨在為我們選擇較優(yōu)預(yù)取距離取值提供指導(dǎo)作用。

4.3 SP的有效預(yù)取距離取值分析

為了檢測(cè)硬件預(yù)取對(duì)有效預(yù)取距離取值范圍的影響[20]，在兩種硬件預(yù)取配置下測(cè)試EM3D, MCF和MST 3個(gè)測(cè)試程序在預(yù)取距離取值范圍內(nèi)的性能變化。這兩種硬件預(yù)取配置情況描述如下：

PF_ON：指DPL和ACL都是打開(kāi)狀態(tài)。PF_OFF：指DPL和ACL都是關(guān)閉狀態(tài)。

圖4 中顯示的是在PF_ON和PF_OFF兩種配置下，相對(duì)于源程序，SP預(yù)取程序的執(zhí)行時(shí)間、主線程 L2 緩存失效次數(shù)、幫助線程 L2 緩存失效次數(shù)、主線程訪存次數(shù)和幫助線程訪存次數(shù)的規(guī)范化數(shù)值。

比較圖4（a）中PF_ON和PF_OFF兩種配置下的結(jié)果表明，L2硬件預(yù)取對(duì)EM3D的SP預(yù)取程序性能產(chǎn)生了明顯影響，但總的來(lái)說(shuō)，隨著預(yù)取距離的不斷增大，程序性能逐漸降低。這一方面說(shuō)明L2硬件預(yù)取增加了緩存污染的嚴(yán)重性，另一方面說(shuō)明隨著預(yù)取距離的不斷增大，緩存污染的嚴(yán)重性也不斷增加。

表2 SP預(yù)取距離參數(shù)的取值范圍

圖4 預(yù)取距離對(duì)SP預(yù)取的性能影響

圖 4（b）中的結(jié)果顯示，當(dāng)預(yù)取距離參數(shù)取值逐漸變大時(shí)，MCF的SP預(yù)取程序中，除L2 緩存失效次數(shù)外，其它各性能參數(shù)的變化趨勢(shì)均相同。而在PF_OFF配置下，各性能參數(shù)的變化均不明顯。這表明當(dāng)關(guān)閉L2硬件預(yù)取時(shí)，MCF的SP預(yù)取程序性能對(duì)預(yù)取距離的變化不敏感。

圖 4（c）顯示的是，當(dāng)預(yù)取距離參數(shù)取值逐漸變大時(shí)，MST的SP預(yù)取程序性能變化情況。從圖4（c）顯示的結(jié)果可以看出，在PF_ON和PF_OFF兩種配置下，都是在預(yù)取距離為 25時(shí)，MST的 SP預(yù)取程序性能發(fā)生了大的變化；當(dāng)預(yù)取距離小于25時(shí)，各性能參數(shù)有緩慢減少的趨勢(shì)；當(dāng)預(yù)取距離大于30時(shí)，程序的執(zhí)行時(shí)間，主線程的L2 緩存失效次數(shù)和訪存次數(shù)均有逐漸增長(zhǎng)的趨勢(shì)，而幫助線程的 L2 緩存失效次數(shù)和訪存次數(shù)均有逐漸減小的趨勢(shì)。

總之，根據(jù)圖4中的顯示結(jié)果，可以得到如下結(jié)論。首先，程序執(zhí)行時(shí)間總是與其訪存次數(shù)有相同的變化趨勢(shì)，說(shuō)明訪存次數(shù)是衡量程序性能的一個(gè)重要指標(biāo)。其次，程序執(zhí)行時(shí)間與其 L2 緩存失效次數(shù)的變化趨勢(shì)不總是相同，表明 L2 緩存失效次數(shù)不能作為衡量程序性能的唯一指標(biāo)。最后，當(dāng)預(yù)取距離高于預(yù)測(cè)范圍內(nèi)的某一數(shù)值時(shí)，程序的性能開(kāi)始逐漸下降。這說(shuō)明當(dāng)預(yù)取時(shí)效性得到保證后，更大的預(yù)取距離導(dǎo)致更嚴(yán)重的緩存污染。

4.4 SP的性能優(yōu)勢(shì)

為了有效分析傳統(tǒng)線程預(yù)取的局限性，作者實(shí)現(xiàn)了兩種傳統(tǒng)線程預(yù)取技術(shù)。其中，提前式線程預(yù)?。ˋhead Prefetching, AP）是在文獻(xiàn)[6]中所描述的線程預(yù)取技術(shù)的基礎(chǔ)上實(shí)現(xiàn)的。能動(dòng)式線程數(shù)據(jù)預(yù)取方法（Active threaded Prefetching, PV）是在文獻(xiàn)[8]中所描述的線程預(yù)取技術(shù)的基礎(chǔ)上實(shí)現(xiàn)的。

圖5和圖6顯示了AP, PV和SP對(duì)測(cè)試程序的性能影響?？傮w來(lái)看，SP為這幾個(gè)測(cè)試程序平均取得了約13 %的加速比，AP平均取得了約4.4 %的加速比，PV平均取得了約5.3 %的加速比。這說(shuō)明本文提出的 SP預(yù)取策略比傳統(tǒng)幫助線程數(shù)據(jù)預(yù)取方法的平均性能好。尤其值得注意的是，對(duì)于測(cè)試程序MST, SP取得了27.1 %的性能提高，而AP和PV下卻都遭受到近2%的性能降低。圖6中顯示的規(guī)范化 CPI數(shù)值（相對(duì)于源程序）進(jìn)一步說(shuō)明了 SP預(yù)取策略相對(duì)于傳統(tǒng)幫助線程數(shù)據(jù)預(yù)取方法的優(yōu)勢(shì)。因此，實(shí)驗(yàn)結(jié)果表明，通過(guò)該策略控制線程數(shù)據(jù)預(yù)取距離能進(jìn)一步提高線程預(yù)取性能。

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

在 SP線程預(yù)取機(jī)制基礎(chǔ)上，通過(guò)分析應(yīng)用程序熱點(diǎn)循環(huán)執(zhí)行的延遲特征和緩存行為特征評(píng)估有效的 SP預(yù)取距離取值范圍，并在該范圍內(nèi)通過(guò)實(shí)驗(yàn)測(cè)試為特定的非規(guī)則數(shù)據(jù)密集應(yīng)用程序選擇合適的 SP預(yù)取距離。通過(guò)實(shí)驗(yàn)結(jié)果我們可以看出，合適的SP預(yù)取距離取值不僅提高了SP預(yù)取機(jī)制的預(yù)取效率，減小了幫助線程引發(fā)緩存污染的可能性，還減少了系統(tǒng)總線壓力和共享資源競(jìng)爭(zhēng)，進(jìn)而優(yōu)化了SP預(yù)取性能。

圖 5 加速比

圖 6 CPI變化

[1] Chen T F and Baer J L. A performance study of software and hardware data prefetching schemes[C]. Proceedings of 21st International Symposium on Computer Architecture,Chicago, USA, 1994: 223-232.

[2] Saavedra R H and Daeyeon P. Improving the effectiveness of software prefetching with adaptive execution[C]. Proceedings of Conference on Parallel Architectures and Compilation Techniques, Boston, USA, 1996: 68-78.

[3] Hur I and Lin C. Feedback mechanisms for improving probabilistic memory prefetching[C]. Proceedings of 15th International Symposium on High Performance Computer Architecture, North Carolina, USA, 2009: 443-454.

[4] Dongkeun K, Liao S S W, Wang P H, et al.. Physical experimentation with prefetching helper threads on Intel,s hyper-threaded processors[C]. Proceedings of International Symposium on Code Generation and Optimization,California, USA, 2004: 27-38.

[5] Lu J. Design and implementation of a lightweight runtime optimization system on modern computer architectures[D].[Ph.D. dissertation], University of Minnesota, 2006.

[6] Ro W W and Gaudiot J L. Speculative pre-execution assisted by compiler （SPEAR）[J]. Journal of Parallel and Distributed Computing, 2006, 66（8）: 1076-1089.

[7] Somogyi S, Wenisch T F, Ailamaki A, et al.. Spatial-temporal memory streaming[C]. Proceedings of the 36th International Symposium on Computer Architecture, Austin, USA, 2009:69-80.

[8] Lee J, Jung C, Lim D, et al.. Prefetching with helper threads for loosely coupled multiprocessor systems[J]. IEEE Transactions on Parallel and Distributed Systems, 2009,20（9）: 1309-1324.

[9] 單書(shū)暢, 胡瑜, 李曉維. 基于數(shù)據(jù)預(yù)取的多核處理器末級(jí)緩存優(yōu)化方法[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2012, 24（9）:1241-1248.Shan Shu-chang, Hu Yu, and Li Xiao-wei. Date prefetching based last-level cache optimization for chip multiprocessors[J]. Journal of Computer-Aided Design & Computer Graphics,2012, 24（9）: 1241-1248.

[10] 張建勛, 古志民, 胡瀟涵, 等. 面向非規(guī)則大數(shù)據(jù)分析應(yīng)用的多核幫助線程預(yù)取方法[J]. 通信學(xué)報(bào), 2014, 35（8）: 137-146.Zhang Jian-xun, Gu Zhi-min, Hu Xiao-han, et al.. Multi-core helper thread prefetching forirregular data intensive applications[J]. Journal on Communications, 2014, 35（8）:137-146.

[11] Marin G, McCurdy C, and Vetter J S. Diagnosis and optimization of application prefetching performance[C].Proceedings of the 27th International ACM Conference on International Conference on Supercomputing, Oregon, USA,2013: 303-312.

[12] Garside J and Audsley N C. Prefetching across a shared memory tree within a network-on-chip architecture[C].Proceedings of 15th International Symposium on System-on-Chip, Melbourne, Australia, 2013: 1-4.

[13] Jain A and Lin C. Linearizing irregular memory accesses for improved correlated prefetching[C]. Proceedings of the 46th IEEE/ACM International Symposium on Microarchitecture（MICRO）, Davis, USA, 2013: 247-259.

[14] Zhao Y, Yoshigoe K J, and Xie M J. Pre-execution data prefetching with I/O scheduling[J]. The Journal of Supercomputing, 2014, 68（2）: 733-752.

[15] 巫旭敏, 殷保群, 黃靜, 等. 流媒體服務(wù)系統(tǒng)中一種基于數(shù)據(jù)預(yù)取的緩存策略[J]. 電子與信息學(xué)報(bào), 2010, 32（10）:2440-2445.Wu Xu-min, Yin Bao-qun, Huang Jing, et al.. A prefetchingbased caching policy in streaming service systems[J]. Journal of Electronics & Information Technology, 2010, 32（10）:2440-2445.

[16] 劉斌, 趙銀亮, 韓博, 等. 基于性能預(yù)測(cè)的推測(cè)多線程循環(huán)選擇方法[J]. 電子與信息學(xué)報(bào), 2014, 36（11）: 2768-2774.Liu Bin, Zhao Yin-liang, Han Bo, et al.. A loop selection approach based on performance prediction for speculative multithreading[J]. Journal of Electronics & Information Technology, 2014, 36（11）: 2768-2774.

[17] Emma P G, Hartstein A, Puzak T R, et al.. Exploring the limits of prefetching[J]. IBM Journal of Research and Development, 2005, 49（1）: 127-144.

[18] Srinath S, Mutlu O, Hyesoon K, et al.. Feedback directed prefetching: improving the performance and bandwidthefficiency of hardware prefetchers[C]. Proceedings of the IEEE 13th International Symposium on High Performance Computer Architecture, Arizona, USA, 2007: 63-74.

[19] Doweck J. White paper: inside intel core microarchitecture and smart memory access[R]. Intel Corporation, 2006.

[20] Hui K and Jennifer L W. To hardware prefetch or not to prefetch?: a virtualized environment study and core binding approach[C]. Proceedings the 8th International Conference on Architectural Support For Programming Languages And Operating Systems, Houston, USA, 2013: 357-368.