隨著科學的日新月異,人們對計算機的處理能力提出更好、更快、更強的要求與挑戰(zhàn),多處理器技術便是這個挑戰(zhàn)的有效突破口。任務調(diào)度是這個突破口中最為關鍵的技術之一。隨著科技的進一步發(fā)展,多處理技術向著不同處理器對同一個任務有不同的處理速度的異構方向發(fā)展,這種異構性也讓異構多處理器的任務的調(diào)度問題變得更加復雜。調(diào)度算法研究中,任務模型大多數(shù)采用有向無環(huán)圖DAG（Directed Acyclic Graph）。任務的調(diào)度問題,已被證明是一個NP完全問題�，F(xiàn)有的大多數(shù)異構多處理器實時任務調(diào)度算法采用的方式是首先初始化分簇,然后將簇進行放置,再對任務進行調(diào)度�；趶椭瓶蓴U展實時任務調(diào)度算法與異構最早時間優(yōu)先算法由于在分簇時綜合考慮任務執(zhí)行時間、處理器空閑狀態(tài)、前趨關系等多個因素從而引起算法時間復雜度過高。針對此種情況,本文研究一種改進的異構多處理器實時任務調(diào)度算法HRTSA（Heterogeneous Real-time Task Scheduling Algorithm for multiprocessors）。本文在初始化分簇時提出一種基于前趨約束的最小執(zhí)行時間分簇策略以降低時間復雜度,為了保證調(diào)... 

【文章來源】：湖南大學湖南省 211工程院校 985工程院校 教育部直屬院校

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

【學位級別】：碩士

【文章目錄】：
摘要
Abstract
插圖索引
附表索引
第1章 緒論
    1.1 多處理器任務調(diào)度研究的背景和意義
    1.2 多處理器任務調(diào)度的國內(nèi)外研究現(xiàn)狀
    1.3 本文研究的內(nèi)容和意義
    1.4 本文工作與本文結構
    1.5 小結
第2章 異構多處理器實時任務調(diào)度的相關研究
    2.1 異構多處理器實時任務調(diào)度的研究方法
        2.1.1 任務模型的三個發(fā)展階段
        2.1.2 研究不同階段的任務調(diào)度的平臺及其意義
    2.2 異構多處理器的實時任務調(diào)度研究的相關概念
    2.3 基于異構多處理器的實時任務調(diào)度算法分析
        2.3.1 RTSDA算法
        2.3.2 HEFT算法
        2.3.3 CPOP算法
        2.3.4 其它任務調(diào)度方法
    2.4 小結
第3章 異構多處理器實時任務分簇策略研究
    3.1 任務分簇策略分析
        3.1.1 RTSDA分簇策略
        3.1.2 HEFT分簇策略
        3.1.3 遺傳分簇策略
        3.1.4 最小執(zhí)行時間分簇策略
    3.2 基于前趨約束的最小執(zhí)行時間分簇策略
        3.2.1 算法基本思想
        3.2.2 算法描述
        3.2.3 算法實例
        3.2.4 算法性能評估分析
    3.3 小結
第4章 一種改進的異構多處理器實時任務調(diào)度算法
    4.1 調(diào)度算法的總體設計
    4.2 基于負載均衡的聚合
        4.2.1 初次分配處理器
        4.2.2 采用負載均衡因子進行合并
    4.3 任務復制
        4.3.1 基于處理器空閑間隙復制
        4.3.2 基于空閑處理器的簇復制
    4.4 刪除無效冗余節(jié)點
    4.5 算法分析
        4.5.1 合并算法分析
        4.5.2 復制策略分析
        4.5.3 冗余節(jié)點處理
        4.5.4 算法時間復雜度分析
    4.6 小結
第5章 算法實驗評估
    5.1 仿真實驗
    5.2 算法評估
    5.3 實驗數(shù)據(jù)
        5.3.1 實驗數(shù)據(jù)圖
        5.3.2 實驗數(shù)據(jù)分析
    5.4 小結
總結
參考文獻
致謝
附錄A 攻讀學位期間發(fā)表的學術論文
附錄B 攻讀學位期間所參與的研究項目


【參考文獻】：
期刊論文
[1]考慮通信競爭的任意處理機網(wǎng)絡表調(diào)度算法[J]. 唐小勇,唐小勇,李肯立,PADUA Divid.  中國科學（F輯:信息科學）. 2009(07)
[2]基于擴展的隨機DAG的EST估算與任務調(diào)度[J]. 胡凱,姜燕,楊志斌,張新宇.  計算機工程. 2008(24)
[3]基于擴展的隨機DAG的并行任務調(diào)度算法研究[J]. 姜燕,胡凱,楊志斌,張新宇.  計算機科學. 2008(07)
[4]基于任務復制的分簇與調(diào)度算法[J]. 何琨,趙勇,黃文奇.  計算機學報. 2008(05)
[5]網(wǎng)格環(huán)境下的靜態(tài)啟發(fā)式任務調(diào)度算法[J]. 張忠平,劉欣媛.  計算機研究與發(fā)展. 2008(S1)
[6]異構實時多處理器系統(tǒng)的動態(tài)調(diào)度算法研究[J]. 楊玉海,賓雪蓮,余勝生,周敬利.  小型微型計算機系統(tǒng). 2008(01)
[7]一種基于分簇復制的DAG任務圖調(diào)度算法[J]. 喬偉光,曾國蓀.  計算機工程. 2006(17)
[8]一種基于任務復制調(diào)度算法研究[J]. 林劍檸,吳慧中.  小型微型計算機系統(tǒng). 2006(07)
[9]同構計算環(huán)境中一種快速有效的靜態(tài)任務調(diào)度算法[J]. 李慶華,韓建軍,Abbas A.Essa.  計算機研究與發(fā)展. 2005(01)
[10]一種基于有向無環(huán)圖的實時任務調(diào)度算法[J]. 何黎剛,韓宗芬,秦嘯,龐麗萍.  華中理工大學學報. 2000(10)

碩士論文
[1]基于遺傳算法的網(wǎng)格任務調(diào)度研究及實現(xiàn)[D]. 陳瑩.四川大學 2006
[2]基于DAG模型的高效并行任務調(diào)度算法研究[D]. 華強勝.中南大學 2004



本文編號：3463214