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

【參考文獻】

相關期刊論文 前10條

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

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

3 韓樂;陳香蘭;李曦;;一種降低核間通信開銷的調度算法[J];計算機系統應用;2014年09期

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

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

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

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

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

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

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

相關博士學位論文 前1條

1 劉彥;異構多核片上系統的任務調度及應用研究[D];湖南大學;2009年

相關碩士學位論文 前4條

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

2 李濤;多核網絡處理器片上總線的設計與驗證[D];西安電子科技大學;2014年

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

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

本文編號：2839724