異構計算平臺上的任務調度算法研究

關鍵詞：異構計算；任務調度；算法研究；性能優(yōu)化

中圖分類號：TP311 文獻標識碼：A

文章編號：1009-3044（2024）28-0059-03

0 引言

異構計算是指將不同類型、不同性能的計算資源（如CPU、GPU、FPGA等）整合到一個統(tǒng)一的計算平臺中，通過協同工作來加速應用程序的執(zhí)行[1]。這種計算模式能夠充分利用各種計算資源的優(yōu)勢，提高計算效率和系統(tǒng)性能。然而，異構計算平臺也帶來了諸多挑戰(zhàn)，其中之一就是任務調度問題。

任務調度是指在異構計算平臺中將任務分配給合適的計算資源，并確定任務的執(zhí)行順序，以達到優(yōu)化系統(tǒng)性能的目的。由于異構計算平臺中計算資源的類型和性能差異較大，如何合理地進行任務調度成為一個具有挑戰(zhàn)性的問題。

1 異構計算平臺任務調度算法概述

任務調度算法是異構計算平臺中的關鍵技術之一。根據調度策略的不同，可以將現有的任務調度算法分為靜態(tài)調度算法和動態(tài)調度算法[2]。靜態(tài)調度算法在編譯時確定任務的執(zhí)行順序和計算資源的分配方案。這類算法的優(yōu)點是實現簡單、開銷小，但缺點是靈活性差，無法適應運行時環(huán)境的變化。常見的靜態(tài)調度算法有列表調度算法、聚類調度算法等。動態(tài)調度算法在運行時根據系統(tǒng)的實時狀態(tài)進行任務調度。這類算法的優(yōu)點是能夠適應環(huán)境變化，實現動態(tài)負載均衡，但缺點是開銷較大。常見的動態(tài)調度算法有基于任務復制的調度算法、基于任務遷移的調度算法等。

2 現有任務調度算法分析

列表調度算法：該算法通過構建一個任務列表，按照列表中的順序依次將任務分配給計算資源。列表的構建通?；谌蝿盏膬?yōu)先級或計算資源的利用率。列表調度算法實現簡單，但無法充分利用異構計算平臺的并行性。

聚類調度算法：該算法將任務按照相似性或關聯性進行聚類，然后將每個聚類分配給合適的計算資源。聚類調度算法能夠減少任務間的通信開銷，但聚類的質量和計算資源的分配方案對系統(tǒng)性能影響較大。

基于任務復制的調度算法：該算法通過復制任務并在不同的計算資源上執(zhí)行，以消除任務間的依賴關系，提高并行度?；谌蝿諒椭频恼{度算法能夠顯著減少任務的等待時間，但會增加系統(tǒng)的開銷和復雜性。

基于任務遷移的調度算法：該算法根據系統(tǒng)的實時狀態(tài)動態(tài)地將任務從一個計算資源遷移到另一個計算資源上執(zhí)行?；谌蝿者w移的調度算法能夠實現動態(tài)負載均衡，但需要解決任務遷移的開銷和決策問題。

3 改進的任務調度算法策略

針對現有任務調度算法存在的問題，本文提出了一種改進的任務調度策略。該策略綜合考慮任務的特性、計算資源的性能和系統(tǒng)的實時狀態(tài)，采用動態(tài)與靜態(tài)相結合的方式進行任務調度。該策略首先根據任務的特性和計算資源的性能進行靜態(tài)分配，然后在運行時根據系統(tǒng)的實時狀態(tài)進行動態(tài)調整。在靜態(tài)分配階段，采用基于任務聚類和資源匹配的方法來確定初始的任務分配方案；在動態(tài)調整階段，根據任務的執(zhí)行情況和系統(tǒng)的負載情況進行動態(tài)的任務遷移和復制。具體分為以下步驟：

3.1 靜態(tài)分析與初始分配

采用了有向無環(huán)圖（DAG） 對任務進行建模，節(jié)點表示任務，邊表示任務間的依賴關系。同時，對計算資源進行抽象建模，包括資源類型、計算能力、可用性等屬性?；谶@些模型，使用聚類算法如K-means將任務聚類并初步分配給相應的計算資源。這一步驟考慮了任務間的通信開銷和數據依賴，以優(yōu)化任務的執(zhí)行順序。

3oeLmo0elfz46/5AU3eBpQA==.2 動態(tài)調整與優(yōu)化

設計了一個輕量級的監(jiān)控機制，周期性地收集各計算資源的負載信息和任務執(zhí)行狀態(tài)。通過實時監(jiān)控數據，實現了負載均衡，包括任務遷移和任務復制兩種機制。任務遷移算法根據負載信息確定遷移的候選任務和目標資源，以減輕過載資源的負擔。任務復制算法則識別關鍵路徑上的任務，并根據資源可用性進行復制和并行執(zhí)行，以減少總體執(zhí)行時間。這些動態(tài)調整算法能夠靈活地應對系統(tǒng)狀態(tài)的變化，確保任務的高效執(zhí)行。

明確需要監(jiān)控的目標：在任務調度中，關注的關鍵指標包括計算資源的負載情況（如CPU使用率、內存占用率、磁盤I/O等）、網絡狀態(tài)（如帶寬、延遲）、任務執(zhí)行狀態(tài)（如執(zhí)行進度、等待時間）以及系統(tǒng)性能（如吞吐量、響應時間）等。這些指標能夠反映系統(tǒng)的實時狀態(tài)和任務調度的效果。

采用輕量級的數據采集方式：可以利用系統(tǒng)自帶的監(jiān)控工具或第三方性能監(jiān)控庫來定期收集數據[3]。此外，還可以采用事件驅動的方式，只在特定事件（如任務開始、任務結束、資源故障等）發(fā)生時進行數據采集，以進一步降低監(jiān)控開銷。

數據處理與分析：收集到的數據需要經過處理和分析才能提供有用的信息[4]。可以通過計算平均值、標準差等統(tǒng)計量來評估資源的負載情況和系統(tǒng)性能。同時，利用機器學習算法對歷史數據進行分析，建立預測模型，以便預測未來一段時間內的系統(tǒng)狀態(tài)和任務需求。

可視化展示與告警機制：為了方便管理人員直觀地了解系統(tǒng)狀態(tài)和任務調度情況，可以將監(jiān)控數據以圖表、儀表盤等形式進行可視化展示。同時，設置告警機制，當某些關鍵指標超過預設閾值時，及時發(fā)出告警信息，以便管理人員快速響應并采取相應措施[5]。

監(jiān)控數據存儲與查詢：為了長期保存監(jiān)控數據并支持后續(xù)的分析和查詢操作，需要設計合理的數據存儲結構。可以選擇使用時間序列數據庫來存儲監(jiān)控數據，以便高效地查詢和分析時間序列數據。同時，建立索引和查詢優(yōu)化機制，提高數據查詢的速度和準確性。

監(jiān)控機制的可擴展性和靈活性：考慮到系統(tǒng)的不斷發(fā)展和變化，監(jiān)控機制需要具備一定的可擴展性和靈活性?？梢圆捎貌寮脑O計思想，將不同的監(jiān)控功能和數據采集方式以插件的形式實現，以便根據需要進行動態(tài)擴展和定制。

3.3 性能優(yōu)化

利用機器學習技術對系統(tǒng)性能進行預測，并根據預測結果調整任務調度策略。同時，設計了啟發(fā)式算法，根據實時性能數據動態(tài)調整任務的執(zhí)行順序和資源分配。這些性能優(yōu)化機制能夠最大化整體性能，提升任務調度的效果。

首先，收集大量歷史任務執(zhí)行數據，包括任務類型、資源需求、執(zhí)行時間等關鍵信息。通過分析這些數據，識別影響任務性能的關鍵因素。隨后，利用隨機森林、神經網絡等機器學習算法構建性能預測模型，該模型能根據任務特征預測執(zhí)行時間和資源需求。通過不斷訓練和優(yōu)化模型，提高預測準確性和穩(wěn)定性。

啟發(fā)式算法是一種基于經驗的、能夠快速找到問題近似最優(yōu)解的算法。在任務調度中，設計了一種啟發(fā)式算法，根據實時性能數據動態(tài)調整任務的執(zhí)行順序和資源分配。具體來說，該啟發(fā)式算法會周期性地收集各計算資源的負載信息和任務執(zhí)行狀態(tài)。然后，它會根據任務的緊急程度、資源的需求情況和系統(tǒng)的整體負載情況，為每個任務計算一個優(yōu)先級得分。該得分綜合考慮了任務的等待時間、執(zhí)行時間和資源利用率等因素。接下來，算法會根據任務的優(yōu)先級得分，對任務隊列進行排序，并優(yōu)先調度得分較高的任務。同時，它還會根據資源的實時負載情況，動態(tài)分配和調整資源，以確保任務能夠在最短的時間內完成。這種啟發(fā)式算法能夠快速做出決策，適應系統(tǒng)的動態(tài)變化。通過不斷優(yōu)化任務的執(zhí)行順序和資源分配，它能夠在滿足任務需求的前提下，最大化整體性能，提升任務調度的效果。

3.4 反饋與調整

在反饋與調整階段，實現了一個性能反饋機制，收集并分析任務執(zhí)行過程中的性能數據。根據性能反饋數據，動態(tài)調整任務調度策略的參數和規(guī)則，以適應系統(tǒng)的變化。這種反饋機制保證了策略的持續(xù)優(yōu)化和適應性，為異構計算平臺的應用和發(fā)展提供了有力支持。

數據收集模塊：性能反饋機制首先通過數據收集模塊來捕獲任務執(zhí)行的關鍵性能指標。這些數據包括但不限于任務執(zhí)行時間、資源利用率（如CPU、內存、磁盤I/O等）、網絡帶寬和延遲、任務隊列長度等。數據收集模塊利用系統(tǒng)監(jiān)控工具、性能計數器或自定義的監(jiān)控腳本來實時獲取這些數據，并將其記錄在性能日志中。

數據處理與分析模塊：收集到的性能數據隨后被送入數據處理與分析模塊。該模塊負責數據的清洗、聚合和轉換，以使其適用于后續(xù)的分析和決策。利用統(tǒng)計分析技術，可以計算出各項性能指標的平均值、標準差、最大值和最小值等，從而了解系統(tǒng)的整體性能水平和波動情況。此外，通過機器學習算法，還可以對歷史數據進行趨勢分析和預測，以便預測未來系統(tǒng)的性能需求。

決策與調整模塊：基于數據處理與分析模塊的輸出結果，決策與調整模塊負責制定任務調度策略的調整方案。它根據當前的性能指標和預測結果，評估當前任務調度策略的有效性，并確定是否需要調整。如果需要調整，該模塊會計算新的參數和規(guī)則，如任務優(yōu)先級、資源分配策略、任務隊列管理策略等，并將其應用于任務調度器中。

應用與監(jiān)控模塊：一旦決策與調整模塊制定了新的任務調度策略，應用與監(jiān)控模塊負責將其應用到系統(tǒng)中，并持續(xù)監(jiān)控其效果。該模塊會實時收集新的性能數據，并將其與之前的數據進行對比，以評估策略調整的效果。如果性能有所提升或保持穩(wěn)定，說明調整有效；否則，可能需要重新調整或采用其他優(yōu)化措施。

通過這樣一個閉環(huán)的性能反饋機制，能夠實現對任務調度策略的持續(xù)優(yōu)化和適應。該機制能夠及時發(fā)現系統(tǒng)的性能瓶頸和問題，并根據實時的性能數據做出相應調整，從而提高任務調度的效率和系統(tǒng)的整體性能。

4 實驗與分析

4.1 實驗設計

為了驗證改進的任務調度策略的有效性，本文設計了一系列實驗，并與現有算法進行了對比分析。實驗結果表明，改進的任務調度策略在多個性能指標上均優(yōu)于現有算法。

實驗環(huán)境：構建了一個包含4種不同類型計算資源（CPU、GPU、FPGA、ASIC） 的異構計算平臺，每種計算資源具有不同的計算能力和特性。

測試任務集：選擇了10個具有不同計算復雜度和數據依賴關系的任務作為測試對象，這些任務涵蓋了科學計算、數據處理和機器學習等應用領域。

對比算法：選擇了列表調度算法（LS） 、聚類調度算法（CS） 和基于任務復制的調度算法（TDS） 作為對比算法。

4.2 實驗指標

任務平均完成時間（Average Completion Time，ACT） ：所有任務從提交到完成的平均時間，單位為秒。

系統(tǒng)吞吐量（Throughput） ：單位時間內完成的任務數量，單位為任務/秒。

負載均衡度（Load Balancing Degree，LBD） ：通過計算各計算資源的利用率方差來衡量負載均衡效果，數值越小，表示負載均衡效果越好。

4.3 實驗結果

表1展示了不同算法在任務平均完成時間、系統(tǒng)吞吐量和負載均衡度方面的實驗結果。

從表1中可以看出，本文提出的改進任務調度策略在任務平均完成時間、系統(tǒng)吞吐量和負載均衡度方面均優(yōu)于現有算法。

任務平均完成時間：改進策略的任務平均完成時間為75 秒，相較列表調度算法的120 秒，降低了37.5%。相較聚類調度算法的100秒和基于任務復制的調度算法的90秒，也分別降低了25%和16.7%。這表明改進策略能夠更有效地利用異構計算平臺的資源，減少任務的等待時間和執(zhí)行時間。

系統(tǒng)吞吐量：改進策略的系統(tǒng)吞吐量為9任務/ 秒，相較列表調度算法的5任務/秒，提高了80%。相較聚類調度算法的6任務/秒和基于任務復制的調度算法的7任務/秒，也分別提高了50%和28.6%。這表明改進策略能夠更高效地調度任務，提高系統(tǒng)的并行處理能力。

負載均衡度：改進策略的負載均衡度為0.10，相較列表調度算法的0.25、聚類調度算法的0.20和基于任務復制的調度算法的0.15，分別降低了60%、50% 和33.3%。這表明改進策略能夠更好地平衡各計算資源的負載，避免資源過載或閑置的情況，提高整體資源利用率。

5 結論與展望

本文對異構計算平臺上的任務調度算法進行了深入研究，分析了現有算法的優(yōu)缺點，并提出了一種改進的任務調度策略。通過實驗驗證，該策略在降低任務完成時間、提高系統(tǒng)吞吐量等方面具備顯著優(yōu)勢。未來，隨著異構計算技術的不斷發(fā)展和應用場景的不斷擴展，任務調度算法將面臨更多的挑戰(zhàn)和機遇。未來的研究工作可以圍繞以下幾個方面展開：進一步優(yōu)化任務調度策略以適應更復雜的應用場景；研究跨平臺、跨架構的任務調度技術以實現更廣泛的資源共享；探索基于機器學習和人工智能技術的任務調度方法以提高調度效率和準確性。