現(xiàn)今計算機已深入人們的日常生活,隨著嵌入式系統(tǒng)設(shè)備的普及,嵌入式應(yīng)用向著深度嵌入、泛載互聯(lián)、普適計算方向發(fā)展。為了提高嵌入式系統(tǒng)的性能,高性能嵌入式計算變得尤為重要。如傳統(tǒng)計算機的發(fā)展趨勢一般,嵌入式系統(tǒng)也進入了多核時代,但與之而來的高能耗和存儲瓶頸卻限制了嵌入式系統(tǒng)的發(fā)展。如何在充分利用多核結(jié)構(gòu)的優(yōu)勢基礎(chǔ)上,降低系統(tǒng)能耗,提高存儲資源利用率,是嵌入式多核系統(tǒng)并行優(yōu)化所關(guān)注的問題。嵌入式多核系統(tǒng)的并行優(yōu)化是近年來計算機學術(shù)界研究的一個重點。并行優(yōu)化包含很多問題,設(shè)計過程的軟硬件劃分、任務(wù)調(diào)度、數(shù)據(jù)存儲分配、內(nèi)聯(lián)網(wǎng)絡(luò)設(shè)計等問題都是其中的重點和難點。本文針對這四個不同的問題,分別引入了智能算法、動態(tài)規(guī)劃算法等經(jīng)典算法,并結(jié)合其他并行優(yōu)化技術(shù)進行研究。并行優(yōu)化通常采用折衷嵌入式系統(tǒng)面積、能耗、時間性能的策略。本文主要的研究工作如以下幾個方面所述:(1)嵌入式系統(tǒng)通常采用軟硬件協(xié)同設(shè)計的方式,軟硬件劃分則是軟硬件協(xié)同設(shè)計中最重要的階段,在有限的系統(tǒng)硬件資源前提下,最大化嵌入式系統(tǒng)的性能;即保持硬件面積不變的情況下,縮短系統(tǒng)的執(zhí)行時間,相應(yīng)地由于任務(wù)執(zhí)行時間的減少,系統(tǒng)的能耗也隨之降低。針對上述問題,本文通過DAG圖將軟硬件劃分問題看作為0-1問題,引入了混合蛙跳算法對該問題進行優(yōu)化,由于原始的蛙跳算法是針對連續(xù)優(yōu)化問題,因此在其局部更新策略中采取了將連續(xù)值轉(zhuǎn)化為離散值的機制。本文的蛙跳算法具有較好的收斂性,與經(jīng)典的模擬退火算法和貪婪模擬退火算法相比,在基準測試程序集上關(guān)鍵路徑任務(wù)完成時間性能分別能提高16.65%和11.46%。(2)任務(wù)調(diào)度是多核系統(tǒng)中不可回避的重要問題,新存儲技術(shù)——非易失性存儲的出現(xiàn),引發(fā)了存儲技術(shù)的革新。新的存儲技術(shù)可以有效降低系統(tǒng)能耗,在嵌入式系統(tǒng)中被應(yīng)用在主存和緩存,數(shù)字信號處理和多媒體應(yīng)用方面。由于程序中的循環(huán)部分通常是最耗時且功耗最大,多核非易失性存儲嵌入式系統(tǒng)任務(wù)調(diào)度研究主要針對數(shù)字信號處理和多媒體等帶循環(huán)的嵌入式應(yīng)用。利用旋轉(zhuǎn)調(diào)度技術(shù)對循環(huán)進行調(diào)度,減少循環(huán)單次迭代中任務(wù)的完成時間,并結(jié)合數(shù)據(jù)遷移和數(shù)據(jù)重計算技術(shù),減少對非易失性主存的寫操作,進一步減少任務(wù)的完成時間。同時對于旋轉(zhuǎn)調(diào)度后的可分配任務(wù),本文采用最大二分匹配的方式求解出其最優(yōu)的分配。與采用旋轉(zhuǎn)盡快調(diào)度策略相比,基礎(chǔ)測試程序的實驗表明,在系統(tǒng)任務(wù)的完成時間、對非易失性存儲的寫次數(shù)和系統(tǒng)能耗上分別有著20.5%、15.03%和34.5%的性能改進,該算法有著極大的可用性。(3)任務(wù)數(shù)據(jù)的存儲分配問題是任務(wù)調(diào)度完成后必須面臨的重要問題。同時采用SRAM和非易失性存儲的混合便箋式存儲代替?zhèn)鹘y(tǒng)硬件控制緩存是一個極優(yōu)解決方案,傳統(tǒng)的數(shù)據(jù)存儲分配工作主要針對單核結(jié)構(gòu)或者單一結(jié)構(gòu)的便箋式存儲。針對采用混合便箋式存儲結(jié)構(gòu)的任務(wù)數(shù)據(jù)分配問題,本文將數(shù)據(jù)遷移技術(shù)與動態(tài)規(guī)劃策略相結(jié)合,提出基于數(shù)據(jù)遷移的動態(tài)數(shù)據(jù)分配優(yōu)化算法。在混合了SRAM和非易失性存儲的便箋式存儲器高速緩存上,將應(yīng)用任務(wù)劃分為多個并行區(qū)域,通過本文提出的算法對數(shù)據(jù)存儲類型的分配,獲得整個并行區(qū)域數(shù)據(jù)分配的近似最優(yōu)解。同樣本文提出的算法,能在多項式時間內(nèi)獲得該近似最優(yōu)解。與迭代數(shù)據(jù)優(yōu)化分配技術(shù)相比,在基準測試程序上的試驗表明,本文提出的算法在系統(tǒng)任務(wù)數(shù)據(jù)的訪問時間、對非易失性存儲的寫次數(shù)、系統(tǒng)能上分別有著33.82%、24.27%和10.00%的性能改進。(4)處理核之間的通信問題是多核系統(tǒng)中不可避免的問題,其是處理完多核間任務(wù)調(diào)度和任務(wù)數(shù)據(jù)分配之后的重要問題,根據(jù)具體應(yīng)用處理核之間的通信,進行核間內(nèi)聯(lián)網(wǎng)絡(luò)的定制和設(shè)計是一個可行的研究方向。設(shè)計出滿足系統(tǒng)核間通信需求、占用系統(tǒng)面積少、低能耗的內(nèi)聯(lián)網(wǎng)絡(luò)是該研究的目標。本文中針對該問題提出了基于任務(wù)節(jié)點和任務(wù)數(shù)據(jù)的通信調(diào)度算法,通過采用總線的點對點連接方式構(gòu)建內(nèi)聯(lián)網(wǎng)絡(luò),在不增加系統(tǒng)調(diào)度長度的前提下,構(gòu)造出滿足系統(tǒng)核間通信需求,核間點對點連接數(shù)最少的內(nèi)聯(lián)網(wǎng)絡(luò)。同時文中根據(jù)核間通信調(diào)度確定算法和內(nèi)聯(lián)網(wǎng)絡(luò)構(gòu)造算法,為內(nèi)聯(lián)網(wǎng)絡(luò)的設(shè)計提供依據(jù)。實驗表明,本文提出的兩種算法的混合,優(yōu)于HLEFT算法和ASAP算法的混合,與單獨采用任務(wù)節(jié)點通信調(diào)度算法相比,該混合算法可以減少總線中15.02%的核間點對點連接。
【學位單位】：湖南大學
【學位級別】：博士
【學位年份】：2015
【中圖分類】：TP368.1
【文章目錄】：
摘要
Abstract
第1章 緒論
    1.1 研究背景
    1.2 研究內(nèi)容
    1.3 本文組織結(jié)構(gòu)
第2章 相關(guān)研究
    2.1 軟硬件劃分相關(guān)研究
    2.2 循環(huán)中任務(wù)調(diào)度算法研究
    2.3 非易失性存儲的研究
    2.4 便箋式存儲的研究
    2.5 多核嵌入式系統(tǒng)內(nèi)聯(lián)網(wǎng)絡(luò)研究
第3章 理論和技術(shù)基礎(chǔ)
    3.1 系統(tǒng)計算模型
        3.1.1 DFG圖模型
        3.1.2 DAG圖模型
    3.2 相關(guān)技術(shù)
        3.2.1 重定時技術(shù)
        3.2.2 數(shù)據(jù)遷移技術(shù)
        3.2.3 數(shù)據(jù)重計算技術(shù)
    3.3 相關(guān)模擬器
        3.3.1 SimpleScalar
        3.3.2 NVSim
        3.3.3 CACTI
    3.4 相關(guān)測試程序
        3.4.1 隨機測試程序
        3.4.2 基準測試程序
第4章 基于SFLA算法的軟硬件劃分
    4.1 本章引言
    4.2 軟硬件劃分模型
        4.2.1 硬件結(jié)構(gòu)
        4.2.2 計算模型
    4.3 基于SFLA算法的軟硬件劃分
        4.3.1 SFLA算法描述
        4.3.2 基于SFLA算法的軟硬件劃分
    4.4 實驗
        4.4.1 基準測試程序集的軟硬件劃分實驗
        4.4.2 隨機程序集上的軟硬件劃分實驗
    4.5 本章小結(jié)
第5章 多核嵌入式系統(tǒng)任務(wù)優(yōu)化調(diào)度
    5.1 本章引言
    5.2 硬件架構(gòu)和計算模型
        5.2.1 硬件架構(gòu)
        5.2.2 計算模型
    5.3 實例說明
    5.4 旋轉(zhuǎn)最大二分匹配算法(RMBM)
        5.4.1 旋轉(zhuǎn)調(diào)度技術(shù)
        5.4.2 數(shù)據(jù)遷移技術(shù)
        5.4.3 數(shù)據(jù)重計算技術(shù)
        5.4.4 旋轉(zhuǎn)最大二分匹配算法
    5.5 實驗
        5.5.1 DSPStone基準測試程序
        5.5.2 Mediabench基準測試程序
        5.5.3 不同核基準測試程序比較
    5.6 本章小結(jié)
第6章 基于數(shù)據(jù)遷移的任務(wù)數(shù)據(jù)優(yōu)化分配
    6.1 本章引言
    6.2 硬件和計算模型
    6.3 實例說明
    6.4 基于數(shù)據(jù)遷移的任務(wù)數(shù)據(jù)優(yōu)化分配
        6.4.1 問題描述
        6.4.2 全局近似最優(yōu)的數(shù)據(jù)分配方案
    6.5 實驗
        6.5.1 基準測試程序的算法性能評估
        6.5.2 隨機程序(DAG)的算法性能評估
    6.6 本章小結(jié)
第7章 多核嵌入式系統(tǒng)內(nèi)聯(lián)網(wǎng)絡(luò)優(yōu)化調(diào)度
    7.1 本章引言
    7.2 基本原理
        7.2.1 多核嵌入式系統(tǒng)結(jié)構(gòu)模型
        7.2.2 多任務(wù)應(yīng)用建模
        7.2.3 研究動機
    7.3 內(nèi)聯(lián)網(wǎng)絡(luò)優(yōu)化調(diào)度
        7.3.1 核間數(shù)據(jù)傳輸問題定義
        7.3.2 任務(wù)節(jié)點的通信優(yōu)化調(diào)度
        7.3.3 數(shù)據(jù)傳輸?shù)耐ㄐ艃?yōu)化調(diào)度
    7.4 實驗
        7.4.1 基準測試程序集實驗
        7.4.2 隨機程序集實驗
        7.4.3 不同處理核之間的性能比較
    7.5 本章小結(jié)
結(jié)論
參考文獻
致謝
附錄A 攻讀學位期間所完成的論文
附錄B 攻讀學位期間主持和參加的科研課題

【參考文獻】

相關(guān)期刊論文 前10條

1 劉東;張進寶;廖小飛;金海;;面向混合內(nèi)存體系結(jié)構(gòu)的模擬器[J];華東師范大學學報(自然科學版);2014年05期

2 孫廣宇;舒繼武;王鵬;;面向非易失內(nèi)存的結(jié)構(gòu)和系統(tǒng)級設(shè)計與優(yōu)化綜述[J];華東師范大學學報(自然科學版);2014年05期

3 韓樂;陳香蘭;李曦;;一種降低核間通信開銷的調(diào)度算法[J];計算機系統(tǒng)應(yīng)用;2014年09期

4 張鴻斌;范捷;舒繼武;胡慶達;;基于相變存儲器的存儲系統(tǒng)與技術(shù)綜述[J];計算機研究與發(fā)展;2014年08期

5 王穎鋒;張彥周;高韜;;多核嵌入式系統(tǒng)總線沖突避免的節(jié)能調(diào)度綜述[J];計算機應(yīng)用研究;2014年04期

6 張鵬;樊曉椏;黃小平;;基于總線訪問的片上調(diào)試方法研究[J];計算機測量與控制;2014年02期

7 沈志榮;薛巍;舒繼武;;新型非易失存儲研究[J];計算機研究與發(fā)展;2014年02期

8 皇甫曉妍;樊曉椏;黃小平;;基于SRAM和STT-RAM的混合指令Cache設(shè)計[J];計算機工程與應(yīng)用;2015年12期

9 徐超;何炎祥;陳勇;劉健博;吳偉;李清安;;一種多核系統(tǒng)可靠性加強的任務(wù)調(diào)度方法[J];電子學報;2013年05期

10 劉彩霞;石峰;薛立成;宋紅;;層次化共享多通道便簽存儲器的嵌入式多核體系[J];計算機輔助設(shè)計與圖形學學報;2010年08期

相關(guān)博士學位論文 前1條

1 劉彥;異構(gòu)多核片上系統(tǒng)的任務(wù)調(diào)度及應(yīng)用研究[D];湖南大學;2009年

相關(guān)碩士學位論文 前4條

1 蔡根;利用程序模式管理便簽存儲器的技術(shù)及模型[D];華東師范大學;2014年

2 李濤;多核網(wǎng)絡(luò)處理器片上總線的設(shè)計與驗證[D];西安電子科技大學;2014年

3 袁立業(yè);NoC上的多核間通信策略研究[D];大連理工大學;2009年

4 石金鋒;基于SPM的寄存器拋出能耗優(yōu)化研究[D];中南大學;2009年

本文編號：2839724