《基於加速效應的多核系統實時調度模型MAMORTS及其算法研究》是依託北京航空航天大學，由張炯擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：基於加速效應的多核系統實時調度模型MAMORTS及其算法研究
- 依託單位：北京航空航天大學
- 項目負責人：張炯
- 項目類別：青年科學基金項目
項目摘要,結題摘要,
項目摘要
研究面向多核的實時調度模型及其算法，基於經典實時調度算法及彈簧調度算法（Elastic scheduling），結合多核處理器上共享Cache的任務之間存在的訪存加速效應，提出並建立基於加速效應的面向多核系統的實時調度模型MAMORTS(Mutual Association based Multi-core Oriented Real Time Schedule)，針對一定約束條件下的實時調度任務集給出實時可調度性判定條件，並給出對應算法和驗證原型系統。主要研究內容為：（1）典型套用實時任務集並行加速因子的研究；（2）基於加速因子的靜態MAMORTS調度模型及其算法；（3）基於任務動態遷移策略的MAMORTS調度模型及其算法。預期研究成果：（1）加速因子分析模型和測量方法；（2）靜態和動態MAMORTS的理論模型、調度算法；（3）翔實的測試數據分析和原型系統。
結題摘要
課題的研究內容按具體開展的過程和主要研究結論主要分以下幾個階段說明： （1）研究並分析Beehive多核處理器的互連結構以及實現技術。Beehive是微軟矽谷研究院利用FPGA實現的令牌環結構多核處理器，課題基於Beehive設計與實現了一種採用新型互連結構的多核處理器NewBeehive。相比於Beehive，NewBeehive 將提供共享二級Cache和Cache一致性，並對其中的RISC核進行改進。 （2）針對多核系統中任務並行執行時的相互影響給出一種任務親和性測試方法，並通過測試任務集對該方法進行驗證。針對最短執行時間和RM調度的最壞執行時間擬合對任務親和性進行套用分析，說明了任務親和性對於任務在多核中的劃分和調度所具有的積極意義，從而在此基礎上給出並實現了多核實時調度模型-MAMORTS。實驗數據和測試分析表明，該調度模型很好的給出了多核架構下的RM實時調度方法。 （3）給出了一種多核實時系統任務間加速因子的定義和測量方法。實驗證明，運行於同一計算系統的相關任務集中，任意兩個任務之間存在不同程度的計算加速效應，這種加速效應在實際系統中可以是加速和減速，定量的加速效果可以通過加速因子數值量化給出，對於周期任務集，加速因子的數值在一定範圍內。本方法中給出了針對多個任務間（任務數 ）的加速因子的測量方法，採取裝載前單獨測量的方法，即在實際任務分配前通過測量計算出所有任務之間的加速關係，且保證加速因子的測量結果符合實際的系統運行情況，從而獲得性能調優的調度策略。 （4）針對一組確定的任務集，找到了判斷這種相關性的通用判定方法，進而可以根據加速因子的數值比較，將任務劃分到不同處理器核上，增加正加速因子比例，減少負加速因子比例，對於提高任務可調度性將很有幫助。基於加速因子的多核實時系統任務劃分方法針對多核實時系統給出了一種基於加速因子的任務劃分方法BF-λ劃分方法：這一划分方法是在Best-Fit裝箱算法上考慮λ加速因子而得到的一種任務劃分方法。對於該劃分方法的簡單說明：在具有k個處理器核的計算環境中，針對任務數量為n的總任務集S，該方法試圖找到一種合適的方案將S劃分為k個子集：對於每一個核i(1≤i≤k)，可以分配在該核上可實時調度的任務子集，且所有子集的和為S，則判定任務集S滿足該方法的實時可調度條件；否則，判定任務集S不滿足該方法的實時可調度條件。
