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

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

?

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

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

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

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

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

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

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

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

1 線程分組映射總體框架

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

圖1 線程分組映射框架

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

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

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

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

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

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

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

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

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

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

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

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

(2)

(3)

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

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

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

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

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

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

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

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

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

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

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

規(guī)則1 將同一線程組中的應(yīng)用線程盡量分配到同一個(gè)處理核的不同硬件線程上。如果該處理核線程已經(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ù)的線程分散到具有獨(dú)立緩存空間的不同處理核上。

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

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

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

圖3 MIC處理器存儲(chǔ)層次圖

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

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

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

5 實(shí)驗(yàn)評(píng)測(cè)及結(jié)果分析

5.1 測(cè)試平臺(tái)及方法

采用PARSEC[14]基準(zhǔn)測(cè)試集中的測(cè)試程序Blackscholes、Ferret、Streamcluster、Raytrace、Bodytrack、Cannel、X264和Dedup,用native輸入集。實(shí)驗(yàn)平臺(tái)由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]性能測(cè)試工具獲取性能指標(biāo)。分別對(duì)本文線程映射方法DagTm方法,OpenMP支持的Compact、Scatter方法,以及理想情況下最優(yōu)的映射方法Oracle從計(jì)算性能、能耗及額外開銷3方面進(jìn)行測(cè)試對(duì)比。

5.2 計(jì)算性能測(cè)試

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

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

5.3 能耗測(cè)試

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

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

5.4 額外開銷測(cè)試

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

圖7 DagTM額外開銷

6 結(jié) 論

本文針對(duì)眾核系統(tǒng)下線程到處理核的映射問題,通過計(jì)算數(shù)據(jù)重用距離來判定線程內(nèi)部的數(shù)據(jù)局部性;用數(shù)據(jù)相關(guān)性矩陣度量線程間的數(shù)據(jù)相關(guān)性;根據(jù)線程相關(guān)性圖,利用最小生成樹實(shí)現(xiàn)不同線程的邏輯分組;最后通過線程組到處理核的綁定實(shí)現(xiàn)線程到處理核的映射。實(shí)驗(yàn)評(píng)測(cè)表明,本文線程分組映射方法在提升計(jì)算性能和降低能耗方面是有效的,可以根據(jù)應(yīng)用程序不同線程之間的數(shù)據(jù)相關(guān)性,將不同線程合理映射到具體眾核處理器不同處理核上,在不引入額外運(yùn)行時(shí)開銷的基礎(chǔ)上,提高系統(tǒng)的計(jì)算性能,降低系統(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é)報(bào), 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]張保, 曹海軍, 董小社, 等. 面向圖形處理器重疊通信與計(jì)算的數(shù)據(jù)劃分方法 [J]. 西安交通大學(xué)學(xué)報(bào), 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)用動(dòng)態(tài)生成樹的GPU顯存數(shù)據(jù)復(fù)用優(yōu)化.2013,47(10):44-50.[doi:10.7652/xjtuxb201310 008]

王龍翔,張興軍,朱國(guó)峰,等.重復(fù)數(shù)據(jù)刪除中的無向圖遍歷分組預(yù)測(cè)方法.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]

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

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

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

官尚元,伍衛(wèi)國(guó),董小社,等.分布式環(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)師。

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

時(shí)間: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