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

【文章頁數(shù)】：66 頁

【學(xué)位級別】：碩士

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



本文編號：3792967