Mort：面向實時數據分發和傳輸優化的依賴性任務卸載框架

殷昱煜 茍紅深 李尤慧子 黃彬彬 萬健

（杭州電子科技大學計算機學院 杭州 310018）

隨著通信技術（如5G）和人工智能等關鍵技術的發展，邊緣計算（edge computing，EC）和物聯網（Internet of things,IOT）等大型分布式信息系統的格局和規模發生了顯著的變化.根據國際數據中心的《中國物聯網連接規模預測，2020—2025》和《2021 年11 月愛立信移動市場報告》顯示，截止到2025 年中國物聯網總連接量將達到102.7 億，將占到亞太地區（除日本外）總連接量的84%[1].同時，這些接入設備產生的數據也在急劇增加.預測顯示，截止到2027 年末移動網絡數據總流量可能達到370 EB[2].這些設備常分布于不同的地理位置，在多個方面存在差異（異構）：1）底層芯片，如EMPC（economic embedded multi-chip package），MCU（microcontroller unit），FPGA（field programmable gate array），DSP（digital signal processor）；2）計算能力；3）上層操作系統，如HelloX，Android IOT/Brillo，Windows 10 IOT Core，Ubuntu Core 16，FreeRTOS，TinyOS；4）網絡通信協議，如MQTT（message queuing telemetry transport），NB-IOT（narrow band IOT），ZigBee，CoAP（constrained application protocol），5G.隨著邊緣業務日趨繁雜，其應用程序也變得復雜，如虛擬/增強現實[3]、智慧交通[4]等.它們的計算需求較大、延遲敏感，普通邊緣設備不能提供其計算需要的資源，而云計算時延太高[5].因此，EC 和IOT 面臨2 個問題亟需解決：1）設備軟硬件異構性帶來的通信難問題，繁雜的協議使得數據共享和隱私保護等操作變得困難；2）低成本和對豐富的計算資源需求之間的平衡問題.低廉的設備成本促進了EC 和IOT 的發展，但卻難以完全滿足現階段的計算需求.

通信難問題主要是因為統一規范的缺失，發布訂閱系統（publish/subscribe system,PSS）[6]常常作為一種解決方案.PSS 是一種數據共享的模式和規范，它并不限制底層采用何種方式進行通信.在一般的實現中PSS 采用TCP/IP 方式，也可以使用如NB-IOT，ZigBee，WIFI 等常見方式.PSS 一般由發布者、訂閱者和事件服務組成，采用以數據為中心的數據分發模式，可以實現大規模分布式系統中各實體間數據的分發.在這種模式下，發布者將數據封裝成事件，訂閱者訂閱自己感興趣的事件，事件服務則負責將各事件分發給訂閱者.在分發過程中，不用關心具體的實體（異構性），發布者和訂閱者無需相互感知和連接，其交互完全匿名，具有靈活性、去耦合、異步通信等重要特點.PSS 在大型分布式消息系統中越來越受到重視，如基于千兆網的自動駕駛應用[7]、物聯網數據共享應用[8]、電力物聯網的應用[9]和機器人通信[10].

對于計算資源不足的問題，學界常常采用任務卸載.任務卸載是指將邊緣終端的計算任務卸載到邊緣服務器等資源豐富的計算節點上，從而同時滿足計算能力和時延要求.任務卸載可以分為2 個子領域[11]：獨立性任務卸載（independent task offloading）和依賴性任務卸（dependent task offloading）.獨立性任務是指任務之間沒有數據依賴關系，彼此獨立.獨立性任務卸載研究的問題往往是在一系列約束條件下，如計算能力、截至時間、電池容量等，如何將持續到達（或已經到達）的多個任務合理地卸載到附近資源豐富的計算節點上，以獲得最大的收益（或減少損失），如文獻[12]的執行時間和電池優化、文獻[13]的計算資源優化等.依賴性任務是指任務之間存在輸入輸出的依賴關系.同獨立性任務卸載相比，依賴性任務卸載問題還需要考慮任務之間的執行順序.對依賴性任務卸載的研究主要集中在仿生[14]、深度強化學習[15-17]等智能算法和數學優化[18]、啟發式[19-20]等傳統優化方法上.

在EC 和IOT 中，異構性帶來的通信難等問題可以通過借助發布訂閱模式提供統一的數據共享規范來解決.計算資源的匱乏可以采用任務卸載，由邊緣計算節點分擔計算需求，同時降低延遲.然而，當發布訂閱系統和任務卸載結合時會產生新的問題，如現有的任務卸載算法不能很好地應用在發布訂閱系統中.發布訂閱模式下的邊緣業務/應用具有3 個特點：1）由多個子任務構成，任務之間有依賴關系；2）任務具有周期性，在一段時間內重復執行單一功能，沒有明確的完成時間；3）任務執行中，往往存在大量的數據分發.因為具有周期性、高頻數據分發等特點，大量現有基于完成時間的任務卸載算法無法很好地應對這類場景.可以重復執行這些基于完成時間的任務卸載算法來模擬周期性，但會不可避免地引入調度等額外開銷.在此類應用中，數據傳輸帶來的開銷變得不可忽視，因此本文聚焦于PSS 下基于數據傳輸優化的依賴性任務卸載問題，并設計實現了框架Mort 來解決該問題.

針對依賴性和執行周期性的特點，Mort 實現了基于靜態代碼分析的任務分解和基于協程（可以理解為一種能夠保存CPU 上下文的函數）的調度模型.底層操作系統更強調通用性，它的調度策略更多的是考慮進程（線程）間的公平性，而無關上層業務.這些子任務間存在依賴關系，執行時有先后次序，若次序靠后的任務先被調度執行，就會浪費此次調度機會和CPU 時間.因此需要一種方式控制這些任務按照依賴次序調度以減少執行周期時間.本文中的任務以協程的方式實現，從而可以在應用層進行調度控制.雖然通過同步或設置進程優先級似乎也能達到同樣的效果，但同步操作依舊不能避免操作系統的錯誤調度，而優先級設置則更多是一種對操作系統的建議，不會得到明確的保證.

針對高頻率數據分發特點，為減少網絡帶寬資源的消耗和網絡擁堵的可能，Mort 實現了2 個任務卸載算法：基于分組的任務卸載（grouping-based task offloading，GBTO）與基于分組和資源融合的任務卸載（grouping and fusion-based task offloading，GFBTO）.GBTO 采用分組策略，在鄰近的計算節點中選擇滿足任務資源需求的節點，并盡可能將任務卸載到其所需數據的源頭.考慮到滿足依賴關系的多個任務卸載到同一個計算節點后可以共享計算資源，由此本文在GBTO 的基礎上提出基于路徑歸并的計算資源優化算法GFBTO，進一步減少帶寬資源的消耗.然而，應用GFBTO 會使得計算節點的負載變高，在某些場景中可能會降低系統響應性.因此GBTO 適用于CPU 密集型任務組，而GFBTO 更加適合I/O 密集型任務組.GFBTO 算法能夠將更多的任務卸載到同一個計算節點，這些任務可以在應用層得到調度，使得其執行周期變短，也適合于時間敏感型任務.無論是GBTO 還是GFBTO 都更傾向于把任務卸載到其輸入源處，盡可能地讓數據在本地處理（哪里產生哪里處理），盡可能地減少數據在網絡中傳輸，同時也減少了由于數據傳輸帶來的網絡延遲，任務能更加及時地計算出結果.為了更好地使用這2 種算法，Mort 會根據各計算節點CPU、I/O 利用率和任務組的I/O 密集型任務的占比來選擇合適的卸載算法.本文的主要貢獻總結為4 個方面：

1）設計實現了任務卸載及管理框架Mort.針對PSS 中任務的依賴性、周期執行性和高頻率數據分發特性，Mort 采用了任務分解、任務卸載和協程調度3 個步驟，增加了任務并行度、減少了網絡數據傳輸量和減少了任務調度開銷.

2）將面向發布訂閱系統的任務卸載數據傳輸優化問題建模為非線性整數規劃問題，并設計了一種基于數據依賴分組策略的優化算法GBTO 來解決它.

3）進一步挖掘任務間依賴特性，在GBTO 基礎上設計了一種基于路徑歸并算法GFBTO.該算法使得卸載到同一計算節點的屬于同一任務組的任務間能共享計算資源.與GBTO 相比，GFBTO 使得同一個計算節點上卸載的任務數量增加，提高了計算節點的負載，但同時也增加了任務并行度和減少了操作系統的調度切換開銷.因此GBTO 更適合CPU 密集型任務，而GFBTO 更適合I/O 密集型和時間敏感型任務.

4）針對GBTO 和GFBTO，設計了仿真和真實場景實驗.在仿真實驗中，GBTO 和GFBTO 的數據傳輸分別能達到OPT 的80%和90%左右，且GBTO 比Greedy高出約50%.在真實場景中，設計了一個分布式的文本統計作業，分別應用GBTO，GFBTO，Greedy 算法卸載，其結果與仿真實驗一致，并且，Mort 本身引入的開銷僅約為2%.

1 任務卸載相關工作

1.1 獨立性任務卸載

設計了一個在線近似算法，并證明了其近似比為2(1+ε)ln(1+d).在動態的移動邊緣計算環境中，

獨立性任務是指卸載的任務之間沒有任何關系，相互獨立.數十年來，獨立性任務卸載領域已有大量成果，它們可以被分為2 類：離線算法[12-13,21-25]和在線算法[11,26-30].離線算法需要知道所有任務的信息，然后統一卸載任務最大化目標.文獻[21,23-24]主要關注如何最小化卸載時服務的響應時間.文獻[21]注意到服務響應時間可能受設備之間連接性的影響，為協調分配，設計了一個分布式卸載算法；文獻[23]提出一個2 層的緩存迭代更新算法來解決該問題，而且還能有效減少卸載過程中的數據傳輸；文獻[24]則是任務卸載和服務緩存在線聯合優化機制，將任務卸載和服務緩存聯合優化問題解耦為任務卸載和服務緩存2 個子問題.在線算法不需要提前知道任務的信息，它們可以在任意時刻到來.文獻[11]從最大化服務提供方收益的角度考慮，利用原始對偶方法文獻[30]考慮IOT 設備的計算任務卸載問題，并基于強化學習設計了一個任務卸載的框架.

文獻[11-13，21-30]所述工作主要面向獨立性任務，它們假設任務以時間次序到達（在線）或已經到達（離線），其目標是最小化任務完成時間或最大化資源收益等.而在具有依賴性、執行周期性和高頻率數據分發等特點的任務卸載問題中，這些算法的作用并不明顯.

1.2 依賴性任務卸載

依賴性任務是指待卸載的任務之間存在輸入的依賴關系[31].依賴性關系卸載問題是典型的DAG 調度問題，屬于NP-Hard，相關工作較少.一些工作借助智能算法嘗試解決該問題[14-16].面對復雜的依賴性組合優化問題，文獻[14]采用了基于隊列優化的粒子群算法來減少整個任務的完成時間和執行開銷.與文獻[14]不同，文獻[15]提出了PTRE（priority-topologyrelative-entropy）算法，將任務DAG 轉化為任務向量序列，從而采用基于深度強化學習的圖映射框架來達到目標.文獻[16]將資源受限的邊緣計算環境下的多作業卸載問題建模為馬爾可夫模型，并利用深度強化學習算法減少其傳輸和計算開銷.智能算法在很多NP-Hard 問題上表現優秀，然而其耗時較長且沒有理論保證其性能.更多的工作嘗試利用數學優化、改進的貪心策略或者精巧的啟發函數來近似求解.在最小化任務完成時間方面，文獻[19]考慮一個應用由多個任務構成，結合服務端的函數配置和任務卸載，設計了一個近似算法，但它卻忽視了邊緣服務器的計算能力.借助DAG 中的關鍵路徑思想，文獻[32]提出了HEFT 啟發式算法以減少任務的最早完成時間.注意到在卸載過程中，邊緣服務器和移動設備側重的點不同，文獻[33]提出一個啟發式算法，盡可能地提高服務器的資源利用率，減少移動設備的能量消耗.文獻[34]認為簡單地將任務分配到遠端云上，其無線通信開銷可能比其收益更大，因此設計算法HTA2，以減少異構移動系統中的能源開銷.另外一些工作[35-37]則綜合考慮任務的完成時間和能量消耗.文獻[35]提出 MAUI，即提供細粒度的應用代碼到遠端服務器的部署，能夠在運行時決策將其代碼卸載到何處，并最大化節省能量和減少時間消耗.文獻[36]從軟件提供方角度出發，考慮最小化遠端計算開銷和移動設備能量消耗，并控制服務響應在一定合理的延遲內，設計了一個多項式時間算法DTP.文獻[37]的目標同樣是節省能量開銷、計算開銷和減少延遲，它設計了一個 3 階段算法 SDR-AO-ST（semidefinite relaxaion，alternating optimization，and sequential tuning），能夠有效減少系統開銷.

文獻[14-16，19，32-37]所述的工作都假設任務有確切的執行時間，數據傳輸是單次的.然而，發布訂閱系統中的任務不僅具有依賴關系，還具有周期性，沒有明確的結束時間，執行中往往存在大量數據分發.針對周期性和大量數據分發的優化不僅可以優化帶寬資源（減少數據在網絡中的傳輸），還能降低等待網絡數據帶來的高延遲（通過將任務卸載到數據源處），然而上述工作沒能考慮這些問題.因此本文基于PSS 設計了面向數據傳輸優化的卸載算法.

2 Mort 架構

為高效地完成業務解析、任務卸載、任務管理以及數據分發等操作，本文設計了Mort，圖1 是它的架構.本節介紹其中主要的組件和系統工作流程.

Fig.1 Mort architecture圖 1 Mort 架構

2.1 作業分解/任務構造組件

用戶通過用戶接口編寫代碼和作業描述文件.作業分解組件借助這些信息構建有向循環圖（directed acyclic graph，DAG）任務組實例，如圖2 所示，其中的dij,rtj分別表示數據依賴和計算資源需求.某些任務除了依賴本組其他任務外還可能需要外部的數據，因此在構建任務組時會創建虛擬任務.該組件構造的DAG 任務組實例會提供給卸載算法組件.

2.2 卸載算法組件

Fig.2 Job decomposition圖 2 作業分解

卸載算法組件會結合鄰近可達計算節點的狀態信息（由任務管理組件提供）和任務組實例，執行GBTO 或者GFBTO 算法，生成詳細的任務卸載計劃.隨后管理組件依照該計劃將任務部署到具體的計算節點上.

2.3 任務管理組件

任務管理組件會維護網絡中所有可達計算節點的狀態，包括計算節點的資源信息、其上運行任務的權限和狀態等信息，為實際的任務卸載提供數據支撐.同時，通過該組件還可以管理各任務的運行狀態.

Fig.3 System workflow圖 3 系統工作流

2.4 數據分發組件

該組件基于發布訂閱模型實現，為其他組件提供數據服務.它主要提供2 個功能：1）同步網絡中邊緣計算節點的狀態信息；2）完成數據的分發.

2.5 持久化組件

持久化組件主要是將設備實時產生的數據持久化.數據持久化能為歷史數據服務提供支持，而且當網絡不穩定時還能在一定程度上提高系統的服務質量（quality of service，QoS）.

2.6 樣例分析

本節以一個例子介紹Mort 在實際場景中是如何實施的，如圖3 所示.考慮這樣一個簡單例子，城市規劃中，紅綠燈時長分配對路段交通擁堵有很大影響，極端情況下可能在幾個路段間引起連鎖反應.在智慧城市中，可以根據路口人流量、車流量、天氣等情況動態改變時長.對于這類動態檢測及控制應用，卸載時需要考慮到數據傳輸的開銷、計算節點的負載等以盡量減少單次計算的時間，因此選擇合適的計算節點尤為重要.

智能紅綠燈場景中，可以將作業構造成4 個子任務：人流量檢測任務、車流量檢測任務、天氣檢測任務和決策任務.城市管理人員將Mort 部署在城市的每一個計算節點上，他們可以在任意一個節點提交作業描述文件.任務構造組件讀取描述文件后將構造這4 個子任務，并將它們傳遞給任務管理組件.任務管理組件會結合任務類型和鄰近節點狀態選擇合適的卸載算法，將任務組和相關信息傳遞給卸載算法組件制定卸載計劃.卸載算法組件執行相關卸載算法后將卸載計劃返回給任務管理組件，任務管理組件再通過數據分發組件將任務分發到各個計算節點執行.任務執行過程中需要訂閱的數據和發布的數據由數據分發組件在各個節點間傳輸.任務執行過程中產生的數據和操作記錄等信息可能會記錄在持久化組件中以供后續分析使用.

數據傳輸以發布訂閱方式進行，且只會發生在計算節點之間.任務卸載到計算節點后，在其生命周期內按照“訂閱到數據—計算—發布數據”這樣的方式循環執行.在任務組構造過程中會為用戶端構造一個任務用來訂閱計算結果.

3 Mort 實現

本節將詳細介紹Mort 主要組成部分的實現.

3.1 作業分解/任務構造組件

作業分解/任務構造組件通過源代碼靜態分析得出任務間的依賴關系（通過訂閱發布的數據類型和一些其他的控制流接口），再結合作業描述文件進一步構造任務組實例.

靜態代碼分析通常有控制流分析[38]和數據流分析[39]兩種，本文采用數據流分析方式.通過分析追蹤各份源代碼中函數調用情況和參數傳遞信息來建立各任務之間的依賴關系.這里結合一個例子闡述其實現方式.假設有一項作業由TaskA，TaskB，TaskC這3 個子任務構成.如圖4 左邊，任務TaskA和TaskB分別訂閱Topic_V1（由任務TaskV1發布）和Topic_V2（由任務TaskV2發布）數據類型，同時發布Topic_A和Topic_B數據類型.任務TaskC同時訂閱Topic_A和Topic_B數據類型.TaskA，TaskB，TaskC這3 個任務分別調用函數Task::RegTask（name,…）注冊自身信息，調用函數Task::RegSub（topic_list）注冊訂閱數據類型，調用函數Task::RegPub（topic_list）注冊發布數據類型.如圖4 中間，分析A代碼時，能夠構建TaskA與TaskV1的數據流關系（通過查詢任務管理組件獲取TaskV1到TaskA的數據量和頻率）；分析B代碼時，能夠構建TaskB與TaskV2的數據流關系；分析C代碼時，能夠部分構建TaskA，TaskB，TaskC之間的數據流關系.如圖4 右邊（任務TaskV1和TaskV2不屬于本次任務組，所以用深色標識），融合TaskA，TaskB，TaskC時，可以完整構建任務DAG 數據流，此時再結合作業描述文件獲取各個任務的資源需求等信息，任務組DAG 就能夠構建完成.在融合時，各任務只能依賴已卸載或存在本任務組中的任務，不能循環依賴.當這些步驟執行后，任務組構建完成.

Fig.4 Static program analysis to build task group圖 4 靜態代碼分析構造任務組

3.2 任務管理組件實現

任務管理組件主要負責響應系統環境的變化、接收用戶命令、執行卸載算法組件給出的卸載計劃以及調度卸載后被抽象成協程的任務，如圖5 所示.

在PSS 中，數據的發布和訂閱需要授權[40].Mort 的權限驗證模塊使用了基于屬性的訪問控制（attributed based access control，ABAC）技術，并增加了地理位置、資源利用率等動態屬性.當系統環境等上下文變化時，可能會引起權限的變化，而且用戶也可以通過用戶接口顯式地改變某些屬性值或權限.為進一步對數據傳輸提供保護，還可以將數據加密后進行傳輸，或為計算節點引入證書等方法.

Fig.5 Task management component logic implementation圖 5 任務管理組件邏輯實現

每一個計算節點上都會部署Mort.為了使這些節點上的任務管理組件信息同步，Mort 啟動后會在數據分發組件中維護/right，/state，/cmd 這3 個數據域，分別用來同步權限、節點/任務狀態和來自其他節點的命令等信息.該組件還包含一個沖突處理模塊，主要負責處理同步導致的節點狀態的不一致.不一致主要是因為多個用戶同時設置不同的權限或命令而引發的沖突.對于這2 種沖突，會根據用戶權限（higher-prior win）、操作先后次序（first-commit win）等情況判定和記錄日志后續恢復等措施解決.

任務卸載后，從任務管理組件的角度來看（任務視圖），一個進程包含多個線程，一個線程包含多個協程，在線程調度協程時（執行視圖），它首先會處理新到來 的命令（函 數process）、更新權 限（函 數updateRight），然后分發數據.在分發數據階段，每個任務都被抽象成了發布者或訂閱者，訂閱者響應數據到來事件，發布者產生過期事件（按一定頻率發布數據）.分發數據主要是處理這2 種事件和權限鑒定.其中函數resume、函數execute、函數suspend操作是協程的調度操作.函數resume表示恢復當前協程的CPU 上下文；函數execute則是讀取或者發布數據；而函數suspend是保存當前協程的CPU 上下文，讓出CPU.

3.3 數據分發組件實現

該組件負責接收發布者的數據、將數據分發給訂閱者和接收/分發來自任務管理組件的命令等功能.數據分發組件的實現采用的是OMG（object management group）發布的DDS（data distribution service）規范[41]，業界也有很多成熟的實現，如FastDDS[42].Mort 除了基于DDS 實現了分布式網絡分發之外，還針對本地數據分發做了優化，如分發到本地的數據不再走網絡部分，而采用進程間共享內存或進程內共享（被綁定在一起的屬于同一任務組的任務間共享）內存的方式.

3.4 卸載算法組件實現

卸載算法組件負責在構造的任務組上執行卸載算法從而給出具體的卸載計劃.下面闡述其具體實現.

3.4.1 卸載算法組件建模

1）作業及任務模型

如圖2 所示，用戶作業由M個依賴性子任務組成，記為J={t1,t2,…,tM}.每個子任務可以表示為ti={di*,rti}，其中di*=(dij)是一個向量，表示任務之間的數據依賴：如果任務ti不依賴tj（tj不需要傳輸數據給ti），則有dij=0；反之，任務ti依賴tj，則依賴數據量為dij（單位：bps）.一般地，這些子任務還可能依賴外部的任務，如圖2 中構造的3 個虛擬任務rt0，rt1，rt2.這3 個任務不屬于該次作業，而是之前已卸載的任務，現存在于某些計算節點上.rt也是一個向量，rt=(rti)i=1,2,…,M.rti表示該任務i的資源需求，為簡單起見，此處指CPU 核數.本文任務模型中，用戶作業指移動邊緣計算中的業務作業，其包含的任務無明確的執行時間，它們可能會滯留計算節點重復執行.每個任務不能再次劃分，且只能分配到一個計算節點.

2）計算節點及卸載模型

假設當前網絡中有N個計算節點，記為C={c1,c2,…,cN}，且每一個計算節點當前有rcj個空閑的CPU 核.設Aij=1 表示將任務i卸載到計算節點j，卸載到每個計算節點的任務不能超過該節點的CPU 空閑容量，因此有

假設網絡中的計算節點總能容納所有的任務（不考慮等待的時間），而且每個任務在其生命周期內只能卸載到一個計算節點上，所以對于本次作業的所有任務有

需要注意，該模型的任務組中的任務可能依賴之前已經卸載了的外部任務.這些約束需要結合實際情況考慮.假設 S是在之前就已經被分配任務的集合，且對應的計算節點集合為 P，有

本文中的計算節點包括2 個部分：邊緣服務器和計算存儲資源相對豐富的邊緣設備，它們一般負責與一定區域的邊緣設備和傳感器交互，包括數據共享和命令傳送.

3）問題模型眾多邊緣設備和傳感器在高速、大量地產生原始數據，這些數據稍后在網絡中共享、處理.卸載任務時考慮數據的傳輸優化可以有效地減少整個網絡中數據的傳輸量.因此本工作中的卸載算法需要解決的問題是：給定一組依賴性任務J={t1,t2,…,tM}（包括它們的CPU 需求和數據依賴）和一組邊緣計算節點C={c1,c2,…,cN}（包括它們的CPU 空閑容量），如何將這些任務卸載到這些計算節點上，使得整個網絡中傳輸的數據最小，即卸載后任務本地處理的數據量最大

Fig.6 Illustration of algorithm 1圖 6 算法 1 的圖解

這是一個非線性整數規劃模型，可以將整數約束用等價的二次項替換，從而達到松弛變量的效果.因此，式（2）可以改為

許多工作已經證明，在異構環境中的DAG 調度是NP-hard[43]，式（6）（7）描述的模型同樣是一個NPhard 問題.

3.4.2 GBTO 算法實現

本節提出了一個基于分組的任務卸載算法GBTO近似地解決該問題，并給出復雜度說明.該算法分為2 個部分：預處理和任務卸載.

1）預處理

在預處理中，借鑒了字符串匹配算法KMP 的思想，盡量挖掘對象自身的模式來加速后面的卸載過程，圖6 和算法1 描述了其細節.

圖6 中，圓形表示任務，圓形中間的rti表示該任務的CPU 需求，圓形上邊的數字表示任務編號，而箭頭上邊的dij表示任務之間數據傳輸量.在預處理時，首先求得任務組的拓撲序列，該操作由算法1 中的函數topologicalS equence完成.然后從后往前遍歷拓撲序列，根據其數據依賴的大小主動選擇一個它的直接前驅任務并為一組（如圖6 中的虛線有向箭頭和算法1 中的行②～?，其中函數merge表示集合的并集操作）.待所有任務選擇完之后，整個作業就被分為了若干組（如圖6 中被分成了3 組：[0,2,4,5,7],[1,3,6],[8]），這些組稍后會作為一個整體考慮.每一個組都有一個領頭任務（不算虛擬任務，如圖6 中的虛邊框任務2 和任務3），它記錄著該組的所有數據依賴量D和資源需求量RT.虛擬任務不參與分組.

算法1.GBTO 預處理.

2）任務卸載

預處理過程構造了若干個初始任務組，該階段將以它們為單位進行2 步驟卸載.圖7 和算法2 詳細描述了此過程.

①預卸載（如圖7 的左半部分，算法2 行②～?）.每一個組的領頭任務嘗試卸載本組任務到各個計算節點cj，并記錄其收益Profitj，即該組任務卸載到計算節點cj上時能保留的依賴數據總量.卸載時可能會出現RT＞rcj的情況，即節點不能容納該組的所有任務.此時領頭任務將依據組內拓撲序列從后向前依次模擬移除任務，直到剩下的任務可以被該節點容納，同時在可被卸載的節點中記錄能取得的最大收益，即Profitimax.

② 正式卸載（圖7 的右半部分，算法2 行?～?）.待所有組預卸載之后，從中選取收益最大的組進行正式卸載（算法2 行?，圖7 中則是組1 在pro fit1取得最大）.被選中的組在卸載之前先移除前一步驟中模擬移除的任務.這些被移除的任務會根據實際情況或加入現存的組或構造新的任務組.具體地，對于每一個被移除的任務，在還未卸載的前驅中選擇依賴數據量最大的前驅，然后并入該前驅所屬的組.如果沒有這樣的前驅存在，則該任務獨自構成一新組（算法2 行?～?，而圖7 中則是組1 移除了1 個任務，該任務被并入到了組2）.正式卸載某一組后需修改計算節點容量，以及計算節點訪問標志，后續剩余組更新時，只需要重新計算發生變化的節點即可（算法2 行?，及圖7 中組2 需要重新計算其Pro fit1）.最后重復執行算法2 行②～?過程，直到所有任務卸載完成.

Fig.7 Illustration of algorithm 2圖 7 算法 2 的圖解

算法2.GBTO 任務卸載.

①預處理過程.比較耗時的2 個操作為計算任務的拓撲序列和遞歸分組.拓撲排序在任務構造時已經完成，故此處不用計算.合并函數merge是線性的，時間復雜度為O(M)，且是本地執行，不需要額外的空間，空間復雜度為O(M).

②任務卸載階段.假設預處理將任務分為了H 組，則在第1 次預卸載過程中需要執行H×N次嘗試.后面的預卸載中，每組只需要重新計算發生變化的計算節點即可，因此，總共的時間復雜度為

其中H ∈[1,M]，而在絕大多數情況下 H接近1，因此GBTO 最壞時間復雜度為O(N×M2)，空間復雜度為O(M).

3.4.3 GFBTO 算法實現

GBTO 算法會依據任務組的CPU 需求判斷能否將該組任務分配到某個計算節點上，而計算組CPU總需求時只是將組內各任務的CPU 需求簡單相加.在一個任務組中，任務之間的關系可以分為2 類：一類是有（直接/間接）前驅后繼關系；一類是無依賴關系.一個任務只有在它的所有前驅任務執行完獲取到輸入數據后才能運行.因此具有前驅后繼關系的任務間沒有并行的必要性，而無依賴關系的多個任務卻可以.如圖8 所示，若讓該任務組內無依賴關系的任務并行，則需要的CPU 可以從9 減少至5（其中數字表示CPU 需求）.引入CPU 資源融合操作后，能減少組CPU 需求，能讓更多有依賴關系的任務卸載到同一節點，就能進一步減少網絡中的數據傳輸.采用資源融合策略后，計算節點的負載會變高，可能會增加CPU 密集型任務的響應時間，因此，GBTO 和GFBTO 的適用場景不同.任務管理組件會檢測各計算節點的狀態，同時會給出使用何種算法的建議.

Fig.8 CPU merge圖 8 CPU 融合

GFBTO 算法的難點在于如何快速確定一組任務中的CPU 最大并行數.針對這一難點本文設計了一個基于路徑歸并的資源融合（road merging-based resource fusion，RMBRF）近似算法.圖9 和算法3～5 詳細展示了其過程.

GBTO 算法中，一組任務卸載時，會根據組內信息判斷其是否卸載，而RMBRF 通過拓撲排序、路徑加入和路徑傳播3 個步驟重新計算了組CPU 總需求信息.后2 個步驟細節為：

1）路徑加入

從任務組的前若干個任務執行開始，到所有任務執行完成（或所有任務都得到執行1 次）會存在多條數據流向，每一條都是一個依賴路徑，圖9 中的每一個標有數字序列的矩形框就是一條路徑.算法3 執行時，會記錄從某一個任務往后存在的所有路徑，即算法3 中的路徑集合Lcur.路徑是從后向前傳播的，當前任務需要選擇一條路徑加入，該路徑通過調用函數theBestRoad得到.函數theBestRoad依照如下原則選擇路徑：計算每一條路徑中的最大CPU 需求（算法4 行①～④），然后比較當前任務的CPU 需求和所有路徑中的最大CPU 需求，若當前任務CPU 需求較大，則選擇CPU 需求最小的路徑加入，否則選最大的加入（算法4 行⑤～⑨）.這一策略使得當前任務加入某一條路徑后，所有路徑最大總CPU 增長最小.

Fig.9 Road merging-based resource fusion（algorithm 3）圖 9 基于路徑歸并的資源融合（算法 3）

2）路徑傳播

類似地，由于存在多個前驅任務，當前任務還需要選擇將某一條路徑向前傳播給哪一個前驅.該前驅通過調用函數theBestFather（算法5）得到.函數theBestFather中選擇前驅結點，采用和函數theBestRoad一樣的策略，不同的是此時根據單條路徑從前驅節點集合中選擇單個任務.圖9 的步驟①～④清晰地描述了路徑加入和路徑傳播2 個過程，但求出的結果不是最優，而是近似最優.

算法3.RMBRF.

算法4.theBestRoad.

算法5.theBestFather.

3）GFBTO 復雜度分析

在GBTO 算法的基礎上，GFBTO 增加了RMBRF操作.RMBRF 包含拓撲排序、路徑加入和路徑傳播3 個步驟.設任務組中邊集為E，則拓撲排序在任務構造期間已經求得，此處不需要再次計算.而路徑加入和路徑傳播只會訪問每條邊1 次、每個頂點1 次，因此，時間復雜度均為O(M+|E|).同時，每個結點和邊也只會存儲1 次，因此空間復雜度同樣是O(M+|E|).

3.4.4 卸載算法的選擇

GFBTO 算法傾向于將更多的任務卸載到同一個計算節點，如果這些任務的計算占比很大，CPU 則會疲于上下文切換，各個任務的有效執行時間將減少，不利于低延時的任務.因此GFBTO 算法會傾向于將I/O 密集型任務放在一起，在部分任務等待I/O 時CPU也能得到更好的利用.

然而，精確地衡量一個任務的計算與I/O 占比很難，Mort 從2 個方面進行估計：1）源代碼靜態分析.4.1 節介紹了如何從源代碼中得到任務組DAG，在DAG 中很容易得知一個任務的輸入和輸出，因此Mort假設，一個有更多輸入源或輸出源的任務的I/O 占比更高.2）計算節點狀態監控.源代碼分析的結果可能存在偏差，為了能夠監控和均衡這一偏差，任務管理組件會實時收集節點的CPU 和I/O 利用率.

結合以上2 點，Mort 采用如下的方式選擇卸載算法：計算多輸入、多輸出任務在整個任務組中的占比，若占比超過一定閾值（默認70%，是一個經驗值，即預估一個作業有70%的時間處于I/O，當處于I/O的時間較多時，更多的線程/協程能有效利用CPU，該值可以配置）就選擇GFBTO，否則選擇GBTO.同時依照節點的CPU 利用率對節點進行排序，GFBTO 從高到低選擇節點進行卸載，GBTO 由低到高選擇節點進行卸載.

以上2 點考慮目前只用于選擇卸載算法，不作為算法運行時的參考因素，不影響算法執行結果.

4 仿真實驗

本節將進行仿真實驗，比較Greedy（采用降序首次適應思想實現的貪心算法）、GBTO、GFBTO、OPT（采用LINGO 18 數學優化軟件求解3.4 節數學模型的最優解）之間的性能.

4.1 仿真實驗設置

1）計算節點分布數據集

計算節點分布數據集[44]開放了共享單車騎行數據集，將之處理后得到單車停靠坐標分布圖（共400多萬個點）.將其按密度劃分為多個區域（半徑200 m），每個區域部署1 個計算節點，從而得到97 個計算節點，如圖10 所示.圓形小點為單車停靠點（其中有大量圓形小點的點坐標重疊），星型為部署的計算節點.為確保任務能一次性卸載到這些節點上，節點的總計算能力與作業總計算需求成正相關，且每個節點的計算能力占比與其管理的點的數量占比正相關.共享單車停靠坐標，可能是人類活動的熱點區域，也可能是城市公共智能設施傾斜的地方，大量的原始數據會在這里產生，因此計算節點適合布置在這些地方.

Fig.10 Distribution of computing nodes圖 10 計算節點分布

2）任務數據集

任務數據集采用的是阿里巴巴2018 年公開的集群作業數據集[45].數據集中包含上千萬個作業，每個作業由1～30 個任務組成.實驗時將數十數百個原始作業融合成一個大型的作業，使其具有上百或上千個任務.每個任務的CPU 需求參照數據集中的數據，并適當地縮小，其范圍為1～3（具有1 個CPU 需求的任務占比60%，具有2 個CPU 需求的任務占比30%，具有3 個CPU 需求的任務占比10%）.本文假設任務之間的數據依賴量均勻分布，其范圍為64～8 192 bps.

Fig.11 Data profits and simulated task distribution mode for simulation experiment圖 11 仿真實驗中數據收益與虛擬任務分布模式

4.2 仿真實驗結果分析

4.2.1 變化虛擬任務分布模式

圖11 中任務數量固定為200，計算節點數目固定為90，只需改變虛擬任務的分布模式.第1 個（ATCP）是虛擬任務更傾向于分配到計算能力強的計算節點上；第2 個（ATCP-R）是虛擬任務更傾向于分配到計算能力弱的計算節點上；第3 個則是采用隨機分布（Random）.很 明顯，在ATCP 中GFBTO 的結果超過了OPT，原因有2 點：1）GFBTO 算法采用了資源融合策略.資源融合使得每個計算節點能夠容納更多的任務，而OPT 模型并沒有資源合并操作.2）虛擬任務被優先分配到了計算能力強的節點上.結合第1 點，這使得GFBTO 算法執行時會更少地移除任務（因為融合后，有充足的CPU 資源），也就能保留更多的組內任務，前驅任務產生的數據也就盡可能地被本地消耗，而不用傳輸到網絡中去.在ATCP-R實驗組中，Greedy 效果尤其差.這是由于大多虛擬任務分配在計算能力差的計算節點上，而貪心策略看重當前次的收益使得這些節點的空間被浪費，陷入了較小的局部極值.

4.2.2 變化任務數量

Fig.12 Data profits and task amount圖 12 數據收益與任務數量

圖12 中計算節點數目固定為90，虛擬任務分配方式固定為隨機分配，任務數量從50 增加到300.可以看到，隨著任務數量的增加，各算法的結果都有所增加，這是因為任務增多，總的數據量也相應增加.與其他實驗組規律比較，不同的有2 組，分別是任務數量為50 和200 時的對比組.任務數量為50 時，GFBTO 超過了OPT，可能的原因是，此時任務數相對于計算節點數目較少，資源融合后資源較充足，更多有依賴關系的任務被卸載到同一計算節點，與4.2.1 節中的ATCP 組相同.任務數為200 時，各算法結果都相對較高，經查閱原始數據發現，GFBTO 的各任務的平均數據量比其他組高約20%.該實驗中，各算法結果規律同4.2.1 節中的Random 組類似.

4.2.3 變化計算節點數量

圖13 中，任務數量固定為200，虛擬任務分布為隨機分配，而計算節點的數量從30 增加到80.該實驗最能體現算法的不同：在計算節點較少時，可選擇的也少；更多有依賴關系的任務被集中在一起，各個算法的差異也就越小.而隨著計算節點數量的增加，選擇變多，算法之間的策略差異被放大.可以看到隨著選擇變多，所有算法情況都在變糟，但GBTO 和GFBTO 表現很穩定，受影響較小.

Fig.13 Data profits and computing nodes amount for simulation experiment圖 13 仿真實驗中數據收益與計算節點數量

實驗結果表明，任務在本地的數據消耗量方面，GBTO 平均高出Greedy 65%上下，GFBTO 在GBTO的基礎上平均提升了約10%，而且GBTO 和GFBTO分別達到了OPT 的82%和94%左右.

5 真實場景實驗

本節構造了一個文本統計與分析應用在真實的硬件環境中測試算法的性能.

5.1 場景實驗設置

1）軟硬件平臺

Fig.14 Hardware platforms圖 14 硬件平臺

本實驗選擇了4 個樹莓派4B（ARM-Cortex-A72,64b 1.5GHz,4-core,4GB）、1 個樹莓派3B（ARM-Cortex-A53,64b,1.4GHz,4-core,1GB）和1 臺PC（Intel i5-10500，3.10 GHz，3.10 GHz，6-core,8GB）作為計算節點，如圖14 所示.實驗中將設備分別編號：計算節點node 0（樹莓派3B），計算節點node 1～node 4（都是樹莓派4B），計算節點node 5（PC）.為確保所有任務都能夠被卸載，各計算節點的計算能力都按其本身的CPU 核數成比例放大.每個機器都以Ubuntu20.04 LTS 作為操作系統，并部署了Mort.實驗過程中，各任務將以50 Hz 的速度在300MB 局域網內發布數據.

Fig.15 Real scenario experiment task instance圖 15 真實場景實驗作業用例

2）作業數據集

如圖15 所示，本文構造了一個文本統計與分析應用.該應用由多個任務組成，每個任務負責統計某個區間內數字出現的頻率.RawData1 和RawData2 分別是一個1MB 的文本文件，F1～F6是應用包含的子任務.應用中，F1統計文本中[0,100）間的數；F2統計[100,199）間的數；而F3統計大于199 的數；F4統計3個區間中的偶數；F5統計3 個區間中的奇數；F6融合所有的結果.各任務統計過程中會將結果發布出去.圖15 中任務上邊數字表示每個任務的CPU 需求，C*表示全局數據域中的具有 C*數據類型的數據域.

5.2 場景實驗結果分析

Fig.16 Data profits and computing nodes amount for scenario experiment圖 16 場景實驗中的數據收益與計算節點數量

Fig.17 Data profits and simulated task distribution mode for scenario experiment圖 17 場景實驗中數據收益與虛擬任務分布模式

Fig.18 Mort performance圖 18 Mort 性能表現

實驗中分別將node 4 和node 5 作為RawData1 和RawData2 的數據源傳感器.實驗時，node 0 從node 4 上讀取RawData1 的數據，node 2 從node 5 上讀取RawData2的數據.圖16 和圖17 展示了3 種算法的效果和仿真實驗一致.圖18 是按照GBTO 算法生成的執行計劃將各個任務分配到2 個計算節點上（node 0：F1，F2，F3，F4，F5，F6；node2：F2,F3，并 且RawData1 在node 0 上，RawData2 在node 2 上）Mort 的各項性能表現.圖18（a）（b）分別是2 個計算節點上訂閱到的數據延遲統計.對于node 0，C2，C4，C5 這3 種數據類型來自網絡，平均延遲約為6.34 ms，而剩下的則是本地處理的數據類型，平均延遲約為0.410 ms；對于node 2，C1 是網絡中的數據類型，訂閱平均延遲為3.650 ms，C2 是本地處理的數據類型，平均延遲為0.4 ms.圖18（c）（d）是2 個計算節點的訂閱數據的丟包率，其丟包率都為0，其含有小數是因為計算時浮點數特性造成的.圖18（e）則是Mort 運行前、運行時、運行后CPU 負載變化.node 0 共運行了4 個發布者和7 個訂閱者；node 2 共運行了2 個訂閱者和4 個發布者.可以看到2 個節點分別在第3 秒和第9 秒時啟動Mort，CPU 使用率約有14%的增幅。從Mort 的運行機制分析，負載的大幅升高主要有3 個原因：1）初始化，包括狀態集初始化、訪問控制初始化、持久化組件初始化、本地數據域初始化等.2）服務發現，服務分發組件會主動發現網絡中其他Mort 實例.3）任務構造和卸載，初始化操作完成后，Mort 會處理用戶應用（如果存在），包括任務構造和卸載.從第12 秒和第16 秒開始，2 個節點的CPU 使用率大幅下降，比初始時僅高了約2%。這一階段，Mort 主要是完成數據分發和狀態維護等工作.在第59 秒時關閉Mort.實驗表明，Mort 生命周期內，計算節點的負載絕大多數時間處于較低水平.

6 結 論

本文設計并實現了任務卸載及管理框架Mort，主要是解決發布訂閱系統中的數據共享問題.任務來自上層業務，需要先對業務進行任務分解.對于任務分解，采用靜態代碼分析方法追蹤函數調用和參數信息，從而構建DAG 任務組.對于任務卸載，將問題建模成優化網絡數據傳輸的非線性整數規劃問題.在偏向于CPU 密集型任務和計算節點負載高場景中，設計了GBTO 算法.在偏向于I/O 密集型任務和時間敏感場景中，設計了GFBTO 算法.仿真和實驗表明，GBTO 和GFBTO 算法能達到最優值的80%和90%左右，且引入的Mort 負載只有約2%.目前，在計算任務卸載計劃中，無論采用GBTO 還是GFBTO，主要依據經驗（歷史數據分析），未來工作中將探索更好的方式，并考慮包含其他的優秀卸載算法，拓寬使用場景.

Mort 的任務管理組件本質上屬于分布式節點協調模塊，其還存在改進之處，如沖突處理.學界已有很多工作，未來考慮將它們融入組件中.此外，在數據隱私保護方面，Mort 目前提供了基于屬性的訪問控制方式，后續可以引入證書等機制，從計算節點方面進一步提升其安全性.

作者貢獻聲明：殷昱煜提供研究思路、審閱論文并提供修改意見；茍紅深完成相關實驗及論文撰寫，并和李尤慧子共同確定算法思路及論文修訂；黃彬彬和萬健審閱論文并提出修改意見.