發(fā)布時(shí)間：2021-10-28 19:08

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

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

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

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

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


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

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



本文編號：3463214