[發明專利]基于遺傳算法和計算拓撲模型的SKA任務調度系統及方法

有效

• 申請號: 202011120020.4
• 申請日: 2020-10-19
• 公開（公告）號: CN112199177B
• 公開（公告）日: 2023-03-31
• 發明（設計）人: 駱源;伏開宇
• 申請（專利權）人: 上海交通大學
• 主分類號: G06F9/48
• 分類號: G06F9/48;G06N3/126
• 代理公司: 上海漢聲知識產權代理有限公司 31236
• 代理人: 胡晶

本發明提供了一種基于遺傳算法和計算拓撲模型的SKA任務調度系統及方法，包括：模塊M1：根據并行任務各個子任務所需要的處理時間所構成的向量X、每個節點的數據處理能力組成的向量Y以及并行任務分配方案A，構建計算拓撲模型；模塊M2：將并行任務各個子任務之間的依賴關系以及各個任務所需要的完成時間通過遺傳算法得到次優調度方案；模塊M3：將得到的次優調度方案通過計算拓撲模型得到任務調度方案，根據任務調度方案得到各個任務所需要的完成時間，重復觸發模塊M2至模塊M3，直至迭代次數達到預設次數，得到最優SKA任務調度方案。本發明輸入簡單，用戶可以方便快捷地構造任務依賴拓撲圖文件，然后將其作為算法的輸入。

技術領域

本發明涉及大數據領域，具體地，涉及一種基于遺傳算法和計算拓撲模型的SKA任務調度系統及方法，更為具體地，涉及一種針對平方公里陣列(SKA)射電天文望遠鏡通過遺傳算法和計算拓撲模型找到一種優化的任務調度方案。

背景技術

隨著數據收集和存儲技術的發展，人類已經積累了大量的天文觀測數據。在天文學領域，圖像在這些數據中占據著越來越大的比重。因此，尋找最適合天文圖像大數據處理的框架至關重要，而天文圖像處理系統的目的則是通過提供可擴展和高效的數據存儲和分析手段，幫助天文學家輕松使用編程模型。

平方公里陣列(SKA)是下一代望遠鏡，它將會產生世界上最大的數據量，其參與國家包括中國，澳大利亞，加拿大，意大利，新西蘭，荷蘭，南非，英國等。該項目預計總投資20億美元。SKA項目的初衷是21世紀的宇宙論仍然有許多基本問題需要解決，如基本粒子的性質和基本力，宇宙的形成和演化以及暗物質的起源。因此，為了便于天文學家進一步觀察早期宇宙的結構，需要建立更高靈敏度和探測速度的望遠鏡，SKA就是其中之一。SKA由數千個無線電波接收器和天線組成。這些設備連接到近1平方公里的接收區，使SKA成為歷史上規模最大，最靈敏的射電望遠鏡群。

在以往的天文學觀測模式中，一般都會有一個專家團隊的工程師在專用服務器上處理收集的圖像，再將其結果提煉成文本目錄以供其他天文學家分析。相反，SKA的目標之一是為全球的天文學家提供對圖像的直接接觸，使得他們能夠自行地對圖像進行分析而不需要借助額外的計算機工程團隊的幫助。這個案例強調需要有效的系統來支持圖像數據的管理和分析：高效，易擴展且易于編程的系統，無需深入的系統專業知識進行部署和調整。令人驚訝的是，目前圍繞支持大規模圖像管理和分析的系統構建所進行的研究工作相當有限。Ras-daman和SciDB是兩個眾所周知的DBMS(數據庫管理系統)，專門用于存儲和處理多維數組數據，經常用作圖像分析。除了這些系統之外，為存儲圖像數據而開發的大多數其他工作主要針對基于關鍵字或相似性搜索的圖像存儲和檢索。

除此之外，現如今許多數據流作業都是計算密集型和數據密集型的。例如，天文數據流應用程序產生大量的數據，并且需要巨大的計算能力來處理數據。傳統上，高性能計算(HPC)設施針對處理這種計算密集型科學應用進行了優化。但是，它們不適合處理數據密集型工作負載。天文數據流管線的一個重要特征是管線既是數據密集型又是計算密集型。例如，對于SKA low，需要超過1TB/s的I/O和3PFLOPS/s的計算能力，這對計算架構和執行框架構成了巨大挑戰。為了應對SDP(科學數據處理)數據流管道的巨大挑戰并確其正確功能，主要研究當前成熟的SKA-SDP管道商用系統。