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

胡 榮，馬軍生

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

0 引 言

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

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

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

圖1 層次化計(jì)算范式下的子任務(wù)完成時(shí)長(zhǎng)

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

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

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

1 初始方案及其啟示

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

表1 本文符號(hào)及定義

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

基于上述描述，本問(wèn)題可以定義如下

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

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

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

在實(shí)際的大規(guī)模分布式應(yīng)用中，系統(tǒng)狀態(tài)通常是定期收集的，且將子任務(wù)從源節(jié)點(diǎn)路由到IPN節(jié)點(diǎn)也會(huì)引入時(shí)延。因而，采集到的系統(tǒng)狀態(tài)數(shù)據(jù)可能是過(guò)時(shí)的、近似的，甚至還會(huì)有錯(cuò)誤存在。在這種情況下，不能假設(shè)在線運(yùn)行過(guò)程中所采集到的系統(tǒng)狀態(tài)數(shù)據(jù)是實(shí)時(shí)的、準(zhǔn)確的。已有研究人員發(fā)現(xiàn)，將任務(wù)直接分發(fā)給看起來(lái)負(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)層次化計(jì)算范式中，并設(shè)計(jì)了延遲感知的Power-of-D算法(tardiness-aware power-of-D，TPD)用于在線任務(wù)調(diào)度。

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

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

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

2.2 挑 戰(zhàn)

盡管在線任務(wù)調(diào)度與超市模型相似，兩者之間還是有一些關(guān)鍵性的區(qū)別。特別的，在層次化計(jì)算范式下應(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)要差。這是因?yàn)?，?jīng)典的Power-of-D總是按照均等概率選擇服務(wù)員，這會(huì)增加弱服務(wù)能力的IPN上子任務(wù)的排隊(duì)時(shí)長(zhǎng)，進(jìn)而增大異構(gòu)系統(tǒng)中顧客的滯留時(shí)間。此外，Power-of-D在異構(gòu)系統(tǒng)中對(duì)d的取值敏感，d取值不合適會(huì)導(dǎo)致顧客(負(fù)載)在服務(wù)員(服務(wù)節(jié)點(diǎn))上分布不均衡，這也會(huì)增長(zhǎng)顧客的滯留時(shí)間。

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

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

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

(10)

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

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

(11)

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

此外，為了保證負(fù)載均衡，還需要仔細(xì)計(jì)算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個(gè)候選IPN中，選擇符合如下條件的IPN節(jié)點(diǎn)k來(lái)服務(wù)子任務(wù)m

(15)

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

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

(16)

2.4 算法流程

將前面的設(shè)計(jì)綜合起來(lái)，設(shè)計(jì)了延遲感知的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是一個(gè)線性時(shí)間算法，算法的時(shí)間復(fù)雜度與IPN節(jié)點(diǎn)的數(shù)量成正比，即O(|K|)。 注意到，在實(shí)際系統(tǒng)中，IPN節(jié)點(diǎn)的數(shù)量通常較小，所以TPD算法可以高效工作。

3 性能評(píng)估

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

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

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

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

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

3.1 實(shí)驗(yàn)設(shè)定

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

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

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

3.2 算法性能

接下來(lái)驗(yàn)證TPD方法的有效性。

在平安校園場(chǎng)景中，考慮兩種子任務(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ù)了較短時(shí)間。在穩(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次。

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

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

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

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

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

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

圖3 穩(wěn)定模式下的平均處置時(shí)長(zhǎng)

圖4 突發(fā)模式下的平均處置時(shí)長(zhǎng)

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

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

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

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

(17)

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

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

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

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

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

4 結(jié)束語(yǔ)

本文研究了分布式應(yīng)用中的任務(wù)調(diào)度問(wèn)題。近年來(lái)，互聯(lián)網(wǎng)、移動(dòng)互聯(lián)網(wǎng)、物聯(lián)網(wǎng)飛速發(fā)展，分布式應(yīng)用產(chǎn)生的數(shù)據(jù)體量越來(lái)越大、異構(gòu)性越來(lái)越強(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)。在這種層次化計(jì)算范式下，任務(wù)完成時(shí)間受到網(wǎng)絡(luò)資源(路由時(shí)延)和計(jì)算資源(中間節(jié)點(diǎn)的計(jì)算能力、處理能力)的雙重約束，受到子任務(wù)的分配策略和調(diào)度策略的雙重影響。

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