唐維賢， 楊銳

(延安大學(xué)， 數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院， 陜西， 延安 716000)

0 引言

由于成本因素、能耗因素和芯片集成規(guī)模的增大，處理器在發(fā)展過程中受到了限制，逐漸向多核方向發(fā)展[1]。多核系統(tǒng)具有易于擴(kuò)充、計算能力強(qiáng)的特點(diǎn)[2]，現(xiàn)有的軟件開發(fā)模式受多核系統(tǒng)發(fā)展的影響逐漸發(fā)生改變，針對并行計算、并行程度和并行算法等方面提出了更高的設(shè)計要求。

對于異構(gòu)多核系統(tǒng)來說，高速且低消耗的多任務(wù)流并行編程模型至關(guān)重要，其在提高異構(gòu)多核系統(tǒng)的處理效率等方面意義重大。為此，趙博穎等[3]提出了基于布谷鳥搜索的多任務(wù)流并行編碼模型，根據(jù)多核集群拓?fù)浣Y(jié)構(gòu)的特點(diǎn)，利用作業(yè)優(yōu)先級編碼方法結(jié)合存儲編輯模型和編程模型，根據(jù)布谷鳥搜索結(jié)果實(shí)現(xiàn)多任務(wù)流并行編碼模型的設(shè)計，但該模型難以探測到異構(gòu)多核系統(tǒng)中存在的慢任務(wù)，導(dǎo)致調(diào)用開銷高。李鵬等[4]提出了基于多FPGA的多任務(wù)流并行編程模型，通過物理耦合方法粗粒度分割數(shù)學(xué)模型，并通過細(xì)粒度分割子系統(tǒng)，在FPGA中映射分割后的模型，在協(xié)調(diào)分配的基礎(chǔ)上實(shí)現(xiàn)多任務(wù)流并行編程，但該模型難以探測到異構(gòu)多核系統(tǒng)中存在的落后任務(wù)，存在計算開銷高的問題。李翠等[5]提出了基于DPDK并行通信的多任務(wù)流并行編程模型，結(jié)合通信系統(tǒng)和DPDK設(shè)計多核并行處理數(shù)據(jù)包、細(xì)粒度監(jiān)控網(wǎng)口，結(jié)合動態(tài)負(fù)載信息、調(diào)整函數(shù)和散列函數(shù)設(shè)計多任務(wù)流并行編程模型，但該模型沒有在編程模型中設(shè)計任務(wù)探測環(huán)節(jié)，導(dǎo)致異構(gòu)多核系統(tǒng)的編程加速比較低。

為了解決上述模型中存在的問題，本文設(shè)計了面向異構(gòu)多核系統(tǒng)的多任務(wù)流并行編程模型。

1 多任務(wù)流并行編程模型設(shè)計

1.1 寄存器重定向

物理寄存器通常在異構(gòu)多核系統(tǒng)的調(diào)度單元中等待調(diào)度，當(dāng)指令在異構(gòu)多核系統(tǒng)中出現(xiàn)阻塞現(xiàn)象時，寄存器在系統(tǒng)中屬于無效占用，造成了外存儲空間和寄存器存儲空間的資源浪費(fèi)[6]。為了解決寄存器在調(diào)度模塊中因無效占用導(dǎo)致的資源浪費(fèi)問題，本研究利用兩級映射關(guān)系對調(diào)度指令進(jìn)行處理。

在經(jīng)典流水線的基礎(chǔ)上增加寄存器重命名等亂序技術(shù)，寄存器之間的關(guān)系可以通過亂序發(fā)射進(jìn)行解耦和分析，利用調(diào)度技術(shù)完成發(fā)射[7]。亂碼發(fā)射時的異構(gòu)多核系統(tǒng)中的寄存器映射如圖1所示。

圖1 寄存器映射

物理寄存器在重命名階段通過處理器分配給體系寄存器，并在映射表中存儲這種映射關(guān)系。寄存器在異構(gòu)多核系統(tǒng)中重定向后的映射示意圖如圖2所示。

圖2 寄存器重定向后的映射示意圖

1.2 指令遷移

存在指令操作的運(yùn)算單元在異構(gòu)多核系統(tǒng)中的種類和數(shù)量較多，異構(gòu)多核系統(tǒng)中的指令通常情況下包含操作指令對應(yīng)的承載對象，多任務(wù)流編程在指定運(yùn)算單元方式下的難度較高，降低了異構(gòu)多核系統(tǒng)的靈活性[8]。

阻塞問題經(jīng)常存在于運(yùn)算單元執(zhí)行指令的過程中，當(dāng)多個指令的執(zhí)行對象為相同運(yùn)算單元時，運(yùn)算周期中存在的運(yùn)算值對應(yīng)一個指令，因此多個指令在運(yùn)算過程中存在競爭，在競爭過程中存在隱患，容易造成指令阻塞。為了在不同的運(yùn)算單元中執(zhí)行不同線程的指令，本文采用指令遷移的方法。

設(shè)計處理器時，建立1張包括異構(gòu)多核系統(tǒng)中所有運(yùn)算資源的資源表，二維網(wǎng)格內(nèi)異構(gòu)多核系統(tǒng)對應(yīng)的坐標(biāo)以及運(yùn)算單元的數(shù)量和種類均存在于資源表中。執(zhí)行系統(tǒng)指令之前，處理器的主要任務(wù)是將各種指令分配到指定的運(yùn)算單元中，指令在相同運(yùn)算單元之間可以進(jìn)行遷移操作。運(yùn)算單元在異構(gòu)多核系統(tǒng)中通過這種機(jī)制可以被充分地利用，縮短了發(fā)射指令所用的時間，降低了編程處理器的難度。

執(zhí)行完指令后運(yùn)算單元會向處理器釋放信息，表明可以接收新的任務(wù)，單元處于空閑狀態(tài)，收到信息后處理器標(biāo)記資源隊列，在資源池中重新納入運(yùn)算單元。

1.3 分離發(fā)射

分離發(fā)射即輸入線程為多路，當(dāng)出現(xiàn)私有資源占用當(dāng)前線程導(dǎo)致出現(xiàn)阻塞現(xiàn)象，且無法被修改或訪問時，可使用另一個線程的共享資源進(jìn)行工作。

線程A和線程B可以在調(diào)度模塊中同時被處理，當(dāng)線程A存在時間難以滿足線程切換條件的阻塞時，可以利用輔助線程機(jī)制解決阻塞問題，線程A中調(diào)度器的主要任務(wù)是在指令調(diào)度過程中輔助線程B進(jìn)行相關(guān)操作，當(dāng)線程A在發(fā)射階段難以滿足要求時，線程B會進(jìn)行輔助操作。

1.4 線程切換

保護(hù)線程現(xiàn)場是線程切換中的重點(diǎn)工作內(nèi)容，釋放線程切換在系統(tǒng)中占用的資源是設(shè)計線程切換操作的重點(diǎn)，利用最小的代價實(shí)現(xiàn)異構(gòu)多核系統(tǒng)的線程切換。

根據(jù)指令在異構(gòu)多核系統(tǒng)中提取信息時，需要獲取虛擬寄存器編號，并將其傳送到對應(yīng)的映射表格和管理表格中。通常情況下，虛擬寄存器在異構(gòu)多核系統(tǒng)中占用的空間極小，可忽略不計，但在異構(gòu)多核系統(tǒng)的硬件設(shè)計中，虛擬寄存器的編號數(shù)量是有限的，為了避免總體編號在線程保留棧中的數(shù)量減少，剔除線程切換過程中存在的無用虛擬寄存器編號，當(dāng)線程喚醒時重新對虛擬寄存器編號進(jìn)行分配。在寄存器保存表中備份釋放后的寄存器映射表，線程切換保護(hù)機(jī)制如圖3所示。

圖3 線程切換保護(hù)機(jī)制

利用記錄表中存在的pc地址在線程恢復(fù)狀態(tài)下重新取值，并恢復(fù)任務(wù)號，寄存器映射關(guān)系根據(jù)寄存器保存表完成恢復(fù)，將虛擬寄存器標(biāo)號重新分配給指令中存在的輸出寄存器，完成恢復(fù)。

2 任務(wù)探測算法

2.1 慢任務(wù)探測

在多任務(wù)流并行編碼模型中需要探測Reduce和Map兩種慢任務(wù)。

通過下述過程計算任務(wù)Progress：假設(shè)P代表模型中存在的任務(wù),C代表在目前階段處理完畢的任務(wù)數(shù)據(jù)量,S代表目前階段對應(yīng)的序號,N代表該階段中存在的待處理數(shù)據(jù)量,subProgress代表任務(wù)在階段內(nèi)的進(jìn)度，其表達(dá)式如下：

(1)

當(dāng)目前階段對應(yīng)的序號為0，即S=0時，Map任務(wù)對應(yīng)的進(jìn)度Progress可通過式(2)計算得到：

Progress=M1×subProgress

(2)

當(dāng)目前階段對應(yīng)的序號為1，即S=1時，Map任務(wù)對應(yīng)的進(jìn)度Progress可通過式(3)計算得到：

Progress=M1+M2×subProgress

(3)

其中，M1、M2代表Map任務(wù)兩階段對應(yīng)的時間。當(dāng)目前階段對應(yīng)的序號為0，即S=0時，Reduce任務(wù)對應(yīng)的進(jìn)度Progress可通過式(4)計算得到：

Progress=R1×subProgress

(4)

當(dāng)目前階段對應(yīng)的序號為1，即S=1時，Reduce任務(wù)對應(yīng)的進(jìn)度Progress為

Progress=R1+R2×subProgress

(5)

當(dāng)目前階段對應(yīng)的序號為2，此時存在：

Progress=R1+R2+R3×subProgress

(6)

式中，R1、R2、R3分別代表的是Reduce任務(wù)三個階段對應(yīng)的時間。假設(shè)avgProgress代表的是平均進(jìn)度，其計算公式如下：

(7)

設(shè)ProgressRate_r、ProgressRate_m分別代表的是Reduce任務(wù)和Map任務(wù)對應(yīng)的執(zhí)行速率，其計算公式如下：

(8)

式中，t代表任務(wù)從開始到結(jié)束所用的時間。在此基礎(chǔ)上，假設(shè)num_r、num_m分別代表Reduce任務(wù)和Map任務(wù)對應(yīng)的數(shù)量，avgProgressRate_m代表Map任務(wù)對應(yīng)的平均速率，其計算公式如下：

(9)

如果Map任務(wù)滿足式(10)，可被判定為慢任務(wù)：

ProgressRate_m<(1-SlowTaskThreshold)×

avgProgressRate_m

(10)

假設(shè)avgProgressRate_r代表Reduce任務(wù)對應(yīng)的平均速率，其計算公式如下：

(11)

如果Reduce任務(wù)滿足下述公式，可被判定為慢任務(wù)：

ProgressRate_r<(1-SlowTaskThreshold)×

avgProgressRate_r

(12)

式中，SlowTaskThreshold代表速率判斷閾值，其值通常為0.1。

2.2 落后任務(wù)探測

當(dāng)不同任務(wù)中的工作分配不均衡或者數(shù)據(jù)傾斜時，可能會出現(xiàn)落后任務(wù)，導(dǎo)致某一個任務(wù)需要處理更多工作，則該任務(wù)被稱為“落后任務(wù)”，其需要滿足以下條件。

(1)在全部任務(wù)中該任務(wù)的剩余時間最長。設(shè)TimeToEnd=(1-Progress)/ProgressRate代表的是完成任務(wù)剩余的時間。

(2)備份任務(wù)在異構(gòu)多核系統(tǒng)中的數(shù)量遠(yuǎn)遠(yuǎn)高于設(shè)定的SpeculationCap閾值。

(3)該任務(wù)的類型為慢任務(wù)。

(4)工作執(zhí)行時間往往大于60 s。

異構(gòu)多核系統(tǒng)中的Reduce任務(wù)和Map任務(wù)均屬于落后任務(wù)。

在非Reduce慢和非Map慢TaskTracker上啟動落后任務(wù)，判定任務(wù)是否完成的依據(jù)是任意一個副本的完成度。

3 實(shí)驗(yàn)與分析

為驗(yàn)證面向異構(gòu)多核系統(tǒng)的多任務(wù)流并行編程模型的整體有效性，設(shè)計如下實(shí)驗(yàn)。本次測試的實(shí)驗(yàn)平臺的配置如表1所示。

表1 平臺配置

分別采用面向異構(gòu)多核系統(tǒng)的多任務(wù)流并行編程模型(模型1)、基于布谷鳥搜索的多任務(wù)流并行編碼模型(模型2)和基于多FPGA的多任務(wù)流并行編程模型(模型3)進(jìn)行測試，對比不同模型的調(diào)用開銷和計算開銷，測試結(jié)果分別如圖4、圖5所示。

圖4 調(diào)用開銷測試結(jié)果

圖5 計算開銷測試結(jié)果

分析圖4中的數(shù)據(jù)可知，模型1的調(diào)用開銷在多次迭代中均在2 000 cycles以內(nèi)，模型2和模型3的調(diào)用開銷遠(yuǎn)遠(yuǎn)高于模型1的調(diào)用開銷。這是因?yàn)槟Ｐ?對異構(gòu)多核系統(tǒng)中慢任務(wù)進(jìn)行探測，提高慢任務(wù)的調(diào)用效率，進(jìn)而縮短了異構(gòu)多核系統(tǒng)的調(diào)用開銷。

根據(jù)圖5可知，模型1的計算開銷在多次迭代中遠(yuǎn)遠(yuǎn)低于模型2和模型3的計算開銷。這是因?yàn)槟Ｐ?通過對落后任務(wù)進(jìn)行探測，以最小的代價實(shí)現(xiàn)多任務(wù)流的并行處理，降低了異構(gòu)多核系統(tǒng)的計算開銷。

將編程加速比作為測試指標(biāo)，對不同模型進(jìn)行測試，測試結(jié)果如圖6所示。

圖6 編程加速比測試結(jié)果

對圖6中的數(shù)據(jù)進(jìn)行分析可知，在多次迭代中，模型1的編程加速比均在16.0以上，模型2和模型3的編程加速比均低于15.0，對比上述模型的測試結(jié)果可知，模型1的編程加速比較高。這是因?yàn)槟Ｐ?通過線程切換處理異構(gòu)多核系統(tǒng)中存在的慢任務(wù)，剔除異構(gòu)多核系統(tǒng)中的落后任務(wù)，提高了模型1的編程加速比。

4 總結(jié)

為了提高異構(gòu)多核系統(tǒng)的計算能力，提高編程靈活性，需要對多任務(wù)流并行編碼模型展開設(shè)計。目前多任務(wù)流并行編程模型存在調(diào)用開銷高、計算開銷高和編程加速比低的問題。本文提出面向異構(gòu)多核系統(tǒng)的多任務(wù)流并行編程模型，將任務(wù)探測算法引入到多任務(wù)流并行編程模型的設(shè)計中，解決了目前編程模型中存在的問題，為異構(gòu)多核系統(tǒng)的發(fā)展奠定了基礎(chǔ)。

在今后的研究中，將進(jìn)一步對所提模型展開優(yōu)化，從優(yōu)化任務(wù)排序的角度進(jìn)一步提高模型的應(yīng)用性能。