[發明專利]一種基于任務復制的多復本容錯并行任務調度方法

有效

• 申請號: 201210225099.6
• 申請日: 2012-06-29
• 公開（公告）號: CN102799475A
• 公開（公告）日: 2012-11-28
• 發明（設計）人: 汪蕓;馬俊
• 申請（專利權）人: 東南大學
• 主分類號: G06F9/46
• 分類號: G06F9/46;G06F9/50
• 代理公司: 南京蘇高專利商標事務所(普通合伙) 32204
• 代理人: 夏雪

技術領域

本發明涉及計算機領域的并行任務調度，特別是有限處理器環境下的容錯并行DAG任務調度方法。?

背景技術

將DAG圖中的并行任務調度到處理器機群中以獲得最短執行時間一直是并行任務調度中的重要研究課題。隨著高速局域網以及分布式計算的發展，基于分布式主存的并行計算獲得了快速的發展，分布式環境下處理器節點以及網絡數據傳輸都有可能會出現失效問題，因此在滿足系統容錯參數f的前提下，追求更短的調度長度成為需要研究的問題。?

并行任務調度一般分為表調度、基于任務機群的調度、非確定性調度和基于任務復制的調度，任務模型一般采用DAG模型。由于局域網環境下通信開銷成為影響并行計算效率的主要因素，而同一處理器上前驅后繼任務間的數據傳輸時間可以忽略不計，一般局域網環境下可以采用任務復制調度思路，任務復制的基本思想是利用處理器的空閑時隙冗余地復制當前任務的前驅任務，從而避免任務間的數據傳輸。常用的任務復制算法有DSH、PY、LWB、BTDH、LCTD、CPFD等。?

上述并行任務調度方法不具備容錯能力，分布式并行環境下，處理器節點和網絡數據傳輸的失效問題使得容錯能力成為并行計算模型的一個主要的考慮因素。一般并行計算的容錯模式主要有被動復制(Passive?replication/Primary?&Backup)和主動復制(Active?replication/N-Modular?redundancy)，主動復制容錯也被稱為多復本容錯。被動復制技術是傳統的考慮時間和空間的容錯方法，該方法的主要思想是從任務只有在主任務出現錯誤的時候才被激活。該模式的主要優點是在提供容錯機制的同時能夠達到很好的可調度性，因為任意的任務節點只有兩個復本，而缺點就是容錯能力有限，系統不能容納超過一個節點的失效問題(fail-stop錯誤)。主動復制技術采用空間冗余思想，為了能夠容納f個計算節點的失效，DAG任務圖中的任意任務節點都將被備份f+1份。下面簡要介紹已有容錯并行調度方法FTBAR算法和FTSA算法。?

FTBAR(Fault?Tolerant?Based?Active?Replication?strategy)算法基于貪心的表調度思想，算法采用稱為調度壓力的代價函數，在算法執行的第n步，任務t_i調度到處理器p_j上的調度壓力公式為：σ⁽ⁿ⁾(t_i,p_j)=S⁽ⁿ⁾(t_i,p_j)+s(t_i)-R^(n-1)，其中，S⁽ⁿ⁾(t_i,p_j)表示任務t_i在處理器p_j上的最早執行時間，s(t_i)表示任務t_i的最遲執行時間，R^(n-1)表示第n-1步時的調度長度，該算法的基本調度思路如下：?

①對于任意未調度任務t_i，計算其在所有處理器上的調度壓力，并記錄調度壓力最小的f+1個處理器；?

②選擇所有未調度任務t_i的所有配對<t_i,p_jk>，選擇其中調度壓力值最大的任務t_i；?

③根據步驟①的記錄將任務t_i調度到調度壓力最小的f+1個處理器上，計算?最早開始時間。?

FTSA(Fault?Tolerant?Scheduling?Algorithm)算法首先采用任務重要性(task?criticalness)的概念來衡量DAG任務的優先級，其計算公式如下：TC(t)=tl(t)+bl(t)，其中，tl(t)表示開始任務到當前任務的最長路徑，該值為動態值，依賴于前驅任務的調度安排，bl(t)表示結束任務到當前任務的靜態值，該值可以在調度開始前根據DAG圖計算出來，FTSA算法的基本思路如下：?

①計算所有未調度任務的重要性值，選擇優先隊列中優先級最高的任務t_i；?

②利用FTSA算法公式計算出任務t_i在所有處理器上的結束時間，并記錄結束時間最早的f+1個處理器，然后將任務t_i調度到這些處理器上；?