面向汽車的異構(gòu)網(wǎng)絡(luò)化嵌入式系統(tǒng)多DAG調(diào)度研究.pdf

1、現(xiàn)代汽車電子系統(tǒng)是計(jì)算與網(wǎng)絡(luò)都異構(gòu)且深度融合的分布式嵌入式系統(tǒng)。系統(tǒng)的異構(gòu)性、網(wǎng)絡(luò)化和復(fù)雜化使得其調(diào)度問題相比通用異構(gòu)分布式系統(tǒng)和傳統(tǒng)嵌入式系統(tǒng)存在差異且更加復(fù)雜?，F(xiàn)代汽車電子系統(tǒng)還是以安全關(guān)鍵為特征的，包含時(shí)間與性能關(guān)鍵、時(shí)間混合關(guān)鍵級(jí)及可靠性混合關(guān)鍵級(jí)的異構(gòu)網(wǎng)絡(luò)化嵌入式系統(tǒng)。為此，本文從汽車功能安全的角度出發(fā)，以確保車輛安全運(yùn)行和車內(nèi)外人身安全為主要目標(biāo)，提出高性能、強(qiáng)實(shí)時(shí)和高可靠的若干調(diào)度理論與方法。
　　異構(gòu)網(wǎng)絡(luò)化汽車電子

2、系統(tǒng)的多種功能應(yīng)用中，任務(wù)間的優(yōu)先級(jí)約束日益復(fù)雜，AUTOSAR規(guī)范也指出需從功能級(jí)的角度對(duì)計(jì)算系統(tǒng)和網(wǎng)絡(luò)系統(tǒng)進(jìn)行集成設(shè)計(jì)。本文將汽車電子系統(tǒng)中的多個(gè)功能應(yīng)用抽象成多個(gè)有向無環(huán)圖DAG。在系統(tǒng)異構(gòu)性、混合關(guān)鍵級(jí)和可靠性目標(biāo)的驅(qū)動(dòng)下，圍繞性能、實(shí)時(shí)和可靠三個(gè)方面開展面向汽車的異構(gòu)網(wǎng)絡(luò)化嵌入式系統(tǒng)的多DAG調(diào)度研究。主要工作和創(chuàng)新點(diǎn)如下。
　　(1)提出異構(gòu)驅(qū)動(dòng)的高性能多DAG靜態(tài)調(diào)度的若干理論與方法。
　　1)針對(duì)異構(gòu)計(jì)算環(huán)境

3、下的單DAG任務(wù)調(diào)度中，向上排序值使用平均計(jì)算開銷的問題，定義異構(gòu)優(yōu)先級(jí)排序值HPRV作為任務(wù)優(yōu)先級(jí)排序標(biāo)準(zhǔn)，實(shí)現(xiàn)計(jì)算開銷的精確化。針對(duì)基于最小最早完成時(shí)間EFT的處理器分配方法僅考慮“向下看”的問題，從“向下看”和“向上看”的角度，定義異構(gòu)最小選擇值HSV作為處理器分配標(biāo)準(zhǔn)，提出高性能的單DAG任務(wù)調(diào)度算法HSV，以適應(yīng)系統(tǒng)的計(jì)算異構(gòu)性。
　　2)針對(duì)融合異構(gòu)網(wǎng)絡(luò)環(huán)境的單DAG任務(wù)與消息調(diào)度中，向上排序值同樣使用平均通信開銷的問

4、題，將通信開銷定位到具體的處理器，實(shí)現(xiàn)通信開銷的精確化。針對(duì)計(jì)算任務(wù)與通信消息獨(dú)立調(diào)度的問題，提出高性能的單DAG任務(wù)與消息同步調(diào)度算法HSV_CC，以適應(yīng)計(jì)算與網(wǎng)絡(luò)都異構(gòu)且深度融合的汽車電子系統(tǒng)。
　　3)針對(duì)異構(gòu)計(jì)算環(huán)境下的多DAG靜態(tài)任務(wù)調(diào)度易出現(xiàn)局部單調(diào)和較高不公平性的問題，分別提出基于HPRV公平策略的多DAG靜態(tài)任務(wù)調(diào)度算法F_MDSTS和多DAG靜態(tài)任務(wù)與消息調(diào)度算法F_MDSTMS，最終實(shí)現(xiàn)高性能及公平的任務(wù)與消息

5、同步調(diào)度。實(shí)驗(yàn)結(jié)果表明，提出的算法能夠滿足時(shí)間與性能關(guān)鍵的異構(gòu)網(wǎng)絡(luò)化汽車電子系統(tǒng)靜態(tài)調(diào)度的高性能與公平性需求。
　　(2)提出混合關(guān)鍵級(jí)驅(qū)動(dòng)的強(qiáng)實(shí)時(shí)多DAG動(dòng)態(tài)調(diào)度的若干理論與方法。
　　1)針對(duì)異構(gòu)計(jì)算環(huán)境下的多DAG動(dòng)態(tài)任務(wù)調(diào)度存在因處理器忙碌而造成阻塞的問題，提出基于HPRV公平策略的多DAG動(dòng)態(tài)任務(wù)調(diào)度算法F_MDDTS。在新DAG到達(dá)時(shí)，可以取消已分配處理器但未開始調(diào)度的任務(wù)，實(shí)現(xiàn)高性能的動(dòng)態(tài)任務(wù)調(diào)度。提出基于關(guān)鍵

6、級(jí)策略的多DAG動(dòng)態(tài)任務(wù)調(diào)度算法C_MDDTS，確保高關(guān)鍵級(jí)應(yīng)用的實(shí)時(shí)性。融合F_MDDTS和C_MDDTS，提出混合關(guān)鍵級(jí)策略的多DAG動(dòng)態(tài)任務(wù)調(diào)度算法MC_MDDTS，既確保高關(guān)鍵級(jí)的實(shí)時(shí)性，又使得低關(guān)鍵級(jí)應(yīng)用得到積極的處理。
　　2)針對(duì)汽車電子系統(tǒng)中通信開銷日益增長的問題，基于最小通信開銷權(quán)值COW，以最小化通信開銷為目標(biāo)，提出公平策略的多DAG動(dòng)態(tài)任務(wù)與消息調(diào)度算法F_MDDTMS。分別提出關(guān)鍵級(jí)策略的多DAG動(dòng)態(tài)任務(wù)與

7、消息調(diào)度算法C_MDDTMS和混合關(guān)鍵級(jí)策略的多DAG動(dòng)態(tài)任務(wù)與消息調(diào)度算法MC_MDDTMS，在性能和實(shí)時(shí)性上取得合理的平衡。實(shí)驗(yàn)結(jié)果表明，提出的算法能夠滿足時(shí)間混合關(guān)鍵級(jí)的異構(gòu)網(wǎng)絡(luò)化汽車電子系統(tǒng)動(dòng)態(tài)調(diào)度的強(qiáng)實(shí)時(shí)和高性能需求。
　　(3)提出可靠性目標(biāo)驅(qū)動(dòng)的高可靠多DAG容錯(cuò)調(diào)度的若干理論與方法。
　　1)通過分析異構(gòu)計(jì)算環(huán)境下DAG任務(wù)的優(yōu)先級(jí)約束，確定任務(wù)的可靠性模型，建立DAG計(jì)算可靠性模型。現(xiàn)有任務(wù)復(fù)制的容錯(cuò)方法要

8、么DAG中的每個(gè)任務(wù)僅有一個(gè)副版本來容忍一個(gè)錯(cuò)誤，要么盲目地使每個(gè)任務(wù)擁有ε個(gè)副本來容忍可能發(fā)生的ε個(gè)故障。針對(duì)上述問題，依次提出滿足DAG計(jì)算可靠性目標(biāo)的任務(wù)復(fù)制下限值算法、貪婪的和經(jīng)濟(jì)的任務(wù)復(fù)制策略算法，精確量化每個(gè)任務(wù)需要復(fù)制的次數(shù)。
　　2)通過考慮任務(wù)與消息的同步特征，在任務(wù)復(fù)制策略的基礎(chǔ)上，分別確定鏈路可靠性、通信路徑可靠性和消息主版本集，最終建立消息可靠性模型和DAG通信可靠性模型。針對(duì)目前汽車電子系統(tǒng)中通信可靠性與

9、容錯(cuò)方法采用固定個(gè)數(shù)的消息或鏈路復(fù)制的問題，依次提出滿足通信可靠性目標(biāo)的消息復(fù)制下限值算法、貪婪的和經(jīng)濟(jì)的消息復(fù)制算法，精確量化各消息需要復(fù)制的次數(shù)。
　　3)基于DAG計(jì)算可靠性模型和任務(wù)復(fù)制容錯(cuò)算法，提出可選策略的多DAG處理器分配算法OSMDPA，實(shí)現(xiàn)任務(wù)與處理器的高效分配?；贒AG通信可靠性和消息復(fù)制容錯(cuò)算法，提出可選策略的多DAG通信路徑分配算法OSMDRA，實(shí)現(xiàn)消息與通信路徑的高效分配?；贠SMDPA和OSMDRA