層次化計算范式數(shù)據(jù)中心任務(wù)調(diào)度方法

胡 榮，馬軍生

(1.吉利學(xué)院 智能科技學(xué)院，四川 成都 641402；2.國防科技大學(xué) 信息通信學(xué)院，湖北 武漢 430000)

0 引 言

近年來，網(wǎng)絡(luò)帶寬不斷增長、通信成本不斷下降，分布式應(yīng)用產(chǎn)生的數(shù)據(jù)量越來越大，這一現(xiàn)象開始得到研究人員的關(guān)注[1,2]。在這些應(yīng)用中，如果源節(jié)點(diǎn)將原始數(shù)據(jù)直接發(fā)送給服務(wù)器，會給網(wǎng)絡(luò)基礎(chǔ)設(shè)施和服務(wù)器帶來極大壓力。為了緩解這一問題，一些研究[3-5]提出，可以在網(wǎng)絡(luò)中部署中間處理節(jié)點(diǎn)(intermediate processing nodes，IPNs)對原始數(shù)據(jù)做預(yù)處理，如壓縮、格式轉(zhuǎn)換、去噪等，再由中間處理節(jié)點(diǎn)將處理后的數(shù)據(jù)發(fā)送給服務(wù)器。在實際的大規(guī)模分布式應(yīng)用中，出于分而治之或負(fù)載均衡等方面的考慮，也常常部署一些性能較高的中間處理節(jié)點(diǎn)，對源節(jié)點(diǎn)產(chǎn)生的原始數(shù)據(jù)進(jìn)行預(yù)處理。本文將分布式應(yīng)用的這種分層的處理模式命名為層次化計算范式。

需要注意的是，分布式應(yīng)用中的一次任務(wù)通常包含多個子任務(wù)。比如，在層次化計算范式中，每個源節(jié)點(diǎn)產(chǎn)生數(shù)據(jù)并經(jīng)由IPN中繼到目標(biāo)節(jié)點(diǎn)的過程，都可以視為一個子任務(wù)。在分布式應(yīng)用中，這些子任務(wù)的預(yù)期完成時長和截止時間可能各不相同[6]，也很難保證所有的子任務(wù)都可以在截止時間之前完成[7]。與已有的研究保持一致[8]，本文試圖通過最小化所有子任務(wù)的總延遲來優(yōu)化分布式應(yīng)用的響應(yīng)時間。

如圖1所示，在層次化計算范式中，某個子任務(wù)的完成時長由3部分組成：子任務(wù)從源節(jié)點(diǎn)出發(fā)，經(jīng)由IPN到達(dá)目標(biāo)節(jié)點(diǎn)引入的路由時延；子任務(wù)在IPN上的處理時長；子任務(wù)在IPN上等待處理時，引入的排隊時長。為了簡便，本文將處理時長和排隊時長之和稱為處置時長。注意到，子任務(wù)的處理時長和路由時延依賴于子任務(wù)的分配策略，排隊時長則依賴于IPN的調(diào)度策略。子任務(wù)的分配策略和調(diào)度策略相互影響，導(dǎo)致路由時延、排隊時長和處理時長的聯(lián)合優(yōu)化并非易事。

圖1 層次化計算范式下的子任務(wù)完成時長

大規(guī)模IDC在不同維度、不同層面上存在異構(gòu)性。比如，為了滿足不同應(yīng)用的資源需求，IDC中往往部署有不同配置的主機(jī)；同時，IDC往往是增量化建設(shè)的，不同批次主機(jī)的配置也有不同。虛擬化IDC中的混布技術(shù)將資源需求不同的應(yīng)用(如在線應(yīng)用和離線應(yīng)用)部署在一起，因而應(yīng)用之間也存在異構(gòu)性。因此層次化計算范式中的中間處理節(jié)點(diǎn)往往是異構(gòu)的，它們的資源總量和處理能力各不相同。這種配置異構(gòu)性使得層次化計算范式中的總延遲最小化變得更加困難。比如，將子任務(wù)分配給處理能力最強(qiáng)的IPN，可以使得預(yù)期處理時長最小，但可能引入很大的路由時延；而將子任務(wù)分配給路由時延最小的IPN，則可能會引入較長的處理時長；此外，如果子任務(wù)在IPN節(jié)點(diǎn)之間分配不均，也可能導(dǎo)致高負(fù)載IPN上的排隊時長過大。

當(dāng)前，針對路由策略的研究[9,10]和針對調(diào)度策略的研究[11]已有很多。廣義來說，路由策略研究的是數(shù)據(jù)(子任務(wù))如何分配給服務(wù)節(jié)點(diǎn)；在子任務(wù)分配過程中，路由策略通常著眼于路由時延優(yōu)化，而不關(guān)注子任務(wù)在服務(wù)節(jié)點(diǎn)上的處置時長。調(diào)度策略研究的是服務(wù)節(jié)點(diǎn)處理數(shù)據(jù)(執(zhí)行子任務(wù))的次序；在決定子任務(wù)的執(zhí)行次序時，調(diào)度策略通常僅著眼于排隊時長優(yōu)化，而不關(guān)注其它。近年來，越來越多的研究開始關(guān)注路由策略和調(diào)度策略之間的相互關(guān)系[12-14]。但是，極少有研究關(guān)注層次化計算范式下的路由策略和調(diào)度策略的相互影響。

層次化計算范式近年來已經(jīng)廣泛出現(xiàn)在大規(guī)模分布式應(yīng)用中，比如分布式信息檢索或智慧城市。層次化計算范式是一個新興且重要的系統(tǒng)架構(gòu)，異構(gòu)層次化計算范式下分布式應(yīng)用的延遲最小化問題很值得研究。本文試圖回答以下問題：如何在異構(gòu)層次化計算范式下，最小化分布式應(yīng)用的總延遲?針對層次化計算范式下路由時延和處置時長的聯(lián)合優(yōu)化需求，并考慮了大規(guī)模應(yīng)用在線運(yùn)行時的實際情況，本文設(shè)計了一種延遲感知的Power-of-D任務(wù)調(diào)度算法(tardiness-aware power-of-dalgorithm，TPD)。最后，基于真實系統(tǒng)場景對上述算法進(jìn)行了性能評估，評估結(jié)果肯定了其有效性。

1 初始方案及其啟示

本小節(jié)給出了層次化計算范式下總延遲最小化的問題定義。表1總結(jié)了問題定義中所使用的符號及含義。

表1 本文符號及定義

某個子任務(wù)m在源節(jié)點(diǎn)產(chǎn)生后，會被中繼到一個且僅被中繼到一個資源總量可以滿足此子任務(wù)的IPN節(jié)點(diǎn)k上，即Qk≥qm。 子任務(wù)到達(dá)IPN后，若該IPN的剩余資源充足，則可以并發(fā)處理多個子任務(wù)；若剩余資源不足，則到達(dá)的子任務(wù)會在優(yōu)先級隊列中等候處理。這里假設(shè)IPN上的優(yōu)先級隊列沒有長度限制。此外，本文考慮子任務(wù)級別的調(diào)度策略，所以假設(shè)子任務(wù)的執(zhí)行過程不可被打斷。

基于上述描述，本問題可以定義如下

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

2 任務(wù)調(diào)度策略

在線運(yùn)行階段，借鑒已有研究經(jīng)驗，假設(shè)子任務(wù)按照泊松過程動態(tài)產(chǎn)生——這也是在線活動建模的常用方法。如算法1所示，在線任務(wù)調(diào)度是以事件驅(qū)動模式進(jìn)行的。具體而言，定期采集分布式應(yīng)用的狀態(tài)，并根據(jù)應(yīng)用狀態(tài)進(jìn)行任務(wù)調(diào)度。對于每個IPN節(jié)點(diǎn)k，子任務(wù)分發(fā)器(dispatcher)定期地采集系統(tǒng)中的傳輸時延ωik和ωkj(第4行)以及IPN的負(fù)載情況(第5行)。如果一個新的子任務(wù)m產(chǎn)生，分發(fā)器會選擇一個IPN節(jié)點(diǎn)k(第7行)，并將子任務(wù)m分發(fā)給k(第8行)。最后，IPN節(jié)點(diǎn)k按照一定的優(yōu)先級對其上的子任務(wù)進(jìn)行處理(第9行)。

算法1:在線任務(wù)調(diào)度流程

(1)repeat

(2) WaitForEvent(&event);

(3)ifevent isCollectInformationthen

(4) CollectLatency();

(5) CollectWorkload();

(6)elseifevent isSubTaskGenerationthen

(7) Select an IPNkto process the new sub-taskm;

(8) Dispatch sub-taskmto IPNk;

(9) IPNkschedules and processes sub-taskm;

(10)untilnomoresub-tasksaregenerated;

在實際的大規(guī)模分布式應(yīng)用中，系統(tǒng)狀態(tài)通常是定期收集的，且將子任務(wù)從源節(jié)點(diǎn)路由到IPN節(jié)點(diǎn)也會引入時延。因而，采集到的系統(tǒng)狀態(tài)數(shù)據(jù)可能是過時的、近似的，甚至還會有錯誤存在。在這種情況下，不能假設(shè)在線運(yùn)行過程中所采集到的系統(tǒng)狀態(tài)數(shù)據(jù)是實時的、準(zhǔn)確的。已有研究人員發(fā)現(xiàn)，將任務(wù)直接分發(fā)給看起來負(fù)載最輕的服務(wù)器上，可能導(dǎo)致系統(tǒng)性能顯著下降。因而，不能僅僅基于采集到的系統(tǒng)狀態(tài)數(shù)據(jù)進(jìn)行任務(wù)調(diào)度。本節(jié)將超市模型(supermarket model)中的Power-of-D范式擴(kuò)展到異構(gòu)層次化計算范式中，并設(shè)計了延遲感知的Power-of-D算法(tardiness-aware power-of-D，TPD)用于在線任務(wù)調(diào)度。

2.1 超市模型與Power-of-D范式

超市模型考慮的是這樣一個場景：顧客依次到達(dá)超市，而后加入到某個服務(wù)員前的隊列中；顧客的到達(dá)模型，是速率為n·λ(0<λ<1) 的泊松流，其中n是服務(wù)員的數(shù)量;所有服務(wù)員的服務(wù)速度相同；服務(wù)員按照先到先服務(wù)(first come first service，F(xiàn)CFS)的原則，依次服務(wù)其隊列中的顧客。超市模型旨在將顧客分配到最佳的服務(wù)員，使得顧客的期望滯留時長(expected sojourn time)最短。若將子任務(wù)視為顧客，將IPN視為服務(wù)員，子任務(wù)調(diào)度與超市模型非常類似。

超市模型的一個典型解決方案是Power-of-D范式。在Power-of-D范式中，每個新來的顧客按照均等概率隨機(jī)選取d個服務(wù)員，而后在選取的服務(wù)員中選擇顧客隊列最短的那個。有文獻(xiàn)[11]證明，d=2時用戶的平均滯留時間比起d=1時有指數(shù)級的改進(jìn)，而d=3時則僅比d=2時有常數(shù)級的改進(jìn)。因此，d通常取值為2，Power-of-D范式也通常被稱為Power-of-Two。Power-of-D在實際的大規(guī)模系統(tǒng)中成效顯著，是因為其在選擇服務(wù)員時引入了隨機(jī)性。這啟發(fā)作者在任務(wù)調(diào)度中也增加隨機(jī)因素。

2.2 挑 戰(zhàn)

盡管在線任務(wù)調(diào)度與超市模型相似，兩者之間還是有一些關(guān)鍵性的區(qū)別。特別的，在層次化計算范式下應(yīng)用Power-of-D范式面臨以下挑戰(zhàn)。

第一，是負(fù)載不均衡。在超市模型中，所有服務(wù)員的服務(wù)能力都是相同的，而IPN節(jié)點(diǎn)的資源總量和處理速度則各不相同。在異構(gòu)系統(tǒng)中，Power-of-D的表現(xiàn)比在同構(gòu)系統(tǒng)中的表現(xiàn)要差。這是因為，經(jīng)典的Power-of-D總是按照均等概率選擇服務(wù)員，這會增加弱服務(wù)能力的IPN上子任務(wù)的排隊時長，進(jìn)而增大異構(gòu)系統(tǒng)中顧客的滯留時間。此外，Power-of-D在異構(gòu)系統(tǒng)中對d的取值敏感，d取值不合適會導(dǎo)致顧客(負(fù)載)在服務(wù)員(服務(wù)節(jié)點(diǎn))上分布不均衡，這也會增長顧客的滯留時間。

第二，是最優(yōu)服務(wù)員的選取。經(jīng)典的Power-of-D范式中，每個顧客選擇隊列最短的服務(wù)員，以最小化該顧客的期望滯留時間(即層次化計算范式場景中的處置時長)。然而在層次化計算范式中，較短的隊列并不一定意味著較短的排隊時長，因為少量的長子任務(wù)可以占用IPN的大量資源和處理能力。此外，層次化計算范式中，不僅關(guān)注處置時長還關(guān)注路由時延，而超市模型則不關(guān)注路由時延(即顧客加入某個服務(wù)員的隊列所需的開銷)。

第三，是子任務(wù)的調(diào)度策略。Power-of-D只關(guān)注如何將顧客分配給合適的服務(wù)員，服務(wù)員則簡單地按照FCFS的規(guī)則提供服務(wù)。因為FCFS規(guī)則中的優(yōu)先級機(jī)制過于簡單(先到達(dá)的顧客的優(yōu)先級總是比后到達(dá)的顧客要高)，所以在優(yōu)化層次化計算范式中的子任務(wù)延遲時是低效的。比如，即使某個子任務(wù)馬上就要超過其截止時間了，它還是需要在隊列中等待它前面的子任務(wù)一一得到處理，這會增加任務(wù)的總延遲和分布式應(yīng)用的響應(yīng)時間。

2.3 應(yīng)對挑戰(zhàn)

(10)

表象處理速度表征了這樣一種現(xiàn)象：由于路由時延的存在，IPN節(jié)點(diǎn)的處理速度看起來變得比其實際處理速度vk慢；某個IPN節(jié)點(diǎn)引入的路由時延越長，子任務(wù)經(jīng)由該IPN處理并轉(zhuǎn)發(fā)所需的時間就越長，因而該節(jié)點(diǎn)的處理速度看起來就越慢。注意到，網(wǎng)絡(luò)中的路由時延會不斷變化，每個IPN節(jié)點(diǎn)的表象處理速度v′k也需要相應(yīng)的不斷更新。

通過定義表象處理速度，IPN節(jié)點(diǎn)k的抽樣概率可以表達(dá)為

(11)

式中：IPN節(jié)點(diǎn)k的抽樣概率與其表象處理速度v′k成正比。這樣，具有較高處理速度和較低路由時延的IPN節(jié)點(diǎn)被選中的機(jī)會就越大，避免了在低配置IPN節(jié)點(diǎn)上發(fā)生擁塞。

此外，為了保證負(fù)載均衡，還需要仔細(xì)計算d值。異構(gòu)超市模型中可以保證負(fù)載均衡的d值的緊下界(tight lower bound)和緊上界(tight upper bound)。其中，d值的下界表達(dá)為

dlower=(1-ε)·f(α,β)

(12)

上界表達(dá)為

dupper=(1+ε)·f(α,β)

(13)

在上述等式中，ε∈[0,1]

(14)

為了選擇最佳的IPN節(jié)點(diǎn)，在抽樣得到的d個候選IPN中，選擇符合如下條件的IPN節(jié)點(diǎn)k來服務(wù)子任務(wù)m

(15)

式中：Queuek表示IPN節(jié)點(diǎn)k上的優(yōu)先級隊列中的子任務(wù)集合。這樣，某個IPN節(jié)點(diǎn)負(fù)載越輕、處理速度越快、傳輸時延越短，子任務(wù)就越傾向于選擇它。通過選擇這樣的IPN節(jié)點(diǎn)，子任務(wù)的預(yù)期完成時長最短。

至于子任務(wù)調(diào)度策略，IPN從其隊列中優(yōu)先選擇處理符合如下條件的子任務(wù)i

(16)

2.4 算法流程

將前面的設(shè)計綜合起來，設(shè)計了延遲感知的Power-of-D算法(tardiness-aware power-of-D，TPD)。該算法的工作流程如算法2所示。

算法2：算法流程

(6) Calculatedaccording to Formula (12) and (13);

(7) Sampledcandidates with probability distribution F;

(8) Routemto the IPNksatisfying Formula (15);

(9) IPNkschedules and processes sub-taskmaccording to Formula (16);

可以看到，算法2是一個線性時間算法，算法的時間復(fù)雜度與IPN節(jié)點(diǎn)的數(shù)量成正比，即O(|K|)。 注意到，在實際系統(tǒng)中，IPN節(jié)點(diǎn)的數(shù)量通常較小，所以TPD算法可以高效工作。

3 性能評估

前面提到，層次化計算范式已經(jīng)出現(xiàn)在諸多應(yīng)用場景中，如分布式檢索、智慧城市等。本節(jié)在平安校園場景中對設(shè)計的方案進(jìn)行評估。平安校園場景的傳輸時延相對較小且較穩(wěn)定，因此子任務(wù)的處置時長占據(jù)了絕大部分完成時長。

本節(jié)在實際場景中對本文提出的解決方案進(jìn)行評估，并將其與其它3種算法進(jìn)行了對比。在評估過程中，試圖回答以下問題：第一，TPD能否有效優(yōu)化分布式應(yīng)用的總延遲？第二，TPD的性能與理論上的最優(yōu)方案之間的差距有多大？

性能評估的主要結(jié)果總結(jié)如下。

延遲優(yōu)化：評估結(jié)果表明，TPD可以顯著降低不同模式的子任務(wù)的平均路由時延、平均處置時長及總延遲。因而，TPD可以有效降低分布式應(yīng)用的響應(yīng)時間。

最優(yōu)性差距：為了明確TPD與理論上的最優(yōu)性能之間的差距，將其與離線最優(yōu)結(jié)果進(jìn)行對比，并定義了最優(yōu)性差距指標(biāo)。在實際場景下，TPD的最優(yōu)性差距比其它策略要小。上述結(jié)果肯定了TPD在在線調(diào)度場景中的有效性。

3.1 實驗設(shè)定

某平安校園系統(tǒng)部署在某大型校園中，該校園面積超過3 000 000平方米。校園中共部署有超過600個攝像頭(源節(jié)點(diǎn))、12個監(jiān)控點(diǎn)(IPN節(jié)點(diǎn))以及1個指揮中心(目標(biāo)節(jié)點(diǎn))。如圖2所示，校園中共有12個重點(diǎn)部位，如博物館、圖書館、教學(xué)樓等。為了更好監(jiān)控這些重點(diǎn)部位的情況，每個重點(diǎn)部位都部署有一個監(jiān)控點(diǎn)。特別的，編號為12的位置為該校主樓，主樓也是指揮中心所在的位置。每個監(jiān)控點(diǎn)都部署有一臺網(wǎng)絡(luò)視頻錄像機(jī)(network video recorder)。攝像頭將視頻片段和照片等發(fā)送到其中一臺網(wǎng)絡(luò)視頻錄像機(jī)上，網(wǎng)絡(luò)視頻錄像機(jī)則將這些視頻片段和照片進(jìn)行轉(zhuǎn)碼，并轉(zhuǎn)發(fā)給指揮中心。在指揮中心，這些視頻將被展示在大屏幕上，并被進(jìn)一步分析(比如火情監(jiān)控或入侵檢測等)。

圖2 平安校園系統(tǒng)平面圖

在該平安校園系統(tǒng)中，具體考慮一個入侵檢測應(yīng)用。攝像頭會自動檢測并拍攝移動物體，拍攝的視頻幀率為30 fps。根據(jù)大型的視頻分析數(shù)據(jù)集可知，時長為5 s到15 s之間的視頻片段足以檢測入侵。因此，在實驗中，假設(shè)視頻片段的長度為5 s到15 s之間(即150幀到450幀之間)。由于增量化部署策略，平安校園系統(tǒng)中的網(wǎng)絡(luò)視頻錄像機(jī)共有兩代，其中有8臺為高性能網(wǎng)絡(luò)視頻錄像機(jī)，4臺為低性能網(wǎng)絡(luò)視頻錄像機(jī)。高性能網(wǎng)絡(luò)視頻錄像機(jī)可以最多并行轉(zhuǎn)碼64路視頻片段，每路的平均轉(zhuǎn)碼速率為1200 fps；低性能網(wǎng)絡(luò)視頻錄像機(jī)可以最多并行轉(zhuǎn)碼32路視頻片段，每路的平均轉(zhuǎn)碼速率為600 fps。經(jīng)過實地測量，該平安校園中，任意兩個地點(diǎn)之間的路由時延在0.005 s到0.015 s之間。因此，在實驗中，將路由時延設(shè)定為lmk∈[0.005,0.03] s， 并假設(shè)路由時延與轉(zhuǎn)發(fā)路徑的長度成正比。

3.2 算法性能

接下來驗證TPD方法的有效性。

在平安校園場景中，考慮兩種子任務(wù)產(chǎn)生模式：穩(wěn)定模式和突發(fā)模式。穩(wěn)定模式描述了子任務(wù)產(chǎn)生的通常狀態(tài)，即子任務(wù)以穩(wěn)定地低速率產(chǎn)生。突發(fā)模式則描述了一些突發(fā)的子任務(wù)，即子任務(wù)的產(chǎn)生速率突然增大，但僅持續(xù)了較短時間。在穩(wěn)定模式下，設(shè)定：子任務(wù)數(shù)M=10000，子任務(wù)產(chǎn)生速率λ=0.7。在突發(fā)模式下，設(shè)定：子任務(wù)數(shù)M=600，子任務(wù)產(chǎn)生速率λ=5。每種子任務(wù)產(chǎn)生模式均運(yùn)行100次。

性能評估中，參與比較的算法如下所列。特別的，PoD、CRO和RND這3種算法中，IPN按照EDD(earliest due date first)策略調(diào)度其上的子任務(wù)。為了充分驗證算法性能，性能評估中，每種算法分別模擬運(yùn)行100次。

TPD：第3節(jié)設(shè)計的延遲感知的Power-of-D算法。

僅考慮處置時間優(yōu)化(Power-of-D，PoD)：經(jīng)典的Power-of-Two策略，即以均等概率隨機(jī)選取兩個IPN，而后將新的子任務(wù)分配給隊列較短的IPN上。Power-of-Two是一個典型的以最小化處置時間為目標(biāo)的策略。

僅考慮路由時延優(yōu)化(consider routing only，CRO)：一個在線版本的僅考慮路由時延優(yōu)化策略，先以均等概率隨機(jī)選取兩個IPN節(jié)點(diǎn)，而后將新子任務(wù)分發(fā)到具有較短路由時延的IPN上。

隨機(jī)(Random，RND)：每次將新子任務(wù)分發(fā)到一個隨機(jī)的IPN。

首先比較了處置時長。平安校園場景下，圖3和圖4分別比較了不同算法在入侵檢測應(yīng)用中，穩(wěn)定模式和突發(fā)模式下的子任務(wù)的平均處置時長。可以看到，TPD明顯優(yōu)于其它算法，因為TPD在任務(wù)調(diào)度中考慮了處置時長優(yōu)化。然而，PoD盡管也考慮了處置時長的因素，但是其表現(xiàn)與CRO相差無幾。這肯定了第2.2節(jié)的討論，Power-of-D范式在異構(gòu)系統(tǒng)中是低效的。

圖3 穩(wěn)定模式下的平均處置時長

圖4 突發(fā)模式下的平均處置時長

其次比較了路由時延。圖5及圖6分別展示了平安校園場景中不同模式下的子任務(wù)的平均路由時延。可以看到，TPD和CRO在兩種子任務(wù)模式下均優(yōu)于其它方案。這是因為在選擇最優(yōu)的IPN時，由于方程式(12)和方程式(13)，TPD通常會抽樣到多于2個備選IPN。因而，TPD比CRO更有可能找到更短的路由路徑，進(jìn)而產(chǎn)生更短的路由時延。

圖5 穩(wěn)定模式下的平均路由時延

圖6 突發(fā)模式下的平均路由時延

最后比較了總延遲及與最優(yōu)性差距。如圖7和圖8所示，TPD下子任務(wù)的總延遲最小。這說明TPD擅長調(diào)度不同模式的子任務(wù)。特別的，為了驗證TPD算法能否有效優(yōu)化分布式應(yīng)用的總延遲，還定義了最優(yōu)性差距Gap來量化算法的最優(yōu)性

(17)

式中：T是使用上述算法進(jìn)行任務(wù)調(diào)度時的總延遲，TLB是總延遲的下界。在線場景中，對于產(chǎn)生的每個子任務(wù)，都遍歷所有的IPN以確定全局最優(yōu)的IPN和全局最優(yōu)的子任務(wù)處理順序，進(jìn)而得到總延遲的下界TLB。如圖9和圖10所示，TPD的最優(yōu)性差距在任何情況下都比其它策略要小。上述結(jié)果肯定了TPD在在線調(diào)度場景中的有效性。

圖7 穩(wěn)定模式下的總延遲

圖8 突發(fā)模式下的總延遲

圖9 穩(wěn)定模式下的最優(yōu)性差距

圖10 突發(fā)模式下的最優(yōu)性差距

4 結(jié)束語

本文研究了分布式應(yīng)用中的任務(wù)調(diào)度問題。近年來，互聯(lián)網(wǎng)、移動互聯(lián)網(wǎng)、物聯(lián)網(wǎng)飛速發(fā)展，分布式應(yīng)用產(chǎn)生的數(shù)據(jù)體量越來越大、異構(gòu)性越來越強(qiáng)。所以，原始數(shù)據(jù)從源節(jié)點(diǎn)發(fā)出后，需要在中間處理節(jié)點(diǎn)上進(jìn)行預(yù)處理，再由中間處理節(jié)點(diǎn)將整合處理后的數(shù)據(jù)轉(zhuǎn)發(fā)給目標(biāo)節(jié)點(diǎn)。在這種層次化計算范式下，任務(wù)完成時間受到網(wǎng)絡(luò)資源(路由時延)和計算資源(中間節(jié)點(diǎn)的計算能力、處理能力)的雙重約束，受到子任務(wù)的分配策略和調(diào)度策略的雙重影響。

本文致力于在異構(gòu)層次化計算范式下，優(yōu)化分布式應(yīng)用的總延遲。具體地，設(shè)計了延遲感知的Power-of-D算法用于子任務(wù)的在線分發(fā)及調(diào)度，該算法將經(jīng)典的Power-of-D范式擴(kuò)展到了層次化計算范式中，可以實現(xiàn)任務(wù)路由時延、處理時長和排隊時長的聯(lián)合優(yōu)化。最后，基于真實系統(tǒng)場景，對本文提出的解決方案進(jìn)行了評估，評估結(jié)果肯定了本方案的有效性。