趙國亮，李云飛，王 川

（1.中國航天科工集團第二研究院706所，北京100854；2.航天恒星科技有限公司，北京100086）

0 引 言

傳統(tǒng)的任務(wù)調(diào)度算法大多是針對同構(gòu)系統(tǒng)設(shè)計的，沒有考慮計算單元之間架構(gòu)、處理能力以及通信帶寬的差異，很難在異構(gòu)系統(tǒng)上達到理想的效果。異構(gòu)多核系統(tǒng)的發(fā)展對任務(wù)調(diào)度算法提出了新的挑戰(zhàn)。

調(diào)度算法主要解決2方面的問題：把計算任務(wù)分配到合適的計算單元上以及安排每個計算單元上任務(wù)的執(zhí)行順序。調(diào)度算法要達到的目標(biāo)主要有完工時間最短、負載均衡、提高系統(tǒng)吞吐量等［1］。

1 研究背景

文獻 ［2－7］中提出了一些異構(gòu)多核系統(tǒng)的任務(wù)調(diào)度算法。這些算法可以分為3類：啟發(fā)式算法，隨機搜素算法，以及兩者混合的算法［1］。啟發(fā)式算法的基本思想就是根據(jù)經(jīng)驗或理論分析建立啟發(fā)規(guī)則，然后由啟發(fā)式規(guī)則指導(dǎo)問題求解。啟發(fā)式算法能夠在短時間內(nèi)得到調(diào)度結(jié)果，但調(diào)度結(jié)果的好壞依賴于啟發(fā)式規(guī)則，而不同類型的應(yīng)用程序通常需要不同的規(guī)則，因而其適應(yīng)性不強。遺傳算法是調(diào)度問題中使用最廣泛的隨機搜索技術(shù)，通過模仿生物進化過程，不斷迭代選擇，產(chǎn)生符合要求的結(jié)果。遺傳算法通常對不同類型的應(yīng)用都可以得到良好的調(diào)度結(jié)果，但是其時間復(fù)雜度比啟發(fā)式算法高得多［2］?；旌系恼{(diào)度算法通常先采用啟發(fā)式算法得到一個初始調(diào)度結(jié)果，然后通過隨機搜素算法對該結(jié)果進行優(yōu)化。混合調(diào)度算法的結(jié)合了兩者的特點，對于各種類型的應(yīng)用程序都能夠在相對較短的時間內(nèi)得到良好的調(diào)度結(jié)果［1］。

本文提出一種啟發(fā)式算法與遺傳算法混合的異構(gòu)多核系統(tǒng)任務(wù)調(diào)度算法—HSCGS（hybrid successor concerned genetic scheduling）［1］。算法的第1階段通過本文提出的列表啟發(fā)式算法—SCLS（successor concerned list scheduling），快速產(chǎn)生一個調(diào)度結(jié)果。然后通過一種針對調(diào)度問題改進的遺傳算法—IGA （improved genetic algorithm）對SCLS產(chǎn)生的調(diào)度結(jié)果進行優(yōu)化。本文將SCLS算法與StarPU 相結(jié)合，通過修改StarPU 調(diào)度引擎，實現(xiàn)了動態(tài)任務(wù)調(diào)度算法DSCLS （dynamic successor concerned list scheduling）。

2 HSCGS算法

本文提出了一種啟發(fā)式和遺傳算法混合的異構(gòu)多核系統(tǒng)任務(wù)調(diào)度算法HSCGS。算法的第1階段通過一種新的啟發(fā)式算法—SCLS，快速產(chǎn)生一個高質(zhì)量的調(diào)度結(jié)果。第2階段，通過遺傳算法對SCLS產(chǎn)生的調(diào)度結(jié)果進行迭代優(yōu)化。

2.1 SCLS算法

SCLS是一種列表啟發(fā)式算法，算法包括2個階段：為每個任務(wù)分配優(yōu)先級，為任務(wù)選擇合適的計算單元。

2.1.1 任務(wù)優(yōu)先級分配

根據(jù)任務(wù)的特點為DAG［1］中的每個任務(wù)計算優(yōu)先級。SCLS算法任務(wù)優(yōu)先級Priority（ni）計算公式如下

2.1.2 選擇計算單元

從任務(wù)隊列里面取出隊首任務(wù)，如果該任務(wù)沒有未調(diào)度的前驅(qū)任務(wù)，則為該任務(wù)選擇最合適的計算單元；如果該任務(wù)有為調(diào)度的前驅(qū)任務(wù)，則選擇為調(diào)度前驅(qū)中優(yōu)先級最大的，并為選中的任務(wù)選擇最合適的計算單元。最合適的計算單元選擇方法如下

其中m＝1…q，q是系統(tǒng)中計算單元總數(shù)，ni是當(dāng)前選擇的任務(wù)，succ（ni）是任務(wù)ni的后繼任務(wù)集合，cm（i，j）是指編號為i和j的任務(wù)間的通信量除以計算單元Pm與其他計算單元通信帶寬的均值。

2.2 IGA算法

這1節(jié)將詳細描述HSCGS的第2階段，即采用IGA［1］算法對啟發(fā)式算法調(diào)度結(jié)果進行優(yōu)化。

2.2.1 遺傳編碼和解碼

使用長度為v （任務(wù)數(shù)量）的一維整型數(shù)組G 進行編碼。數(shù)組下標(biāo)i表示任務(wù)編號，對應(yīng)位置的整型值j表示任務(wù)ni分配到計算單元Pj上執(zhí)行。編碼中不包含任務(wù)優(yōu)先級信息，任務(wù)的優(yōu)先級遵循SCLS算法中的優(yōu)先級分配結(jié)果。

在解碼階段，需要一維整型編碼G 和表示應(yīng)用程序的DAG 以及SCLS 算法中的優(yōu)先級分配結(jié)果。每次循環(huán)從SCLS算法的任務(wù)隊列中取出隊首任務(wù)，如果ni沒有未分配的前驅(qū)任務(wù)，則為任務(wù)ni選擇計算單元G ［i］；如果任務(wù)ni有未調(diào)度的前驅(qū)任務(wù)，則選擇其中優(yōu)先級最大的前驅(qū)任務(wù)nm，并將nm分配到計算單元G ［m］上執(zhí)行，直到任務(wù)隊列為空，解碼結(jié)束。

2.2.2 初始化

遺傳算法的初始種群包括SCLS算法產(chǎn)生的調(diào)度結(jié)果，假設(shè)種群規(guī)模為N，其余N－1個初始個體隨機生成，即編碼G 中的每個分量都是1到q之間的一個隨機數(shù)，其中q表示系統(tǒng)中計算單元的數(shù)量。種群規(guī)模的最小值為q。

2.2.3 適應(yīng)度計算

定義fitness為種群中個體的適應(yīng)度，表示調(diào)度結(jié)果的質(zhì)量。適應(yīng)度的計算方法如下

式中：makespan——完工時間 （調(diào)度總長度），即完工時間越短，個體的適應(yīng)度越高。

2.2.4 交叉和突變

（1）交叉：交叉運算作用于種群池中的2個個體 （稱為父個體），運算結(jié)果產(chǎn)生2 個新的個體 （稱為子個體），每個子個體包含了2個父個體中的信息。交叉操作的具體過程為：首先，在每個父個體上隨機選擇2個交叉點 （數(shù)組下標(biāo)）；然后交換父個體中交叉點之間的部分，這樣就產(chǎn)生了2個新的個體。

交叉運算發(fā)生的概率用PC表示，例如PC為0.8，則種群池中80%的個體進行交叉操作［8］。

（2）突變：突變運算作用于種群池中的單個個體，運算結(jié)果產(chǎn)生一個新的個體，子個體包含父個體中的部分信息以及部分新信息。突變操作的具體過程為：隨機選擇1個下標(biāo)，然后將該下標(biāo)位置的值變?yōu)?到p之間的1個隨機數(shù)，其中p表示系統(tǒng)中計算單元的數(shù)量。

突變運算發(fā)生的概率用Pm表示，例如Pm為0.5，則種群池中50%的個體進行突變操作。

2.2.5 預(yù)處理

遺傳算法種群形成過程中會產(chǎn)生一些非常相似的個體，這可能使算法陷入一個局部優(yōu)化的過程，這種現(xiàn)象通常稱為 “再生”。

為了避免 “再生”問題，在優(yōu)選之前，要進行對當(dāng)前種群進行預(yù)處理，合并一部分相似度過高的個體。

預(yù)處理的具體過程是：首先，計數(shù)器Counter初始為0，隨機選取種群中2個個體 （一維整型數(shù)組）；然后，掃描2個個體，發(fā)現(xiàn)對應(yīng)下標(biāo)處數(shù)值相同 （即同樣的任務(wù)分配到了同樣的計算單元上），計數(shù)器加1。掃描結(jié)束后計算相似度S

（一）多閱讀積累故事。每天在課每周我會用一節(jié)課時間，給同學(xué)們講故事，有時是我站在講臺上給同學(xué)們繪聲繪色手舞足蹈的邊說邊演；有時我把故事說完，會讓孩子根據(jù)故事中的角色進行表演，并且允許他們自行改編。這也為他們改變故事和給故事寫續(xù)集做好了充分的準(zhǔn)備。

式中：Length＝v，表示編碼長度。如果相似度S超過閾值T，則將選取的2個個體中適應(yīng)度較低的從種群里移除，否則不作處理。然后，再隨機選取2個未處理過的個體進行相似度檢測。

預(yù)處理發(fā)生的概率為PW，即預(yù)處理的個體數(shù)與種群規(guī)模比值為PW，PW＜ （PC＋Pm）。

2.2.6 優(yōu)選方法

本文的優(yōu)選方法，下一次迭代的初始種群由3部分組成，選擇過程如下：

首先，比較所有由交叉和突變產(chǎn)生的子個體與其父個體，如果子個體優(yōu)于父個體，將其放入下一次迭代初始種群，假設(shè)符合條件的為N1個。然后，如果N＞N1，令N2＝N－N1，選取當(dāng)前種群中適應(yīng)度前N2＊20%的個體，放入下一次迭代初始種群。最后，隨機選取當(dāng)前種群中N2＊80%的個體，放入下一次迭代初始種群。這樣下一次迭代初始種群中共有N 個個體。優(yōu)選過程結(jié)束，遺傳算法開始新一輪迭代。

2.2.7 結(jié)束條件

本文為了算法實現(xiàn)的簡便，采用的是迭代到MaxG 次后結(jié)束，MaxG 在算法開始前定義，其最佳值與應(yīng)用程序的特點以及硬件系統(tǒng)相關(guān)。

2.3 實驗結(jié)果及討論

本章將通過模擬實驗，比較 HSCGS 與 H2GS、HEFT、CPOP和DLS的各項性能指標(biāo)，從而展示HSCGS算法的優(yōu)勢。

2.3.1 性能指標(biāo)

（1）標(biāo)準(zhǔn)化的調(diào)度長度 （NSL）［9］，是指一個調(diào)度結(jié)果的實際調(diào)度長度除以調(diào)度長度的下限

調(diào)度長度的下限是指假設(shè)將關(guān)鍵路徑上的任務(wù)都分配到同一個計算單元上 （使關(guān)鍵路徑上任務(wù)執(zhí)行時間總和最小的計算單元）所有任務(wù)計算時間的總和。

（2）加速比 （Speedup），是指將所有任務(wù)分配到1 個最快的處理器上串行執(zhí)行的時間比上調(diào)度算法的完工時間

（3）算法效率 （Efficiency），假設(shè)計算單元數(shù)量為q，則算法效率計算公式如下

本文的實驗通過不同算法對多種DAG 的3種指標(biāo)的平均值對比來展示各個算法性能的優(yōu)劣。

2.3.2 實驗參數(shù)選擇

（1）計算單元數(shù)量q＝ ｛2，4，8，16，32｝；

（2）計算單元異構(gòu)系數(shù)Ph＝ ｛2，4，8，16｝；

（3）通信帶寬異構(gòu)系數(shù)Bh＝ ｛1，5，10，15｝；

（4）Pc＝0.7；Pm＝0.5；Pw＝0.8；

（5）種群大小PopSize＝2＊q；

（6）遺傳算法迭代次數(shù)G＝ ｛5，10，15，20｝。

2.3.3 結(jié)果及討論

實驗結(jié)果分2部分進行展示：第1部分是隨機生成的應(yīng)用程序DAG，第2部分是2種常用應(yīng)用程序—快速傅里葉變換和高斯消元法。

2.3.3.1 隨機生成的DAG 實驗結(jié)果

本實驗對于N 的每個取值隨機生成300 個DAG （共1500個DAG），分別計算H2GS、HSCGS、DLS、HEFT和CPOP 調(diào)度結(jié)果的NSL 和Speedup均值，結(jié)果如圖1、圖2所示。從結(jié)果可以看出，對于不同的應(yīng)用程序規(guī)模，HSCGS的結(jié)果與H2GS接近， 比 DLS、HEFT 和CPOP好。

圖1 隨機DAG 的NSL對比

2.3.3.2 常用應(yīng)用程序DAG 實驗結(jié)果

（1）快速傅里葉變換 （FFT）：FFT 算法DAG 的形式與其輸入抽樣點數(shù)有關(guān)，假設(shè)輸入抽樣點數(shù)為M，則DAG中的任務(wù)數(shù)N＝ （2＊M－1） （M＊log2M）。本實驗中M值為2至32，增量為2。圖3展示了不同輸入抽樣點數(shù)下的4種調(diào)度算法結(jié)果的平均NSL值。平均NSL從低到高為｛H2GS，HSCGS，HEFT，DLS，CPOP｝，其中 H2GS，HSCGS非常接近。

圖2 隨機DAG 的speedup對比

圖3 快速傅里葉變換的NSL對比

（2）高斯消元法：高斯消元法的DAG 與輸入矩陣規(guī)模相關(guān)，若輸入矩陣大小為M＊M，則DAG 的任務(wù)數(shù)N＝（M2＋M－2）／2，本實驗中采用的輸入矩陣規(guī)模為5 至20。圖4展示了對于不同的輸入矩陣規(guī)模，4種算法調(diào)度結(jié)果的平均NSL 值，從低到高排列為 ｛HSCGS，H2GS，HEFT，DLS，CPOP｝，其中HEFT 和H2GS相差很小。

圖4 高斯消元法的NSL對比

3 DSCLS算法

StarPU 是一個支持異構(gòu)多核架構(gòu)的運行時系統(tǒng)，不僅提供了異構(gòu)計算資源的統(tǒng)一視圖，還考慮到了計算任務(wù)在異構(gòu)系統(tǒng)上的高效映射和執(zhí)行，同時屏蔽了很多底層細節(jié)［10］。

StarPU 的2個主要特點是：①一個任務(wù)有多種實現(xiàn)，例如任務(wù)矩陣乘法要在一個由CPU 和GPU 組成的異構(gòu)系統(tǒng)上執(zhí)行，需要CPU 版本和GPU 版本2種實現(xiàn)；②計算單元間的數(shù)據(jù)傳輸是由StarPU 來完成的，對編程者是透明的。

圖5是StarPU 執(zhí)行任務(wù)流程概況，展示了StarPU 各模塊的功能及模塊間的關(guān)系。應(yīng)用程序首先提交任務(wù)，當(dāng)任務(wù)就緒后，調(diào)度器將其調(diào)度到其中一個設(shè)備上，然后設(shè)備執(zhí)行任務(wù)的合適實現(xiàn)版本，該任務(wù)執(zhí)行完后，其后繼任務(wù)就會被釋放，同時該任務(wù)的回調(diào)程序會被執(zhí)行。

圖5 StarPU 任務(wù)執(zhí)行流程

本文通過修改StarPU 的調(diào)度引擎，將靜態(tài)調(diào)度算法SCLS與StarPU 相結(jié)合，實現(xiàn)了動態(tài)調(diào)度算法DSCLS。

3.1 DSCLS算法概述

DSCLS算法的流程如圖6所示。

圖6 DSCLS算法流程

（1）應(yīng)用程序中通過StarPU 提供的標(biāo)簽API指定任務(wù)間的依賴關(guān)系；DSCLS根據(jù)標(biāo)簽構(gòu)建應(yīng)用程序的DAG 結(jié)構(gòu)圖，結(jié)構(gòu)圖中只包含任務(wù)間的依賴關(guān)系信息，沒有任務(wù)執(zhí)行時間及通信時間信息；

（2）StarPU 可以在每個任務(wù)執(zhí)行后記錄數(shù)據(jù) （在每個計算單元上的執(zhí)行時間和數(shù)據(jù)在計算單元間的傳輸時間），用以構(gòu)建基于歷史信息的性能模型，DSCLS通過性能模型估計任務(wù)的執(zhí)行時間和通信時間，并將這些數(shù)據(jù)填入DAG結(jié)構(gòu)圖，從而構(gòu)建完整的應(yīng)用程序初始DAG；

（3）DSCLS 根據(jù)應(yīng)用程序初始DAG 計算任務(wù)的優(yōu)先級；

（4）DSCLS選取優(yōu)先級最高的就緒任務(wù)，然后根據(jù)任務(wù)各實現(xiàn)版本與計算單元的 “適應(yīng)度”，為任務(wù)選擇最 “合適”的實現(xiàn)版本及計算單元，然后執(zhí)行任務(wù)；

（5）DSCLS通過任務(wù)的回調(diào)程序更新應(yīng)用程序初始DAG，然后重新計算任務(wù)的優(yōu)先級，再從就緒任務(wù)中選擇優(yōu)先級最高的進行調(diào)度執(zhí)行，直到應(yīng)用程序執(zhí)行結(jié)束。

3.2 基于StarPU 的DSCLS算法實現(xiàn)

3.2.1 StarPU 任務(wù)模型

StarPU 任務(wù)由執(zhí)行邏輯與數(shù)據(jù)句柄2部分組成。執(zhí)行邏輯包括任務(wù)的多個不同實現(xiàn)版本以及性能模型、功耗模型等信息。StarPU 使用數(shù)據(jù)句柄來管理任務(wù)所訪問的數(shù)控塊，追蹤數(shù)據(jù)在整個執(zhí)行期間的狀態(tài)。

只要編程者提供了對應(yīng)的實現(xiàn)版本，StarPU 任務(wù)就可以在任意多個計算單元上執(zhí)行，包括不訪問主存的協(xié)處理器 （如GPU）。StarPU 中使用結(jié)構(gòu)體starpu＿task來表示一個任務(wù)。StarPU 任務(wù)由執(zhí)行邏輯 （starpu＿codelet）與數(shù)據(jù)句柄 （starpu＿data＿handle＿t）2部分組成。執(zhí)行邏輯包括任務(wù)的多個不同實現(xiàn)版本以及性能模型、功耗模型等信息。StarPU 使用數(shù)據(jù)句柄來管理任務(wù)所訪問的數(shù)控塊，追蹤數(shù)據(jù)在整個執(zhí)行期間的狀態(tài)。

StarPU 通過任務(wù)標(biāo)簽 （starpu＿tag＿t）指定任務(wù)間的依賴關(guān)系。

3.2.2 StarPU 性能模型

性能模型用于預(yù)測任務(wù)的執(zhí)行和通信情況，對于動態(tài)任務(wù)調(diào)度算法用重要的指導(dǎo)作用。

要構(gòu)建性能模型，首先要決定模型需要依賴哪些信息，即如何表示性能模型。最主要的信息就是任務(wù)執(zhí)行邏輯和硬件架構(gòu)。例如在CUDA 設(shè)備上執(zhí)行矩陣乘法，可以在性能模型中用一個二元組＜Matrix Multiplication，CUDA＞來表示。為了更加準(zhǔn)確的表示性能，還需要加入任務(wù)所處理的數(shù)據(jù)規(guī)模?？梢杂靡粋€與數(shù)據(jù)規(guī)模相關(guān)的函數(shù)來表示，例如矩陣大小規(guī)模為S，在用三元組＜Matrix Multiplication，CUDA，O（S3／2）＞來表示在CUDA 設(shè)備上執(zhí)行規(guī)模為S的矩陣乘法。數(shù)據(jù)規(guī)模僅用數(shù)據(jù)總量來表示通常是不夠精確的，假設(shè)某任務(wù)處理大小為m＊n的矩陣時間復(fù)雜度為O（n2m），那性能模型必須能夠區(qū)分大小為1024＊512和512＊1024的矩陣。但是這些信息需要對任務(wù)執(zhí)行邏輯具有詳細的了解，很難在運行時自動獲取。

構(gòu)建性能模型的方式有多種，比較極端的方式就是編程者顯示的構(gòu)造。這需要編程者對應(yīng)用程序及底層硬件系統(tǒng)非常了解，而且每當(dāng)應(yīng)用程序或硬件發(fā)生變化，都需要重新構(gòu)造。

一種常見的方式是使用特定的預(yù)測程序來構(gòu)建性能模型。雖然這種方式適用于被廣泛使用的任務(wù) （如BLAS），但需要特定的測試套件及相應(yīng)輸入數(shù)據(jù)，還要編寫額外的程序。這種方式通常不考慮計算單元間的交互 （如共享緩存、總線競爭），對于異構(gòu)多核系統(tǒng)很難獲得可靠的預(yù)測結(jié)果。

在動態(tài)任務(wù)調(diào)度中，并不要求性能模型精度非常高，重要的是獲取任務(wù)和計算單元的匹配程度以及計算單元間的相對速度，以便在調(diào)度時選擇 “適當(dāng)”的策略。

StarPU 使用基于歷史執(zhí)行信息的性能模型。如圖7所示，性能模型的構(gòu)建過程包括3步：在任務(wù)執(zhí)行時，記錄任務(wù)實際執(zhí)行時間，并將記錄加入任務(wù)執(zhí)行日志 （表格）中；在進行調(diào)度時，按照任務(wù)簽名和數(shù)據(jù)規(guī)模查詢?nèi)蝿?wù)執(zhí)行日志，獲取記錄的執(zhí)行時間；為應(yīng)用程序提供性能反饋，更新對應(yīng)信息。

圖7 性能模型反饋循環(huán)

（1）記錄任務(wù)實際執(zhí)行時間。大部分處理器廠商都提供循環(huán)計數(shù)器，這樣記錄任務(wù)實際執(zhí)行時間就非常容易。對于缺少這種功能的處理器，StarPU 進行特殊處理。例如Cell處理器，需要將SPE 記錄的實際執(zhí)行時間與輸出數(shù)據(jù)一起傳輸給PPE。

（2）標(biāo)識任務(wù)執(zhí)行實例。StarPU 使用數(shù)據(jù)的布局和規(guī)模來唯一的標(biāo)識任務(wù)計算單元上的執(zhí)行實例。數(shù)據(jù)的布局用哈希值hdata表示。StarPU 使用k 元組 （n1，n2，…，nk）來標(biāo)識任意一個數(shù)據(jù)塊，k的具體數(shù)值與數(shù)據(jù)類型有關(guān)。如圖8所示，任務(wù)執(zhí)行邏輯為矩陣與向量做乘法，矩陣A 的布局用h（nx，ny）表示，向量X 與Y 的布局分別用h（nx）與h（ny）表示。這樣某個任務(wù)在一個計算單元上的執(zhí)行實例都可以用唯一的哈希值標(biāo)識，哈希值相同表示數(shù)據(jù)布局相同。

圖8 性能模型中任務(wù)執(zhí)行實例的唯一標(biāo)識

（3）查詢模型及反饋。每個任務(wù)在一個計算單元上的所有執(zhí)行實例都用一個二維表來記錄，表中的每一行記錄了＜數(shù)據(jù)布局，數(shù)據(jù)規(guī)模＞相同的所有實例的平均執(zhí)行時間、偏差和實例個數(shù)。任務(wù)提交后，StarPU 會根據(jù)＜任務(wù)名，計算單元＞確定性能模型中的一張二維表，然后計算其哈希值以定位表中的某一行，這樣就可以獲取該任務(wù)實例的平均執(zhí)行時間。該任務(wù)執(zhí)行完以后，StarPU 會根據(jù)任務(wù)的實際執(zhí)行時間更新表中的對應(yīng)行。

3.2.3 StarPU 調(diào)度引擎

異構(gòu)多核系統(tǒng)的任務(wù)調(diào)度問題是NP 完全問題，因此一般的調(diào)度策略都不能保證對于所有的應(yīng)用程序和硬件平臺都能得到較好的結(jié)果。StarPU 提供了一個調(diào)度引擎，可以方便的選擇各種已有調(diào)度算法和實現(xiàn)新的調(diào)度算法。

如圖9所示，StarPU 調(diào)度引擎的作用是將任務(wù)分派到各個計算單元上。從應(yīng)用程序的角度來看，任務(wù)被Push到調(diào)度引擎中；而從計算單元的角度來看，任務(wù)從調(diào)度引擎中Pop出來。調(diào)度引擎內(nèi)部的實現(xiàn)方式對應(yīng)用程序和計算單元來說都是透明的，既可以是最簡單的先進先出順序選擇計算單元，也可以是像HEFT 這樣復(fù)雜的調(diào)度算法。

圖9 StarPU 調(diào)度引擎

表1列出了部分StarPU 已經(jīng)實現(xiàn)的調(diào)度算法。Greedy策略就是在FIFO 隊列的基礎(chǔ)上加入優(yōu)先級信息，優(yōu)先級最高的任務(wù)排在隊首，最早被pop 到空閑的計算單元上。Greedy策略中所有任務(wù)都排列在一個中心隊列中，不利于多核環(huán)境下任務(wù)的并行。WS （work－stealing）策略具有多個任務(wù)隊列，如果中心隊列為空，調(diào)度引擎會將其他隊列中的任務(wù)pop到計算單元上。Greedy和WS在選擇計算單元時都沒有考慮到計算單元間的性能差異，不適用與異構(gòu)系統(tǒng)。StarPU 實現(xiàn)的HEFT 和DM 都是基于性能模型的，利用性能模型估測任務(wù)的執(zhí)行時間和通信時間，以任務(wù)最早完成時間最短為原則選擇計算單元，二者主要區(qū)別是DM 沒有考慮通信時間。

表1 StarPU 已實現(xiàn)的調(diào)度算法

3.3 DSCLS算法實現(xiàn)

StarPU 使用結(jié)構(gòu)體starpu＿sched＿policy來定義調(diào)度策略。只要實現(xiàn)結(jié)構(gòu)體中相應(yīng)的函數(shù)就可以實現(xiàn)自定義調(diào)度策略。

若要在應(yīng)用程序運行時采用自定義的調(diào)度策略，可以通過StarPU 運行時環(huán)境配置結(jié)構(gòu)體starpu＿conf，也可以通過修改環(huán)境變量STARPU＿SCHED 來實現(xiàn)。

SCLS算法主要包括2個步驟：計算任務(wù)優(yōu)先級和為任務(wù)選擇計算單元。DSCLS算法中任務(wù)的優(yōu)先級是動態(tài)變化的，在編譯時為任務(wù)確定初始優(yōu)先級，運行時每執(zhí)行完一個任務(wù)，都會根據(jù)實際執(zhí)行情況重新計算未調(diào)度任務(wù)的優(yōu)先級。

（1）初始化。StarPU 編譯應(yīng)用程序時根據(jù)Tag信息確定任務(wù)的前驅(qū)后繼關(guān)系，構(gòu)建應(yīng)用程序DAG 結(jié)構(gòu)圖。為了構(gòu)建完整的DAG 還需要將任務(wù)執(zhí)行時間和通信時間信息填入DAG 結(jié)構(gòu)圖。這些工作需要在調(diào)度引擎初始化時完成，即在init＿sched函數(shù)中實現(xiàn)。任務(wù)的平均執(zhí)行時間和平均通信時間可以從性能模型中獲取。

構(gòu)建完初始DAG 后就可以按照SCLS算法中的優(yōu)先級計算方法計算任務(wù)的初始優(yōu)先級，優(yōu)先級計算過程也在init＿sched函數(shù)中實現(xiàn)。

（2）選擇計算單元。計算引擎初始化結(jié)束后，選取任務(wù)隊列中優(yōu)先級最高的任務(wù)，然后按照SCLS算法計算適應(yīng)度的方式，計算每個＜計算單元，實現(xiàn)版本＞對的適應(yīng)度，選擇適應(yīng)度最大的進行調(diào)度。例如任務(wù)名為SEGMM的任務(wù)有3個實現(xiàn)版本，分別為SEGMM＿CPU、SEGMM＿CUDA、SEGMM＿OpenCL。計算平臺由2個GPU （編號：GPU0，GPU1）和一個8核CPU （編號：CPU0，……，CPU7）組成。其中＜GPU1，SEGMM＿CUDA＞適應(yīng)度最高，則在將SEGMM＿CUDA 分派到GPU1上執(zhí)行。

（3）反饋和更新。任務(wù)調(diào)度完以后，其實際運行時間已經(jīng)可以估算，該任務(wù)與其前驅(qū)的實際通信時間也可以估算。這時需要對DAG 進行更新，用實際測得的時間替換平均時間，并更新性能模型中的對應(yīng)記錄。DAG 更新完成后，算法會重新計算任務(wù)優(yōu)先級。

3.4 實驗

3.4.1 實驗環(huán)境

實驗環(huán)境為一臺惠普XV8600 服務(wù)器，由一個多核CPU 和2個GPU 組成，具體參數(shù)見表2和表3，操作系統(tǒng)為Ubuntu 10.04，StarPU 版本為1.0.4。

表2 CPU 參數(shù)

表3 GPU 參數(shù)

3.4.2 測試用例

本文實驗使用4 種測試用例來測試調(diào)度算法的性能：LU 分解、Cholesky分解、Monte－Carlo法求PI和BLAS中的GEMM 子程序。

（1）LU 分解。在線性代數(shù)中，LU 分解是矩陣分解的一種，可以將一個矩陣分解為一個下三角矩陣和一個上三角矩陣的乘積 （有時是它們和一個置換矩陣的乘積）。LU分解主要應(yīng)用在數(shù)值分析中，用來解線性方程、求反矩陣或計算行列式。

（2）Cholesky分解。在線性代數(shù)中，Cholesky分解是將一個正定Hermitian矩陣分解成為一個下三角陣和它的共軛轉(zhuǎn)置陣的乘積。

（3）GEMM （general matrix multiply）。GEMM 是BLAS （basic linear algebra subprograms）中的一組子程序，用于計算矩陣乘法，包括SGEMM （單精度）、DGEMM（雙精度）等等。

3.4.3 對比算法

本文實驗將DSCLS算法與StarPU 調(diào)度引擎中已經(jīng)實現(xiàn)的幾種調(diào)度策略進行對比。

（1）random：random 策略使用一個隊列 （先進先出）管理所有提交到調(diào)度引擎的任務(wù)，并且隨機選擇計算單元執(zhí)行任務(wù)。

（2）eager：eager策略就是在random 策略的基礎(chǔ)上加入了任務(wù)優(yōu)先級信息，使用一個優(yōu)先級隊列管理所有提交到調(diào)度引擎的任務(wù)，隨機選擇計算單元執(zhí)行任務(wù)。

（3）ws：ws（work stealing）策略默認將任務(wù)分派到執(zhí)行調(diào)度算法的計算單元，當(dāng)有計算單元空閑時，從負載最重的計算單元上遷移任務(wù)到檢測到第1個空閑計算單元。

（4）dm：dm 策略使用性能模型指導(dǎo)調(diào)度，依據(jù)任務(wù)最早完成時間選擇計算單元，只考慮任務(wù)執(zhí)行時間，忽略任務(wù)間通信時間。

（5）cpu－only：cpu－only策略以eager為基礎(chǔ)，選擇計算單元事只選擇類型為CPU 的計算單元。

（6）gpu－only：gpu－only策略以eager為基礎(chǔ)，選擇計算單元事只選擇類型為GPU 的計算單元。

3.4.4 性能指標(biāo)

本實驗中用于衡量算法性能的性能指標(biāo)如下：①程序運行時間，測試用例執(zhí)行開始到結(jié)束所用時間；②系統(tǒng)吞吐量，系統(tǒng)在單位時間內(nèi)所處理的數(shù)據(jù)量；③Speed，每秒處理的隨機點個數(shù)，只用于Monte Carlo法求PI。

本文實驗性能指標(biāo)的計算方式：每組程序重復(fù)運行12次，去掉最大值和最小值，其余10個取平均值。

3.4.5 實驗結(jié)果與討論

本文實驗使用多種數(shù)據(jù)規(guī)模、數(shù)據(jù)劃分塊數(shù)、任務(wù)調(diào)度算法來運行幾個基準(zhǔn)測試程序，記錄實驗數(shù)據(jù)并計算各個性能指標(biāo)。

LU 分解、Cholesky 分解和SGEMM 的矩陣規(guī)模｛256，512，1024，2048，4096｝，數(shù)據(jù)劃分塊數(shù) ｛4，16，64，256，1024｝。其中SGEMM 矩陣C 規(guī)模固定為1024＊1024，Monte Carlo法求PI的隨機點數(shù) ｛4＊Amount，8＊Amount，16＊Amount，32＊Amount，64＊Amount｝，Amount＝16＊1024＊1024。

實驗數(shù)據(jù)表明，對于4種基準(zhǔn)測試程序，DSCLS算法的任務(wù)完成總時間和系統(tǒng)吞吐量 （或Speed）都優(yōu)于其他幾種算法。

如圖10所示，隨著數(shù)據(jù)規(guī)模的增加LU 分解的完工時間不斷增漲，在整個變化過程中DSCLS調(diào)度算法的完工時間都是最短的，而且隨著數(shù)據(jù)規(guī)模的增大，DSCLS的優(yōu)勢越來越明顯。

圖10 LU 分解完工時間隨數(shù)據(jù)規(guī)模變化

接著，本文以LU 分解為例分析矩陣規(guī)模不變的情況下，數(shù)據(jù)劃分塊數(shù)變化對完工時間的影響。如圖11 所示，對于幾種數(shù)據(jù)分塊情況，DSCLS的完工時間都比其他幾種算法短。數(shù)據(jù)劃分塊數(shù)由4增加到256 的過程中，完工時間一直處于下降趨勢，當(dāng)數(shù)據(jù)劃分塊數(shù)增加到1024時，完工時間沒有繼續(xù)降低反而增高了。這是因為劃分塊數(shù)增加雖然可以增加程序的并行度，但同時會導(dǎo)致通信代價上升，劃分的塊數(shù)過多，任務(wù)間的通信代價的增長遠大于并行度增加所帶來的計算時間縮短，所以完工時間反而會增加。

圖11 數(shù)據(jù)劃分塊數(shù)對結(jié)果的影響

4 結(jié)束語

本文提出了一種新的混合式靜態(tài)調(diào)度算法—HSCGS，用于解決異構(gòu)多核分布式系統(tǒng)中的任務(wù)調(diào)度問題。

HSCGS算法分為2個大的階段。第1階段采用一種考慮后繼節(jié)點的列表啟發(fā)式算法—SCLS，生成一個近似的最優(yōu)解。第2階段采用改進的遺傳算法—IGA，對第1階段產(chǎn)生的調(diào)度結(jié)果進行迭代優(yōu)化，以產(chǎn)生最終的調(diào)度結(jié)果。

實驗結(jié)果顯示，HSCGS算法調(diào)度結(jié)果的與其他一種算法 （HEFT、DLS、CPOP）相比就有較明顯的優(yōu)勢。本文實驗還針對2種常用的標(biāo)準(zhǔn)程序 （快速傅里葉變換和高斯消元法），為4 種算法進行了對比測試。HSCGS 在平局NSL和算法并行效率2方面依然優(yōu)于其他一種算法。

本文通過修改StarPU 調(diào)度引擎，將SCLS 與StarPU相結(jié)合，實現(xiàn)了動態(tài)任務(wù)調(diào)度算法DSCLS，并通過與random、ws、dm、cpu－only等動態(tài)調(diào)度算法的對比實驗展示了DSCLS的性能優(yōu)勢。

本文基于DAG 的任務(wù)調(diào)度問題研究，是在任務(wù)劃分已經(jīng)完成的基礎(chǔ)上進行的，沒有對任務(wù)劃分方法進行研究分析，而任務(wù)劃分對后續(xù)的任務(wù)調(diào)度具有重要的影響，需要在今后的研究中彌補這一不足。

［1］Wang C，Gu J，Wang Y，et al.A hybrid heuristic－genetic algorithm for task scheduling in heterogeneous multi－core system［M］.Algorithms and Architectures for Parallel Processing.Berlin：Springer Berlin Heidelberg，2012：153－170.

［2］Kumar R，Tullsen DM，Jouppi NP，et al.Heterogeneous chip multiprocessors［J］.Computer，2005，38 （11）：32－38.

［3］Daoud MI，Kharma N.A hybrid heuristic－genetic algorithm for task scheduling in heterogeneous processor networks ［J］.Journal of Parallel and Distributed Computing，2011，71 （11）：1518－1531.

［4］Daoud MI，Kharma N.A high performance algorithm for static task scheduling in heterogeneous distributed computing systems［J］.Journal of Parallel and Distributed Computing，2008，68（4）：399－409.

［5］Wen Y，Xu H，Yang J.A heuristic－based hybrid genetic－variable neighborhood search algorithm for task scheduling in heterogeneous multiprocessor system ［J］.Information Sciences，2011，181 （3）：567－581.

［6］Eswari R，Nickolas S.Path－based heuristic task scheduling algorithm for heterogeneous distributed computing systems［C］／／International Conference on Advances in Recent Technologies in Communication and Computing.IEEE，2010：30－34.

［7］Kwok YK，Ahmad I.Static scheduling algorithms for allocating directed task graphs to multiprocessors［J］.ACM Computing Surveys，1999，31 （4）：406－471.

［8］Eiben AE，Hinterding R，Michalewicz Z.Parameter control in evolutionary algorithms ［J］.IEEE Transactions on Evolutionary Computation，1999，3 （2）：124－141.

［9］Bansal S，Kumar P，Singh K.An improved duplication strategy for scheduling precedence constrained graphs in multiprocessor systems［J］.IEEE Transactions on Parallel and Distributed Systems，2003，14 （6）：533－544.

［10］Augonnet C，Thibault S，Namyst R，et al.StarPU：A unified platform for task scheduling on heterogeneous multi－core architectures ［J］.Concurrency and Computation：Practice and Experience，2011，23 （2）：187－198.