可重構(gòu)計算技術(shù)結(jié)合了通用處理器(General-Purpose Processor, GPP)和專用集成電路(Application Specific Integrated Circuits, ASIC)兩者的優(yōu)點,能夠提供硬件的高效性和軟件的可編程性,是當(dāng)前熱門的研究課題之一。動態(tài)部分可重構(gòu)技術(shù)是可重構(gòu)計算技術(shù)的最新進(jìn)展之一。該技術(shù)能夠在可重構(gòu)系統(tǒng)正常工作的情況下,配置其中部分可重構(gòu)資源,使得一部分任務(wù)的執(zhí)行能夠與另一部分任務(wù)的配置同時進(jìn)行。動態(tài)重構(gòu)技術(shù)能提高系統(tǒng)的靈活性和資源利用率,從而提升整個系統(tǒng)的性能。 在動態(tài)可重構(gòu)系統(tǒng)中,硬件任務(wù)的調(diào)度是影響動態(tài)可重構(gòu)系統(tǒng)性能的關(guān)鍵因素之一。為了盡量提高系統(tǒng)芯片的利用率,降低硬件任務(wù)的拒絕率和調(diào)度時間開銷,這就需要采用高質(zhì)量的調(diào)度算法來對硬件任務(wù)進(jìn)行合理的調(diào)度和管理。本文針對實時任務(wù)在二維可重構(gòu)器件上的在線放置和調(diào)度問題,主要完成了以下工作： (1)本文考慮將硬件任務(wù)按照長、寬及調(diào)度時間構(gòu)成一個三維資源模型,將每個硬件任務(wù)看成是一個空間塊,提出了一種基于三維空間鄰接度的放置算法。該算法首先對可重構(gòu)資源進(jìn)行編碼,到達(dá)的任務(wù)總是通過某個頂點依附另一個任務(wù)的邊界被放置,確定候選的放置頂點；然后以到達(dá)任務(wù)與已放置在三維空間的鄰接度為代價函數(shù),選擇代價函數(shù)值最大的頂點放置任務(wù),從而使得到達(dá)任務(wù)與已放置任務(wù)在三維空間接觸的鄰接面最大�？墒谷蝿�(wù)安排得更緊湊,減小對系統(tǒng)資源的浪費,提高芯片利用率。 (2)本文提出了一種基于頂點鏈表的硬件任務(wù)間最小空間調(diào)度算法MSSA (minimun space scheduling algorithm),該算法充分考慮利用任務(wù)的松弛時間內(nèi)的調(diào)度延遲,采用基于三維空間鄰接度的放置方法,選擇松弛時間內(nèi)使得鄰接度最大的放置頂點和任務(wù)開始執(zhí)行時間來執(zhí)行任務(wù),使得任務(wù)更加整齊、緊密的放置,從而降低任務(wù)拒絕率,提高硬件任務(wù)執(zhí)行的并發(fā)度和資源利用率。 (3)設(shè)計仿真實驗,將MSSA調(diào)度算法分別和Stuffing算法、MGS算法、CR算法,從任務(wù)拒絕率、可重構(gòu)資源面積利用率和時間復(fù)雜度上進(jìn)行比較。四種算法采用相同的參數(shù),實驗結(jié)果表明,MSSA算法在任務(wù)調(diào)度成功率和芯片利用率明顯優(yōu)于已有算法,同時在運行時間和開銷上并未明顯增加。
【學(xué)位單位】：湖南大學(xué)
【學(xué)位級別】：碩士
【學(xué)位年份】：2010
【中圖分類】：TP302.1
【文章目錄】：
摘要
Abstract
插圖索引
附表索引
第1章 緒論
    1.1 研究背景
    1.2 研究的意義
    1.3 研究的主要內(nèi)容
    1.4 擬解決的關(guān)鍵問題
    1.5 本文的組織
第2章 可重構(gòu)計算技術(shù)
    2.1 可重構(gòu)計算技術(shù)概述
        2.1.1 可重構(gòu)計算技術(shù)的定義
        2.1.2 可重構(gòu)計算技術(shù)的發(fā)展歷史
        2.1.3 可重構(gòu)計算的應(yīng)用
    2.2 動態(tài)可重構(gòu)系統(tǒng)
        2.2.1 技術(shù)分類
        2.2.2 動態(tài)可重構(gòu)系統(tǒng)的重構(gòu)方式
        2.2.3 動態(tài)可重構(gòu)系統(tǒng)的優(yōu)點
    2.3 可重構(gòu)片上系統(tǒng)與可重構(gòu)操作系統(tǒng)
    2.4 可重構(gòu)計算系統(tǒng)的研究方向和難題
    2.5 硬件任務(wù)在線放置模型
        2.5.1 任務(wù)模型
        2.5.2 資源模型
    2.6 模型的描述與基本概念
        2.6.1 模型的描述
        2.6.2 基本概念
    2.7 小結(jié)
第3章 硬件任務(wù)的放置算法
    3.1 放置算法綜述
        3.1.1 基于矩形的放置算法
        3.1.2 基于頂點鏈表的放置算法
        3.1.3 常用放置算法的特性
    3.2 一種基于空間鄰接度的放置算法
        3.2.1 數(shù)據(jù)結(jié)構(gòu)
        3.2.2 代價函數(shù)
        3.2.3 算法描述
        3.2.4 放置實例
    3.3 仿真實驗及結(jié)果分析
        3.3.1 仿真試驗平臺
        3.3.2 性能評估及分析
    3.4 小結(jié)
第4章 MSSA實時任務(wù)調(diào)度算法
    4.1 基本概念
    4.2 調(diào)度模型
    4.3 調(diào)度算法相關(guān)研究工作
    4.4 MSSA調(diào)度算法
        4.4.1 數(shù)據(jù)結(jié)構(gòu)
        4.4.2 算法描述
    4.5 MSSA調(diào)度算法實例
    4.6 小結(jié)
第5章 仿真實驗與結(jié)果分析
    5.1 仿真實驗設(shè)計
    5.2 實驗參數(shù)
    5.3 實驗結(jié)果及性能分析
    5.4 小結(jié)
結(jié)論和展望
參考文獻(xiàn)
附錄A 攻讀學(xué)位期間所發(fā)表的學(xué)術(shù)論文與參加的項目
致謝

【引證文獻(xiàn)】

相關(guān)碩士學(xué)位論文 前1條

1 趙馨;可重構(gòu)嵌入式系統(tǒng)軟硬件劃分方法的研究[D];哈爾濱理工大學(xué);2012年

本文編號：2829990