基于任務(wù)調(diào)度算法的系統(tǒng)評(píng)價(jià)方法

基于任務(wù)調(diào)度算法的系統(tǒng)評(píng)價(jià)方法

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