面向大數(shù)據(jù)任務(wù)的調(diào)度方法

李孜穎，石振國(guó)

（南通大學(xué)信息科學(xué)技術(shù)學(xué)院，江蘇南通 226001）

（*通信作者電子郵箱chinaemail@sohu.com）

0 引言

隨著近些年數(shù)據(jù)爆發(fā)式的增長(zhǎng)，越來(lái)越多的人將注意力集中到了大數(shù)據(jù)領(lǐng)域。大數(shù)據(jù)具有容量巨大、種類繁多、來(lái)源復(fù)雜、價(jià)值密度低等特征［1］，對(duì)此，市面上也出現(xiàn)了很多通用底層大數(shù)據(jù)系統(tǒng)來(lái)處理大數(shù)據(jù)，如Hadoop、Spark 等［2］。然而對(duì)于多數(shù)大數(shù)據(jù)系統(tǒng)，內(nèi)部任務(wù)的劃分標(biāo)準(zhǔn)不一，對(duì)大數(shù)據(jù)任務(wù)資源的分配也缺乏一定合理性，大數(shù)據(jù)任務(wù)處理流程存在不規(guī)范的問(wèn)題。因此，本文將任務(wù)調(diào)度理論引入到大數(shù)據(jù)任務(wù)處理中，幫助建立合理的大數(shù)據(jù)任務(wù)管理體系，從而規(guī)范大數(shù)據(jù)任務(wù)處理流程，提高大數(shù)據(jù)任務(wù)處理效率。

調(diào)度即是一種時(shí)間、空間上的排序。例如車站對(duì)班車的排班是一種調(diào)度，操作系統(tǒng)將進(jìn)程提交給中央處理器（Central Processing Unit，CPU）也是一種調(diào)度。大數(shù)據(jù)的處理過(guò)程也可以看作是一種任務(wù)調(diào)度，即根據(jù)實(shí)際的大數(shù)據(jù)任務(wù)和資源情況，將資源分配給相應(yīng)的大數(shù)據(jù)任務(wù)加以執(zhí)行的過(guò)程，而任務(wù)調(diào)度的關(guān)鍵則在于如何精準(zhǔn)地劃分任務(wù)以及合理高效地為任務(wù)分配資源。

任務(wù)調(diào)度問(wèn)題在許多不同領(lǐng)域中都有一定的研究［3-9］。例如，文獻(xiàn)［7］針對(duì)廣域信息管理系統(tǒng)，提出一種多服務(wù)質(zhì)量（Quality of Service，QoS）約束條件的蟻群優(yōu)化任務(wù)調(diào)度算法；文獻(xiàn)［8］針對(duì)移動(dòng)云計(jì)算中有向無(wú)環(huán)圖（Directed Acyclic Graph，DAG）模型的任務(wù)調(diào)度問(wèn)題，提出了一種能效任務(wù)調(diào)度算法；文獻(xiàn)［9］針對(duì)對(duì)等網(wǎng)絡(luò)環(huán)境，提出一種能有效利用網(wǎng)絡(luò)資源的基于相似度的任務(wù)調(diào)度算法等。

上述文獻(xiàn)均是對(duì)任務(wù)調(diào)度問(wèn)題的研究，但將任務(wù)調(diào)度理論與大數(shù)據(jù)相結(jié)合還不多見。本文將大數(shù)據(jù)任務(wù)的處理看作是一種任務(wù)調(diào)度，并以此為基礎(chǔ)，提出一種面向大數(shù)據(jù)任務(wù)的調(diào)度方法模型。本文工作主要有：

1）針對(duì)大數(shù)據(jù)任務(wù)劃分標(biāo)準(zhǔn)不統(tǒng)一、處理流程不規(guī)范的問(wèn)題，在大數(shù)據(jù)任務(wù)處理中引入任務(wù)調(diào)度理論，建立合理的任務(wù)管理體系，精準(zhǔn)劃分任務(wù)，規(guī)范任務(wù)流程，提高大數(shù)據(jù)處理效率。

2）針對(duì)大數(shù)據(jù)容量巨大、種類和來(lái)源復(fù)雜、噪聲多的問(wèn)題，引入粗糙集中的決策表屬性約簡(jiǎn)方法，提出一種基于互信息的大數(shù)據(jù)決策表約簡(jiǎn)模型，從而減少大數(shù)據(jù)分析任務(wù)的數(shù)據(jù)量，提高大數(shù)據(jù)分析效率。

3）針對(duì)大數(shù)據(jù)任務(wù)資源分配缺乏一定合理性的問(wèn)題，引入模糊數(shù)學(xué)中的模糊綜合評(píng)價(jià)方法，將模糊綜合評(píng)價(jià)的結(jié)果作為對(duì)任務(wù)分配資源的依據(jù)，提高任務(wù)資源分配合理性。

4）針對(duì)大數(shù)據(jù)任務(wù)的處理，提出一種面向大數(shù)據(jù)任務(wù)的調(diào)度方法模型，并給出算法具體流程和步驟，從而實(shí)現(xiàn)對(duì)大數(shù)據(jù)任務(wù)的調(diào)度。

5）將所提出的面向大數(shù)據(jù)任務(wù)的調(diào)度方法模型應(yīng)用在實(shí)際數(shù)據(jù)集中測(cè)試，并對(duì)測(cè)試結(jié)果進(jìn)行分析；實(shí)驗(yàn)結(jié)果表明，該調(diào)度模型能夠有效提高處理大數(shù)據(jù)任務(wù)的效率。

1 大數(shù)據(jù)任務(wù)分析及處理方法

1.1 大數(shù)據(jù)任務(wù)分析

在現(xiàn)代主流的大數(shù)據(jù)系統(tǒng)中，大數(shù)據(jù)任務(wù)通常用DAG 表示［10］，其中頂點(diǎn)是大數(shù)據(jù)任務(wù)，連接頂點(diǎn)的邊是大數(shù)據(jù)任務(wù)之間的關(guān)系。不可避免的，大數(shù)據(jù)任務(wù)間要共享集群資源，對(duì)此，按照什么樣的標(biāo)準(zhǔn)劃分大數(shù)據(jù)任務(wù)并為其分配資源就成為了一個(gè)十分重要的問(wèn)題。

在現(xiàn)代大數(shù)據(jù)系統(tǒng)中，通?？蓪⒋髷?shù)據(jù)任務(wù)分為四大類，即數(shù)據(jù)采集、數(shù)據(jù)處理與集成、數(shù)據(jù)分析以及數(shù)據(jù)解釋［11］。在大數(shù)據(jù)處理的過(guò)程中，由于經(jīng)過(guò)數(shù)據(jù)采集任務(wù)所得到的數(shù)據(jù)，其數(shù)據(jù)結(jié)構(gòu)各不相同，因此需要對(duì)采集到的數(shù)據(jù)處理成統(tǒng)一標(biāo)準(zhǔn)格式的數(shù)據(jù)，并將處理后的數(shù)據(jù)進(jìn)行存儲(chǔ)。數(shù)據(jù)完成預(yù)處理任務(wù)后，需要選用合適的數(shù)據(jù)分析方法對(duì)這些處理過(guò)的數(shù)據(jù)進(jìn)行分析，并通過(guò)可視化等技術(shù)，將數(shù)據(jù)分析的結(jié)果向用戶展示。

1.2 決策表的相關(guān)概念

決策表是用來(lái)描述和分析過(guò)程化決策情形的一種表格狀表示方式［12］。在決策表中，以行、列的形式來(lái)描述和表示決策規(guī)則和知識(shí)信息。決策表概念的系統(tǒng)化定義如下。

定理1設(shè)ai(i=1，2，…，m)表示可供選擇的決策行為，AS是ai的集合。θkj(j=1，2，…，n)是一個(gè)邏輯表達(dá)式，Sj表示θkj的集合。用xij表示實(shí)施決策ai后，自然狀態(tài)是θj的決策結(jié)果，xij={0，1}。決策表DT即可用來(lái)表示一個(gè)從θj到xij的映射。由定理1 可知，一個(gè)決策結(jié)果在決策表模型中是由一個(gè)或多個(gè)Sj表示的，即每一個(gè)xij對(duì)應(yīng)輸入的不同Sj，不同的Sj會(huì)形成不同的xij。

在定理1 所述經(jīng)典決策表模型中，只有行為和結(jié)果，對(duì)于一些復(fù)雜的系統(tǒng)，往往有多種不同的行為同時(shí)起作用，在這種情況下，不能僅僅考慮行為與結(jié)果，對(duì)此，有帶權(quán)重的決策表模型［13］如下：

定理2設(shè)Ai(i=1，2，…，m)表示可供選擇的第i個(gè)決策行為集，Sj(j=1，2，…，n)表示第j個(gè)結(jié)果集。用Xij表示決策集Ai對(duì)結(jié)果集Sj的權(quán)重集，且

引入變量P[j]表示各結(jié)果集發(fā)生的可能性，則

設(shè)閾值為q，則

1.3 基于互信息的大數(shù)據(jù)決策表約簡(jiǎn)模型

屬性約簡(jiǎn)又稱知識(shí)約簡(jiǎn)，是指為了保留最小屬性數(shù)的特征子集，在不改變知識(shí)庫(kù)分類能力的前提下，刪除冗余知識(shí)的過(guò)程［14］。當(dāng)前數(shù)據(jù)庫(kù)系統(tǒng)通?？梢詫?duì)數(shù)據(jù)進(jìn)行插入、查找、分類等操作，但是想要知曉數(shù)據(jù)間到底有著怎樣的內(nèi)在聯(lián)系卻很困難，而屬性約簡(jiǎn)可以更好地幫助發(fā)現(xiàn)數(shù)據(jù)其中的聯(lián)系［15-19］。

在決策表中，為了了解各種條件屬性對(duì)于決策重要性的影響，可以計(jì)算條件屬性與決策屬性間的互信息［20］，因此可以利用互信息對(duì)決策表進(jìn)行屬性約簡(jiǎn)。

根據(jù)式（6），可通過(guò)計(jì)算決策屬性D與條件屬性a之間互信息的大小，來(lái)衡量條件屬性對(duì)于決策的重要性?；バ畔⒅翟酱?，該屬性對(duì)于決策起到的重要性也就越大。對(duì)于決策表的約簡(jiǎn)，有下述定理：

定理3在相容決策表DT中，A?C，當(dāng)且僅當(dāng)MI(D：C)=MI(D：A)時(shí)，A是C相對(duì)于決策屬性集D的一個(gè)約簡(jiǎn)，且A相對(duì)于D是獨(dú)立的。［22］

根據(jù)定理3，本文提出基于互信息的大數(shù)據(jù)決策表約簡(jiǎn)算法，算法從初始的條件屬性集開始，循環(huán)并逐步刪去冗余屬性。本文算法具體步驟如下：

輸出DT的約簡(jiǎn)結(jié)果AR。

Step1 計(jì)算DT的互信息MI（D：C）。

Step2 從C中隨機(jī)選取一個(gè)條件屬性ai，計(jì)算出對(duì)于每一個(gè)ai∈C，其互信息MI(D：{ai})的值，并按照升序進(jìn)行排列。

Step3 令A(yù)R=DT，重復(fù)以下操作直至循環(huán)結(jié)束：

Step3.1 計(jì)算MI(D：AR-{ai})的值。

Step3.2 如果MI(D：C)=MI(D：AR-{ai})，ai可約簡(jiǎn)，令A(yù)R=AR-{ai}；反之，ai不可約簡(jiǎn)，AR不變。

Step4 循環(huán)結(jié)束，得到約簡(jiǎn)結(jié)果AR。

1.4 模糊綜合評(píng)價(jià)法

在模糊數(shù)學(xué)的所有綜合評(píng)價(jià)法之中，模糊綜合評(píng)價(jià)法是常用的一種方法。根據(jù)模糊數(shù)學(xué)中的隸屬度原理，模糊綜合評(píng)價(jià)法可以將對(duì)事物的定性評(píng)價(jià)轉(zhuǎn)變成對(duì)事物的定量評(píng)價(jià)，因此該方法也經(jīng)常用于為受到多種因素影響的事物進(jìn)行全面的綜合評(píng)價(jià)［23］。

針對(duì)大數(shù)據(jù)任務(wù)調(diào)度系統(tǒng)，任務(wù)的調(diào)度結(jié)果也是受多種因素影響，具有不確定性和模糊性，因此可用模糊綜合評(píng)價(jià)法來(lái)對(duì)任務(wù)進(jìn)行分類，將對(duì)任務(wù)評(píng)價(jià)的結(jié)果作為對(duì)任務(wù)進(jìn)行調(diào)度的結(jié)果。

模糊綜合評(píng)價(jià)步驟［24］如下：

1）確定評(píng)價(jià)對(duì)象。

2）確定評(píng)價(jià)指標(biāo)集U。

評(píng)價(jià)指標(biāo)集是指評(píng)價(jià)者對(duì)被評(píng)價(jià)對(duì)象進(jìn)行評(píng)價(jià)所依照的評(píng)價(jià)指標(biāo)的集合，可能會(huì)存在多級(jí)指標(biāo)，且U={u1，u2，…，un}。

3）確定評(píng)價(jià)等級(jí)（評(píng)語(yǔ)集）V。

不同的評(píng)價(jià)者對(duì)不同的評(píng)價(jià)對(duì)象可能會(huì)有不同的評(píng)價(jià)等級(jí)。評(píng)語(yǔ)集就是這些所有可能的評(píng)價(jià)結(jié)果的集合。且V={v1，v2，…，vm}。

4）確定評(píng)價(jià)指標(biāo)的權(quán)重W。

各評(píng)價(jià)指標(biāo)的權(quán)重大小，反映了各評(píng)價(jià)指標(biāo)對(duì)于評(píng)價(jià)結(jié)果的重要程度大小。由于各評(píng)價(jià)指標(biāo)權(quán)重大小的不同，可能導(dǎo)致最終得到的評(píng)價(jià)結(jié)果差異很大，因此如何確定評(píng)價(jià)指標(biāo)的權(quán)重是模糊綜合評(píng)價(jià)中至為關(guān)鍵的一步。權(quán)重W=(w1，w2，…，wn)，且各評(píng)價(jià)因素的權(quán)重總和為1，即1(wi＞0)。

常用的確定權(quán)重的方法主要有德爾菲法確定權(quán)重法、層次分析（Analytic Hierarchy Process，AHP）確定權(quán)重法、熵值確定權(quán)重法等。

德爾菲法確定權(quán)重法［25］是根據(jù)專家的知識(shí)、經(jīng)驗(yàn)、綜合分析能力等，對(duì)各項(xiàng)評(píng)價(jià)指標(biāo)判斷、分析并為其賦予權(quán)值，該方法是最常用的確定權(quán)重方法。

將定性與定量相結(jié)合是AHP［26］的特點(diǎn)，核心是定量描述決策者的經(jīng)驗(yàn)和判斷，增強(qiáng)決策依據(jù)，提高決策準(zhǔn)確性。為綜合計(jì)算各指標(biāo)的權(quán)重系數(shù)，AHP建立了等級(jí)評(píng)價(jià)指標(biāo)體系，根據(jù)同等級(jí)的指標(biāo)直接相對(duì)重要性來(lái)衡量。

熵值確定權(quán)重法［27］是一種客觀的賦權(quán)法，通過(guò)對(duì)各項(xiàng)指標(biāo)進(jìn)行觀測(cè)，并根據(jù)所觀測(cè)得到的信息大小確定各項(xiàng)指標(biāo)權(quán)重。信息熵是信息論中對(duì)信息的不確定性的一種量化度量，信息熵公式為

其中：p表示隨機(jī)變量x的輸出概率。通過(guò)式（7）可以看出，信息量越大，變量x的不確定性越小，信息熵也就越??；反之亦然。因此可以使用信息熵來(lái)衡量各指標(biāo)的變異程度，從而計(jì)算出各項(xiàng)指標(biāo)的權(quán)重。

針對(duì)大數(shù)據(jù)任務(wù)，采用層次分析法AHP 確定各評(píng)價(jià)指標(biāo)的權(quán)重。

5）建立模糊關(guān)系矩陣R。

單因素模糊評(píng)價(jià)［28］即逐個(gè)對(duì)被評(píng)事物依據(jù)評(píng)價(jià)指標(biāo)集U進(jìn)行量化，也就是得到評(píng)價(jià)對(duì)象ui(i=1，2，…，n)對(duì)每個(gè)評(píng)價(jià)結(jié)果的隸屬度(R|ui)，進(jìn)而可以得到模糊關(guān)系矩陣R，即

6）合成模糊綜合評(píng)價(jià)結(jié)果矢量。

對(duì)多個(gè)評(píng)價(jià)指標(biāo)進(jìn)行綜合評(píng)價(jià)，選用適當(dāng)?shù)哪：铣伤阕樱瑢⒛：龣?quán)重W與各被評(píng)事物的模糊關(guān)系矩陣R進(jìn)行合成，可以得到各被評(píng)價(jià)事物的模糊綜合評(píng)價(jià)結(jié)果矢量B，且

常見的模糊合成算子有M(∧，∨)、M(·，∨)、M(∧，⊕)、M(·，⊕)四種［23］，這四種算子的特點(diǎn)如表1所示。

表1 四種模糊合成算子的特點(diǎn)Tab.1 Features of four fuzzy synthetic operators

針對(duì)大數(shù)據(jù)任務(wù)的特性，采用加權(quán)平均型的模糊合成算子M(·，⊕)，對(duì)于多個(gè)被評(píng)價(jià)對(duì)象，可以依據(jù)其等級(jí)位置進(jìn)行排序。

2 面向大數(shù)據(jù)任務(wù)的調(diào)度方法模型

2.1 任務(wù)調(diào)度模型原理

由于歷史調(diào)度任務(wù)中，資源使用情況以及執(zhí)行時(shí)間均已知。根據(jù)K近鄰思想［29］，對(duì)于輸入的新實(shí)例，若在訓(xùn)練集中能找到與該實(shí)例最相鄰的k個(gè)實(shí)例，并且這些實(shí)例多數(shù)屬于某個(gè)類，就把該輸入的新實(shí)例分類到這個(gè)類中。若兩個(gè)任務(wù)數(shù)據(jù)集的模糊綜合評(píng)價(jià)結(jié)果相近，可以認(rèn)為這兩個(gè)任務(wù)數(shù)據(jù)集的資源使用情況以及執(zhí)行時(shí)間也相近。

當(dāng)要執(zhí)行新的大數(shù)據(jù)任務(wù)數(shù)據(jù)集時(shí)，先對(duì)其進(jìn)行屬性約簡(jiǎn)，再對(duì)其進(jìn)行模糊綜合評(píng)價(jià)，根據(jù)評(píng)價(jià)結(jié)果調(diào)度分配資源。該流程如圖1所示。

圖1 調(diào)度策略流程Fig.1 Scheduling strategy flowchart

2.2 任務(wù)調(diào)度模型算法

有n個(gè)歷史任務(wù)的數(shù)據(jù)集DS={DS1，DS2，…，DSn}

Step1 對(duì)DS進(jìn)行屬性約簡(jiǎn)，得到約簡(jiǎn)后的結(jié)果DS′；對(duì)DS′進(jìn)行模糊綜合評(píng)價(jià)，得到評(píng)價(jià)后的結(jié)果DS″={DS"1，DS"2，…，DS"n}。

Step2 輸入新任務(wù)P，對(duì)P進(jìn)行屬性約簡(jiǎn)，得到約簡(jiǎn)后的結(jié)果Q。

Step3 對(duì)Q進(jìn)行模糊綜合評(píng)價(jià)，得到評(píng)價(jià)結(jié)果B。

Step4 遍歷DS″，找出與B最為相近的DSj"。

Step5 根據(jù)DSj"的歷史資源分配和歷史任務(wù)執(zhí)行情況生成工作流，預(yù)估并為P分配資源。

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

3.1 實(shí)驗(yàn)過(guò)程

為評(píng)估本文所提出的算法，采用基于Apache Hadoop平臺(tái)的Oozie［30］框架進(jìn)行任務(wù)調(diào)度。

實(shí)驗(yàn)選取UCI（University of California Irvine）［31］數(shù)據(jù)庫(kù)中的10 個(gè)數(shù)據(jù)集，將其中70%的數(shù)據(jù)集用作訓(xùn)練數(shù)據(jù)集，30%的數(shù)據(jù)集用作測(cè)試數(shù)據(jù)集。通過(guò)所提出的基于互信息的屬性約簡(jiǎn)方法對(duì)UCI 數(shù)據(jù)集進(jìn)行屬性約簡(jiǎn)，之后對(duì)屬性約簡(jiǎn)后的數(shù)據(jù)集進(jìn)行模糊綜合評(píng)價(jià)，以模糊綜合評(píng)價(jià)結(jié)果在測(cè)試集上預(yù)測(cè)的實(shí)際表現(xiàn)來(lái)評(píng)估本文算法。實(shí)驗(yàn)所選取的數(shù)據(jù)集信息如表2所示，其中：m表示約簡(jiǎn)前的條件屬性個(gè)數(shù)，M表示約簡(jiǎn)后的條件屬性個(gè)數(shù)。

將各數(shù)據(jù)集的樣本數(shù)u1、類別數(shù)u2、約簡(jiǎn)后的條件屬性數(shù)u3、數(shù)據(jù)集要執(zhí)行的任務(wù)類型u4作為評(píng)價(jià)對(duì)象，即指標(biāo)集U={u1，u2，u3，u4}。將各數(shù)據(jù)集與歷史調(diào)度任務(wù)數(shù)據(jù)集的相似度1～5 作為評(píng)語(yǔ)集，其中5 表示最為相似，1 表示最不相似，即評(píng)語(yǔ)集V={1，2，3，4，5}。對(duì)U中的每一個(gè)ui做單因素判斷，確定ui對(duì)每個(gè)評(píng)價(jià)結(jié)果的隸屬度(R|ui)，進(jìn)而確定模糊關(guān)系矩陣R，即各數(shù)據(jù)集從不同的單指標(biāo)來(lái)看對(duì)各等級(jí)模糊子集的隸屬程度。

單因素評(píng)價(jià)獲得模糊關(guān)系矩陣后，為評(píng)價(jià)指標(biāo)集中的各個(gè)指標(biāo)在評(píng)價(jià)目標(biāo)中的不同地位和作用，在控制實(shí)驗(yàn)樣本和實(shí)驗(yàn)環(huán)境不變的前提下，各評(píng)價(jià)因素的權(quán)值變化如圖2 所示，得到各評(píng)價(jià)因素的最優(yōu)權(quán)值W=(0.1，0.1，0.2，0.6)。

表2 實(shí)驗(yàn)所用數(shù)據(jù)集信息Tab.2 Information of datasets used in experiments

用W對(duì)R中不同的行進(jìn)行綜合，得到該被評(píng)事物從總體上來(lái)看對(duì)各等級(jí)模糊子集的隸屬程度，即模糊綜合評(píng)價(jià)結(jié)果向量B。以B的結(jié)果為基礎(chǔ)，生成工作流并提交給Oozie 進(jìn)行調(diào)度。

圖2 各評(píng)價(jià)因素的權(quán)值變化Fig.2 Weight changes of different evaluation factors

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

為評(píng)估本文算法效果，將樸素貝葉斯（Naive Bayes，NB）算法、誤差反向傳播（error Back Propagation，BP）算法、均方根傳遞（Root Mean Square Prop，RMSProp）算法與本文算法進(jìn)行對(duì)比。其中：NB 算法是一種利用概率統(tǒng)計(jì)進(jìn)行分類的算法；BP 算法是一種按照誤差逆向傳播算法訓(xùn)練的多層前饋神經(jīng)網(wǎng)絡(luò)算法，在實(shí)際中被廣泛采用；RMSProp算法加入衰減系數(shù)控制歷史信息獲取，是一種有效且實(shí)用的神經(jīng)網(wǎng)絡(luò)優(yōu)化算法。不同算法的預(yù)測(cè)準(zhǔn)確度對(duì)比實(shí)驗(yàn)結(jié)果如表3所示。

整體來(lái)看，本文算法在平均預(yù)測(cè)準(zhǔn)確度上比NB 算法高7.42 個(gè)百分點(diǎn)，比BP 算法高5.16 個(gè)百分點(diǎn)，比RMSProp 算法高3.74 個(gè)百分點(diǎn)，這是由于屬性約簡(jiǎn)保留了最小屬性數(shù)的特征子集，在不改變知識(shí)庫(kù)分類能力的同時(shí)，去除了數(shù)據(jù)集中的噪聲，從而提高了預(yù)測(cè)精度。結(jié)合不同的數(shù)據(jù)集分析，對(duì)于特征數(shù)較少的數(shù)據(jù)集如Iris、Balance scale，本文算法的預(yù)測(cè)精度略高于其他三種；對(duì)于特征數(shù)較多的數(shù)據(jù)集如Ionosphere、Sonar等，本文算法較其他算法在預(yù)測(cè)精度上有顯著提高。

為評(píng)估本文所提調(diào)度算法性能，將HCPFS（Heterogeneous Critcal Path First Synthesis）算法［32］和HIPLTS（Heterogeneous Improved Priority List for Task Scheduling）算法［33］與本文算法進(jìn)行對(duì)比。采用調(diào)度長(zhǎng)度下界比（Schedule Length Ratio，SLR）、加速比作為算法評(píng)估指標(biāo)，SLR和加速比sr的計(jì)算公式如下所示：

表3 不同算法的預(yù)測(cè)準(zhǔn)確度對(duì)比實(shí)驗(yàn)結(jié)果 單位：%Tab.3 Experimental results comparison of prediction accuracy by different algorithms unit：%

使用Oozie 按照文獻(xiàn)［34］提供的方法生成隨機(jī)任務(wù)圖。具體設(shè)置參數(shù)如下：

1）節(jié)點(diǎn)數(shù)nodes={20，30，40，50，60，70，80，90，100}；

2）節(jié)點(diǎn)出度outdegree={1，2，5，20}；

3）通信計(jì)算比（Communication to Computation Ratio，CCR），CCR={0.1，0.2，0.5，1，2，5，10}；

4）圖形狀參數(shù)α={0.5，1.0，2.0}；

5）處理器計(jì)算開銷β={0.1，0.2，0.25，0.5，0.6，0.75，1}。

三種調(diào)度算法平均SLR和平均sr的實(shí)驗(yàn)對(duì)比結(jié)果如圖3所示。

圖3 三種調(diào)度算法平均SLR和sr的實(shí)驗(yàn)對(duì)比結(jié)果Fig.3 Experimental results comparison of average SLR and sr by three scheduling algorithms

通過(guò)實(shí)驗(yàn)數(shù)據(jù)可以看出，相較于HCPFS 算法和HIPLTS算法，本文算法的平均SLR分別下降了12.14%和4.56%，平均sr分別提升了7.14%和42.56%，說(shuō)明本文算法具有更好的任務(wù)調(diào)度性能，能夠有效提高任務(wù)調(diào)度效率。

4 結(jié)語(yǔ)

針對(duì)大數(shù)據(jù)處理流程中如何合理高效分配資源的問(wèn)題，本文引入任務(wù)調(diào)度理論，提出了一種面向大數(shù)據(jù)任務(wù)的調(diào)度方法。該方法結(jié)合粗糙集理論，引入決策表模型進(jìn)行屬性約簡(jiǎn)，從而去除不重要和冗余屬性以保持知識(shí)分類的不變，提高大數(shù)據(jù)任務(wù)處理的效率；同時(shí)引入模糊綜合評(píng)價(jià)方法，將模糊綜合評(píng)價(jià)結(jié)果作為對(duì)任務(wù)進(jìn)行調(diào)度的依據(jù)，提高任務(wù)資源分配合理性。通過(guò)在UCI 數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果分析表明，該算法能有效提高預(yù)測(cè)精度；通過(guò)與HCPFS 算法和HIPLTS 算法實(shí)驗(yàn)對(duì)比，表明本文算法能有效提高大數(shù)據(jù)系統(tǒng)中任務(wù)調(diào)度的效率。接下來(lái)的工作是考慮使用機(jī)器學(xué)習(xí)方法進(jìn)行模糊綜合評(píng)價(jià)，優(yōu)化算法生成工作流的流程，提高算法性能。