面向異構(gòu)多核系統(tǒng)的多任務(wù)流并行編程模型設(shè)計(jì)

唐維賢， 楊銳

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

0 引言

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

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

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

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

1.1 寄存器重定向

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

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

圖1 寄存器映射

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

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

1.2 指令遷移

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

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

設(shè)計(jì)處理器時(shí)，建立1張包括異構(gòu)多核系統(tǒng)中所有運(yùn)算資源的資源表，二維網(wǎng)格內(nèi)異構(gòu)多核系統(tǒng)對(duì)應(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ā)射指令所用的時(shí)間，降低了編程處理器的難度。

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

1.3 分離發(fā)射

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

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

1.4 線程切換

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

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

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

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

2 任務(wù)探測(cè)算法

2.1 慢任務(wù)探測(cè)

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

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

(1)

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

Progress=M1×subProgress

(2)

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

Progress=M1+M2×subProgress

(3)

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

Progress=R1×subProgress

(4)

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

Progress=R1+R2×subProgress

(5)

當(dāng)目前階段對(duì)應(yīng)的序號(hào)為2，此時(shí)存在：

Progress=R1+R2+R3×subProgress

(6)

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

(7)

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

(8)

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

(9)

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

ProgressRate_m<(1-SlowTaskThreshold)×

avgProgressRate_m

(10)

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

(11)

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

ProgressRate_r<(1-SlowTaskThreshold)×

avgProgressRate_r

(12)

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

2.2 落后任務(wù)探測(cè)

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

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

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

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

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

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

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

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

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

表1 平臺(tái)配置

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

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

圖5 計(jì)算開銷測(cè)試結(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)槟Ｐ?對(duì)異構(gòu)多核系統(tǒng)中慢任務(wù)進(jìn)行探測(cè)，提高慢任務(wù)的調(diào)用效率，進(jìn)而縮短了異構(gòu)多核系統(tǒng)的調(diào)用開銷。

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

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

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

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

4 總結(jié)

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

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