異構集群中CPU與GPU協同調度算法的設計與實現

高 原，顧文杰，丁雨恒，彭 暉，陳泊宇，顧雯軒

(1.南瑞集團(國網電力科學院)有限公司 南瑞研究院，江蘇 南京 211106；2.國電 南瑞科技股份有限公司 系統研發中心，江蘇 南京 211106；3.南瑞集團有限公司 智能電網保護和運行控制國家重點實驗室，江蘇 南京 211106)

0 引 言

近年來，大規模CPU/GPU異構混合并行系統在云計算、大數據、人工智能等科學計算領域獲得了廣泛應用，但其復雜體系結構為并行計算的研究提出了巨大挑戰[1]。

文獻[2-6]研究實現的CPU/GPU并行計算模型僅支持節點內調度，且執行效率受限于節點計算性能。文獻[7,8]討論了同構集群環境下的并行計算，未考慮異構環境中各節點間不同計算能力下的差異化任務數據分發及計算節點內CPU/GPU二次協同調度問題。文獻[9,10]討論了異構集群環境下的編程框架，但任務的分配需要預先規劃，不適合大量離散任務動態產生的場景。文獻[11]設計的系統解除了GPU應用程序和MPI通信程序的耦合，未考慮異構集群系統中差異化計算資源條件下的數據動態調度及精確化通信控制問題。綜上所述，研究文獻存在以下不足：①CPU和GPU計算任務的分配相對的割裂開來，未考慮協同并行計算的問題；②未討論異構集群系統中差異化計算資源情況下，動態調度計算任務的問題；③MPI通信未考慮計算任務的細粒度劃分和多次精確化通信控制。

本文研究了基于異構集群系統的節點間調度和節點內CPU與GPU協同并行計算的問題，設計并實現了基于兩級調度的CPU與GPU協同計算的動態調度算法。算法解決了節點資源異構情況下差異化任務數據調度分發及節點內CPU/GPU動態調度協同并發計算的問題，避免了單節點木桶短板效應造成系統級任務長尾現象。實驗測試結果表明，使用本文算法的效率比MPI框架效率提高了11倍。

1 MPI框架下的多節點GPU并行計算特征

MPI(message passing interface)是分布式并行計算環境下消息傳遞的標準接口，Open MPI是一個開源高效的MPI實現，提供了并發和多線程應用服務[12,13]。

本文研究時使用了openmpi的最新版本3.1.2對MPI并發任務進行了計算任務數據的分發測試，以適合GPU高并發處理的矩陣相加作為計算用例來測試計算時間。本文計算任務數據均以流式數據作為源數據，采用分批方式處理，單批次處理的數據量大小以矩陣塊單元(大小為16 M)為單位進行設定。系統配置4個節點，并發進程數設置為4。主進程(rank=0)所在的節點擔任分發任務，同時也作為計算節點。其它3個節點均擔任計算任務，為計算節點。計算任務數據分發采用MPI Scatter一對多通信方式。本批次處理計算任務數據量設置為1600 M(100矩陣塊)，4個節點均承擔數據接收任務和并行計算任務，每個節點默認接收到的并行計算任務數據量為400 M(25矩陣塊)。數據分發過程中對每個計算節點的網卡I/O情況進行監視。得到每個節點的網絡IO特征如圖1所示。圖1中橫坐標是時間，單位是s；縱坐標是網卡流量，單位是KB/s。實線是網卡輸入流量，虛線是網卡輸出流量。

圖1 MPI Scatter分發數據的網絡I/O特征

從圖1中可分析得出以下MPI Scatter分發任務數據的網絡I/O特征：

(1)主進程(rank=0)所在的1號節點一直有網絡流量輸出，說明其持續進行數據分發，此外，其它節點均有網絡流量輸入，說明其它節點均承擔數據接收的任務；

(2)主進程不間斷發送數據，各數據接收節點串行接收數據；

(3)各數據接收節點在主進程開始分發數據一段時間后才開始網絡數據的接收。

在研究過程中使用多種文件大小進行測試，雖然曲線在每次測試中的開始、結束時間不一樣，最大值也不一樣，但都符合以上特征。從特征中可分析出MPI框架分發數據的如下幾點缺陷：

(1)主進程(rank=0)所在的1號節點順序分發數據，其它計算節點串行接收數據，未接收數據前，計算節點處于等待接收數據的狀態，造成計算資源的閑置和浪費；

(2)沒有考慮到系統的異構性，計算性能較強和較弱的節點接收到的計算任務數據量是一致的，即承擔了相同的計算任務量，這種情況下，計算性能差的節點將拖慢整個計算任務的執行過程，導致任務長尾現象。

圖2是各節點任務數據計算的GPU使用率特征曲線圖。圖中橫坐標是時間，單位是s；縱坐標是GPU使用率，單位是百分比(%)。

圖2 GPU使用率特征

圖3是各節點的數據接收等待時間、數據傳輸時間和GPU并行計算處理時間的特征堆積條形圖，該圖標識了圖1 和圖2的數據接收等待、數據傳輸和任務執行的順序及持續時間。圖中橫坐標是時間，單位是s；縱坐標是計算節點；不同的填充圖案分別表示等待時間、傳輸時間、處理時間。

圖3 等待時間、傳輸時間、處理時間概化圖

從圖2和圖3可以看出主進程(rank=0)所在的1號節點在數據讀取完成后，立即開始了GPU并行計算。其它計算節點在不同的等待時長后，開始接收網絡數據，數據接收完畢后開始GPU并行計算。3號節點和4號節點等待的時間較長。1號節點和3號節點由于GPU計算性能較弱，拖慢了整個計算任務的計算過程，導致任務的長尾現象，其中3號節點的長尾現象比較明顯。

從圖4可以看出，CPU計算資源沒有得到充分的利用，CPU只是完成了簡單的數據接收、數據預處理及計算結果整合與反饋，承擔的工作量相對不飽滿，資源閑置浪費。

圖4 CPU使用率特征

2 支持異構集群的CPU與GPU協同調度算法

2.1 算法的軟件框架

CPU從單核發展為多核，大幅度提高了處理器性能，擅長處理控制密集型任務。本文中CPU參與并行計算任務均采用多線程方式。GPU是顯卡的核心，天生眾核，適合運行密集型并行計算的程序。CPU和GPU的功能互補性使CPU+GPU的異構并行計算構架得到了迅速的發展[14]。

本文算法的設計思想是考慮系統資源的異構性，實現了基于兩級調度的CPU與GPU協同計算的動態調度算法，讓性能弱的節點處理較少的計算任務，性能強的節點處理更多的計算任務，有效提高CPU/GPU異構混合并行系統的整體并發度，減少任務執行時間。算法的主要內容分為3個步驟：①節點計算能力綜合測評，算法在各計算節點的CPU和GPU上分別處理單位矩陣測試任務，根據各節點返回的CPU和GPU計算耗時進行分析，獲得節點內 CPU/GPU 計算能力比值、各節點綜合計算能力比值、各節點處理單位矩陣任務綜合耗時(以下簡稱節點處理能力)以及集群單位時間內綜合計算能力；②計算任務全局動態調度，算法將當前計算任務以單位矩陣為單元進行細粒度劃分，再根據節點計算能力測評信息在集群內實時動態調度，實現計算節點“能者多勞”，保證整個系統并發運行和負載均衡；③計算任務節點內協同調度，一方面算法在各計算節點上建立數據緩存隊列和數據處理隊列，數據緩存隊列主要向全局調度模塊請求數據，數據處理隊列主要負責向CPU和GPU輸送數據進行處理，在數據處理隊列為空的情況下，隊列角色動態切換，保障數據傳輸和數據處理并發性，避免節點資源的閑置；另一方面算法根據節點綜合計算能力測評中CPU和GPU處理能力進行動態任務調度，完成節點級的協同調度。

本文調度算法的軟件框架如圖5所示。

圖5中的全局調度模塊可獨立部署，也可部署在計算節點上，節點調度模塊分別部署在每個計算節點上。全局調度模塊負責各計算節點資源和工作狀態監視信息的收集工作，并完成系統內工作任務的動態調度。節點調度模塊使用兩個數據隊列，分別完成向全局調度模塊實時請求數據并緩存，和向CPU、GPU輸送待處理數據的工作。與此同時，節點調度模塊完成節點上CPU和GPU計算任務的協同調度工作。

2.2 算法設計思想

現有技術中CPU/GPU異構混合并行系統進行任務調度方面的研究一般是采取對各種類型硬件的計算能力或者是任務在各類處理器上的運行時間進行預測，然后進行一次性任務分配。這種方法缺項明顯，因此預測可能不夠準確，會造成各個計算節點的結束時間不一致，造成有些節點有長尾現象，其它節點可能在最后階段空閑，沒有充分發揮集群的計算能力，任務完成時間沒有達到最短。針對這些問題，本文算法設計思想如下：

(1)在全局模塊調度中，進行硬件計算資源CPU和GPU的狀態監視，在任務執行之前運行單元矩陣測試任務，保證對集群整體和各節點進行精確化的計算能力測評，為計算任務數據在全局和節點內調度提供可靠的任務分配權重；

(2)在全局模塊調度中，計算任務數據以單位矩陣為單元進行細粒度劃分。各節點單次計算任務的矩陣塊數依據節點處理能力進行不均等動態劃分；

(3)在節點調度模塊中，設置數據緩存隊列和數據處理隊列，并發完成數據緩存和數據處理任務，避免節點資源的閑置；

圖5 調度算法的軟件框架

(4)在節點調度模塊中，根據計算節點上CPU和GPU的計算處理能力，按比例分配矩陣塊，進行協同調度和并行計算。

2.3 算法描述

算法的執行過程就是各個計算節點從全局調度模塊分多批次動態獲取數據，并在節點內部的CPU與GPU之間動態調度數據的過程。下面具體描述算法的步驟，假設全局調度模塊所在的節點也作為一個計算節點。

步驟1 全局調度模塊在調度任務前，先將單位矩陣測試任務數據分發到各計算節點，各計算節點通過節點調度模塊，把測試數據分別在的CPU和GPU上執行，獲得集群內各節點CPU、GPU計算耗時；

步驟2 全局調度模塊根據集群各節點測試矩陣任務的CPU、GPU計算耗時，計算出節點處理能力、各節點綜合計算能力比值以及集群綜合計算能力，作為全局動態調度依據。節點調度模塊根據節點內CPU、GPU計算耗時得出節點內CPU、GPU計算能力比值，作為節點內計算任務調度依據；

步驟3 全局調度模塊將計算任務數據以單位矩陣為單元，依據節點處理能力，進行不均等動態劃分；

步驟4 節點調度模塊所在的各計算節點請求數據時，全局調度模塊依據各個節點的處理能力值，按比例分發與其計算能力相匹配的矩陣塊數到各計算節點，權值越高的節點分得的越多，等待先完成計算的節點再次進行請求，保證整個系統并發運行和負載均衡，避免一次性分發完畢造成的某些節點的長尾現象；

步驟5 節點調度模塊在各計算節點內設置兩條節點級數據存儲隊列，節點調度模塊在兩條數據存儲隊列之間動態切換隊列角色(數據緩存隊列和數據處理隊列之間按照調度策略進行角色轉換)和向全局調度模塊請求計算任務數據，具體偽代碼如下所示：

START:while (全局調度模塊計算任務數據 > 0) do

if 數據隊列1size == 0 && 數據隊列2size == 0 then

向全局調度模塊請求數據，存入數據隊列1，數據隊列1角色轉變為數據處理隊列，數據隊列2轉為數據緩存隊列

開啟線程循環監視數據緩存隊列，當數據緩存隊列為空、網絡空閑、全局調度模塊計算任務數據>0時，循環請求數據存入數據緩存隊列

endif

if 數據處理隊列size != 0 then

for i = 0 to 數據處理size/(CPU+GPU處理能力權值) do

根據本節點CPU和GPU處理能力權值按比例分發處理

else

if 數據緩存隊列size != 0 then

數據處理和數據緩存隊列角色對換

else

goto START

endif

endif

步驟6 步驟5中根據本節點CPU和GPU處理能力權值按比例分發處理，即計算節點的CPU從當前處理隊列中獲取數據開始處理時，選擇一部分數據并根據本節點的CPU和GPU處理能力權值按比例分發到CPU和GPU進行處理；當GPU空閑時繼續遷移數據到GPU進行處理，對CPU的調度同理。同時在隊列上進行加鎖處理，避免兩個處理器獲得重復的數據，直至當前處理隊列中的數據為空。實現了節點上的數據在CPU和GPU間動態調度，保證了一個節點的CPU和GPU的充分并發執行和負載均衡；

步驟7 當數據緩存隊列為空，節點調度模塊立刻向全局調度模塊請求下一批數據，如果全局調度模塊返回空數據集則說明全部數據已經分發完成，當前處理隊列的數據全部處理完成后，當前計算任務完成。

算法分發測試任務到各計算節點，運行任務并計算CPU和GPU的處理能力比值的計算量和計算節點數量線性相關，即復雜度為O(n)。全局調度模塊依據節點處理能力拆分計算數據的計算量和數據量大小線性相關，即復雜度為O(n)。計算節點向全局調度模塊請求計算任務數據的復雜度為O(1)。節點調度模塊依據CPU和GPU處理能力權值在節點內部動態分發數據的計算量和數據處理隊列數據量大小線性相關，即復雜度為O(n)。因此本文算法的總體復雜度為O(n)。

2.4 算法實例分析

下面以4個節點構成的CPU/GPU協同調度集群，單批次處理數據量設置為1.6 G(100矩陣塊)進行CPU/GPU混合并行計算的場景舉例，具體分析本算法的CPU/GPU協同調度流程，如圖6和圖7所示。

圖7 節點級調度模塊數據調度

圖6是全局調度模塊數據分發，圖7是節點調度模塊數據調度，圖8是兩種類型數據存儲隊列角色輪換。為了充分利用計算資源，圖6中全局調度模塊所在的節點同時部署了節點調度模塊，也作為計算節點，承擔計算任務，圖6中其它節點只部署節點調度模塊，作為計算節點，承擔計算任務。

圖8 兩種類型數據存儲隊列角色輪換

算法開始時全局調度模塊和各計算節點的節點調度模塊通過心跳保持通信，實時監視集群中各節點的運行狀態，同時收集各計算節點的CPU和GPU的狀態信息。

四川省出臺的《關于加強孤兒保障工作的實施意見》中規定，扶持孤兒成年后就業。按規定落實好社會保險補貼、崗位補貼等扶持政策。積極提供就業服務和就業援助，及時將成年后就業困難且符合條件的孤兒納入就業援助范圍，依托基層公共就業人才服務機構了解就業需求，開展免費就業咨詢，提供有針對性的就業幫扶。大力開發公益性崗位，將成年后就業困難的孤兒優先安排到政府開發的公益性崗位就業。鼓勵自主創業，對符合條件的成年孤兒，給予場地安排、稅費減免、小額擔保貸款及貼息、創業服務和培訓等方面的優惠政策。按規定落實好職業培訓補貼、職業技能鑒定補貼等政策。開展多種形式的職業培訓。

第一步計算節點性能耗時評測。全局調度模塊將單位矩陣測試任務數據分發到4個計算節點，各計算節點分別把測試任務分發到CPU和GPU中分別執行，獲得集群內各節點CPU和GPU計算耗時。4個節點GPU、CPU耗時分別為(1.55、10)、(0.24、6.26)、(5.72、17)和(0.49、17)，單位：s。

第二步集群計算資源綜合分析。全局調度模塊根據第一步獲取的各計算節點CPU和GPU計算耗時，取倒數即為計算效率，以此計算得到節點內CPU和GPU計算效率比值以及集群各計算節點效率比值。4個節點內部GPU∶CPU的計算效率比依次為87∶13、96∶3、75∶25、97∶3。4個節點的綜合計算效率比為：10∶59∶3∶28。因此，每次計算節點調度模塊向全局調度模塊請求數據時，全局調度模塊單次下發的數據量以單位矩陣為單元按綜合計算效率比例分發。

第三步計算任務數據細粒度拆分與各計算節點及節點內GPU/CPU處理量劃分。全局調度模塊將計算任務數據以單位矩陣為單元進行拆分，然后依據節點處理能力，進行不均等動態劃分。1.6 G任務數據首先依據4個計算節點綜合計算效率比進行數據量等比例拆分，然后拆分數據量除以單位矩陣大小并向下取整，得出各計算節點矩陣劃分的個數。按綜合計算效率比例拆分后，剩余的矩陣依據各節點GPU、CPU單位矩陣耗時情況進行二次試算分配，試算最優目標為總體耗時最短。按照以上策略，各節點矩陣塊數(GPU/CPU)分配量分別為9(8/1)、61(59/2)、2(2/0)、28(28/0)。

第四步全局調度模塊計算任務數據分發。全局調度模塊依據4個計算節點的節點調度模塊數據請求和其綜合計算效率比10∶59∶3∶28，以單位矩陣為單元，按比例分發計算任務矩陣，并等待下一個完成計算的節點再次進行請求。

第五步計算節點的節點調度模塊在兩條數據存儲隊列之間動態切換角色和向全局調度模塊請求計算任務數據。圖8中左側是節點調度模塊正在從當前處理隊列中調度數據塊給本節點中的CPU和GPU進行處理，節點中的數據緩存隊列為空。圖8中間是節點調度模塊發現本節點中的數據緩存隊列為空，并且本節點中的網絡帶寬處于空閑狀態，則開始向全局調度模塊請求數據，存入數據緩存隊列。圖8右側是當前處理隊列中的數據處理完畢，則數據緩存隊列的角色立刻轉變為當前處理隊列，開始向本節點中的CPU和GPU輸送數據進行處理。同時，節點調度模塊準備進行下一輪的網絡傳輸。

第六步計算節點內動態調度計算任務數據至CPU和GPU中協同并行計算。計算節點根據第三步計算的各節點及節點內GPU/CPU矩陣塊分配量信息，分發處理計算任務矩陣。圖7中的計算節點上的CPU的計算能力相對GPU來講一般比例較小，所以優先滿足CPU參與的并行計算需求矩陣塊。因此圖7中左側當第一次調度時，節點調度模塊檢查調度策略計算的CPU/GPU塊分配信息，如果有配額則調度一個數據塊到CPU上，循環調度多個數據塊到GPU上。圖7中間表示GPU處理完多個數據塊后，節點調度模塊根據調度策略塊分配信息，如果有配額，則再次調度多個數據塊到GPU上，如果無配額，則GPU運算結束。圖7右側表示緊接著CPU處理完一個數據塊后，節點調度模塊根據調度策略塊分配信息，如果有配額，則再次調度一個數據塊到CPU上，由于CPU計算性能較弱，在算法執行階段時刻保持一個塊任務在CPU上執行，如果無配額，則CPU運算結束。重復前述的步驟直到當前處理隊列為空。

第七步循環請求和處理任務數據。各計算節點循環執行第四步至第六步，直到全局調度模塊返回空數據集時，且當前處理隊列的數據全部處理完成后，當前計算節點計算任務完成，進而當各計算節點完成計算任務并返回，整個計算任務全部完成。

3 實驗結果與分析

本文算法的實驗環境同前文提到的4節點環境，網絡帶寬均為1000 Mb/s，其它硬件配置如下。

node1配置：

操作系統：CentOS Linux release v7.4

CPU：Intel Core i5-4590

GPU：NVIDIA Quadro 2000

內存：32 G

硬盤：SATA 6.0 Gbps 1 TB

node2配置：

操作系統：CentOS Linux release v7.4

CPU：Intel Xeon E5-2660 v3

GPU：NVIDIA GeForce TITAN Xp

內存：128 G

硬盤：SATA 6.0 Gbps 1 TB

node3配置：

操作系統：CentOS Linux release v7.4

CPU：Intel Xeon CPU E5-1603 v3

GPU：NVIDIA NVS 315

內存：32 G

硬盤：SATA 6.0 Gbps 1 TB

node4配置：

操作系統：CentOS Linux release v7.4

CPU：Intel Xeon CPU E5-1603 v3

GPU：GeForce GTX 1050 Ti

內存：32 G

硬盤：SATA 6.0 Gbps 1 TB

3.1 性能結果對比

在實驗環境中，單批次處理流式數據量(數據塊數)分別設置為0.64 G(40)、0.96 G(60)、1.28 G(80)、1.6 G(100)、1.92 G(120)、2.24 G(140)、2.56 G(160)共7種工況。本文對各工況單批次計算任務數據進行并行計算，并將使用基于兩級調度的CPU與GPU協同計算的動態調度算法與傳統的MPI/GPU并行計算性能測試結果進行對比，結果如圖9所示。

圖9 使用本文協同調度算法與傳統MPI/GPU 并行計算性能對比

傳統的MPI/GPU并行計算在數據分發與綜合利用計算資源參與并行計算時，沒有考慮各個節點計算資源的異構性，按“能者多勞”原則分配任務，同時未充分利用CPU參與并行計算，造成資源閑置。本文的算法針對以上的問題做出了很大的改進。從圖9中可以看出在處理多種單批次流式數據量的情況下，使用本文的協同調度算法效率是傳統MPI/GPU并行計算的計算效率的11倍左右，驗證了本文算法的有效性。

3.2 網卡I/O、GPU、CPU實時曲線分析

實驗中，在使用本文協同調度算法調度處理1.6 G的單批次流式數據，4個節點網絡I/O特征、GPU使用率特征和CPU使用率特征分別如圖10、圖11和圖12所示。

圖10 網絡I/O特征

網絡I/O特征如圖10所示。圖中橫坐標為時間，單位為s。縱坐標是網卡流量，單位為KB/s。實線為輸入流量，虛線為輸出流量。

從圖10可以看出，每個節點的網絡輸入和輸出流量相對均衡和穩定，在時間維度上基本呈現出均勻分布，網絡帶寬得到了有效合理的利用。同時性能較弱的節點會獲得較少的數據量，如3號節點。使用本文協同調度算法的網絡帶寬利用率比傳統的MPI/GPU并行計算的要高，是因為前者數據傳輸和數據處理是并行進行的，大幅度減少了網絡傳輸等待耗時。

GPU使用率特量如圖11所示。圖11中橫坐標是時間，單位是s；縱坐標是GPU使用率，單位是百分比(%)。

圖11 GPU使用率特征

從圖11可以看出，每個節點的GPU使用率在整個數據計算任務執行過程中基本滿負載。執行計算任務的時間大致相等，沒有出現長尾現象，GPU計算性能得到了最大程度的發揮。使用本文協同調度算法的GPU利用率比傳統的MPI/GPU并行計算的要高，4個節點幾乎同時開始了GPU并行計算，且結束時間趨于一致。

CPU使用率特量如圖12所示。圖12中橫坐標是時間，單位是s；縱坐標是CPU使用率，單位是百分比(%)。

圖12 CPU使用率特征

從圖12可以看出，節點1和節點2的CPU得到了充分的利用，參與了整個計算任務執行過程。節點3和節點4未參與并行計算，主要是因為全局調度模塊根據測試任務評估結果，計算得出節點3和節點4計算性能較弱，如果分配并行計算任務的矩陣塊，必然造成整個計算任務執行過程的長尾現象，所以，節點3和節點4CPU的主要任務為數據接收、數據預處理及計算結果整合與反饋。

從圖10、圖11和圖12中可分析得出使用本文支持異構集群的CPU/GPU協同調度算法與傳統MPI/GPU并行計算有如下改進：

(1)所有節點在計算任務分發開始時，幾乎同時開始了GPU和CPU的并行計算；

(2)所有節點在整個計算任務執行過程中，網絡傳輸負載相對比較均衡；

(3)所有節點的GPU得到了充分的利用；

(4)所有節點的CPU根據計算任務的性能評估，在不會造成計算任務長尾現象的情況下，共同參與了并行計算任務，充分利用了CPU多線程的并行計算性能。

將圖10、圖11和圖12與圖1、圖2和圖4進行對比分析，可以看出本文的CPU/GPU協同調度算法比傳統 MPI/GPU 并行計算框架具有更高的資源利用率。

4 結束語

本文介紹了在復雜異構的集群系統中對計算任務數據進行CPU與GPU協同計算的兩級動態調度算法。針對傳統MPI/GPU并行計算的節點能力預測不準確，任務分配不合理，任務執行耗時出現長尾現象，未考慮集群各節點資源的異構性等問題提出了改進方法。算法利用全局和節點兩級調度機制、計算資源性能測評、數據緩存/處理雙隊列等策略，在集群系統中進行“能者多勞”的全局任務分配，在節點內完成CPU和GPU的二次動態任務調度，有效避免了單節點計算性能的木桶短板效應而造成的任務長尾現象，集群系統的計算資源得到了合理有效的綜合利用，保證了系統的整體負載均衡性，有效提高CPU/GPU異構混合并行系統的整體并發度，減少計算任務的整體耗時。