劉永波 李亞瓊 周 博 李守超 宋云奎

（1.江蘇潤(rùn)和軟件股份有限公司 南京 210012）（2.中國(guó)科學(xué)院軟件研究所 北京 100190）

1 引言

機(jī)器學(xué)習(xí)是當(dāng)前越來(lái)越重要的大規(guī)模數(shù)據(jù)分析技術(shù)，廣泛應(yīng)用于在線搜索、市場(chǎng)營(yíng)銷、醫(yī)療保健和信息安全等領(lǐng)域。機(jī)器學(xué)習(xí)包括訓(xùn)練和推理等兩個(gè)階段，訓(xùn)練階段從訓(xùn)練數(shù)據(jù)集構(gòu)建機(jī)器學(xué)習(xí)模型，推理階段使用該模型對(duì)新輸入進(jìn)行預(yù)測(cè)。機(jī)器學(xué)習(xí)模型是輸入到輸出映射的近似函數(shù)，模型訓(xùn)練通常需要基于大規(guī)模數(shù)據(jù)集，經(jīng)過(guò)多次迭代計(jì)算，直到收斂。模型訓(xùn)練是探索性過(guò)程，通過(guò)反復(fù)訓(xùn)練調(diào)整超參數(shù)和模型結(jié)構(gòu)，生成最終模型［12］。該過(guò)程在開(kāi)始時(shí)生成一個(gè)低質(zhì)量的模型，并通過(guò)迭代訓(xùn)練改進(jìn)模型的質(zhì)量，隨著數(shù)據(jù)量的增長(zhǎng)，更多迭代的完成，訓(xùn)練與優(yōu)化的成本會(huì)不斷增加。由于機(jī)器學(xué)習(xí)的訓(xùn)練需要較高的時(shí)間和資源開(kāi)銷，機(jī)器學(xué)習(xí)工程師更傾向于在短時(shí)間內(nèi)使用較好的模型來(lái)進(jìn)行初步驗(yàn)證和測(cè)試。隨著大數(shù)據(jù)時(shí)代的到來(lái)，機(jī)器學(xué)習(xí)復(fù)雜度和數(shù)據(jù)量增長(zhǎng)速度遠(yuǎn)遠(yuǎn)超過(guò)硬件發(fā)展速度，小規(guī)模集群已無(wú)法滿足機(jī)器學(xué)習(xí)的物理資源需求。云計(jì)算平臺(tái)可以用來(lái)為多租戶提供共享物理資源，以高效執(zhí)行多個(gè)分布式機(jī)器學(xué)習(xí)模型的訓(xùn)練，云計(jì)算資源調(diào)度成為提高機(jī)器學(xué)習(xí)執(zhí)行效率與云計(jì)算資源利用率的關(guān)鍵技術(shù)［13］。

近年來(lái)，云計(jì)算資源調(diào)度工作主要包括以下幾類：在大規(guī)模機(jī)器學(xué)習(xí)框架方面，機(jī)器學(xué)習(xí)lib［1］，TensorFlow［2］，MXNet［3］，CNTK［4］優(yōu)化了模型訓(xùn)練過(guò)程中多維矩陣操作的計(jì)算資源分配，加快了訓(xùn)練過(guò)程，減少了任務(wù)同步的開(kāi)銷；在機(jī)器學(xué)習(xí)模型優(yōu)化方面，文獻(xiàn)［5］使用規(guī)劃算法發(fā)現(xiàn)超參數(shù)，并自動(dòng)排除錯(cuò)誤的測(cè)試，以加速模型的搜索過(guò)程；在任務(wù)執(zhí)行資源使用和運(yùn)行時(shí)間方面，Ernest［6］基于大規(guī)模數(shù)據(jù)分析的內(nèi)部計(jì)算和通信結(jié)構(gòu)預(yù)測(cè)任務(wù)執(zhí)行情況；CherryPick［7］使用貝葉斯優(yōu)化改進(jìn)云配置選擇的過(guò)程；在集群資源調(diào)度方面，文獻(xiàn)［8］主要關(guān)注資源公平、工作優(yōu)先級(jí)、集群利用率或資源優(yōu)化；在基于SLA的資源調(diào)度方面，Morpheus［9］基于完成作業(yè)的最后期限調(diào)度批處理作業(yè)，Jockey［10］將離線預(yù)測(cè)和動(dòng)態(tài)資源分配結(jié)合，以確保批處理查詢滿足延遲的SLA［14］，同時(shí)減少對(duì)共享集群的其他工作的影響。以上方法主要存在以下問(wèn)題：首先，對(duì)任務(wù)執(zhí)行進(jìn)行離線分析，當(dāng)用戶調(diào)試或調(diào)整模型時(shí)，計(jì)算結(jié)構(gòu)會(huì)經(jīng)常發(fā)生變化，并且?guī)?lái)巨大計(jì)算開(kāi)銷；其次，資源調(diào)度關(guān)注于單個(gè)任務(wù)的執(zhí)行情況和資源利用率，忽略了模型訓(xùn)練的整體任務(wù)完成質(zhì)量。

針對(duì)以上問(wèn)題，本文提出了一種面向分布式機(jī)器學(xué)習(xí)的云計(jì)算資源調(diào)度方法。根據(jù)歷史監(jiān)測(cè)數(shù)據(jù)建立迭代次數(shù)與模型質(zhì)量提升間的模型，在線預(yù)測(cè)資源分配對(duì)模型質(zhì)量提升的影響。制定資源分配策略，以達(dá)到在云計(jì)算平臺(tái)運(yùn)行的多個(gè)并發(fā)執(zhí)行的模型訓(xùn)練任務(wù)的整體性能最大化的目標(biāo)。實(shí)驗(yàn)結(jié)果表明，所提出的方法能夠提高資源利用率，快速適應(yīng)任務(wù)和負(fù)載的動(dòng)態(tài)變化。

2 資源調(diào)度方法

機(jī)器學(xué)習(xí)模型訓(xùn)練任務(wù)是反復(fù)迭代的過(guò)程，隨著迭代次數(shù)增加，模型訓(xùn)練的收益逐漸減小，因此，分配更多的資源給那些可能獲得更高收益的任務(wù)，可以提高整體的模型訓(xùn)練性能和資源利用率。本方法通過(guò)歷史數(shù)據(jù)建立迭代次數(shù)與模型質(zhì)量提升間的關(guān)聯(lián)模型以在線預(yù)測(cè)資源分配對(duì)模型質(zhì)量提升的影響，進(jìn)而制定資源分配策略以達(dá)到在云計(jì)算平臺(tái)運(yùn)行的多個(gè)并發(fā)執(zhí)行的模型訓(xùn)練任務(wù)的整體性能最大化的效果，從而提高資源利用率，快速適應(yīng)任務(wù)和負(fù)載的動(dòng)態(tài)變化。

在探索機(jī)器學(xué)習(xí)模型配置空間時(shí)，用戶通常會(huì)提交訓(xùn)練作業(yè)，監(jiān)測(cè)時(shí)間限制與損失價(jià)值。這兩種方法在實(shí)踐中都得到了廣泛的應(yīng)用，但也有明顯的缺陷。在時(shí)間限制方面，在固定的時(shí)間窗口內(nèi)訓(xùn)練機(jī)器學(xué)習(xí)模型通常會(huì)導(dǎo)致不可預(yù)測(cè)的質(zhì)量，這是因?yàn)橥ǔ：茈y預(yù)測(cè)在截止時(shí)間前的損失值。更重要的是，當(dāng)一個(gè)訓(xùn)練作業(yè)與其他作業(yè)共享集群資源時(shí)，截止時(shí)間完成的迭代次數(shù)也取決于集群的工作負(fù)載和調(diào)度器。在損失值方面，不同算法中的損失值是不同的，有完全不同的含義。另外，模型結(jié)構(gòu)和訓(xùn)練算法的復(fù)雜性，使得損失函數(shù)的收斂速度隨著隨機(jī)方法而變化，模型的穩(wěn)定程度不高。因此，在探索性的機(jī)器學(xué)習(xí)訓(xùn)練中，本文權(quán)衡多個(gè)并發(fā)作業(yè)之間的質(zhì)量運(yùn)行時(shí)，自動(dòng)化探索過(guò)程，避免了用戶對(duì)任意的權(quán)衡進(jìn)行推理。

在決定為不同模型訓(xùn)練任務(wù)分配資源之前，需要預(yù)測(cè)分配資源后模型訓(xùn)練任務(wù)所能夠提升的模型質(zhì)量，即任務(wù)在下個(gè)調(diào)度周期將會(huì)損失的收益。機(jī)器學(xué)習(xí)訓(xùn)練任務(wù)的執(zhí)行，是在分區(qū)數(shù)據(jù)集上進(jìn)行的。我將每個(gè)迭代的總CPU時(shí)間表示為c·S，其中c是由算法復(fù)雜度決定的常數(shù)，S是迭代中處理的數(shù)據(jù)的大小。從調(diào)度器可以收集到任務(wù)CPU時(shí)間和數(shù)據(jù)大小，這樣就能夠通過(guò)線性回歸的方法，從過(guò)去迭代的監(jiān)測(cè)數(shù)據(jù)中，學(xué)習(xí)常數(shù)c。那么，我們通過(guò)c·S/N可以預(yù)測(cè)一個(gè)迭代的運(yùn)行時(shí)，其中N是分配給該任務(wù)的任務(wù)CPU數(shù)量。進(jìn)一步，我們還需要預(yù)測(cè)將來(lái)幾次迭代中的收益損失減少，以評(píng)估模型質(zhì)量的提升。我們利用曲線擬合的方法，根據(jù)損失值的歷史來(lái)預(yù)測(cè)未來(lái)的損失。在近期獲得的損失值對(duì)于預(yù)測(cè)近期的損失價(jià)值更有幫助。當(dāng)新的迭代完成時(shí)，分配給損失值的權(quán)重會(huì)指數(shù)衰減，并且每個(gè)預(yù)測(cè)都調(diào)整了曲線方程的參數(shù)。在預(yù)測(cè)了分配一定資源的條件下收益損失值后，需要分配CPU以最大化提高多個(gè)模型的整體質(zhì)量提升。本文所提出的資源調(diào)度方法基于假設(shè)，所有并發(fā)運(yùn)行作業(yè)具有相同的重要性，這樣能夠平等對(duì)待比較收益損失的變化。同時(shí)，所提出的方法可以通過(guò)為損失值前邊乘以相應(yīng)的權(quán)重以對(duì)待不同重要性的作業(yè)。

算法1：面向分布式機(jī)器學(xué)習(xí)的云計(jì)算資源調(diào)度

輸入：T：調(diào)度周期；S：作業(yè)處理的數(shù)據(jù)量；totalRes：?jiǎn)卧Y源數(shù)量

輸出：｛aj｝，j=1，2，…，n（n為作業(yè)數(shù)量）

Lossj（aj）｛

iter=（T×aj）/（c×S）；

return（μk-b+c）；

｝

JobScheduling（All jobs）｛

for jobs do

aj=1；

totalRes=totalRes-1；

?j=Lossj(aj)-Lossj(aj+r)；

JobQueue.enqueue（job，?j）；

end for

while totalRes＞0 do

job=JobQueue.dequeue（）；

aj=aj+1；

totalRes=totalRes-1；

?j=Lossj(aj)-Lossj(aj+r)；

JobQueue.enqueue（job，?j）；

end while

return｛aj｝

｝

本文提出的面向分布式機(jī)器學(xué)習(xí)的云計(jì)算資源調(diào)度方法的執(zhí)行流程如算法1所示，具體包括以下步驟：

1）在線資源調(diào)度策略的制定，每隔T時(shí)間執(zhí)行一次，預(yù)測(cè)機(jī)器學(xué)習(xí)在將來(lái)的T時(shí)間內(nèi)執(zhí)行迭代次數(shù)為iter=（T×r）/（c×S），其中，c是由算法復(fù)雜度所決定的常數(shù)，S是每次迭代處理的數(shù)據(jù)量，r是分配的單位資源；

2）每個(gè)機(jī)器學(xué)習(xí)任務(wù)j在t時(shí)刻分配資源aj，定義收益損失函數(shù)為：Lossj（aj）=μiter-b+c，其中，iter為到t時(shí)刻的迭代次數(shù)，μ，b，c為常數(shù)，可以通過(guò)歷史迭代次數(shù)以及損失函數(shù)值計(jì)算求解；

3）為每個(gè)任務(wù)j分配單位資源r，預(yù)測(cè)資源分配后得到的收益損失值變化為?j=Lossj(aj)-Lossj(aj+r)，將該資源分配給收益損失值變化最大的任務(wù) j，更新aj=aj+r；

4）在滿足條件：∑jaj≤C，表示任務(wù)j分配資源aj總和不大于資源池中可分配資源的總量C下，重復(fù)第四步，從而達(dá)到臺(tái)并發(fā)執(zhí)行的J個(gè)任務(wù)在將來(lái)T時(shí)間內(nèi)的收益損失減少量最大化。

本方法通過(guò)歷史數(shù)據(jù)建立迭代次數(shù)與模型質(zhì)量提升間的關(guān)聯(lián)模型，能夠在線預(yù)測(cè)資源分配對(duì)模型質(zhì)量提升的影響；能夠從整體上考慮在云計(jì)算平臺(tái)運(yùn)行的多個(gè)并發(fā)執(zhí)行的模型訓(xùn)練任務(wù)的性能，提高資源利用率，快速適應(yīng)任務(wù)和負(fù)載的動(dòng)態(tài)變化。

3 資源調(diào)度框架

集群調(diào)度框架負(fù)責(zé)管理跨多個(gè)作業(yè)的資源分配，本文面向數(shù)據(jù)分析框架（如Hadoop、Spark）分為兩層調(diào)度：作業(yè)級(jí)別的調(diào)度器將資源分配給運(yùn)行在Worker上的并發(fā)作業(yè)，而任務(wù)級(jí)調(diào)度器則側(cè)重于將作業(yè)中的任務(wù)分配給可用的Worker?，F(xiàn)有的工作級(jí)別調(diào)度器（如Yarn［15］，Mesos［11］）主要根據(jù)資源公平或優(yōu)先級(jí)分配資源，那么，由于調(diào)度策略與作業(yè)中的質(zhì)量改進(jìn)無(wú)關(guān)，對(duì)于機(jī)器學(xué)習(xí)訓(xùn)練任務(wù)，調(diào)度器通常會(huì)做出次優(yōu)的調(diào)度決策。調(diào)度器應(yīng)該從每個(gè)作業(yè)中收集質(zhì)量和延遲信息，并動(dòng)態(tài)調(diào)整資源分配，以優(yōu)化集群范圍內(nèi)的質(zhì)量改進(jìn)。本文所提出的是一種細(xì)粒度的作業(yè)級(jí)調(diào)度器：關(guān)注于在競(jìng)爭(zhēng)的機(jī)器學(xué)習(xí)作業(yè)之間分配集群資源，需要在短時(shí)間間隔內(nèi)完成。短時(shí)間間隔的調(diào)度確保了跨作業(yè)的資源的持續(xù)再平衡，其迭代時(shí)間從幾十到數(shù)百毫秒不等。在一個(gè)共享的集群中，多個(gè)用戶不斷提交訓(xùn)練作業(yè)。公平調(diào)度作業(yè)在整個(gè)生命周期中都將獲得其公平的集群資源。如果在早期階段給了這個(gè)工作更多的資源，準(zhǔn)確性（損失）可能會(huì)更快地增加（減少），當(dāng)它的潛在改進(jìn)很大時(shí)，分配更多的資源。

圖1 面向機(jī)器學(xué)習(xí)的云計(jì)算資源調(diào)度框架

建立資源調(diào)度框架如圖1所示，調(diào)度器用來(lái)協(xié)調(diào)共享云計(jì)算資源的多個(gè)機(jī)器學(xué)習(xí)模型訓(xùn)練作業(yè)的資源分配。作業(yè)驅(qū)動(dòng)程序包含迭代訓(xùn)練邏輯，為每個(gè)迭代生成任務(wù)，并跟蹤作業(yè)的整體進(jìn)度。調(diào)度器與并發(fā)執(zhí)行作業(yè)的驅(qū)動(dòng)程序進(jìn)行通信，跟蹤作業(yè)進(jìn)度并定期更新資源分配。在每個(gè)調(diào)度階段的開(kāi)始階段，調(diào)度器根據(jù)作業(yè)的工作負(fù)載、資源需求和任務(wù)進(jìn)度分配資源。每個(gè)作業(yè)由一組任務(wù)組成，每個(gè)任務(wù)處理數(shù)據(jù)集分區(qū)上的數(shù)據(jù)。在機(jī)器學(xué)習(xí)模型訓(xùn)練中，任務(wù)根據(jù)數(shù)據(jù)集分區(qū)對(duì)模型參數(shù)進(jìn)行更新。當(dāng)任務(wù)完成數(shù)據(jù)處理，所有任務(wù)的更新結(jié)果聚集并發(fā)送回作業(yè)驅(qū)動(dòng)程序以更新機(jī)器學(xué)習(xí)模型。調(diào)度器也可以從一些作業(yè)驅(qū)動(dòng)程序中回收資源單元，并將它們分配給其他作業(yè)。本文使用云計(jì)算調(diào)度框架實(shí)現(xiàn)在Apache Spark，及其相應(yīng)的機(jī)器學(xué)習(xí)庫(kù)機(jī)器學(xué)習(xí)ib，云計(jì)算調(diào)度方法實(shí)現(xiàn)在Spark作業(yè)調(diào)度器中，訓(xùn)練數(shù)據(jù)集緩存在集群共享內(nèi)存中的Spark Dataframes，每次迭代處理訓(xùn)練數(shù)據(jù)。

本文采用令牌算法實(shí)現(xiàn)資源分配策略。令牌是在每個(gè)調(diào)度周期，加到每個(gè)作業(yè)的所有分配內(nèi)核的CPU時(shí)間。本文將任務(wù)分配給可用的Worker，并且通過(guò)搜集Spark的統(tǒng)計(jì)信息，跟蹤任務(wù)消耗的令牌數(shù)量。如果作業(yè)用完分派的相應(yīng)令牌數(shù)量，則任務(wù)執(zhí)行結(jié)束。采用Spark機(jī)器學(xué)習(xí)ib編寫(xiě)的機(jī)器學(xué)習(xí)應(yīng)用能夠直接在我們所提出的框架上運(yùn)行，而不必做任何改動(dòng)。我們的框架擴(kuò)展了底層優(yōu)化器（如隨機(jī)森林）的API，在每次迭代報(bào)告收益損失。因此，用戶只需要應(yīng)用定義好損失函數(shù)，暴露給框架所定義損失函數(shù)的API，框架即可以運(yùn)行，得到相應(yīng)的調(diào)度決策。

4 實(shí)驗(yàn)評(píng)價(jià)

實(shí)驗(yàn)環(huán)境是由10個(gè)阿里云的虛擬機(jī)實(shí)例構(gòu)建成的集群，每個(gè)資源單元包括2個(gè)vCPU，8GBRAM內(nèi)存，通過(guò)10G以太網(wǎng)連接。訓(xùn)練常用的機(jī)器學(xué)習(xí)模型，包括分類算法：支持向量機(jī)、神經(jīng)網(wǎng)絡(luò)、邏輯回歸；回歸算法：線性回歸，GBT回歸；無(wú)監(jiān)督學(xué)習(xí)算法：k均值聚類，LDA。運(yùn)行80個(gè)機(jī)器學(xué)習(xí)模型訓(xùn)練作業(yè)，以平均到達(dá)時(shí)間15 s的泊松分布將作業(yè)提交到集群。本文采用網(wǎng)上公開(kāi)數(shù)據(jù)集（Associat?ed Press Dataset-LDA.Retrieved 04/20/2017，URL：http：//www.cs.columbia.edu/～blei/lda-c）進(jìn)行機(jī)器模型的訓(xùn)練，所有的訓(xùn)練數(shù)據(jù)集緩存在Spark數(shù)據(jù)幀的共享內(nèi)存集群中。當(dāng)模型收益損失的標(biāo)準(zhǔn)化量低于閾值時(shí)，模型訓(xùn)練收斂，本文比較資源調(diào)度方法與公平調(diào)度策略之間的模型質(zhì)量提升效果。

首先，本文通過(guò)實(shí)驗(yàn)來(lái)表明所提出方法能夠從整體上減少收益損失。如圖2所示，將滑動(dòng)窗口大小設(shè)置為14min，每2min進(jìn)行一次資源調(diào)度，初始收益損失為0.2，由于本文方法的目標(biāo)是從減少云計(jì)算平臺(tái)上運(yùn)行模型訓(xùn)練作業(yè)的整體收益損失，經(jīng)過(guò)14分鐘訓(xùn)練，本文方法的收益損失為0.045，而公平調(diào)度方法為0.09，降低了約50%。

圖2 收益損失變化

而后，本文通過(guò)實(shí)驗(yàn)來(lái)測(cè)量完成不同的損失值所需要的時(shí)間。如圖3所示，本文方法將更多的資源分配給最有可能提高質(zhì)量的工作，進(jìn)一步迭代需要更長(zhǎng)時(shí)間，本文方法可以減少用戶得到較好模型的等待時(shí)間。

圖3 收益損失減少變化

最后，本文通過(guò)實(shí)驗(yàn)來(lái)觀察不同任務(wù)資源分配的變化情況。如圖4所示，本文根據(jù)作業(yè)收益的變化情況分為三組：第一組是具有較高收益損失的作業(yè)，占到作業(yè)總數(shù)的20%；第二組是具有中等收益損失的作業(yè)，占到作業(yè)總數(shù)的30%；第三組是具有較低收益損失的作業(yè)，占到作業(yè)總數(shù)的50%。相應(yīng)的，集群的CPU資源按比例分給三個(gè)組，本文方法將53%的計(jì)算資源分配給第一組20%的作業(yè)，將16%的計(jì)算資源分配給第三組50%的作業(yè)。本文方法將更多計(jì)算資源分配給最有可能改進(jìn)模型質(zhì)量的訓(xùn)練作業(yè)，因此，可以從整體上顯著改進(jìn)訓(xùn)練效果，減少收益損失。

圖4 各組作業(yè)資源分配比例

5 結(jié)語(yǔ)

本文提出了一種面向分布式機(jī)器學(xué)習(xí)的云計(jì)算資源調(diào)度方法。根據(jù)歷史監(jiān)測(cè)數(shù)據(jù)建立迭代次數(shù)與模型質(zhì)量提升間的模型，在線預(yù)測(cè)資源分配對(duì)模型質(zhì)量提升的影響。制定資源分配策略，以達(dá)到在云計(jì)算平臺(tái)運(yùn)行的多個(gè)并發(fā)執(zhí)行的模型訓(xùn)練任務(wù)的整體性能最大化的目標(biāo)。實(shí)驗(yàn)結(jié)果表明，所提出的方法能夠提高資源利用率，快速適應(yīng)任務(wù)和負(fù)載的動(dòng)態(tài)變化。