不規(guī)則任務(wù)在圖形處理器集群上的調(diào)度策略

平 凡，湯小春*，潘彥宇，李戰(zhàn)懷

（1.西北工業(yè)大學(xué)計算機學(xué)院，西安 710129；2.工信部大數(shù)據(jù)存儲與管理重點實驗室（西北工業(yè)大學(xué)），西安 710129）

0 引言

隨著制造工藝的進步，計算機體系架構(gòu)發(fā)生了巨大變化，從單核處理器架構(gòu)逐步演變?yōu)槎嗪颂幚砥骷軜?gòu)。然而進入信息時代后，需要處理的計算也呈指數(shù)增長。面對海量數(shù)據(jù)存儲和計算，中央處理器（Central Processing Unit，CPU）難以滿足計算需求，圖形處理器（Graphics Processing Unit，GPU）由于其性能/成本效率比的優(yōu)勢被廣泛使用?，F(xiàn)階段，CPU-GPU異構(gòu)系統(tǒng)成為高性能集群的主流模式，CPU 和GPU 屬于不同類型的計算資源，分別負(fù)責(zé)不同類型的計算任務(wù)。CPU 負(fù)責(zé)執(zhí)行復(fù)雜邏輯處理和事務(wù)處理等計算，GPU 相較于CPU 具有眾多計算單元和簡單的緩存結(jié)構(gòu)，更適用于密集型的大規(guī)模數(shù)據(jù)并行計算，兩者相互配合能夠極大提升數(shù)據(jù)處理的計算速度［1］。

雖然GPU 可以提高大多數(shù)通用任務(wù)的計算性能，但是實際生產(chǎn)環(huán)境中經(jīng)常存在大規(guī)模的有限并行性作業(yè)，例如在線傳感器的過濾、交通攝像頭畫面的質(zhì)量檢測等。這些作業(yè)的并行度一般由注入數(shù)據(jù)的大小決定，計算復(fù)雜度由任務(wù)的計算模式?jīng)Q定。它們的最大特點是線程數(shù)一般小于1024，需要的存儲大小不超過2048 MB，任務(wù)與任務(wù)之間基本沒有依賴關(guān)系，這類任務(wù)被稱為不規(guī)則任務(wù)。針對這類大規(guī)模的不規(guī)則任務(wù)集合，如何減少任務(wù)的處理時間和提高GPU 資源利用率，是目前迫切需要解決的問題。

然而，現(xiàn)有的多數(shù)研究著重于將這類程序從CPU 移植到GPU 上進行，從而獲取程序并行化帶來的性能提升。由于GPU 和CPU 體系架構(gòu)的不同，現(xiàn)有的任務(wù)調(diào)度方法并沒有充分利用整個集群上GPU 之間的并行能力和GPU 處理器自身的并行能力，造成了GPU 計算資源的浪費，使得系統(tǒng)整體吞吐量并沒有大幅提高。

根據(jù)GPU 體系結(jié)構(gòu)的特點，其性能/成本效率比的優(yōu)勢會隨著計算任務(wù)并行度降低而降低。針對大規(guī)模的不規(guī)則任務(wù)集合，Parboil2 的測試結(jié)果顯示，傳統(tǒng)調(diào)度方式在GPU 資源方面的平均利用率只有20%～70%［2］。本文分析了現(xiàn)有的針對GPU 集群中調(diào)度不規(guī)則任務(wù)集合的策略，發(fā)現(xiàn)其未充分考慮GPU 計算特性、需求不規(guī)則特點以及如何實現(xiàn)GPU 共享等關(guān)鍵問題，從而導(dǎo)致系統(tǒng)的資源利用率不高。

針對使用GPU 集群加速大規(guī)模不規(guī)則獨立任務(wù)集合的調(diào)度問題，本文提出了一種新的調(diào)度框架GSF（GPU Scheduling Framework），采用統(tǒng)一計算設(shè)備架構(gòu)（Compute Unified Device Architecture，CUDA）流并行以及GPU 顯存細(xì)粒度共享的方式，使得不規(guī)則任務(wù)能夠在CPU-GPU 異構(gòu)高性能集群上高效地調(diào)度執(zhí)行。模型的輸入為一組并行度有限的不規(guī)則獨立任務(wù)，任務(wù)數(shù)目可達到上千，每個任務(wù)具有獨立計算數(shù)據(jù)并且GPU 計算資源的需求（包括顯存、線程等）均已知。GSF采用參數(shù)傳遞的方法將CPU線程與CUDA流［3］綁定，通過指定流編號將CPU 線程啟動的核函數(shù)添加到對應(yīng)流中執(zhí)行，在同一GPU 上形成了多任務(wù)并行的執(zhí)行流水線，有效實現(xiàn)了任務(wù)級別的并行和GPU 資源利用率的提升。然后，在模型基礎(chǔ)上，設(shè)計并實現(xiàn)了一種適配不規(guī)則獨立任務(wù)的調(diào)度算法，通過任務(wù)分組的方式合并不規(guī)則任務(wù)并調(diào)度到滿足資源需求的GPU 設(shè)備上執(zhí)行，以提升GPU 顯存利用率。最后，利用測試程序與現(xiàn)有調(diào)度算法進行比較以驗證本文所提出的調(diào)度策略的可行性和有效性。

1 相關(guān)工作

已有研究工作表明，異構(gòu)集群中GPU 任務(wù)的有效調(diào)度對于提高資源利用率和最小化執(zhí)行時間至關(guān)重要。文獻［4-5］分別設(shè)計了運行時的多任務(wù)調(diào)度框架，實現(xiàn)多任務(wù)共享GPU資源，但這些解決方案只關(guān)注單GPU 調(diào)度問題，無法擴展到集群環(huán)境中。文獻［6］為解決GPU 低利用率問題提出以線程束為基本單位虛擬化和動態(tài)調(diào)度GPU 的計算核心，通過持續(xù)運行一個內(nèi)核守護進程實現(xiàn)高利用率，但這種方法同樣無法擴展到集群環(huán)境。文獻［7］針對云環(huán)境運行執(zhí)行時間較短的GPU 任務(wù)問題，提出了一種基于優(yōu)先級的非搶占式先入先出（First In First Out，F(xiàn)IFO）任務(wù)調(diào)度策略，能夠減少平均響應(yīng)時間和總執(zhí)行時間，然而這種方法沒有實現(xiàn)多任務(wù)共享GPU，對資源利用率提升效果不明顯。一些研究工作［8-9］試圖通過改進硬件設(shè)計來提升GPU 資源利用率，比如文獻［8］動態(tài)地定制線程束以減少不規(guī)則應(yīng)用帶來的影響，這些方法都很難立即部署在現(xiàn)有GPU 上使用。因此，通用軟件方法［10-14］是解決問題的關(guān)鍵。文獻［11］分析了現(xiàn)有研究中調(diào)度不規(guī)則任務(wù)時忽略的關(guān)鍵因素，提出了一種兩級任務(wù)調(diào)度模型以實現(xiàn)在所有GPU 上計算資源的統(tǒng)一分配和共享，同時將計算數(shù)據(jù)重合的任務(wù)合并為任務(wù)組進行調(diào)度。這種模型能解決不規(guī)則任務(wù)帶來的負(fù)載不均和資源利用率低的問題，但調(diào)度大量獨立任務(wù)的效果并不突出。

異構(gòu)集群中的任務(wù)調(diào)度可根據(jù)是否存在相互依賴關(guān)系分為獨立任務(wù)調(diào)度和關(guān)聯(lián)任務(wù)調(diào)度，獨立任務(wù)調(diào)度又可分為在線模式和批處理模式，本文研究屬于獨立任務(wù)調(diào)度批處理模式，即提交的任務(wù)集合統(tǒng)一調(diào)度。經(jīng)典算法包括最小完成時間（Minimum Completion Time，MCT）算法［15］、Min-min 算法［16］和Max-min 算法［16］等。MCT 算法將每個任務(wù)分配到使其具有最早完成時間的處理器上計算，保證各處理器的負(fù)載均衡，但并非每個任務(wù)的實際執(zhí)行時間都是最小的。Min-min 算法核心思想是優(yōu)先調(diào)度具有最快執(zhí)行完成時間的任務(wù)，并將該任務(wù)映射到最快完成的處理器。Max-min 與Min-min 算法的思想正好相反，選取最大最早完成時間的任務(wù)優(yōu)先調(diào)度，可能造成短任務(wù)的調(diào)度延遲非常大。上述算法在計算調(diào)度方案時都只考慮任務(wù)執(zhí)行時間的因素，沒有考慮到如何提升GPU 資源利用率，很難適用于本文研究的不規(guī)則獨立任務(wù)集合場景。文獻［17］中針對利用GPU 加速計算的大量獨立任務(wù)提出了一種動態(tài)調(diào)度算法，能夠?qū)⑷蝿?wù)分散到CPU 或GPU 上執(zhí)行以減少總的執(zhí)行時間，但這種方法只適用于特定程序。

本文旨在設(shè)計實現(xiàn)一種通用的調(diào)度框架，按照合理的調(diào)度策略將不規(guī)則的獨立任務(wù)集合分散到集群中不同的GPU上計算，通過軟件機制實現(xiàn)多任務(wù)共享GPU 資源計算，目標(biāo)是實現(xiàn)GPU 資源利用率和任務(wù)處理效率的提升。首先，調(diào)度框架通過配置文件來設(shè)置輸入的任務(wù)詳情，可同時混合調(diào)度多種不同計算內(nèi)容的任務(wù)；其次，通過參數(shù)傳遞建立執(zhí)行節(jié)點CPU 線程和CUDA 流之間的聯(lián)系，CPU 線程加載的GPU 計算會加載到綁定的流中順序執(zhí)行，不僅實現(xiàn)了多任務(wù)并行而且避免多個任務(wù)計算相互影響；最后，調(diào)度算法中采用任務(wù)組的形式調(diào)度，能減少調(diào)度延遲并縮短總執(zhí)行時間。

2 調(diào)度框架設(shè)計與實現(xiàn)

2.1 GSF系統(tǒng)架構(gòu)

GSF 系統(tǒng)整體架構(gòu)如圖1 所示，運行在CPU-GPU 異構(gòu)集群上，整體上采用主從模式，由一個調(diào)度框架進程和多個執(zhí)行器進程組成。調(diào)度框架就是系統(tǒng)控制節(jié)點，負(fù)責(zé)集群管理和任務(wù)調(diào)度；其余節(jié)點為從節(jié)點，負(fù)責(zé)啟動并運行執(zhí)行器。調(diào)度框架會按照內(nèi)置的調(diào)度算法將用戶提交的任務(wù)集分發(fā)到選擇GPU 對應(yīng)的執(zhí)行器。執(zhí)行器在接收到任務(wù)后，將其加載到GPU 中計算。每個從節(jié)點可運行的最大執(zhí)行器數(shù)量與GPU設(shè)備數(shù)量相等。假如，某個從節(jié)點包含兩塊GPU，那么最多可運行兩個執(zhí)行器進程，節(jié)點上包含的CPU 計算資源會被平均分配。執(zhí)行器中采用操作系統(tǒng)提供的CGroup［18］的資源隔離功能，將計算資源與執(zhí)行器進程綁定，能防止執(zhí)行器間的資源競爭。

圖1 GSF系統(tǒng)架構(gòu)Fig.1 GSF system architecture

2.2 調(diào)度框架

調(diào)度框架由用戶接口、調(diào)度器和可感知GPU 的資源管理器［19-20］三部分組成。用戶通過接口提交任務(wù)信息，包括可執(zhí)行程序路徑、運行參數(shù)和GPU 資源需求等，接口負(fù)責(zé)將信息轉(zhuǎn)換為規(guī)定格式消息轉(zhuǎn)發(fā)給調(diào)度器?？筛兄狦PU 的資源管理器是調(diào)度框架運行的重要支持，通過周期性地從各個從節(jié)點收集資源來管理和監(jiān)控集群的資源狀態(tài)，包括CPU、內(nèi)存、磁盤和GPU 等，資源管理器以Resource Offer 方式向調(diào)度器分配當(dāng)前可用資源。當(dāng)調(diào)度器收到任務(wù)和資源信息，通過調(diào)度算法將任務(wù)與資源合理地匹配，以實現(xiàn)集群資源利用率和任務(wù)處理效率最大化。另外，調(diào)度器通過執(zhí)行器返回的狀態(tài)信息對任務(wù)進行監(jiān)控，當(dāng)某個任務(wù)出錯時立即重新調(diào)度。

2.3 執(zhí)行器

執(zhí)行器是運行在從節(jié)點的進程，根據(jù)調(diào)度框架發(fā)出的指令啟動和結(jié)束，由線程管理器、任務(wù)控制器、任務(wù)隊列和工作線程四個模塊構(gòu)成。執(zhí)行器的作用是將接收的任務(wù)加載到GPU 上計算，原因是GPU 程序需通過CPU 進程加載啟動，因此執(zhí)行器運行時只需利用CPU 資源。線程管理器負(fù)責(zé)在執(zhí)行器進程啟動后創(chuàng)建指定數(shù)量的工作線程，在進程結(jié)束前銷毀所有線程。任務(wù)控制器負(fù)責(zé)將接收的任務(wù)添加到任務(wù)隊列中，并監(jiān)控其執(zhí)行狀態(tài)，當(dāng)執(zhí)行成功或出錯時返回狀態(tài)信息給調(diào)度器。任務(wù)隊列是線程安全的，可同時被多個線程訪問，但一個任務(wù)只能被一個線程得到，隊列中的任務(wù)則按照到達的順序依次排列。工作線程是持續(xù)運行的多個CPU 線程，每個線程對應(yīng)一個CUDA 流，線程搶占到的任務(wù)會被添加到對應(yīng)的流中執(zhí)行核函數(shù)利用GPU計算。

執(zhí)行器的運行場景如圖2 所示，多個線程運行任務(wù)相當(dāng)于在多個CUDA 流中計算。每個流是一個順序操作隊列，不同流之間的計算是并行的。這種方式在保證GPU 中每個流執(zhí)行的任務(wù)所需資源被滿足的情況下，顯著提高資源利用率和任務(wù)處理效率。

圖2 多線程執(zhí)行示意圖Fig.2 Schematic diagram of multi-threaded execution

2.4 系統(tǒng)運行流程

調(diào)度模型按照以下步驟運行（步驟序號與圖1 中序號對應(yīng)）：

①各個執(zhí)行節(jié)點上的執(zhí)行器定時向可感知GPU 的資源管理器匯報當(dāng)前執(zhí)行器上的可用資源信息，包括GPU 可用顯存大小、可用內(nèi)存大小等；

②用戶通過接口向調(diào)度框架提交任務(wù)集合信息，包括任務(wù)類型、計算信息和資源需求等；

③接口將輸入的任務(wù)集合信息轉(zhuǎn)換為規(guī)定格式并發(fā)送給調(diào)度器；

④資源管理器收到資源變更，通知調(diào)度器當(dāng)前可用資源；

⑤調(diào)度器將根據(jù)內(nèi)置的調(diào)度算法將任務(wù)調(diào)度到可用的GPU計算資源對應(yīng)的執(zhí)行器；

⑥執(zhí)行器接收到任務(wù)后，首先將其添加到任務(wù)隊列；

⑦線程池中活躍的線程搶占隊列新添加的任務(wù)；

⑧搶占成功的線程將任務(wù)的核函數(shù)加載到對應(yīng)的CUDA流中執(zhí)行。

3 調(diào)度策略

3.1 問題描述

假設(shè)不規(guī)則獨立任務(wù)集由n個相互獨立的GPU 任務(wù)組成，每個任務(wù)都具有有限并行度，GPU 資源需求較低。定義T={t1，t2，…，tn} 代表任務(wù)集，每個任務(wù)可細(xì)化為ti={tid，tsize，tres}。其中：tid表示任務(wù)編號；tsize表示任務(wù)計算數(shù)據(jù)量大??；tres表示任務(wù)的資源需求，主要考慮任務(wù)的GPU 顯存需求。由于實際場景中，多個任務(wù)之間的資源需求和計算數(shù)據(jù)量都可能不同，認(rèn)為任務(wù)集合具有不規(guī)則特性。調(diào)度集合T時必須考慮GPU 任務(wù)的計算特性和資源需求，否則會造成GPU 資源浪費和負(fù)載不均衡。定義G={g0，g1，…，gm}代表GPU 處理器集合，組成一個分布式異構(gòu)GPU 計算集群，每個GPU 由向量gj={gid，gcapacity}表示。其中：gid表示GPU 處理器編號；gcapacity表示GPU 可用資源集合，可細(xì)化為gcapacity={gid，gmem，gcore}，分別代表GPU 編號、可用顯存和流多處理器等資源情況。

GSF研究的任務(wù)調(diào)度問題可以概括為：將集合T的n個任務(wù)按照策略分別調(diào)度到m個不同的GPU 上執(zhí)行，任務(wù)資源需求不同、沒有關(guān)聯(lián)依賴并且可以并行計算。調(diào)度目標(biāo)是實現(xiàn)高效的批量GPU 任務(wù)處理，保證了調(diào)度效率和顯存利用率的提升。定義S={s1，s2，…，sm}來表示最終的調(diào)度方案，可視為不相交的任務(wù)劃分問題，其中sj表示調(diào)度到第j塊GPU 上的任務(wù)集合，?si∩sj=?，?si，sj?T。

由于GPU 任務(wù)計算所需的資源和時間與輸入數(shù)據(jù)量正相關(guān)，若采用一般的調(diào)度策略很容易造成資源浪費，并造成任務(wù)執(zhí)行出錯。本文研究的調(diào)度算法就是針對這類不規(guī)則任務(wù)集合的調(diào)度問題，為了便于研究和實現(xiàn)，算法中忽略了寄存器、GPU數(shù)據(jù)傳輸寬度效率等因素的影響，認(rèn)為只要任務(wù)的顯存需求被滿足，對應(yīng)的GPU 就能將其正確執(zhí)行。原因是如果顯存未被滿足，任務(wù)會直接執(zhí)行出錯，而線程、流多處理器等資源未被滿足，只會造成延遲等待直到可以執(zhí)行。

3.2 針對不規(guī)則獨立GPU任務(wù)集的調(diào)度算法

一般情況下，采用貪心算法來調(diào)度不規(guī)則的GPU 任務(wù)集，按照任務(wù)編號順序依次將任務(wù)調(diào)度到第一個滿足顯存需求的GPU 上，每個任務(wù)調(diào)度后就更新對應(yīng)GPU 的可用資源情況，如此循環(huán)直到所有任務(wù)執(zhí)行完成。此算法邏輯簡單易于實現(xiàn)，但時間復(fù)雜度與可用GPU 數(shù)量和任務(wù)數(shù)量正相關(guān)，對于不規(guī)則任務(wù)集合來說，貪心算法可能無法得到最優(yōu)分配結(jié)果。假設(shè)存在兩個可用顯存分別為10 GB 和8 GB 的GPU，有6 個顯存需求分別為6 GB、3 GB、3 GB、2 GB、2 GB 和2 GB 的不規(guī)則任務(wù)。按照貪心算法進行分配，第一個GPU 上的任務(wù)為｛6 GB，3 GB｝，第二個GPU 上分配的任務(wù)是｛3 GB，2 GB，2 GB｝，6 個任務(wù)中將有1 個任務(wù)無法分配。如果按照｛6 GB，2 GB，2 GB｝、｛3 GB，3 GB，2 GB｝分配，則6個任務(wù)都可以正常執(zhí)行。

針對貪心算法存在的問題，將任務(wù)按照GPU 數(shù)量劃分為多個不相交的子集，分別調(diào)度到滿足資源約束的處理器上，在顯存滿足的前提下保證每個GPU 的計算單元被充分使用。本文提出了一種擴展貪心調(diào)度（Extended-grained Greedy Scheduling，EGS）算法，利用回溯搜索的思想將n個任務(wù)劃分成m個子集，根據(jù)顯存約束嘗試將任務(wù)添加到合適的子集中，保證每個子集的顯存之和不超過GPU 集群的顯存最小值，然后將子集整體調(diào)度到某個GPU 上計算。由于回溯劃分會得到多種調(diào)度方案，因此為每種方案計算一個負(fù)載權(quán)重，計算方法如式（1）所示：

其中：ti.mem表示第i個任務(wù)所需的顯存大??；gj.Mem表示第j個GPU 的顯存大小。負(fù)載權(quán)重等于每個GPU 已用顯存與可用總顯存比例的和，權(quán)重越大代表顯存資源越被充分利用。

另一方面，為了降低計算最優(yōu)解的時間復(fù)雜度，算法中設(shè)置了一個優(yōu)化算法的精度值β。利用β與任務(wù)數(shù)目相乘得到劃分子集的任務(wù)數(shù)目count，從任務(wù)集合中挑選count個任務(wù)按照上述步驟進行劃分，每次按照負(fù)載權(quán)重最大的方案調(diào)度，重復(fù)操作直到集合中所有任務(wù)都被調(diào)度。EGS算法將任務(wù)調(diào)度粒度從單個任務(wù)提升到任務(wù)集合，不僅能顯著提升GPU 的顯存資源利用率，還能降低任務(wù)集總執(zhí)行時間。EGS 算法的偽代碼如算法1所示。

算法1 擴展貪心調(diào)度算法。明了EGS 算法工作流程。算法中首先利用輸入的精度值β計算每次劃分子集的任務(wù)數(shù)目（第1）行），然后循環(huán)任務(wù)集合分別計算調(diào)度方案，直到所有任務(wù)均被調(diào)度算法結(jié)果（第2）行～第12）行）。在計算過程中，首先初始化變量和保存中間結(jié)果的數(shù)組（第3）行～第5）行），緊接著從T中隨機挑選count個任務(wù)組成T'（第6）行）并計算任務(wù)分組的顯存上限即集群中單個GPU 的顯存最小值（第7）行），然后調(diào)度divide 函數(shù)得到所有劃分方案和對應(yīng)的負(fù)載權(quán)重（第8）行）。在得到所有方案后，找出負(fù)載權(quán)重最重的方案（第9）行），將T'按照其結(jié)果進行調(diào)度（第10）行），最后從T中刪除此次計算中已被調(diào)度的任務(wù)進行下一次判斷（第11）行）。

EGS 調(diào)度算法的核心功能由divide 函數(shù)實現(xiàn)，核心思想是按照回溯遍歷思想將每個任務(wù)嘗試劃分到多個不同集合，最終得到多種不同的劃分方案。函數(shù)結(jié)束條件為是否遍歷到集合邊界，如到達邊界則利用式（1）計算此方案對應(yīng)的調(diào)度權(quán)重保存到weight數(shù)組對應(yīng)位置并結(jié)束此次遞歸。每個任務(wù)遞歸計算時，首先將GPU 集合按照當(dāng)前可用顯存降序排列，其目的是保證將任務(wù)優(yōu)先調(diào)度到當(dāng)前顯存使用率最低的GPU上。然后遍歷集合依次判斷是否能滿足任務(wù)的顯存需求，如滿足則添加到對應(yīng)的方案中遞歸處理下一個任務(wù)，不滿足則回退到上一層遞歸。該函數(shù)的偽代碼如算法2所示。

算法2 divide方法。

綜上所述，通過分組調(diào)度的思想，EGS算法有效地解決了不規(guī)則獨立GPU 任務(wù)集的調(diào)度問題，其時間復(fù)雜度為O(n*2count)，其中，n是集合包含的任務(wù)總數(shù)，count指由精度值確定的每次劃分子集的任務(wù)數(shù)目。

4 實驗與結(jié)果分析

4.1 實驗設(shè)置

為了分析本文所提出的調(diào)度算法，將其分別與貪心調(diào)度算法、MCT 調(diào)度算法和Min-min 調(diào)度算法進行對比。利用表1列舉的基準(zhǔn)程序進行評價，程序來源于一些實際應(yīng)用和GPU基準(zhǔn)集合，包括Rodinia、YOLOv3 和NVIDIA 編程指南［21］。實驗時通過一個隨機任務(wù)生成器混合指定數(shù)量和輸入配置的各類程序，得到最終的任務(wù)集提交到調(diào)度框架，集合中每個任務(wù)計算數(shù)據(jù)相互獨立、資源需求不同，滿足引言中提出的不規(guī)則獨立任務(wù)集合定義。

表1 基準(zhǔn)程序詳情Tab.1 Benchmark program details

實驗將部署在一個由8 臺NF5468M5 服務(wù)器組成的GPUCPU 異構(gòu)集群上，每個服務(wù)器由2 塊型號為Intel Xeon Sliver 4110的CPU，內(nèi)存為32 GB ECC Registered DDR42666，磁盤為2 TB 3.5"7200 r/min SAS硬盤；每個服務(wù)器中配置2塊型號為NVIDIA GeForceRTX 2080TI 的GPU，每塊GPU 的顯存大小為10989 MB；使用的CUDA版本為cuda_10.1.105_418.39。

4.2 評價指標(biāo)

實驗中將利用任務(wù)集合總調(diào)度時長和GPU 設(shè)備使用率、顯存使用率來評價算法的優(yōu)劣。

1）調(diào)度時長。GPU 任務(wù)的執(zhí)行效率，即時間越短效率越高，其計算方法為任務(wù)集初始提交到最后一個任務(wù)執(zhí)行完成整個過程的間隔時間。

2）設(shè)備使用率。由NVIDIA SMI工具測量得到，指采樣周期內(nèi)GPU 設(shè)備計算核函數(shù)的活躍時間占比，利用率越高代表該設(shè)備越活躍，初始時置為0。

3）顯存使用率。由NVIDIA-SMI工具測量得到，指此GPU當(dāng)前已用顯存與可用顯存的比例，利用率越高代表該GPU 資源越被充分利用，初始時置為0。

4.3 結(jié)果分析

4.3.1 EGS算法參數(shù)對比

從算法1的偽代碼可知，EGS算法初始根據(jù)精度值β與任務(wù)總數(shù)相乘得到每次劃分子集的任務(wù)數(shù)目，以降低算法的時間復(fù)雜度，精度值對調(diào)度結(jié)果具有重要影響。利用隨機任務(wù)生成器提交包含1000 個不同計算數(shù)據(jù)量的矩陣乘法任務(wù)組成的不規(guī)則GPU 任務(wù)集合來驗證不同β值對算法的影響。實驗設(shè)置如下：調(diào)度框架運行在主節(jié)點，集群的兩個從節(jié)點分別啟動2 個執(zhí)行器，并設(shè)置執(zhí)行器的并行任務(wù)數(shù)目為2。β數(shù)值分別設(shè)置為0.1、0.2、0.4 和0.6，每種數(shù)值情況運行任務(wù)集3次。圖3 給出了不同精度值對應(yīng)的評價指標(biāo)結(jié)果，每條曲線代表一個精度值對應(yīng)的集群GPU 平均顯存使用率變化和總執(zhí)行時長。

圖3 不同精度值的結(jié)果對比Fig.3 Comparison of results with different precision values

從圖3 可以看出，β設(shè)置為0.4 時，EGS 算法調(diào)度效果最優(yōu)，整體維持了較高的顯存使用率，并且總執(zhí)行時間最短。原因是每次劃分子集的任務(wù)數(shù)目為400，只需要3次劃分即可完成調(diào)度，每次劃分到單個GPU 上至多有50 個任務(wù)，GPU 的顯存資源被占滿的同時充分利用了其他計算資源，沒有資源競爭的沖突出現(xiàn)。當(dāng)β設(shè)置小于0.4，單次劃分的任務(wù)數(shù)目較少，導(dǎo)致GPU資源空閑浪費；當(dāng)β設(shè)置大于0.4，單次劃分任務(wù)數(shù)目較多，在單GPU 中產(chǎn)生了資源競爭，因此雖然顯存使用率較高，但總執(zhí)行時間較長。綜合來看，精度值β主要影響了任務(wù)集合循環(huán)次數(shù)和劃分子集遞歸次數(shù)，設(shè)置合理的β能充分發(fā)揮EGS算法調(diào)度優(yōu)勢。

另一方面，由于EGS屬于批處理調(diào)度模式，當(dāng)任務(wù)子集調(diào)度到某個節(jié)點所有任務(wù)可同時啟動。利用GSF 系統(tǒng)調(diào)度時，并行任務(wù)數(shù)目可具體表示為CUDA 流數(shù)目，不同流中任務(wù)并行執(zhí)行，核函數(shù)計算和數(shù)據(jù)傳輸并行隱藏了部分延遲開銷。并行度較低，無法充分利用GPU 資源；并行度較高，可能出現(xiàn)資源競爭問題。因此，采用由100 個不同輸入圖片檢測程序組成的不規(guī)則GPU 任務(wù)集合來驗證并行任務(wù)數(shù)目對算法的影響。實驗設(shè)置如下：調(diào)度框架運行在主節(jié)點，集群的兩個從節(jié)點分別啟動2 個執(zhí)行器，算法初始輸入的精度值固定為0.4，設(shè)置數(shù)目分別為1、2和4。每種情況運行三次，得到各項指標(biāo)策略的平均結(jié)果如圖4所示。

圖4 不同并行任務(wù)數(shù)目的結(jié)果對比Fig.4 Comparison of results with different numbers of parallel tasks

圖4（a）顯示了不同任務(wù)并行度對應(yīng)的集群GPU 平均設(shè)備利用率變化情況，圖4（b）顯示了不同任務(wù)并行度對應(yīng)的集群GPU 平均顯存利用率變化情況。當(dāng)任務(wù)順序執(zhí)行時，兩種利用率都保持在30%以下，造成了GPU 資源的空閑浪費。當(dāng)并行任務(wù)數(shù)目等于2時，顯存利用率維持在70%左右，GPU 設(shè)備被完全利用，集合總執(zhí)行時長最短。原因是2 兩個模型同時運行會充分利用資源，實現(xiàn)多任務(wù)并行效果，有效提升了執(zhí)行效率。當(dāng)并行任務(wù)數(shù)目等于4 時，顯存利用率最優(yōu)且維持在90%左右，設(shè)備利用率也處于較高數(shù)值，但執(zhí)行時長最長。原因是圖片檢測程序使用的寄存器、流多處理器資源較多，當(dāng)4 個模型同時在一個GPU 上檢測時會造成資源競爭使任務(wù)執(zhí)行阻塞，從而導(dǎo)致執(zhí)行時間較長。值得一提的是，實驗設(shè)置并行任務(wù)數(shù)目為5 時，任務(wù)會執(zhí)行出錯結(jié)束運行，因為此時分配到單個GPU 的任務(wù)顯存總需求超過其可用顯存，造成顯存溢出無法正確執(zhí)行。顯存和設(shè)備利用率變化不是正相關(guān)的，必須根據(jù)任務(wù)的資源需求確定合適的并行任務(wù)數(shù)目才能達到資源利用率和任務(wù)處理效率提升的平衡。

4.3.2 調(diào)度算法性能對比

為了進一步評價算法的性能利用優(yōu)勢，在相同實驗配置下將EGS 算法與貪心算法、MCT 算法和Min-min 算法整體對比，從不同測量指標(biāo)綜合評估算法性能。測試輸入為表1 介紹的三種基準(zhǔn)程序混合生成的獨立GPU 任務(wù)集合，該集合滿足不規(guī)則特點。通過隨機任務(wù)生成器提交任務(wù)集合到調(diào)度器，采用四種調(diào)度算法分別調(diào)度集合到GPU計算。

首先，設(shè)計實驗對比不同任務(wù)數(shù)目情況下各個調(diào)度算法得到的總執(zhí)行時長。具體設(shè)置如下：調(diào)度框架運行在主節(jié)點，集群的兩個從節(jié)點分別啟動2個執(zhí)行器，執(zhí)行器精度值β固定為0.4、并行任務(wù)數(shù)目固定為2，設(shè)置集合任務(wù)數(shù)目分別為250、500 和1000。每種情況運行3 次，測量得到各種指標(biāo)平均結(jié)果如圖5所示。

圖5 不同調(diào)度算法的執(zhí)行時長對比Fig.5 Comparison of execution time of different scheduling algorithms

從圖5 的執(zhí)行時長對比結(jié)果來看，隨著任務(wù)數(shù)量的增加四種算法的調(diào)度時長都保持增長，EGS 相較于其他策略具有明顯的性能優(yōu)勢，并且這種優(yōu)勢持續(xù)保持。任務(wù)數(shù)量等于250時，EGS的調(diào)度時長相較于其他三種調(diào)度算法分別減少為原來的39%、50%和59%；任務(wù)數(shù)量等于500時，EGS的調(diào)度時長相較于其他三種調(diào)度算法分別減少為原來的52%、59%和66%；任務(wù)數(shù)量等于1000 時，EGS 的調(diào)度時長相較于其他三種調(diào)度算法分別減少為原來的58%、64%和80%。對于不同的不規(guī)則GPU任務(wù)集合，EGS算法的效果都保持最優(yōu)，原因是EGS通過將不同數(shù)據(jù)規(guī)模的任務(wù)劃分到同一任務(wù)集合中整體調(diào)度，得到全局最優(yōu)調(diào)度方案，保證了多任務(wù)共享GPU 資源，有效發(fā)揮了GPU 的計算潛力，提升了任務(wù)處理效率。而其他三種調(diào)度算法都依次調(diào)度集合中的任務(wù)，將任務(wù)調(diào)度到最佳的GPU 上計算，調(diào)度結(jié)果只是局部最優(yōu)解，無法實現(xiàn)多任務(wù)共享GPU資源，造成了GPU資源的極大浪費。

接下來，通過實驗進行不同調(diào)度算法得到的GPU 利用率對比。具體設(shè)置如下：調(diào)度框架運行在主節(jié)點，集群的兩個從節(jié)點分別啟動2 個執(zhí)行器，執(zhí)行器精度值β固定為0.4、并行任務(wù)數(shù)目固定為2，固定集合任務(wù)數(shù)目為1000。利用隨機任務(wù)生成器提交集合，測量得到各種性能指標(biāo)的平均結(jié)果如圖6所示。

從圖6 中利用率變化曲線可以看出，EGS 在調(diào)度不規(guī)則獨立GPU 任務(wù)集合時集群整體的設(shè)備利用率和顯存利用率表現(xiàn)最優(yōu)，貪心調(diào)度的利用率表現(xiàn)最差。EGS 的設(shè)備利用率峰值可維持在100%，顯存利用率峰值可維持在95%，相較于其他三種常見的獨立任務(wù)調(diào)度策略具有明顯優(yōu)勢。原因是EGS算法在計算時將不同資源需求的不規(guī)則任務(wù)組合形成集合整體調(diào)度，單個集合的資源需求更大，多任務(wù)共享GPU 計算資源，能最大限度發(fā)揮GPU 的計算潛力。而其他三種調(diào)度算法都是以單個任務(wù)為粒度執(zhí)行調(diào)度，顯存資源的使用情況不規(guī)律、波動較大且空閑率較高。綜合執(zhí)行時長和GPU 資源利用率兩類指標(biāo)的測量結(jié)果來看，EGS 算法在調(diào)度不規(guī)則的獨立GPU任務(wù)集合時效果較好。

圖6 不同調(diào)度算法的資源利用率對比Fig.6 Comparison of resource utilization of different scheduling algorithms

5 結(jié)語

本文研究了CPU-GPU 異構(gòu)集群中不規(guī)則獨立任務(wù)的調(diào)度策略，通過分析GPU 任務(wù)的計算特點和多任務(wù)共享GPU 資源的運行機制，分析不規(guī)則獨立任務(wù)集合造成GPU 利用率低下的原因。在此基礎(chǔ)上，設(shè)計并實現(xiàn)了一種擴展貪心調(diào)度算法，將調(diào)度粒度提升至任務(wù)集合，為集群中各個GPU 分配能滿足資源需求的任務(wù)集合調(diào)度并運行，找到全局最優(yōu)的調(diào)度方案。另一方面，提出了一種基于線程池和CUDA 流實現(xiàn)的調(diào)度系統(tǒng)，結(jié)合調(diào)度策略能保證資源利用率和任務(wù)處理效率的提升。但本文研究還存在一些不足：目前只考慮了任務(wù)信息已知的靜態(tài)調(diào)度情況，無法反映實際生產(chǎn)環(huán)境中的調(diào)度，另外算法計算中只涉及顯存資源約束，對于流多處理器、寄存器等資源沒有考慮，可能造成同一GPU 中多個任務(wù)出現(xiàn)資源競爭問題。因此，未來要完善調(diào)度相關(guān)問題，進一步提升GPU資源利用率。