【摘要】：實(shí)時(shí)程序最壞情況執(zhí)行時(shí)間（Worst-Case Execuion Time, WCET）分析是指在程序或者程序片段執(zhí)行之前獲得其最壞情況的執(zhí)行時(shí)間估值。事先獲知任務(wù)的WCET估值是實(shí)時(shí)系統(tǒng)進(jìn)行調(diào)度及可調(diào)度性分析的前提，也是檢查實(shí)時(shí)系統(tǒng)性能是否滿足要求的依據(jù)。隨著VLSI技術(shù)的發(fā)展，多核處理器已經(jīng)取代單核處理器成為時(shí)代的主流。而實(shí)時(shí)領(lǐng)域由于應(yīng)用需求的提高開(kāi)始對(duì)高性能的多核處理器投入越來(lái)越多地關(guān)注。但是，在多核處理器中，任務(wù)在訪問(wèn)硬件共享資源時(shí)會(huì)產(chǎn)生干擾，一個(gè)任務(wù)的執(zhí)行時(shí)間可能會(huì)受到并行任務(wù)的影響。較之于體系結(jié)構(gòu)簡(jiǎn)單的單核處理器而言，多核處理器在體系結(jié)構(gòu)上對(duì)實(shí)時(shí)系統(tǒng)WCET分析提出了更多的挑戰(zhàn)和難題。 本文從影響多核處理器可預(yù)測(cè)性的硬件共享資源入手，深入研究了引起干擾的硬件共享資源對(duì)WCET估值的影響：片上共享資源（共享Cache、片上互連）和片外共享資源（片外共享存儲(chǔ)），提出了基于多核處理器平臺(tái)的實(shí)時(shí)系統(tǒng)WCET分析方法。所取得的研究成果主要包括： 1、提出了一種基于多核處理器平臺(tái)的實(shí)時(shí)系統(tǒng)WCET靜態(tài)分析模型。該模型借鑒成熟的單核WCET靜態(tài)分析流程，在底層微體系結(jié)構(gòu)分析中綜合考慮片上共享資源和片外共享資源干擾對(duì)實(shí)時(shí)任務(wù)執(zhí)行時(shí)間的影響，以及共享資源干擾之間的相互影響。該模型用于指導(dǎo)后續(xù)的多核共享資源干擾分析、WCET計(jì)算和基于多核處理器平臺(tái)的WCET分析工具的設(shè)計(jì)與實(shí)現(xiàn)。 2、提出了一種基于指令取指執(zhí)行時(shí)序范疇的共享指令Cache干擾分析方法。該方法考慮線程控制邏輯和執(zhí)行時(shí)序?qū)Ω蓴_的影響，基于指令取指執(zhí)行時(shí)序范疇判斷并行線程間在共享Cache上的干擾狀態(tài)。理論分析證明該方法的有效性，實(shí)驗(yàn)結(jié)果表明，該方法在保守的地址映射分析方法的基礎(chǔ)上可以更合理地分析共享Cache干擾，從而獲得更精確的WCET估值。 3、提出了一種迭代的共享總線干擾分析方法。針對(duì)共享Cache和共享總線的多核結(jié)構(gòu)，綜合考慮共享總線干擾和共享Cache干擾對(duì)線程WCET估值的影響以及二者之間的相互影響，以獲得更精確的WCET估值。其核心思想是根據(jù)本文提出的基于指令取指執(zhí)行時(shí)序范疇的共享Cache干擾分析方法，考慮共享總線對(duì)共享Cache訪問(wèn)時(shí)序的影響以及共享Cache干擾狀態(tài)對(duì)共享總線的訪問(wèn)影響，確定合理的共享Cache和共享總線干擾狀態(tài)，通過(guò)收斂的迭代分析方法獲得更精確的WCET估值。 4、提出了一種基于訪問(wèn)時(shí)序范疇的片外共享存儲(chǔ)訪問(wèn)干擾分析方法。該方法針對(duì)并行線程競(jìng)爭(zhēng)訪問(wèn)片外共享存儲(chǔ)引起的干擾問(wèn)題，借鑒執(zhí)行圖的思想構(gòu)建線程存儲(chǔ)訪問(wèn)圖，在此基礎(chǔ)上確定父輩窗口和干擾窗口：通過(guò)父輩窗口分析存儲(chǔ)訪問(wèn)操作之間的影響以確定合理的線程存儲(chǔ)訪問(wèn)延遲，通過(guò)干擾窗口分析并行線程間片外共享存儲(chǔ)訪問(wèn)干擾，從而獲得合理的、更精確的存儲(chǔ)訪問(wèn)時(shí)間開(kāi)銷(xiāo)。該方法不僅考慮了線程內(nèi)的存儲(chǔ)訪問(wèn)請(qǐng)求之間的影響，而且基于時(shí)序范疇更好的分析了并行線程間的存儲(chǔ)訪問(wèn)請(qǐng)求干擾。 5、設(shè)計(jì)并實(shí)現(xiàn)了基于多核處理器平臺(tái)的實(shí)時(shí)系統(tǒng)WCET靜態(tài)分析工具M(jìn)CTA�；谇懊嫣岢龅母蓴_分析方法，在多核處理器平臺(tái)的實(shí)時(shí)系統(tǒng)WCET靜態(tài)分析模型的指導(dǎo)下，設(shè)計(jì)并實(shí)現(xiàn)了面向多核處理器的WCET靜態(tài)分析工具M(jìn)CTA。MCTA在底層微體系結(jié)構(gòu)分析中考慮共享資源干擾對(duì)WCET估值的影響以及干擾之間的相互影響，以此獲得更精確的WCET估值。WCET分析工具的實(shí)現(xiàn)、實(shí)驗(yàn)驗(yàn)證和評(píng)估結(jié)果表明，本文提出的上述技術(shù)是有效的，能夠很好地應(yīng)用于多核處理器在實(shí)時(shí)系統(tǒng)中的設(shè)計(jì)和實(shí)現(xiàn)。
【圖文】：

引發(fā)了體系結(jié)構(gòu)技術(shù)的深刻變革[4]。如圖 1.2 所示，經(jīng)過(guò)最近幾年的展，以多核處理器為代表的先進(jìn)體系結(jié)構(gòu)已經(jīng)逐漸取代單核處理器器性能的主要途徑[5][6][7]。多核處理器在一個(gè)芯片中集成多個(gè)處理器的層次化、功能的模塊化與分布化，它讓每個(gè)功能部件都盡量的簡(jiǎn)盡可能保持連線的局部性。較之單核處理器，，多核處理器具有很多多核處理器可以在較低的時(shí)鐘頻率下提供單核處理器需要很高時(shí)鐘的計(jì)算性能。多核處理器較低的時(shí)鐘頻率也可以很好的滿足功耗、限制。

.2 邏輯執(zhí)行順序?qū)蚕?Cache 干擾的于取指執(zhí)行時(shí)序范疇的干擾分法獲得指令的取指執(zhí)行時(shí)序范bj和 bm、bn，可以通過(guò)取指執(zhí)行含的指令分別為：bi1、…、bii基本塊 bm和 bj在共享 Cache 題可知，此時(shí)二者內(nèi)部指令的( ) ( ) ) ( ) || ( mk jj start start IF b IF b It > latest t latest t( ) ( ) ( ) ( ) || ( mk jj start start sIF b IF b It t > latest t latest t( ) ( )mkstartIF b≥ earliest t且( stIFlatest t ) ( )) ( ) mkstartIF b≤ latest t且earliest
【學(xué)位授予單位】：國(guó)防科學(xué)技術(shù)大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2011
【分類(lèi)號(hào)】：TP332

【參考文獻(xiàn)】

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

1 姬孟洛;李軍;王馨;齊治昌;;一種基于抽象解釋的WCET自動(dòng)分析工具[J];計(jì)算機(jī)工程;2006年14期

本文編號(hào)：2690634