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

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

0 引言

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

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

2.2 調(diào)度框架

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

2.3 執(zhí)行器

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

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

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

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

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

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

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

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

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

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

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

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

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

3 調(diào)度策略

3.1 問(wèn)題描述

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

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

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

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

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

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

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

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

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

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

算法2 divide方法。

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

4 實(shí)驗(yàn)與結(jié)果分析

4.1 實(shí)驗(yàn)設(shè)置

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

表1 基準(zhǔn)程序詳情T(mén)ab.1 Benchmark program details

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

4.2 評(píng)價(jià)指標(biāo)

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

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

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

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

4.3 結(jié)果分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)語(yǔ)

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