基于任務調度算法的系統(tǒng)評價方法

基于任務調度算法的系統(tǒng)評價方法

0多核系統(tǒng)功能性質與性能指標適當的任務調整算法可以充分利用多核系統(tǒng)的性能優(yōu)勢。文獻隨著多核系統(tǒng)復雜程度的增加以及受延遲、功耗、面積等因素的約束和限制,其功能行為與性能指標變得密不可分,許多關鍵的功能性質必須附帶性能指標才有意義1多核系統(tǒng)的任務調整模型1.1imc-f引入性能評價函數后的IMC-F可以通過一個八元組1.2任務調度算法仿真多核系統(tǒng)任務調度問題主要討論如何將待調度任務集分配到合適的處理器核上運行以使得任務集的執(zhí)行滿足性能要求。多核系統(tǒng)任務調度問題通過四元組Sched=(T,C,ν,λ)來表示。其中:T={T多核系統(tǒng)任務調度問題就是在滿足系統(tǒng)性能要求的前提下解決集合T到集合C的映射問題。在整個調度過程中,任務T通過以上對任務狀態(tài)的分析,多核系統(tǒng)任務調度問題的IMC-F模型Γ為:a)b)e)費用函數Ff)標記函數L(sh)S通過遍歷IMC-F模型Γ中的所有路徑刻畫任務調度算法解空間。通過對路徑上每個狀態(tài)的即時費用累加得到任務調度算法的累加費用值,從而可以對算法性能進行評價。IMC-F模型Γ中,由于每次調度最多有C2公務調度算法的動態(tài)測量2.1任務集t的調度優(yōu)化Sched對應IMC-F模型中從初始狀態(tài)s其中:b調度算法Ψ對任務集T進行調度后生成的路徑若能被Sched對應IMC-F模型Γ接收則算法Ψ功能正確;否則,算法Ψ因各種原因引起功能錯誤(包括算法邏輯錯誤、處理器節(jié)點故障等)。2.2基于貝爾曼方程的計算為了對任務調度算法產生的系統(tǒng)開銷進行評價,擴展aC-SL的狀態(tài)公式,增加費用算子F。擴展后的aCSL狀態(tài)公式由以下語法產生:其中:f∈[0,∞),Δ∈{≤,<,≥,>},k>0,t∈RaCSL的路徑公式刻畫了執(zhí)行路徑應該滿足的條件,由以下語法產生:使用標記函數L:s累積費用值函數是路徑上的費用期望值,可以通過貝爾曼方程進行迭代計算:式(1)描述了當前狀態(tài)的累積費用值函數與下一狀態(tài)的累積費用值函數的關系。其中γ為折扣因子,表示當前轉移費用與累積費用的關系,γ=0表示只考慮當前狀態(tài)變遷產生的費用;γ=1表示同時考慮當前狀態(tài)和后續(xù)狀態(tài)變遷產生的費用?；趯β窂焦胶蜖顟B(tài)公式中費用算子F的語義分析,以下分情況對Exp其中:→/b)若c)若情況3其他條件下Exp通過以上對Exp2.3任務調度算法動態(tài)度量在Sched對應IMC-F模型Γ和擴展的aCSL的基礎上,多核系統(tǒng)動態(tài)度量方法動態(tài)記錄算法Ψ運行時數據,在統(tǒng)一的模型下實現了對算法Ψ的功能驗證和性能評估。令L:s記錄算法Ψ運行時行為序列及對應行為產生的費用值ATL=b推論1s推論1中條件a)表示模型Γ接收路徑σ,即算法Ψ導出的路徑σ唯一對應模型Γ中的一條路徑,算法Ψ功能滿足預期。推論1中條件b)表示算法Ψ對應路徑上的累積費用值函數在Δf限定的區(qū)間內,算法Ψ性能滿足預期。推論1對算法功能正確性進行驗證的同時實現了統(tǒng)一模型下的性能評估,從功能、性能的角度確保了算法行為可預期。3狀態(tài)公式s的運用設Sched中處理器核集合C={C假設每分鐘有一個任務集到達多核系統(tǒng),則λ在模型Γ的基礎上,利用aCSL路徑公式和狀態(tài)公式對初始狀態(tài)s其中:事件用例1令Ψaction(value)表示動作及其發(fā)生的時間,t(action)=value。同理,ATLATL根據EDF算法,最后一個分配的任務為T用例2令Ψ根據關鍵路徑算法,最后一個分配的任務為T4動態(tài)度量方法本文基于改進的IMC構建了多核系統(tǒng)任務調度算法功能模型,擴展aCSL刻畫了多核系統(tǒng)任務調度算法解空間,量化了模型中任意解應該滿足的性能預期,本文提出的多核系統(tǒng)任務調度算法的動態(tài)度量方法充分發(fā)揮了IMC模型的性能評價功能,從功能、性能的角度,在理論上確保了算法行為