面向異構多核系統(tǒng)的多任務流并行編程模型設計

唐維賢， 楊銳

(延安大學， 數學與計算機科學學院， 陜西， 延安 716000)

0 引言

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

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

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

1 多任務流并行編程模型設計

1.1 寄存器重定向

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

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

圖1 寄存器映射

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

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

1.2 指令遷移

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

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

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

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

1.3 分離發(fā)射

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

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

1.4 線程切換

保護線程現場是線程切換中的重點工作內容，釋放線程切換在系統(tǒng)中占用的資源是設計線程切換操作的重點，利用最小的代價實現異構多核系統(tǒng)的線程切換。

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

圖3 線程切換保護機制

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

2 任務探測算法

2.1 慢任務探測

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

通過下述過程計算任務Progress：假設P代表模型中存在的任務,C代表在目前階段處理完畢的任務數據量,S代表目前階段對應的序號,N代表該階段中存在的待處理數據量,subProgress代表任務在階段內的進度，其表達式如下：

(1)

當目前階段對應的序號為0，即S=0時，Map任務對應的進度Progress可通過式(2)計算得到：

Progress=M1×subProgress

(2)

當目前階段對應的序號為1，即S=1時，Map任務對應的進度Progress可通過式(3)計算得到：

Progress=M1+M2×subProgress

(3)

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

Progress=R1×subProgress

(4)

當目前階段對應的序號為1，即S=1時，Reduce任務對應的進度Progress為

Progress=R1+R2×subProgress

(5)

當目前階段對應的序號為2，此時存在：

Progress=R1+R2+R3×subProgress

(6)

式中，R1、R2、R3分別代表的是Reduce任務三個階段對應的時間。假設avgProgress代表的是平均進度，其計算公式如下：

(7)

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

(8)

式中，t代表任務從開始到結束所用的時間。在此基礎上，假設num_r、num_m分別代表Reduce任務和Map任務對應的數量，avgProgressRate_m代表Map任務對應的平均速率，其計算公式如下：

(9)

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

ProgressRate_m<(1-SlowTaskThreshold)×

avgProgressRate_m

(10)

假設avgProgressRate_r代表Reduce任務對應的平均速率，其計算公式如下：

(11)

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

ProgressRate_r<(1-SlowTaskThreshold)×

avgProgressRate_r

(12)

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

2.2 落后任務探測

當不同任務中的工作分配不均衡或者數據傾斜時，可能會出現落后任務，導致某一個任務需要處理更多工作，則該任務被稱為“落后任務”，其需要滿足以下條件。

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

(2)備份任務在異構多核系統(tǒng)中的數量遠遠高于設定的SpeculationCap閾值。

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

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

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

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

3 實驗與分析

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

表1 平臺配置

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

圖4 調用開銷測試結果

圖5 計算開銷測試結果

分析圖4中的數據可知，模型1的調用開銷在多次迭代中均在2 000 cycles以內，模型2和模型3的調用開銷遠遠高于模型1的調用開銷。這是因為模型1對異構多核系統(tǒng)中慢任務進行探測，提高慢任務的調用效率，進而縮短了異構多核系統(tǒng)的調用開銷。

根據圖5可知，模型1的計算開銷在多次迭代中遠遠低于模型2和模型3的計算開銷。這是因為模型1通過對落后任務進行探測，以最小的代價實現多任務流的并行處理，降低了異構多核系統(tǒng)的計算開銷。

將編程加速比作為測試指標，對不同模型進行測試，測試結果如圖6所示。

圖6 編程加速比測試結果

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

4 總結

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

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