分布式任務調度問題在大數據時代具有重要的地位,同構處理器環(huán)境下的任務調度問題是此類復雜問題的基礎。它所研究的是如何將多個具有先后順序約束關系的任務分配到可用處理器上進行執(zhí)行,達到最小化調度長度(Makespan)的目的。此問題是NP難度的,除非P=NP,否則在多項式時間內不能得到精確解。該問題得到了學者們的廣泛研究,并致力于找到高效、簡單且占用資源少的方法來解決該問題。國內外代表性的求解思路包括基于優(yōu)先級列表、基于分簇、基于任務復制三種方向。將分簇思想和任務復制技術相結合被普遍認為是最佳的求解途徑。分簇思想的核心是將具有約束關系的任務盡可能的放在同一臺處理器上執(zhí)行,以此來減少不同處理器之間的通信開銷。任務復制技術的核心思想是將同一個任務復制到多臺處理器上執(zhí)行,以犧牲處理器計算資源的方式來換取更早的完工時間,簡而言之是一種以空間換取時間的做法。本文結合分簇思想和任務復制技術,提出了基于轉化樹和任務復制的調度算法(Transformation Tree and Task Duplication(TTTD))。算法主要包含預處理、轉化樹、序列合并等三個重要步驟。針對實際工作中可能存在可用處理...

【文章頁數】：66 頁

【學位級別】：碩士

【文章目錄】：
摘要
Abstract
1 緒論
    1.1 研究背景及意義
    1.2 國內外研究現狀
    1.3 研究內容
    1.4 組織結構
2 問題模型和定義
    2.1 問題描述
    2.2 問題形式化定義
    2.3 本章小結
3 核心算法設計
    3.1 基于轉化樹和任務復制的調度算法
    3.2 考慮處理器數量約束的優(yōu)化算法
    3.3 本章小結
4 實驗與分析
    4.1 測試方法
    4.2 測試算例
    4.3 實驗結果
    4.4 本章小結
5 總結與展望
    5.1 總結
    5.2 展望
致謝
參考文獻



本文編號：3792967