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

【引證文獻(xiàn)】

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

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

本文編號(hào)：2829990