巨濤,張興軍,陳衡,董小社

(西安交通大學(xué)電子與信息工程學(xué)院,710049,西安)

?

面向眾核系統(tǒng)的線程分組映射方法

巨濤,張興軍,陳衡,董小社

(西安交通大學(xué)電子與信息工程學(xué)院,710049,西安)

為了使應(yīng)用線程更合理地映射到眾核處理器具體處理核上,提出一種利用不同線程內(nèi)部數(shù)據(jù)局部性及不同線程間數(shù)據(jù)相關(guān)性的特點、結(jié)合具體硬件架構(gòu)特征的線程分組映射方法。通過計算數(shù)據(jù)重用距離,分析應(yīng)用程序線程內(nèi)部數(shù)據(jù)局部性,用線程相關(guān)性矩陣度量不同線程間的數(shù)據(jù)相關(guān)性;根據(jù)應(yīng)用程序數(shù)據(jù)相關(guān)性及眾核處理器硬件架構(gòu)特點,通過設(shè)計數(shù)據(jù)相關(guān)性子樹生成算法,將應(yīng)用線程分為能反映不同線程數(shù)據(jù)訪問特點的邏輯組;在線程邏輯分組的基礎(chǔ)上,通過線程到處理核的綁定實現(xiàn)線程到具體處理器不同處理核硬件線程的合理映射。實驗結(jié)果表明:與傳統(tǒng)映射方法相比,該線程分組映射方法在不產(chǎn)生額外運行時開銷的基礎(chǔ)上,計算性能平均提高了14%,能耗降低了12%。該方法可以根據(jù)應(yīng)用程序不同線程之間的數(shù)據(jù)相關(guān)性,將不同線程合理映射到具體眾核處理器不同處理核上,在不引入額外運行時開銷的基礎(chǔ)上,提升眾核系統(tǒng)的計算效能。

眾核系統(tǒng);線程映射;數(shù)據(jù)相關(guān)性;數(shù)據(jù)重用距離;線程邏輯分組

如何在充分利用眾核處理器高計算能力的同時降低系統(tǒng)能耗是眾核系統(tǒng)面臨的關(guān)鍵問題[1]。隨著多核/眾核技術(shù)的發(fā)展,眾核處理器片內(nèi)集成的處理器核數(shù)越來越多,進(jìn)一步加劇了多個處理核對片上共享計算資源(例如共享緩存和共享帶寬)的爭用。在程序運行過程中,如果將具有頻繁信息交互的線程分配到不同處理核的硬件線程之上,會引入較高的存儲訪問延遲,造成高的數(shù)據(jù)傳輸開銷;如果將無數(shù)據(jù)相關(guān)性的多個線程分配到同一個處理核上,會因不同線程訪問不同數(shù)據(jù),導(dǎo)致共享緩存數(shù)據(jù)的頻繁換入換出,造成高的共享存儲訪問沖突,增加額外傳輸開銷。只有將應(yīng)用程序數(shù)據(jù)局部性和處理器存儲架構(gòu)有效結(jié)合起來,實現(xiàn)應(yīng)用程序到處理核的合理映射,才能降低不同線程之間的共享存儲訪問沖突、減少額外傳輸開銷,提高計算資源利用率,提升應(yīng)用程序的計算性能,降低異構(gòu)系統(tǒng)整體能耗[2]。

已有的根據(jù)程序局部性特點進(jìn)行任務(wù)分配的研究工作[3-5],通過對程序數(shù)據(jù)及存儲訪問相關(guān)性進(jìn)行剖分、離線分析,然后劃分任務(wù),不考慮運行平臺物理架構(gòu)特點,直接將線程映射到處理核上,不能客觀反映不同線程在具體運行平臺上運行時的數(shù)據(jù)相關(guān)性特點。文獻(xiàn)[6-9]根據(jù)程序運行時局部性特點進(jìn)行動態(tài)遷移后實現(xiàn)線程到處理核的映射,但是動態(tài)剖分程序局部性及動態(tài)遷移線程都會引入較高的額外運行時開銷,有的還需特定的硬件支持[8],限制了其通用性。在處理核數(shù)眾多且存儲結(jié)構(gòu)復(fù)雜的眾核系統(tǒng)上,由于同時要考慮計算性能和系統(tǒng)的整體能耗,以上線程映射方法不能滿足眾核系統(tǒng)高效能的計算需求。

本文針對以上問題,通過設(shè)計不同線程數(shù)據(jù)重用距離(data reuse distance,DRD)[4]計算方法,分析不同線程間的數(shù)據(jù)相關(guān)性。在程序運行前,結(jié)合程序本身固有的數(shù)據(jù)相關(guān)性和眾核系統(tǒng)硬件架構(gòu)特征,對程序線程進(jìn)行邏輯分組。之后將不同線程組映射到不同處理核上,使程序數(shù)據(jù)局部性和運行平臺架構(gòu)特點較好匹配,盡量最大化核內(nèi)數(shù)據(jù)共享,最小化核間數(shù)據(jù)交互,減少因存儲訪問延遲及共享存儲沖突造成的過高額外存儲訪問及通信開銷,在充分利用處理核計算資源的同時盡量降低系統(tǒng)能耗。

1 線程分組映射總體框架

首先根據(jù)運行平臺所支持的最大硬件線程數(shù),將應(yīng)用程序劃分為相應(yīng)數(shù)量的應(yīng)用線程。通過設(shè)計線程內(nèi)數(shù)據(jù)局部性檢測機(jī)制,剖分不同線程的存儲訪問數(shù)據(jù),計算線程數(shù)據(jù)重用距離。根據(jù)數(shù)據(jù)重用距離信息,通過設(shè)計數(shù)據(jù)相關(guān)性判定方法,分析線程內(nèi)部數(shù)據(jù)局部性及不同線程間的數(shù)據(jù)相關(guān)性。具體采用模式分類的方法將不同的線程歸并為不同的局部性模式,根據(jù)線程不同的局部性模式,用相關(guān)性矩陣度量不同線程間的數(shù)據(jù)相關(guān)性。最后通過設(shè)計相關(guān)性子樹生成算法,在相關(guān)性矩陣及相關(guān)性圖的基礎(chǔ)上,對應(yīng)用線程進(jìn)行邏輯分組,并結(jié)合眾核系統(tǒng)硬件架構(gòu)特征,將不同線程分配到能使程序局部性和硬件架構(gòu)特點較好匹配的處理核上,實現(xiàn)計算任務(wù)到處理核的合理映射。總體實現(xiàn)框架如圖1所示。

圖1 線程分組映射框架

2 程序數(shù)據(jù)局部性檢測

通過剖分統(tǒng)計各個線程的訪問數(shù)據(jù),設(shè)計數(shù)據(jù)重用距離計算方法,分析不同線程內(nèi)和線程間數(shù)據(jù)局部性。采用并行方式剖分線程的數(shù)據(jù)存儲訪問信息,并行計算不同線程的數(shù)據(jù)重用距離。具體參考文獻(xiàn)[10-12]中的方法,使用Intel Pin API編寫Pin工具,并行統(tǒng)計每個線程的存儲訪問數(shù)據(jù)、計算線程內(nèi)每個數(shù)據(jù)的重用距離,根據(jù)線程內(nèi)不同數(shù)據(jù)重用距離信息,計算反映整個線程數(shù)據(jù)局部性的平均數(shù)據(jù)重用距離。

2.1 訪問數(shù)據(jù)統(tǒng)計

采用在平衡二叉樹中插入結(jié)點的方式統(tǒng)計訪問數(shù)據(jù)。二叉樹每個結(jié)點用一個結(jié)構(gòu)體表示N(T;E;F;W;R)。每個數(shù)據(jù)項存儲以下信息:T為時間戳,記錄數(shù)據(jù)被訪問的次序;E記錄所訪問的數(shù)據(jù)元素;F記錄數(shù)據(jù)被訪問的次數(shù);W為權(quán)重,記錄當(dāng)前結(jié)點所包含的子結(jié)點數(shù);R為數(shù)據(jù)重用距離。

數(shù)據(jù)重用信息統(tǒng)計算法包含掃描訪問數(shù)據(jù)、數(shù)據(jù)結(jié)點的插入、原數(shù)據(jù)結(jié)點刪除、數(shù)據(jù)重用度的統(tǒng)計、數(shù)據(jù)重用距離計算5個過程,具體算法如下。

步驟1 定義結(jié)點數(shù)據(jù)結(jié)構(gòu)N(T;E;F;W;R)及空二叉樹。

步驟2 調(diào)用Pin工具并行掃描不同線程所訪問的數(shù)據(jù)變量,記錄掃描到的數(shù)據(jù)時間戳ti以及數(shù)據(jù)變量di。

步驟3 給待插入結(jié)點數(shù)據(jù)項賦初值:T=ti;E=di;F=1;W=1;R=∞。

步驟4 中序遍歷當(dāng)前二叉樹,判斷待插入數(shù)據(jù)是否包含在樹中已有結(jié)點中,若待插入結(jié)點數(shù)據(jù)包含在二叉樹中,則:①調(diào)用數(shù)據(jù)重用距離計算函數(shù)(見2.2節(jié)),計算當(dāng)前數(shù)據(jù)重用距離R;②統(tǒng)計待插入結(jié)點數(shù)據(jù)重用頻度F及權(quán)重W;③刪除當(dāng)前二叉樹中查找的已有數(shù)據(jù)結(jié)點;④調(diào)整平衡二叉樹,將待插入結(jié)點插入到當(dāng)前平衡二叉樹中。

步驟5 若待插入結(jié)點數(shù)據(jù)沒包含在二叉樹中,則直接將待插入結(jié)點插入到當(dāng)前平衡二叉樹中。

步驟6 重復(fù)步驟2～5直到掃描完線程的所有訪問數(shù)據(jù),最后生成在結(jié)點中包含線程所有不同訪問數(shù)據(jù)信息的平衡二叉樹。

步驟7 將樹中重用距離為無窮大的結(jié)點的重用距離統(tǒng)一調(diào)整為樹中總的結(jié)點個數(shù)M(即樹中根結(jié)點數(shù)據(jù)項W的值),表示當(dāng)前最大的重用距離。

步驟8 完成數(shù)據(jù)重用信息的統(tǒng)計。

2.2 數(shù)據(jù)重用距離計算

數(shù)據(jù)重用距離統(tǒng)計了相同訪問數(shù)據(jù)最近兩次訪問間隔內(nèi)不同訪問數(shù)據(jù)的個數(shù),是一個能較好反映應(yīng)用程序數(shù)據(jù)局部性的指標(biāo)[3-4],本文通過設(shè)計數(shù)據(jù)重用距離計算方法,同時將其封裝為獨立的函數(shù),在統(tǒng)計訪問數(shù)據(jù)信息時直接調(diào)用。具體計算數(shù)據(jù)重用距離算法實現(xiàn)過程如下。

步驟1 在當(dāng)前樹中查找包含待插入數(shù)據(jù)的結(jié)點,若無,則該數(shù)據(jù)為首次訪問,重用距離設(shè)置為無窮大。

步驟2 如果找到包含要插入數(shù)據(jù)的結(jié)點,則:①若查到的目標(biāo)結(jié)點時間戳小于根結(jié)點時間戳,則該結(jié)點為根結(jié)點左子樹結(jié)點,根結(jié)點右子樹結(jié)點數(shù)加上其子樹中時間戳大于目標(biāo)結(jié)點時間戳的所有結(jié)點數(shù)即為待插入結(jié)點的數(shù)據(jù)重用距離;②若查到的目標(biāo)結(jié)點時間戳大于根結(jié)點時間戳,則目標(biāo)結(jié)點根結(jié)點右子樹中,時間戳大于目標(biāo)結(jié)點時間戳的結(jié)點數(shù)r即為待插入結(jié)點數(shù)據(jù)重用距離。

步驟3 比較計算出的待插入結(jié)點數(shù)據(jù)重用距離和當(dāng)前查找到的目標(biāo)結(jié)點數(shù)據(jù)重用距離,將兩者中較小值作為待插入結(jié)點最終的數(shù)據(jù)重用距離R。

步驟4 根結(jié)點左子樹(或右子樹)中,時間戳大于目標(biāo)結(jié)點時間戳的數(shù)據(jù)結(jié)點數(shù)計算方法如下:①賦初值為0;②將當(dāng)前包含目標(biāo)結(jié)點的右子結(jié)點的W值賦給r,并將目標(biāo)結(jié)點作為當(dāng)前結(jié)點;③回溯到當(dāng)前結(jié)點父結(jié)點;④如果當(dāng)前父結(jié)點不為根結(jié)點且其時間戳大于目標(biāo)結(jié)點時間戳,則將當(dāng)前父結(jié)點的W值和其左子結(jié)點的W值相減后加到r中,將當(dāng)前結(jié)點父結(jié)點作為當(dāng)前結(jié)點,轉(zhuǎn)到步驟3繼續(xù)執(zhí)行;⑤如果當(dāng)前父結(jié)點時間戳小于目標(biāo)結(jié)點時間戳,則將當(dāng)前父結(jié)點作為當(dāng)前結(jié)點,直接轉(zhuǎn)到步驟3繼續(xù)執(zhí)行;⑥如果當(dāng)前父結(jié)點為根結(jié)點,則計算完成,當(dāng)前r值即為根結(jié)點左子樹(或右子樹)中時間戳大于當(dāng)前結(jié)點時間戳的結(jié)點數(shù)。

2.3 線程平均數(shù)據(jù)重用距離計算

通過遍歷生成的每個線程對應(yīng)二叉樹,計算反映每個線程內(nèi)數(shù)據(jù)局部性的平均數(shù)據(jù)重用距離。設(shè)線程總數(shù)為K,每個線程的平均數(shù)據(jù)重用距離為Rj(j=1,2,…,K),線程內(nèi)每個數(shù)據(jù)的重用距離為ri,線程訪問的不同數(shù)據(jù)總數(shù)為M(平衡二叉樹結(jié)點數(shù)),則線程平均數(shù)據(jù)重用距離為

(1)

3 數(shù)據(jù)相關(guān)性判定

3.1 線程內(nèi)數(shù)據(jù)局部性模式

根據(jù)數(shù)據(jù)存儲訪問特點,設(shè)置數(shù)據(jù)重用距離閾值Dmin及Dmax,以重用距離閾值為基準(zhǔn),將數(shù)據(jù)重用距離劃分為3個不同的區(qū)間,每個區(qū)間對應(yīng)一種局部性模式。局部性模式定義如下:數(shù)據(jù)共享模式(data sharing pattern,DSP),RjDmax,該模式下線程所訪問數(shù)據(jù)的時間局部性差,數(shù)據(jù)之間相互獨立,無數(shù)據(jù)相關(guān)性;數(shù)據(jù)依賴模式(data dependency pattern,DDP),Dmin≤Rj≤Dmax,該模式下線程所訪問數(shù)據(jù)有一定的時間局部性,數(shù)據(jù)之間存在數(shù)據(jù)依賴關(guān)系,有一定的數(shù)據(jù)相關(guān)性。

數(shù)據(jù)重用距離閾值的選取對算法性能有重要的影響。如果閾值Dmin選取得太小,會將一些有一定數(shù)據(jù)相關(guān)性的線程排除在DSP模式類之外,反之,則會將一些沒有較好數(shù)據(jù)相關(guān)性的線程包含在DSP模式類中。同理,對閾值Dmax的選取同樣存在使線程局部性模式分類不準(zhǔn)確的問題。本文數(shù)據(jù)重用距離閾值Dmin和Dmax是通過多次實驗測試比較后獲得的。通過對不同基準(zhǔn)測試程序進(jìn)行測試,計算出各個程序的數(shù)據(jù)局部性信息,分析不同程序數(shù)據(jù)局部性特性和數(shù)據(jù)重用距離的關(guān)系,比較所測得的具有較強(qiáng)數(shù)據(jù)共享性程序的數(shù)據(jù)重用距離,將其中最大的數(shù)據(jù)重用距離作為閾值Dmin;比較具有相互獨立訪存關(guān)系程序的數(shù)據(jù)重用距離,將其中最小的數(shù)據(jù)重用距離作為閾值Dmax。本文實驗中Dmin和Dmax分別為每個測試時間間隔內(nèi)數(shù)據(jù)訪問量的50%和85%。

3.2 線程間數(shù)據(jù)相關(guān)性度量

分析出各個線程數(shù)據(jù)局部性模式后,將不同線程歸并為不同的模式類,再分析不同模式類內(nèi)不同線程間的數(shù)據(jù)相關(guān)性。通過比較同一個模式類內(nèi)不同線程間所訪問的相同數(shù)據(jù)個數(shù),并記入線程相關(guān)性矩陣中,最后通過相關(guān)性矩陣來度量線程間的數(shù)據(jù)相關(guān)性。線程相關(guān)性矩陣反映了不同線程間的數(shù)據(jù)共享特性,矩陣的行標(biāo)和列標(biāo)分別代表不同的線程ID,矩陣中的每個元素值代表對應(yīng)行列所指線程間的數(shù)據(jù)共享量,矩陣元素值越大,表明對應(yīng)線程之間數(shù)據(jù)共享性越好,線程間的相關(guān)性越強(qiáng)。計算出線程相關(guān)性矩陣后再將該矩陣轉(zhuǎn)換成能直觀反映線程間數(shù)據(jù)相關(guān)性的相關(guān)性圖。相關(guān)性圖是一個頂點代表不同線程ID、邊代表對應(yīng)兩線程間的數(shù)據(jù)共享量的無向圖。

4 基于數(shù)據(jù)相關(guān)性的線程分組映射

本文基于數(shù)據(jù)相關(guān)性的線程分組映射方法DagTM(data affinity grouping based thread mapping),以反映不同線程存儲訪問特性的數(shù)據(jù)相關(guān)性為基礎(chǔ),結(jié)合眾核處理器存儲層次特點,分兩步實現(xiàn)應(yīng)用線程到處理核的靜態(tài)映射。第一步,應(yīng)用線程的邏輯分組。根據(jù)計算出的線程相關(guān)性圖,結(jié)合眾核處理器處理核所能同時支持的最大硬件線程數(shù),將線程邏輯分組問題抽象成一個圖的分解問題,即將線程相關(guān)性圖分解為K棵子樹。具體通過設(shè)計相關(guān)性子樹生成算法實現(xiàn)線程的邏輯分組。第二步,在線程邏輯分組的基礎(chǔ)上,結(jié)合眾核處理器架構(gòu)特點實現(xiàn)線程組內(nèi)應(yīng)用線程到眾核處理器不同處理核不同硬件線程的映射。

4.1 相關(guān)性子樹生成算法

(1)設(shè)G=(V,E)是一個無向連通的加權(quán)圖,其中頂點V表示不同線程的集合,邊E代表線程間的數(shù)據(jù)相關(guān)性的集合。圖中每條邊(Ti,Tj)∈E,且都有一個權(quán)值ω(Ti,Tj),表示兩線程間的共享數(shù)據(jù)量,如圖2a所示。圖G的總頂點數(shù)為Nt,表示總的線程數(shù);Np表示生成的每棵子樹所要包含的節(jié)點數(shù);K表示最終生成的子樹個數(shù)。

(2)從圖G上生成K棵子樹,每棵子樹用Sk(k=1,2,…,K)表示。生成的每棵子樹最多包含Np個節(jié)點,同時保證當(dāng)前生成的每棵子樹邊的權(quán)值之和最大,即滿足如下約束條件

(2)

(3)

(3)通過借鑒Prim最小生成樹算法,從無向連通圖中生成滿足上述約束條件的K棵子樹。具體算法如下。

輸入 一個加權(quán)無向連通圖G=(V,E),其中頂點集合為V,邊集合為E。子樹中所包含的最大頂點數(shù)為Np。

步驟1 查找圖G中最大權(quán)值的邊,將該邊及相應(yīng)的頂點加入到當(dāng)前子樹集合中。

步驟2 以最大權(quán)值邊為基礎(chǔ),搜索連接該邊頂點其他邊中權(quán)值最大的作為當(dāng)前要生成子樹的邊,并將該邊及對應(yīng)頂點加入到當(dāng)前子樹集合中。

步驟3 判斷當(dāng)前子樹包含的頂點個數(shù)Nk:①如果Nk

步驟4 在圖G剩余頂點構(gòu)成的邊集中查找當(dāng)前權(quán)值最大的邊,之后轉(zhuǎn)到步驟2繼續(xù)執(zhí)行,如圖2e所示。

步驟5 如果圖G中剩余頂點構(gòu)成的邊集為空,則整個子樹生成過程結(jié)束,如圖2g所示。

輸出 生成不同子樹的Sk,如圖2h所示。

圖2a～圖2h示意了圖中包含的8個線程通過上面的相關(guān)性子樹生成算法,在處理器所支持的最大4個硬件線程的情況下,被劃分成兩個線程組的整個過程。圖中相同背景條紋的結(jié)點表示同一個線程組。

4.2 線程組到處理核的映射規(guī)則

借鑒文獻(xiàn)[5]中的映射算法,通過線程到處理核的靜態(tài)綁定實現(xiàn)映射,具體映射規(guī)則如下。

規(guī)則1 將同一線程組中的應(yīng)用線程盡量分配到同一個處理核的不同硬件線程上。如果該處理核線程已經(jīng)全部分配,則將應(yīng)用線程分配到相鄰處理核的硬件線程上。

(a)初始Affinity圖 (b) 查找最大邊 (c) 查找邊 (T1,T7) (T7,T3)

(d) 查找邊 (e) 分解出子樹S1 (f) 查找邊(T2,T4)和 (T3,T6) (T4,T5)

規(guī)則2 將不同線程組中的應(yīng)用線程分配到不同處理核的硬件線程上,使無共享數(shù)據(jù)的線程分散到具有獨立緩存空間的不同處理核上。

(g)查找邊(T2,T5) (h)完成兩棵子樹分解圖2 相關(guān)性圖的子樹生成過程

4.3 線程分組映射實現(xiàn)

線程分組映射實現(xiàn)分為線程內(nèi)數(shù)據(jù)局部性檢測、線程間數(shù)據(jù)相關(guān)性度量、線程邏輯分組、線程組到處理核映射及執(zhí)行4個部分。為說明具體的線程映射過程,用一個8線程并行應(yīng)用程序到Intel MIC眾核處理器(具體存儲架構(gòu)如圖3所示,圖中Pi和Ti分別表示不同的處理單元和線程)上的映射為例,比較傳統(tǒng)OpenMP運行時的線程映射方法和本文DagTM方法的映射結(jié)果。圖4比較了傳統(tǒng)的OpenMP支持的Compact、Scatter映射方法和本文DagTM方法不同的映射結(jié)果。圖4a中因Compact只考慮充分利用處理核資源,不考慮線程間的數(shù)據(jù)相關(guān)性,具有高共享量的線程T1、T3、T6、T7被分派到兩個不同的處理核上,因要分別在兩個處理核的片內(nèi)緩存上存儲相同共享數(shù)據(jù),增加了額外的數(shù)據(jù)存儲開銷。圖4b中Scatter方式主要考慮負(fù)載平衡,將所有線程均勻地分布在不同的處理核上,會引入過高的額外數(shù)據(jù)存儲訪問,同時還存在處理核不能充分利用、系統(tǒng)能耗過高的問題。圖4c中DagTM同時考慮不同線程之間的數(shù)據(jù)局部性和運行平臺架構(gòu)特點,減少了額外數(shù)據(jù)訪問及數(shù)據(jù)傳輸,在映射時充分利用處理核資源,以提高每個處理核的資源利用率,降低系統(tǒng)的整體能耗。

圖3 MIC處理器存儲層次圖

(a)OpenMP內(nèi)置的Compact映射模式

(b)OpenMP內(nèi)置的Scatter映射模式

(c)DagTM映射方法圖4 不同線程到處理核硬件線程映射方式比較

5 實驗評測及結(jié)果分析

5.1 測試平臺及方法

采用PARSEC[14]基準(zhǔn)測試集中的測試程序Blackscholes、Ferret、Streamcluster、Raytrace、Bodytrack、Cannel、X264和Dedup,用native輸入集。實驗平臺由2路8核E5-2670 CPU和1塊Xeon Phi 7110P MIC卡構(gòu)成眾核系統(tǒng),使用Red Hat Enterprise Linux Server release 6.3操作系統(tǒng),Intel parallel_studio_xe_2013_update3_intel64 MIC集成開發(fā)編譯環(huán)境。通過PAPI_5.4.1[15-16]性能測試工具獲取性能指標(biāo)。分別對本文線程映射方法DagTm方法,OpenMP支持的Compact、Scatter方法,以及理想情況下最優(yōu)的映射方法Oracle從計算性能、能耗及額外開銷3方面進(jìn)行測試對比。

5.2 計算性能測試

圖5顯示了DagTM及其他3種映射方法相對于OS默認(rèn)映射方法first-touch policy的基準(zhǔn)測試程序計算時間相對減少率。DagTM平均計算性能提升了近14%,Oracle計算性能提升了16%,Compact、Scatter映射方法計算性能分別提升了2%、3%。DagTM計算性能達(dá)到了Oracle映射的81.3%,優(yōu)于其他兩種映射方法。Compact和Scatter在所有測試程序下性能提升都低于DagTM,Blackscholes、X264、Dedup等實例作為測試程序時甚至低于OS默認(rèn)的映射方法,主要原因是Compact和Scatter沒有考慮不同線程之間的數(shù)據(jù)相關(guān)性,會引起不同線程之間共享存儲訪問沖突及額外的數(shù)據(jù)傳輸開銷。

圖5 4種映射方法相對于OS默認(rèn)映射方法的性能提升

5.3 能耗測試

能耗也是眾核系統(tǒng)考慮的主要問題,一方面通過充分利用計算資源、減少額外的數(shù)據(jù)傳輸來降低能耗;另一方面可通過DVFS技術(shù)動態(tài)調(diào)整處理核的工作狀態(tài),采用物理的方法來降低能耗。本文主要通過充分利用計算資源、減少計算時間來相對降低系統(tǒng)能耗。如圖6所示,DagTM方法平均能耗相對于OS默認(rèn)方法降低了12.6%,Compact、Scatter方法相對能耗分別降低了3.8%、2.4%,最優(yōu)映射方法Oracle的相對能耗降低了15%。由于DagTM方法在線程映射時考慮了數(shù)據(jù)相關(guān)性,可以減少數(shù)據(jù)訪問沖突,提高共享資源利用率,降低數(shù)據(jù)傳輸開銷,減少程序的運行時間,相應(yīng)地減少了系統(tǒng)的整體能耗。

圖6 不同映射方法相對于OS默認(rèn)映射方法的 能耗降低比例

5.4 額外開銷測試

DagTM映射方法由于要在程序執(zhí)行之前進(jìn)行重用距離的度量及線程分組等預(yù)處理,會引入一定的額外預(yù)處理開銷,但在程序執(zhí)行過程中不會引入額外的運行時開銷。圖7顯示了DagTM方法預(yù)處理所用時間占整個程序運行時間比例,作為衡量額外開銷的指標(biāo)。平均引入的額外預(yù)處理時間占總執(zhí)行時間的11%。在線程所訪問數(shù)據(jù)時間局部性差的情況下,因DagTM映射方法不會引入額外的運行時開銷,所以計算性能和系統(tǒng)默認(rèn)的映射方法相當(dāng)。

圖7 DagTM額外開銷

6 結(jié) 論

本文針對眾核系統(tǒng)下線程到處理核的映射問題,通過計算數(shù)據(jù)重用距離來判定線程內(nèi)部的數(shù)據(jù)局部性;用數(shù)據(jù)相關(guān)性矩陣度量線程間的數(shù)據(jù)相關(guān)性;根據(jù)線程相關(guān)性圖,利用最小生成樹實現(xiàn)不同線程的邏輯分組;最后通過線程組到處理核的綁定實現(xiàn)線程到處理核的映射。實驗評測表明,本文線程分組映射方法在提升計算性能和降低能耗方面是有效的,可以根據(jù)應(yīng)用程序不同線程之間的數(shù)據(jù)相關(guān)性,將不同線程合理映射到具體眾核處理器不同處理核上,在不引入額外運行時開銷的基礎(chǔ)上,提高系統(tǒng)的計算性能,降低系統(tǒng)的整體能耗。

[1] BRODTKORB A R, DYKEN C, HAGEN T R, et al. State-of-the-art in heterogeneous computing [J]. Scientific Programming, 2010, 18(1): 1-33.

[2] 巨濤, 朱正東, 董小社. 異構(gòu)眾核系統(tǒng)及其編程模型與性能優(yōu)化技術(shù)研究綜述 [J]. 電子學(xué)報, 2015, 43(1): 111-119. JU Tao, ZHU Zhendong, DONG Xiaoshe. The feature, programming model and performance optimization strategy of heterogeneous many-core system: a review [J]. Chinese Journal of Electronics, 2015, 43(1): 111-119.

[3] ZHANG Yuanrui, KANDEMIR M, YEMLIHA T. Studying inter-core data reuse in multicores [J]. ACM Sigmetrics Performance Evaluation Review, 2011, 39(1): 25-36.

[4] WU Mengju, YEUNG D. Efficient reuse distance analysis of multicore scaling for loop-based parallel programs [J]. ACM Transactions on Computer Systems, 2013, 31(1): 1-37.

[5] MURALIDHARA S P, KANDEMIR M, KISLAL O. Reuse distance based performance modeling and workload mapping [C]∥Proceedings of the 9th Conference on Computing Frontiers. New York, USA: ACM, 2012: 193-202.

[6] MATTHIAS D, EDUARDO H M C, PHILIPPE O A, et al. kMAF: automatic kernel-level management of thread and data affinity [C]∥Proceedings of the 23rd International Conference on Parallel Architectures and Compilation Techniques. New York, USA: ACM, 2014: 277-288.

[7] DING Wei, KANDEMIR M, YEDLAPALLI P, et al. Locality-aware mapping and scheduling for multicores [C]∥Proceedings of the International Symposium on Code Generation and Optimization. Piscataway, NJ, USA: IEEE, 2013: 1-12.

[8] EDUARDO H M, MATTHIAS D, MARCO A Z, et al. Dynamic thread mapping of shared memory applications by exploiting cache coherence protocols [J]. Journal of Parallel and Distributed Computing, 2014, 74(3): 2215-2228.

[9] XIANG Xiaoya, DING Chen, LUO Hao, et al. HOTL: a higher order theory of locality [C]∥Proceedings of the 18th International Conference on Architectural Support for Programming Languages and Operating Systems. New York, USA: ACM, 2013: 343-356.

[10]BACH M, CHARNEY M, COHN R, et al. Analyzing parallel programs with pin [J]. IEEE Computer, 2010, 43(3): 34-41.

[11]DEREK L, MILIND K, VIJAY S P. Accelerating multicore reuse distance analysis with sampling and parallelization [C]∥Proceedings of the 19th International Conference on Parallel Architectures and Compilation Techniques. New York, USA: ACM, 2010: 53-64.

[12]NIU Qingpeng, DINAN J, LU Qinda, et al. PARDA: a fast parallel reuse distance analysis algorithm [C]∥Proceedings of the IEEE 26th International Parallel and Distributed Processing Symposium. Piscataway, NJ, USA: IEEE, 2012: 1284-1294.

[13]張保, 曹海軍, 董小社, 等. 面向圖形處理器重疊通信與計算的數(shù)據(jù)劃分方法 [J]. 西安交通大學(xué)學(xué)報, 2011, 45(4): 1-5. ZHANG Bao, CAO Haijun, DONG Xiaoshe, et al. Novel GPU data partitioning method to overlap communication and computation [J]. Journal of Xi’an Jiaotong University, 2011, 45(4): 1-5.

[14]BIENIA C, KUMAR S, SINGH J P, et al. The PARSEC benchmark suite: characterization and architectural implications [C]∥Proceedings of the 17th International Conference on Parallel Architectures and Compilation Techniques. New York, USA: ACM, 2008: 72-81.

[15]DAN T, JAGODE H, YOU H, et al. Collecting performance data with PAPI-C [J]. Tools for High Performance Computing. Berlin, Germany: Springer Verlag, 2009: 157-173.

[16]WEAVER V M, JOHNSON M, KASICHAYANULA K, et al. Measuring energy and power with PAPI [C]∥Proceedings of the IEEE International Conference on Parallel Processing Workshops. Piscataway, NJ, USA: IEEE, 2012: 262-268.

[本刊相關(guān)文獻(xiàn)鏈接]

劉強(qiáng),董小社,朱正東,等.一種短作業(yè)環(huán)境下的延遲調(diào)度算法.2015,49(2):1-5.[doi:10.7652/xjtuxb201502001]

李亮,王恩東,朱正東,等.應(yīng)用動態(tài)生成樹的GPU顯存數(shù)據(jù)復(fù)用優(yōu)化.2013,47(10):44-50.[doi:10.7652/xjtuxb201310 008]

王龍翔,張興軍,朱國峰,等.重復(fù)數(shù)據(jù)刪除中的無向圖遍歷分組預(yù)測方法.2013,47(10):51-56.[doi:10.7652/xjtuxb 201310009]

張保,董小社,白秀秀,等.CPU-GPU系統(tǒng)中基于剖分的全局性能優(yōu)化方法.2012,46(2):17-23.[doi:10.7652/xjtuxb 201202004]

張保,曹海軍,董小社,等.面向圖形處理器重疊通信與計算的數(shù)據(jù)劃分方法.2011,45(4):1-5.[doi:10.7652/xjtuxb 201104001]

曹仰杰,錢德沛,伍衛(wèi)國,等.一種面向多處理器系統(tǒng)的在線低功耗調(diào)度算法.2010,44(8):15-19.[doi:10.7652/xjtuxb 201008004]

馮國富,董小社,丁彥飛,等.面向Cell寬帶引擎架構(gòu)的異構(gòu)多核訪存技術(shù).2009,43(2):1-5.[doi:10.7652/xjtuxb2009 02001]

官尚元,伍衛(wèi)國,董小社,等.分布式環(huán)境中高效信任管理的研究.2009,43(6):15-19.[doi:10.7652/xjtuxb200906004]

薛正華,劉偉哲,董小社,等.基于思維進(jìn)化的集群作業(yè)調(diào)度方法研究.2008,42(6):651-654.[doi:10.7652/xjtuxb200806 001]

(編輯 武紅江)

A Grouping Mapping Mechanism of Threads on Many-Core Systems

JU Tao,ZHANG Xingjun,CHEN Heng,DONG Xiaoshe

(School of Electronic and Information Engineering, Xi’an Jiaotong University, Xi’an 710049, China)

A grouping mapping mechanism of threads is proposed to reasonably map application threads to specific processing cores of a many-core processor according to the characteristics of applications. The mechanism bases on the data locality of intra-thread and the data correlation of inter-threads, and combines with the features of hardware architecture of many-core processor. The locality of intra-thread data is analyzed by computing the data reuse distance, and the correlation of inter-threads data is quantified by using a affinity matrix. Threads are divided into different logical groups by designing an algorithm to generate affinity spanning subtree. The reasonable mapping from application to core is realized by binding the thread to the processing core. Experimental results and a comparison with a traditional mapping mechanism show that the proposed mapping mechanism obtains nearly 14% improvement in computing performance and 12% reduction in energy consumption without introducing additional runtime overhead. The mechanism reasonably maps application threads to specific processing cores of many-core processors, and improves computing efficiency of many-core systems.

many-core system; thread mapping; data affinity; data reuse distance; logical thread grouping

2016-02-26。

巨濤(1980—),男,博士生;董小社(通信作者),男,教授,博士生導(dǎo)師。

國家自然科學(xué)基金資助項目(61572394,U1304603);國家高技術(shù)研究發(fā)展計劃資助項目(2014AA01A302);深圳市科技計劃資助項目(JCYJ20120615101127404)。

時間:2016-07-21

http:∥www.cnki.net/kcms/detail/61.1069.T.20160721.1102.002.html

10.7652/xjtuxb201610009

TP399

A

0253-987X(2016)10-0057-07