异构网络化汽车电子系统中多DAG离线任务调度

doi:10.3969/j.issn.1000-436X.2013.12.003

摘要/Abstract

摘要：

公平性和通信开销已成为影响调度性能的主要瓶颈，首先在任务优先级排序阶段，提出基于通信开销权值的轮转调度的公平排序标准；在处理器选择阶段，提出在插入法的基础上将任务分配到具有最小选择值的选择标准；综合上述2个阶段，提出以降低调度长度和减少通信开销为目标的多 DAG 离线公平任务调度(MDOFTS,multiple DAGs off-line and fairness task scheduling)算法。异构网络化汽车电子系统是一个典型的混合关键级嵌入式系统，既要确保实时性又要降低调度长度，提出了以满足安全关键DAG的多DAG离线优先级任务调度(MDOPTS,multiple DAGs off-line and Priority task scheduling)算法。综合MDOFTS和MDOPTS，提出多DAG离线自适应任务调度(MDOATS,multiple DAGs off-line and adaptive task scheduling)算法，在满足实时性的基础上提高调度性能。实例分析和实验结果表明，提出的算法在调度长度、通信开销、不公平性、最差响应时间和实时性上都优于其他算法。

关键词: 异构网络化汽车电子系统, 多DAG, 通信开销, 调度长度, 实时性

Abstract:

Fairness and communication overhead have become the major bottleneck in performance of scheduling,a fair sorting criteria based on round-robin with communication overhead weight was proposed and a selection criteria based on assigning the task to the minimum selection value considering insertion was proposed in processor selection phase.The multiple DAG off-line and fairness task scheduling(MDOFTS)algorithm was proposed combining the above two phases to reduce the schedule length and communication overhead.Heterogeneous networked automobile electronic systems are typical mixed-criticality embedded systems,which must make sure to be real-time and to reduce scheduling length.The multiple DAG off-line and priority task scheduling (MDOPTS) algorithm was proposed to make sure the safety-critical DAG.The multiple DAG off-line and adaptive task scheduling(MDOATS)algorithm was proposed to improve the system performance on the basis of real-time based on MDOFTS and MDOPTS.Example analysis and experimental results show that the MDOFTS algorithm is better than other algorithms in schedule length,communication overh unfairness,worst-case response time and real-time.

Key words: heterogeneous networked automotive electronic systems, multiple DAG, communication overhead, schedule length, real-time

谢国琪,李仁发,杨帆,黄卫红. 异构网络化汽车电子系统中多DAG离线任务调度[J]. 通信学报, 2013, 34(12): 20-32.

Guo-qi XIE,Ren-fa LI,Fan YANG,Wei-hong HUANG. Multiple DAG off-line task scheduling for heterogeneous networked automobile electronic systems[J]. Journal on Communications, 2013, 34(12): 20-32.

图/表 17

图1

表1

表2

表3

图2

表4

表5

图3

图4

图5

图6

图7

图8

图9

图10

图11

图12

参考文献 20

[1]	BUCKL C , CAMEK A , KAINZ G , et al. The software car:building ICT architectures for future electric vehicles[A]. 2012 IEEE Interna-tional Electric Vehicle Conference(IEVC)[C]. Kuching,Malaysia, 2012.1-8.
[2]	FURST S . Challenges in the design of automotive software[A]. Pro-ceedings of the Conference on Design,Automation and T in Eu-rope[C]. Dresden,Germany, 2010.256-258.
[3]	KONIK D . Development of the dynamic drive for the new 7series of the BMW group[J]. International Journal of Vehicle Design, 2002,28(1):131-149.
[4]	Audi A8'10 electrical and network systems[EB/OL]. , 2010.
[5]	BARUAH S K , BURNS A , DAVIS R I . Response-time analysis for mixed criticality systems[A]. The 32nd IEEE Real-Time Systems Symposium[C]. Vienna,Austria, 2011.34-33.
[6]	ALDERISI G , CALTABIANO A , VASTA G , et al. Simulative assess-ments of IEEE 802.1 Ethernet AVB and time-triggered Ethernet for advanced driver assistance systems and in-car infotainment[A]. Vehi-cular Networking Conference(VNC)[C]. Seoul,Republic of Korea, 2012.187-194.
[7]	TOPCUOGLU H , HARIRI S , WU M . Performance-effective and low-complexity task scheduling for heterogeneous computing[J]. IEEE Transactions on Parallel and Distributed Systems, 2002,13(3):260-274.
[8]	谢勇，李仁发，阮华斌等. 最优的 FlexRay 静态段配置算法[J]. 通信学报， 2012,33(11):33-40. XIE Y , LI R F , RUAN H B , et al. Optimal Configuration algorithm for static segment of FlexRay[J]. Journal on Communications, 2012,33(11):33-40.
[9]	H?NIG U , SCHIFFMANN W . A meta-algorithm for scheduling mul-tiple DAGs in homogeneous system environments[A]. The 18th Inter-national Conference on Parallel and Distributed Computing Sys-tems[C]. Dallas,USA, 2006.147-152.
[10]	ZHAO H N , SAKELLARIOU R . Scheduling multiple DAGs onto heterogeneous systems[A]. The 20th International Parallel and Distri-buted Processing Symposium[C]. Rhodes Island,Greece, 2006.14.
[11]	田国忠，肖创柏，徐竹胜等. 异构分布式环境下多 DAG 工作流的混合调度策略[J]. 软件学报， 2012,23(10):2720-2734. TIAN G Z , XIAO C B , XU Z S , et al. Hybrid scheduling strategy for multiple DAGs workflow in heterogeneous system[J]. Journal of Software, 2012,23(10):2720-2734.
[12]	HSU C C , HUANG K C , WANG F J . On line scheduling of workflow applications in grid environments[J]. Future Generation Computer Systems, 2011,27(6):860-870.
[13]	ARABNEJAD H , BARBOSA J . Fairness resource sharing for dynam-ic workflow scheduling on Heterogeneous Systems[A]. 2012 IEEE 10th International Symposium on Parallel and Distributed Processing with Applications (ISPA)[C]. Madrid,Spain, 2012.633-639.
[14]	KLOBEDANZ K , KOENIG A , MUELLER W . A reconfiguration approach for fault-tolerant flexray networks[A]. Design,Automation＆ Test in Europe Conference ＆ Exhibition (DATE)[C]. Grenoble,France, 2011.1-6.
[15]	KLOBEDANZ K , KOENIG A , MUELLER W , et al. Self-reconfiguration for fault-tolerant flexRay networks[A]. 2011 14th IEEE International Symposium on Distributed Computing Work-shops(ISORCW)[C]. Newport Beach,CA, 2011.207-216.
[16]	HAGRAS T , JANECEK J . A high performance,low complexity algo-rithm for compile-time task scheduling in heterogeneous systems[J]. Parallel Computing, 2005,31(7):653-670.
[17]	LI T , BAUMBERGER D , HAHN S . Efficient and scalable mul ipro-cessor fair scheduling using distributed weighted round- robin[J]. ACM Sigplan Notices, 2009,44(4):65.
[18]	MOHANTY R , BEHERA H S , PATWARI K , et al. Priority based dynamic round robin (PBDRR) algorithm with intelligent ti slice for soft real time systems[J]. International Journal of Advanced Com-puter Seience and Applications, 2011,2(2):46-50.
[19]	CHEN Y , ZENG G , RYO K , et al. Effects of queueing jitter on worst-case response times of CAN messages with offsets[A]. In Proc of the Embedded System Symposium in Japan[C]. Tokyo,Japan, 2012.119-126.
[20]	DICK R P , RHODES D L , WOLF W . TGFF:task graphs for free[A]. Proceedings of the 6th International Workshop on Hardware/Software Codesign[C]. Seattle,USA, 1998.97-101.

算法特点	算法
算法特点	M_HEFT	Fairness(E-Fairness)	OWM	FDWS
插入法	是	是	否	是
公平性	对短DAG不公平	对后调度DAG不公平	对短DAG不公平	对长DAG不公平
算法复杂度	O(n²×d×p)	O(n²×d×p+d³×p)	O(n²×d×p)	O(n²×d×p)

向上排序值	DAG
	DAG-A										DAG-B
	A₁	A₂	A₃	A₄	A₅	A₆	A₇	A₈	A₉	A₁₀	B₁	B₂	B₃	B₄	B₅
rank _upd(n_i,p₁)	105	79	79	86	75	67	45	39	50	21	44	20	33	38	7
rank _upd(n_i,p₂)	95	69	75	66	56	62	39	31	30	7	42	20	31	31	6
rank _upd(n_i,p₃)	114	81	86	87	70	67	44	43	47	16	55	20	30	34	5
rank _upd(n_i)	523.5	150.6	80	159.4	67	65.3	42.7	27.7	42.3	0	141	20	30	34	0

算法结果	算法
算法结果	M_HEFT	E-Fairness(off-line)	OWN(off-line)	FDWS(off-line)	MDOFTS
任务优先级	A₁,A₃,A₄,A₂,A₅,A₆,A₉,A₇,B₁,A₈,B₄,B₃,B₂,A₁₀,B₅	A₁,B₁,A₃,A₄,A₂,A₅,A₆,B₄,A₉,A₇,A₈,A₁₀,B₃,B₂,B₅	A₁,B₁,A₃,B₄,A₄,B₃,A₂,B₂,A₅,B₅,A₆,A₉,A₇,A₈,A₁₀	B₁,A₁,B₄,A₃,B₃,A₄,B₂,A₂,B₅,A₅,A₆,A₉,A₇,A₈,A₁₀	A₁,B₁,B₄,A₄,B₃,A₂,B₂,A₃,A₅,B₄,A₆,A₇,A₉,A₈,A₁₀
调度长度DAG-A	81	89	81	87	78
调度长度DAG-B	59	49	42	40	41
不公平性	0.389 831	0.175 418	0.118 17	0.008 046	0.121 951
通信开销DAG-A	127	127	128	141	58
通信开销DAG-B	20	19	21	22	15
通信开销率	0.532 6	0.529 0	0.539 9	0.605 1	0.264 5

算法结果	算法
算法结果	MDOFTS	MDOPTS	MDOATS
优先级	A₁,B₁,B₄,A₄,B₃,A₂,B₂,A₃,A₅,B₄,A₆,A₇,A₉,A₈,A₁₀	B₁,B₄,B₃,B₂,B₅,A₁,A₃,A₄,A₂,A₅,A₆,A₉,A₇,A₈,A₁₀	B₁,A₁,B₄,A₄,B₃,A₂,B₂,A₃,B₅,A₅,A₆,A₇,A₉,A₈,A₁₀
调度长度DAG-A	78	99	80
调度长度DAG-B	41	36	38
不公平性	0.121 951	0.212 121	0.034 868
通信开销DAG-A	58	58	82
通信开销DAG-B	15	25	25
通信开销率	0.264 5	0.300 7	0.387 9
时间复杂度	O(n²×d×p)	O(n²×d×p)	O(n³×d² ×p)