杜清華，張凱

（1.復(fù)旦大學(xué) 軟件學(xué)院，上海 200438；2.復(fù)旦大學(xué) 計算機科學(xué)技術(shù)學(xué)院，上海 200438）

0 概述

為了滿足數(shù)據(jù)科學(xué)的多種需求，具有擴展性的跨平臺數(shù)據(jù)分析系統(tǒng)不斷涌現(xiàn)，如Rheem［1］、Musketeer［2］等。這類系統(tǒng)將Java、Spark［3］等不同數(shù)據(jù)處理平臺作為底層實現(xiàn)，為用戶抽象出一套數(shù)據(jù)分析接口，幫助用戶更加簡單地完成對復(fù)雜數(shù)據(jù)分析任務(wù)的計算。數(shù)據(jù)分析任務(wù)在跨平臺系統(tǒng)中將以工作流為載體進行計算，工作流主要存在邏輯工作流和物理工作流兩種形式。用戶通過接口編寫邏輯工作流，然后系統(tǒng)需要為邏輯工作流中的每個算子選擇相應(yīng)的物理實現(xiàn)而形成可執(zhí)行的物理工作流。邏輯算子的平臺選擇對于工作流整體性能至關(guān)重要，因為算子在不同平臺上的實現(xiàn)會存在性能間的顯著差異，這也是針對跨平臺工作流進行優(yōu)化的主要方式之一。

目前，部分研究人員［4-5］針對跨平臺工作流采用了基于成本的優(yōu)化方法，利用函數(shù)公式對影響算子運行成本的因素進行建模，從而獲得可以估計某個算子具體運行時間的成本模型［6］。然而，將傳統(tǒng)成本優(yōu)化方法應(yīng)用于跨平臺工作流時會存在兩個問題：首先，成本模型普遍具有一個固定的函數(shù)形式，例如Rheemix［7］中所使用的線性函數(shù)式成本模型，由于線性表達式本身具有難以表達復(fù)雜或非線性關(guān)系的特點，導(dǎo)致其不能很好地反映各因素對不同平臺、不同計算類型算子運行時間成本的影響程度；其次，它需要系統(tǒng)管理員做大量工作來調(diào)優(yōu)函數(shù)式成本模型的參數(shù)。尤其在跨平臺系統(tǒng)中這個問題會更加嚴(yán)重，因為跨平臺系統(tǒng)的算子數(shù)量會數(shù)倍于傳統(tǒng)數(shù)據(jù)處理平臺［1］，這將使得函數(shù)模型的參數(shù)數(shù)量很容易達到數(shù)百條，手工調(diào)整它們不僅具有挑戰(zhàn)性而且非常耗時［8］。

隨著機器學(xué)習(xí)的發(fā)展，一些工作開始探索使用新的方式來實現(xiàn)跨平臺工作流優(yōu)化。Robopt［9］使用隨機森林算法作為成本模型，雖然該算法的魯棒性較好，但是無法捕捉工作流中所隱含的信息，如工作流的結(jié)構(gòu)信息和算子的運行時序信息等。由于不同的算子具有不同的屬性（如參數(shù)、子節(jié)點），這使得物理工作流具有獨特的結(jié)構(gòu)信息。雖然部分研究［10-12］在成本估計上探索了結(jié)構(gòu)信息并取得了不錯的效果，但他們的目標(biāo)僅適用于單平臺查詢優(yōu)化，如數(shù)據(jù)庫查詢優(yōu)化等。文獻［13-15］提出使用基于成本的強化學(xué)習(xí)優(yōu)化方法，該方法雖然可以降低優(yōu)化器的維護成本，但是十分依賴模型的設(shè)計及訓(xùn)練數(shù)據(jù)，且啟發(fā)式方法所固有的不穩(wěn)定性將在某些情況下導(dǎo)致優(yōu)化效果并不明顯。

為了提升跨平臺工作流的執(zhí)行性能，本文提出一種GGFN（GAT-BiGRU-FC Network）模型作為成本模型，用于實現(xiàn)高效的跨平臺工作流優(yōu)化。基于圖注意力機制和循環(huán)網(wǎng)絡(luò)門控機制，GGFN 模型可以在具有有向無環(huán)圖（Directed Acyclic Graph，DAG）結(jié)構(gòu)的跨平臺工作流上挖掘結(jié)構(gòu)信息和記憶算子的運行時序信息，該模型以算子特征和工作流特征作為輸入，從而對跨平臺工作流實現(xiàn)更準(zhǔn)確的成本估計。在此基礎(chǔ)上，通過對邏輯算子的實現(xiàn)平臺進行枚舉，并選擇其中運行時間成本低的物理工作流作為最終的優(yōu)化結(jié)果。同時，為加速枚舉過程，本文設(shè)計延遲貪婪剪枝方法以降低優(yōu)化時間的開銷。

1 背景及相關(guān)工作

1.1 跨平臺工作流優(yōu)化

工作流優(yōu)化是數(shù)據(jù)處理平臺用于提升性能的主要方式，優(yōu)化通過將邏輯工作流轉(zhuǎn)換為運行成本更低的可執(zhí)行物理工作流，從而加快數(shù)據(jù)處理任務(wù)的運行速度?；诔杀镜膬?yōu)化方法［16］是傳統(tǒng)工作流優(yōu)化中最常用的方法之一，而成本模型是實現(xiàn)基于成本優(yōu)化的基礎(chǔ)。例如，KeystoneML［17］在進行工作流優(yōu)化時，依據(jù)資源使用情況、輸入輸出基數(shù)以及算子信息等給出相應(yīng)的函數(shù)公式作為成本模型。文獻［18］使用循環(huán)神經(jīng)網(wǎng)絡(luò)作為成本模型來預(yù)測數(shù)據(jù)庫查詢計劃的運行成本。文獻［19］提出為工作流中的表達式創(chuàng)建多個機器學(xué)習(xí)模型并以此實現(xiàn)準(zhǔn)確度更好、覆蓋率更高的成本估計。

然而，跨平臺系統(tǒng)在跨平臺工作流優(yōu)化方面并沒有像數(shù)據(jù)庫或其他數(shù)據(jù)處理平臺一樣擁有成熟且可靠的優(yōu)化方法。例如，文獻［20］雖然介紹了跨平臺系統(tǒng)相關(guān)工作，但并未針對其工作流提供優(yōu)化方法，BigDAWG［21］為跨平臺工作流所提供的優(yōu)化方式需要用戶通過Scope 和Cast 命令指定運行工作流的具體平臺。這種優(yōu)化方式不僅存在優(yōu)化效果的不確定性，而且增加了用戶的工作量和難度。此外，LaraDB［22］和Myria［8］通過利用已有經(jīng)驗所制定的規(guī)則實現(xiàn)優(yōu)化，但是過度耦合的優(yōu)化規(guī)則會給系統(tǒng)的擴展性帶來困難。因此，基于成本的優(yōu)化方法仍然是研究人員進行跨平臺工作流優(yōu)化所使用的主要方式。例如，Rheemix［7］為其系統(tǒng)中每個算子定義了成本的計算過程，但是由于跨平臺系統(tǒng)中算子數(shù)量大、計算類型多，因此將這種函數(shù)式的成本模型應(yīng)用于跨平臺優(yōu)化很容易出現(xiàn)參數(shù)規(guī)模達到數(shù)百而產(chǎn)生參數(shù)調(diào)優(yōu)困難的問題。Musketeer［2］通過對每個算子成本進行累加的方式計算工作流整體成本，然而這種方式會忽略不同平臺算子間的數(shù)據(jù)傳輸所帶來的時間成本。雖然Robopt［9］使用了機器學(xué)習(xí)算法來避免繁瑣的參數(shù)調(diào)優(yōu)工作，但是其成本模型由于擴展性不足且無法捕捉工作流的潛在信息，而不能實現(xiàn)更好的優(yōu)化效果。

1.2 圖注意力網(wǎng)絡(luò)與門控循環(huán)單元

圖注意力網(wǎng)絡(luò)（Graph Attention Network，GAT）是由PETAR等［23］所提出的用于處理圖結(jié)構(gòu)數(shù)據(jù)的神經(jīng)網(wǎng)絡(luò)模型。GAT 可以通過堆疊應(yīng)用注意力機制的網(wǎng)絡(luò)層來獲取圖上每個節(jié)點的鄰域特征，并為鄰域中的不同節(jié)點分配不同的權(quán)重作為注意力系數(shù)。這使得可以在不需要高成本的矩陣運算和預(yù)先知道圖結(jié)構(gòu)信息的情況下實現(xiàn)高效的圖信息處理。通過這種方式，GAT 可以解決基于頻域的圖處理方法所無法解決的動態(tài)圖問題，如圖卷積網(wǎng)絡(luò)（Graph Convolutional Network，GCN）［24］，同時也能應(yīng)用于圖的歸納學(xué)習(xí)和直推學(xué)習(xí)。需要注意的是，由于GAT網(wǎng)絡(luò)是對圖頂點進行逐個運算，每次計算都需要對圖上所有頂點進行循環(huán)遍歷，這意味著GAT 可以擺脫傳統(tǒng)圖結(jié)構(gòu)處理中的Laplacian 矩陣的束縛并實現(xiàn)對有向圖的處理。

門控循環(huán)單元（Gate Recurrent Unit，GRU）是由CHO等［25］提出用于解決長期記憶和反向傳播中的梯度等問題的網(wǎng)絡(luò)模型，與長短期記憶（Long Short-Term Memory，LSTM）同為循環(huán)神經(jīng)網(wǎng)絡(luò)（Recurrent Neural Network，RNN）的變體。LSTM 的門控機制被廣泛應(yīng)用于分析并捕獲時間序列數(shù)據(jù)中的長期依賴關(guān)系。GRU 在LSTM 的基礎(chǔ)上通過優(yōu)化門結(jié)構(gòu)而保證了對于序列數(shù)據(jù)的長期記憶效果。在大量的實驗數(shù)據(jù)中證明，GRU 在模型準(zhǔn)確度方面與LSTM 有著相似的效果，但由于GRU 的門控數(shù)少于LSTM，在模型訓(xùn)練中將會有更少的參數(shù)需要計算，因此GRU的模型收斂速度會更快。

2 相關(guān)概念及問題定義

邏輯工作流是由用戶根據(jù)任務(wù)需求所創(chuàng)建而形成的DAG 型結(jié)構(gòu)的有向數(shù)據(jù)流圖。其頂點是邏輯算子，表示對數(shù)據(jù)進行分析處理的任務(wù)邏輯且與平臺無關(guān)，邊代表算子之間的數(shù)據(jù)流。邏輯工作流用符號可以表示為lw={O,E}。其中，O={o1,o2,…,on}表示邏輯算子集合，oi表示第i個邏輯算子，n表示邏輯算子的數(shù)量，E={e1,e2,…,em}表示數(shù)據(jù)流邊集合，ek=[oi,oj]表示算子間的數(shù)據(jù)流邊。

定義1（跨平臺工作流優(yōu)化）針對跨平臺工作流，給定一個優(yōu)化轉(zhuǎn)換操作Opt=Min{pltSec(?)}，實現(xiàn)將邏輯工作流lw 轉(zhuǎn)化為最優(yōu)物理工作流pwmin。在由平臺選擇操作pltSec（lw）所生成的物理工作流集合PW 中存在pwj?PW，使得對于任意的pwi?PW，pwi≠pwj，滿 足cost(pwj)≤cost(pwi)。此 時，pwmin=pwj=Opt(lw)為跨平臺工作流優(yōu)化的目標(biāo)結(jié)果。

3 基于GGFN 模型的跨平臺工作流優(yōu)化

3.1 方法概述

為了提升跨平臺工作流的執(zhí)行性能并克服已有優(yōu)化工作中的問題，本文提出一種基于GGFN 模型的跨平臺工作流優(yōu)化方法，該方法的整體優(yōu)化框架如圖1 所示。

圖1 基于GGFN 模型的跨平臺工作流優(yōu)化框架Fig.1 Cross-platform workflow optimization framework based on GGFN model

首先對于用戶輸入的邏輯工作流進行向量化操作，從而避免后續(xù)每次進行成本估計時向量轉(zhuǎn)換所帶來的優(yōu)化開銷。接著對每個邏輯算子進行算子實現(xiàn)平臺的枚舉，同時利用延遲貪婪剪枝方法以加速枚舉過程。枚舉算法將使用基于圖注意力網(wǎng)絡(luò)和門控循環(huán)單元所形成的GGFN 模型對跨平臺工作流所做出的成本估計結(jié)果為依據(jù)進行平臺選擇。最后成本最低的物理工作流向量將會被選擇出來，并將其反向量化為可執(zhí)行的物理工作流后進行部署和執(zhí)行。與此同時，物理工作流的執(zhí)行過程會將被記錄并進行日志分析，以此來作為后續(xù)GGFN 模型的線下訓(xùn)練數(shù)據(jù)。

3.2 GGFN 模型

對物理工作流進行準(zhǔn)確的成本估計是本文實現(xiàn)高效跨平臺工作流優(yōu)化的重要基礎(chǔ)。在總結(jié)了已有工作的不足之處后，本文提出了基于圖注意力神經(jīng)網(wǎng)絡(luò)（GAT）與門控循環(huán)單元（GRU）的GGFN 成本模型，其結(jié)構(gòu)如圖2 所示。該模型包含兩個輸入部分，一是算子特征，二是工作流特征。算子特征將經(jīng)過圖注意力網(wǎng)絡(luò)的處理來捕捉工作流的整體結(jié)構(gòu)信息以及各個算子之間的交互關(guān)系。雙向門控循環(huán)單元將對算子之間的運行時序關(guān)系進行挖掘并獲得相應(yīng)的運行狀態(tài)信息，其編碼結(jié)果將與工作流特征進行融合。融合后的特征將被輸入到3 層全連接層進行工作流運行時間成本的預(yù)測，并在輸出層得到預(yù)測結(jié)果。

圖2 基于GAT 和BiGRU 的GGFN 模型架構(gòu)Fig.2 The GGFN model architecture based on GAT and BiGRU

3.2.1 輸入特征

GGFN 模型的輸入特征被設(shè)計為以下2 個部分：

1）工作流特征。工作流的整體信息表示以及輸入數(shù)據(jù)集信息，包括算子數(shù)量、平臺數(shù)量、結(jié)構(gòu)信息、輸入數(shù)據(jù)集大小、輸入數(shù)據(jù)集分布、輸入平均元組大小等。

2）算子特征。工作流中每個算子的信息表示，包括算子并行度、父節(jié)點數(shù)量、子節(jié)點數(shù)量、用戶自定義函數(shù)（User Defined Function，UDF）復(fù)雜度、計算分析類型、輸入輸出基數(shù)、算子運行平臺等。

其中，算子特征結(jié)合鄰接矩陣來表示跨平臺工作流的DAG 結(jié)構(gòu)，從而可以更好地幫助GGFN 模型挖掘工作流結(jié)構(gòu)信息和算子的運行時序信息。該設(shè)計滿足特征的擴展性要求，當(dāng)在跨平臺系統(tǒng)中添加新的平臺或算子時，只需進行相應(yīng)特征位的映射范圍擴展。

3.2.2 圖注意力網(wǎng)絡(luò)

由于GAT 中的注意力機制可以為每個鄰居節(jié)點分配不同的注意力系數(shù)，因此可以識別出相對于當(dāng)前節(jié)點更重要的鄰居節(jié)點。在跨平臺工作流中，不同算子對相鄰算子的影響程度是不同的。例如，F(xiàn)liter 算子會通過減少數(shù)據(jù)量而對下一個鄰居算子的數(shù)據(jù)處理時間產(chǎn)生較大影響，而Sort 算子對后續(xù)鄰居算子的影響將取決于該鄰居算子對數(shù)據(jù)順序的依賴性。此外，由于跨平臺工作流為DAG 圖結(jié)構(gòu)，圖網(wǎng)絡(luò)模型將可以更好地實現(xiàn)對工作流結(jié)構(gòu)信息的捕捉。因此，本文在GGFN 模型中引入圖注意力網(wǎng)絡(luò)（GAT）來實現(xiàn)對工作流整體結(jié)構(gòu)信息和算子間關(guān)系信息的特征提取。

GAT 的計算主要包括兩步，首先是計算注意力系數(shù)，計算過程如式（1）、式（2）所示：

其中：W為共享參數(shù)對頂點特征進行增維；[?||?]表示對節(jié)點i和j變換后的特征進行拼接操作；a(?)表示將拼接后的高位特征映射到一個實數(shù)上。式（1）用于計算節(jié)點i和其鄰居（j?Ni）間的相似系數(shù)；式（2）通過LeakyReLU(?)進行歸一化操作得到節(jié)點i和j的注意力系數(shù)αij。

然后需要根據(jù)計算好的注意力系數(shù)進行特征的加權(quán)求和。為了加強GAT 模型在學(xué)習(xí)過程中的穩(wěn)定性，本文引入了多頭注意力機制來獲得多個注意力系數(shù)關(guān)系，如圖3 所示。

圖3 GAT 中的多頭注意力機制Fig.3 Multi-head attention mechanism in GAT

圖3 所示為在K個注意力機制下（K=3）算子節(jié)點的更新狀態(tài)。通過利用多頭注意力機制計算節(jié)點新特征的計算公式如式（3）所示：

3.2.3 門控循環(huán)單元

跨平臺工作流以算子順序執(zhí)行，運行時間包括從源算子到所有算子執(zhí)行完成的最終狀態(tài)，因此需要考慮前序執(zhí)行算子的計算時間及計算狀態(tài)語義?；谏鲜銮闆r，可以利用循環(huán)神經(jīng)網(wǎng)絡(luò)（RNN）對序列數(shù)據(jù)的記憶效果來獲取跨平臺工作流中算子執(zhí)行順序?qū)ψ罱K狀態(tài)的影響。而門控循環(huán)單元（GRU）作為循環(huán)神經(jīng)網(wǎng)絡(luò)的一種特殊形式，利用其門控機制可以很好地實現(xiàn)長期記憶并避免RNN 中梯度消失和梯度爆炸的問題。本文GGFN 模型中的GRU 用于記憶算子結(jié)構(gòu)和運行的時序信息，并對其特征進行編碼。GRU 的單元結(jié)構(gòu)如圖4 所示。

圖4 GRU 單元結(jié)構(gòu)Fig.4 The unit structure of GRU

在圖4 中，rt為重置門，用于控制前一時刻隱層單元對當(dāng)前輸入的影響，有助于捕獲運行序列中的短期依賴關(guān)系，zt為更新門，用于控制過去信息的保留和傳遞情況，有助于捕獲物理算子運行時間序列中的長期依賴關(guān)系。在t時刻，GRU 的計算過程如式（4）～式（7）所示：

其中：xt為t時刻的輸入；W表示權(quán)重參數(shù)；b表示偏差向量；ht-1、ht分別表示t?1和t時刻的候選隱 藏層狀態(tài)。

在跨平臺工作流中，不同的算子實現(xiàn)需要在不同平臺中運行，因此后續(xù)算子的實現(xiàn)平臺對當(dāng)前平臺算子的數(shù)據(jù)輸出格式及數(shù)據(jù)傳輸是存在時間成本影響的。為了捕捉這種影響關(guān)系，本文使用雙向GRU（BiGRU）來實現(xiàn)上下文語義的提取。BiGRU可以利用雙向通道實現(xiàn)正向和反向的信息積累，從而在物理工作流中獲得更加豐富的特征信息。

3.2.4 模型輸出

將經(jīng)過特征工程處理后的工作流特征Fw與BiGRU 的輸出outg相融合，得到工作流的最終表示為w，即：

跨平臺工作流的最終表示w將被傳入至3 層全連接神經(jīng)網(wǎng)絡(luò)中進行特征學(xué)習(xí)，并產(chǎn)生該工作流運行時間的預(yù)測結(jié)果tw。跨平臺物理工作流在GGFN模型中的整體估計過程即為：

其中：Ow為物理工作流的算子特征部分；Fw為物理工作流特征部分。

3.2.5 模型損失函數(shù)

在模型訓(xùn)練過程中，本文采用式（10）作為GGFN模型的損失函數(shù)，其結(jié)合了均方損失（Mean Square Error，MSE）和絕對值損失（Mean Absolute Error，MAE）的優(yōu)勢。在計算損失過程中，當(dāng)預(yù)測偏差小于δ時采用平方誤差，當(dāng)預(yù)測偏差大于δ時采用的線性誤差，降低了對離群點的懲罰程度，也更具魯棒性。

其中：y表示工作流運行時間的真實值；f(x)表示模型運行時間的預(yù)測值，超參數(shù)δ將根據(jù)在訓(xùn)練數(shù)據(jù)集上的訓(xùn)練效果進行調(diào)整。

3.3 算子平臺枚舉

利用成本模型進行算子平臺的枚舉并選擇成本較低的物理工作流是整個優(yōu)化方法中必經(jīng)的一步，但是在進行算子平臺枚舉過程中會面臨笛卡爾積組合造成的指數(shù)搜索空間的問題。因此，本文在GGFN 模型的基礎(chǔ)上提出了應(yīng)用剪枝的枚舉算法實現(xiàn)將邏輯工作流轉(zhuǎn)換為可執(zhí)行的物理工作流。

3.3.1 工作流剪枝

假設(shè)一個邏輯工作流包含m個算子，每個算子有k個對應(yīng)的實現(xiàn)平臺可以選擇，那么如果枚舉所有的可能，則將會形成km個物理工作流。研究人員針對該問題提出了其解決辦法，如文獻［26］使用一種簡單的搜索空間修剪技術(shù)，即傳統(tǒng)貪婪剪枝方法，在枚舉過程中僅保留當(dāng)前步驟下成本最低的物理工作流。這種貪婪剪枝方法雖然簡單但是會產(chǎn)生局部最優(yōu)的結(jié)果。而Musketeer［2］使用了動態(tài)規(guī)劃啟發(fā)式算法返回給定線性順序的最優(yōu)k路劃分，但是該方法只能探索工作流中算子的單一線性排序，這使得在進行枚舉前需要先將DAG 型工作流進行線性排序操作，而這會導(dǎo)致在k路劃分時錯過可能的算子平臺間的階段劃分和合并的機會。為了降低枚舉搜索空間并減少優(yōu)化時間開銷，本文提出了較貪婪剪枝方法更加有效且易實現(xiàn)的延遲貪婪剪枝方法，該方法可以在保持工作流結(jié)構(gòu)特點的基礎(chǔ)上實現(xiàn)高效的剪枝操作。

由于傳統(tǒng)貪婪剪枝方法在枚舉過程中僅保留一個成本最低的物理工作流，這樣很容易產(chǎn)生局部最優(yōu)的情況因此延遲貪婪剪枝方法保留了包含兩個不確定算子的所有物理工作流，從而在可接受優(yōu)化開銷范圍內(nèi)增加了更多選擇。該剪枝方法的主要依據(jù)是：如果兩個子物理工作流中尾部算子的實現(xiàn)平臺相同，那么它們與其他算子連接所需要的數(shù)據(jù)轉(zhuǎn)換等成本都是相同的。成本低的子工作流在添加算子形成新的子工作流后也將有更低的成本。通過使用該剪枝方法，枚舉復(fù)雜度將由指數(shù)級O(km)降為平方級O(mk2)。

3.3.2 枚舉算法及復(fù)雜度分析

本文在使用GGFN 模型作為成本模型的基礎(chǔ)上，提出了應(yīng)用延遲貪婪剪枝的算子平臺枚舉算法，如算法1 所示。

算法1算子平臺枚舉算法

算子平臺枚舉算法將邏輯工作流lw 作為輸入，并得到最優(yōu)物理工作流pwmin，其中假設(shè)lw 中的算子數(shù)量為m。首先，需要對lw 進行向量化處理并拓撲排序得到所有算子的集合（第2 行）。然后，遍歷所有算子并枚舉其實現(xiàn)平臺，將算子及其實現(xiàn)平臺放入隊列中（第3 行～第6 行），該過程的時間復(fù)雜度為O(n)。獲取源算子與其實現(xiàn)平臺集合作為生成物理工作流向量集合PV 的初始值（第8 行）。接下來將通過循環(huán)來添加算子至物理工作流向量。首先是獲取當(dāng)前物理工作流的所有下一個待連接算子及其實現(xiàn)平臺集合（第11 行），遍歷待連接算子并取其與當(dāng)前子物理工作流的笛卡爾積進行枚舉連接（第12 行～第14 行）。從算子向量中刪除已連接算子，然后將不同連接組合所形成的子物理工作流進行剪枝，剪枝將基于GGFN 模型進行，同時更新當(dāng)前子物理工作流集合（第15 行～第22 行），該過程的時間復(fù)雜度為O(n2)。當(dāng)算子向量隊列為空時，枚舉連接過程完成，整體過程的時間復(fù)雜度為O(mn2)。接著獲取PV中成本最低的物理工作流向量并進行反向量化為最優(yōu)物理工作流pwmi（n第24行），最后返回結(jié)果（第25行）。因此，算子平臺枚舉算法的總時間復(fù)雜度為O(mn2)=O(n+mn2)。

本文在GGFN 成本模型對跨平臺物理工作流成本準(zhǔn)確預(yù)測的基礎(chǔ)上，通過應(yīng)用算子平臺枚舉算法，為每個邏輯算子選擇合適的實現(xiàn)平臺，并完成從邏輯工作流到物理工作流的優(yōu)化轉(zhuǎn)換。

4 實驗與結(jié)果分析

本節(jié)通過多組實驗來評估本文的優(yōu)化方法，并證明該方法可以基于GGFN 模型為跨平臺工作流中的算子選擇合適的運行平臺，并利用跨平臺系統(tǒng)的多平臺優(yōu)勢提高任務(wù)的執(zhí)行速度，GGFN 模型對于成本估計具有更高的準(zhǔn)確度。

4.1 實驗設(shè)置

4.1.1 實驗環(huán)境

實驗在一個由3 個節(jié)點組成的集群上進行，每個節(jié)點都包含2 個16 核的Intel Xeon Gold 5218 處理器，1 個NVIDIA Tesla T4 GPU，4 個32 GB DDR4 的RAM 以及2 TB 的固態(tài)硬盤SSD，操作系統(tǒng)為Ubuntu 20.0.1。部署在集群上的計算平臺包括：Java 1.8，Spark 2.4.5，F(xiàn)link 1.13.2，SparkML 2.4.5，JgraphT 1.4.0，GraphX 2.4.5，Sklearn 0.24.1，Gensim 4.1.0，Tensorflow 2.6，PyTorch 1.7.1。

4.1.2 實驗數(shù)據(jù)集

本文在實驗中根據(jù)工作流情況使用多個不同的數(shù)據(jù)集。其中，WordCount 任務(wù)與Word2Vec 任務(wù)使用Wikipedia 公開數(shù)據(jù)集，該數(shù)據(jù)集是源自Wikipedia 網(wǎng)站中用于文本檢索的常用典型數(shù)據(jù)集。PageRank 任務(wù)使用斯坦福大學(xué)公開數(shù)據(jù)集LiveJournal-Network，該數(shù)據(jù)集包含免費在線社區(qū)LiveJournal 中近500 萬會員及其朋友之間的關(guān)聯(lián)關(guān)系，在實驗中被用于進行PageRank計算來統(tǒng)計該社交平臺中重要用戶的權(quán)重信息。此外，用于模擬真實計算場景的用戶信用分析任務(wù)將使用Kaggle 平臺上的Credit-Card-Approval-Prediction數(shù)據(jù)集。該數(shù)據(jù)集包含歐洲某國用戶基本信息與其相關(guān)信貸記錄的情況，數(shù)據(jù)集中包括用戶信用記錄表和用戶基本信息表兩個部分。其中用戶基本信息表主要包括用戶編號、性別、教育程度、婚姻狀況、出生時間、職業(yè)、家庭情況等信息。用戶信用記錄表主要包括用戶編號、記錄月份、借貸信用狀態(tài)。此外，由于上述部分數(shù)據(jù)集的大小固定，因此需要對其進行數(shù)據(jù)切片或數(shù)據(jù)復(fù)制等操作，使其可以符合實驗中跨平臺工作流的輸入大小。

4.1.3 實驗參數(shù)設(shè)置及評價標(biāo)準(zhǔn)

在GGFN 模型訓(xùn)練的參數(shù)設(shè)置中，優(yōu)化器采用Adam，跨平臺工作流的算子特征維度為63，工作流特征維度為39。GAT 網(wǎng)絡(luò)層數(shù)為2，多頭注意力K為2，隱藏層節(jié)點數(shù)為128。BiGRU 網(wǎng)絡(luò)的層數(shù)為2，隱藏層節(jié)點數(shù)為128。全連接層的隱藏節(jié)點數(shù)設(shè)置為128。模型訓(xùn)練的學(xué)習(xí)率和Dropout 分別設(shè)置為0.001 和0.4。

為了評估GGFN 模型的準(zhǔn)確度，本文使用絕對誤 差（Absolute Error，AE）及相對誤差（Relative Error，RE）作為評價標(biāo)準(zhǔn)，定義如下：

其中：|PW|表示物理工作流的數(shù)量；r(?)表示物理工作流pw 的真實運行時間；e(?)表示成本模型對pw 的估計運行時間。

4.2 訓(xùn)練數(shù)據(jù)生成

模型訓(xùn)練需要大量物理工作流及運行時間作為訓(xùn)練數(shù)據(jù)，但由于跨平臺系統(tǒng)為新興平臺系統(tǒng)，因此并沒有充足的執(zhí)行日志作為訓(xùn)練數(shù)據(jù)。本文的訓(xùn)練數(shù)據(jù)首先需要通過數(shù)據(jù)生成的方式產(chǎn)生，然后在系統(tǒng)使用過程中收集執(zhí)行日志并在線下完成模型訓(xùn)練。本文在文獻［27］的基礎(chǔ)上改進了其數(shù)據(jù)模擬方式并生成了用于模型冷啟動的訓(xùn)練數(shù)據(jù)。首先，運行包括少量輸入數(shù)據(jù)的全部工作流以及中等和大量輸入數(shù)據(jù)的少量工作流，并記錄運行時間。然后，將已執(zhí)行的工作流進行標(biāo)注，同時對結(jié)果數(shù)據(jù)進行多項式插值和數(shù)據(jù)擬合，并取插值和擬合的均值作為運行時間標(biāo)簽，如圖5 所示。

圖5 訓(xùn)練數(shù)據(jù)生成示例Fig.5 Example of training data generation

圖5 為某次訓(xùn)練數(shù)據(jù)生成的示意圖。根據(jù)工作流輸入數(shù)據(jù)的行數(shù)以及實際運行時間，分別對其進行5 階多項式插值以及3 階多項式擬合。而對于模擬生成的數(shù)據(jù)，取插值和擬合結(jié)果的均值作為該工作流在指定輸入數(shù)據(jù)集行數(shù)的運行時間標(biāo)簽。

4.3 單平臺下優(yōu)化效果分析

首先評估基于GGFN 模型的跨平臺工作流優(yōu)化方法在平臺選擇時的優(yōu)化效果。為了使選擇效果更加明顯，在實驗中設(shè)置為僅選擇一個平臺來運行相應(yīng)的任務(wù)工作流。本次實驗選擇了WordCount、PageRank 和Word2Vec 三個任務(wù)作為批處理、圖計算以及機器學(xué)習(xí)任務(wù)的工作流代表來進行實驗，并分別在不同平臺上運行，以此觀察優(yōu)化方法能否為相應(yīng)的工作流選擇最佳的執(zhí)行平臺。圖6～圖8 顯示了在改變數(shù)據(jù)集大小的情況下3 個不同任務(wù)在各自平臺下的運行時間。其中，倒三角表示本文優(yōu)化方法在相應(yīng)數(shù)據(jù)輸入情況下為工作流選擇的執(zhí)行平臺。可以發(fā)現(xiàn)，圖中結(jié)果顯示了不同工作流在不同平臺上的運行時間是存在顯著差異的，部分平臺運行時間差距達到5 倍以上，這也表明通過優(yōu)化為工作流中的算子選擇合適的平臺對加快任務(wù)運行的重要性。

圖6 WordCount 任務(wù)運行時間對比Fig.6 The comparison of WordCount task runtime

圖7 PageRank 任務(wù)運行時間對比Fig.7 The comparison of PageRank task runtime

圖8 Word2Vec 任務(wù)運行時間對比Fig.8 The comparison of Word2Vec task runtime

在圖6 所示的WordCount 任務(wù)中，當(dāng)數(shù)據(jù)集較小時（如0.05 GB），JavaStream 由于單機優(yōu)勢而獲得較快的執(zhí)行速度，而Spark 和Flink 平臺卻由于分布式通信等開銷的影響導(dǎo)致其速度較慢。在數(shù)據(jù)集大于1 GB 后可以明顯發(fā)現(xiàn)，JavaStream 的運行時間突增，且在30 GB 時出現(xiàn)運行異常。而Spark 通過分布式節(jié)點進行數(shù)據(jù)處理，與計算時間相比通信開銷所帶來的影響開始變得很小?；贕GFN 的優(yōu)化方法發(fā)現(xiàn)這一差異并準(zhǔn)確地選擇出最佳運行平臺。

圖7 顯示了PageRank 進行10 次迭代計算情況下的執(zhí)行時間。在小規(guī)模圖上，Jgrapht性能優(yōu)于其他平臺，但在大規(guī)模圖上，Graphx的性能卻是Jgrapht的3～4倍，這是由于平臺的定位是面對不同規(guī)模的圖數(shù)據(jù)集，而對于圖8 中的Word2Vec 任務(wù)，由于Gensim 對該算法進行了優(yōu)化，且使用Cython 提高計算性能，因此在該項任務(wù)中一直保持較快的執(zhí)行速度。

可以看到，在近87%的情況下，基于GGFN 模型的優(yōu)化方法選擇了最佳的執(zhí)行平臺，即使是在兩個運行平臺時間相差較小的情況下。只有在少數(shù)困難的情況下未能選擇出最佳的平臺，如Word2Vec 任務(wù)在5 MB 輸入時。因此，可以得出以下結(jié)論：基于GGFN 模型的優(yōu)化方法可以為絕大部分任務(wù)選擇出最佳平臺并防止任務(wù)陷入極端的執(zhí)行情況，如在30 GB 下的WordCount 任務(wù)并未選擇JavaStream 作為執(zhí)行平臺。

4.4 多平臺下優(yōu)化效果分析

本節(jié)將評估基于GGFN 模型的優(yōu)化方法能否利用多平臺優(yōu)勢加速任務(wù)工作流的執(zhí)行。實驗使用一個真實環(huán)境下的用戶信用相關(guān)性分析任務(wù)作為實驗工作流，如圖9 所示。該工作流包含11 個算子，使用Credit-Card-Approval-Prediction 數(shù)據(jù)集作為工作流輸入。該數(shù)據(jù)集包含用戶信息和用戶信用記錄兩個部分。該工作流對此數(shù)據(jù)集進行處理后使用Kmeans 分析影響用戶信用的相關(guān)因素。

圖10 顯示了該任務(wù)工作流僅在JavaStream、Spark、Flink 的單平臺下的運行情況，以及使用了基于GGFN 模型的優(yōu)化方法為工作流中算子根據(jù)情況選擇實現(xiàn)平臺后的運行情況?？梢园l(fā)現(xiàn)，在輸入數(shù)據(jù)集小于1 GB 時，優(yōu)化方法僅選擇JavaStream 作為執(zhí)行平臺，因為此時的JavaStream 運行時間總是小于其他平臺數(shù)據(jù)處理時間以及中間結(jié)果的文件生成所帶來的時間開銷。當(dāng)數(shù)據(jù)集大于1 GB 時，優(yōu)化方法選擇結(jié)合JavaStream 和Flink 或者Spark 進行計算。其中，由于算子1～算子3 所在分支的輸入數(shù)據(jù)集（用戶信用記錄表）僅包含3 列數(shù)據(jù)，且數(shù)據(jù)集大小僅為用戶信息表的30%，算子ReduceBy 會把數(shù)據(jù)壓縮至輸入數(shù)據(jù)的5%。因此，該分支總是被選擇由JavaStream 執(zhí)行。例如，在輸入數(shù)據(jù)集為2 GB 時優(yōu)化方法選擇了JavaStream 和Spark 平臺并將任務(wù)工作流分為兩部分執(zhí)行。

圖10 用戶信用分析任務(wù)運行時間對比Fig.10 The comparison of user credit analysis task runtime

基于GGFN 的成本優(yōu)化方法利用多平臺優(yōu)勢，根據(jù)不同情況為跨平臺工作流中的算子選擇合適的實現(xiàn)平臺從而提升性能。在該實驗中，使用基于GGFN 的成本優(yōu)化方法對任務(wù)工作流進行優(yōu)化后，性能較單機最差情況提升近3 倍，運行時間縮短60%以上，性能較單機最好情況提升近25%。

4.5 GGFN 模型分析

成本模型旨在幫助優(yōu)化方法根據(jù)預(yù)測的運行成本選擇最佳的物理工作流并避免出現(xiàn)最壞的情況，因此準(zhǔn)確的成本估計至關(guān)重要。為了評估GGFN 模型對于成本估計的準(zhǔn)確性，本文根據(jù)文獻［9］復(fù)現(xiàn)了Robopt 優(yōu)化器中基于隨機森林的成本模型。同時為了驗證GGFN 模型對于時間和結(jié)構(gòu)信息的提取能力，本文將其與深度神經(jīng)網(wǎng)絡(luò)（Deep Neural Networks，DNN）進行比較。DNN 包含8 個隱藏層，每個隱藏層有256 個神經(jīng)元，其模型輸入是算子特征和工作流特征向量的串接。在此基礎(chǔ)上，本文在WordCount、Word2Vec、PageRank 和用戶信用分析4 個任務(wù)上分別評估了GGFN 模型、隨機森林（RF）模型以及DNN模型的絕對誤差值（AE）以及相對誤差值（RE），如表1 所示。

表1 各個成本模型的AE 與RE值Table 1 AE and RE values of each cost model

實驗結(jié)果表明，GGFN 模型的準(zhǔn)確度優(yōu)于Robopt 中所采用的隨機森林模型以及DNN 成本模型。在絕對誤差方面，GGFN 比DNN 最高降低了81.1 s，比隨機森林模型最高降低了24.9 s。而在相對誤差方面，GGFN 模型比隨機森林模型提高近14.9%，比DNN 提高達42.6%。由于DNN 模型參數(shù)復(fù)雜，因此需要更多的訓(xùn)練數(shù)據(jù)幫助其分析影響成本的因素。雖然此次訓(xùn)練數(shù)據(jù)來自冷啟動和部分執(zhí)行日志，但仍不足以訓(xùn)練出可以準(zhǔn)確估計DAG 型工作流成本的DNN 模型。隨機森林模型由于相對簡單，因此具有更好的魯棒性，實驗中訓(xùn)練速度最快，使用也相對簡單，但在成本預(yù)測誤差方面與本文中的GGFN 模型相比仍有差距。這也充分說明了GGFN 模型可以利用GAT 和BiGRU 來提取DAG 型工作流中算子的結(jié)構(gòu)和時序信息，以實現(xiàn)更加準(zhǔn)確的成本估計。

4.6 優(yōu)化時間開銷分析

本文實驗評估了基于GGFN 模型進行跨平臺工作流優(yōu)化過程的時間開銷。在跨平臺工作流中增加算子來探究優(yōu)化延遲的變化情況，并通過對比來說明延遲貪婪剪枝的效果。其中每個算子的對應(yīng)平臺數(shù)目設(shè)定為3，這也是目前算子平均所擁有的平臺實現(xiàn)數(shù)，實驗結(jié)果如圖11 所示?？梢园l(fā)現(xiàn)，在算子數(shù)量小于15 時，基于GGFN 模型的優(yōu)化時間開銷僅比貪婪剪枝算法多1.5 s，但可以最大程度地避免產(chǎn)生局部最優(yōu)的情況，即使在算子數(shù)量為25 時，此時的優(yōu)化時間開銷仍小于3 s，這對于基于GGFN 模型優(yōu)化方法所帶來的性能提升來說是可接受的。為了保證優(yōu)化效果最大化并降低優(yōu)化時間開銷，因此在枚舉過程中使用延遲貪婪剪枝方法可以降低優(yōu)化時間，相比貪婪剪枝方法也具有較好的優(yōu)化效果。

圖11 優(yōu)化延遲開銷對比Fig.11 The comparison of optimization delay overhead

5 結(jié)束語

在大數(shù)據(jù)時代，結(jié)合多個平臺的跨平臺數(shù)據(jù)處理系統(tǒng)開始興起，而針對跨平臺系統(tǒng)的工作流優(yōu)化由于存在成本預(yù)測準(zhǔn)確度低等問題而難以實現(xiàn)較好的效果。本文提出一種高效的跨平臺工作流優(yōu)化方法。使用由圖注意力網(wǎng)絡(luò)和門控循環(huán)單元組成的GGFN 模型作為成本模型，用來捕捉跨平臺工作流的結(jié)構(gòu)信息和算子運行時序信息?；诔杀灸Ｐ偷墓烙嫿Y(jié)果，通過應(yīng)用枚舉算法為邏輯算子選擇合適的實現(xiàn)平臺，完成邏輯工作流到物理工作流的優(yōu)化轉(zhuǎn)換。實驗結(jié)果表明，基于GGFN 模型的優(yōu)化方法將現(xiàn)有跨平臺工作流性能提升近3 倍，且GGFN 模型可進行更準(zhǔn)確的成本估計。后續(xù)將進一步優(yōu)化剪枝方法和平臺枚舉算法，減少時間開銷，并與成本模型相結(jié)合，在低延遲開銷的情況下實現(xiàn)更好的跨平臺工作流優(yōu)化效果。