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

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

Abstract

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

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.

Figures/Tables 17

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

算法特点	算法
算法特点	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)

Multiple DAG off-line task scheduling for heterogeneous networked automobile electronic systems

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 17

References 20

Related Articles 15

Metrics

Recommended 0

处理器	DAG
	DAG-A										DAG-B
	A₁	A₂	A₃	A₄	A₅	A₆	A₇	A₈	A₉	A₁₀	B₁	B₂	B₃	B₄	B₅
p₁	14	13	11	13	12	13	7	5	18	21	4	9	18	21	7
p₂	8	19	13	8	13	16	15	11	12	7	5	10	17	15	6
p₃	16	18	19	17	10	9	11	14	20	16	6	11	16	19	5

[1]	Jinkang ZHU, Mingyang CHAI, Wuyang ZHOU. Three-three-three network architecture and learning optimization mechanism for B5G/6G [J]. Journal on Communications, 2021, 42(4): 62-75.
[2]	Wufei WU,Renfa LI,Gang ZENG,Yong XIE,Guoqi XIE. Survey of the intelligent and connected vehicle cybersecurity [J]. Journal on Communications, 2020, 41(6): 161-174.
[3]	Ying GUO,Lun LI,Peng WANG. Real time interpolation algorithm based on Lanczos kernel [J]. Journal on Communications, 2017, 38(6): 142-147.
[4]	Gang JU,Liang YUAN,Xiao-yue LIU,Hao-en YUE. Study on mobile target real-time image registration based on improved SURF algorithm [J]. Journal on Communications, 2017, 38(1): 177-186.
[5]	Quan CHEN,Hong GAO. Dynamic switching based real-time routing in low-duty-cycle wireless sensor networks [J]. Journal on Communications, 2015, 36(10): 224-234.
[6]	. Link quality based path delay analysis in wireless sensor networks [J]. Journal on Communications, 2014, 35(6): 13-109.
[7]	Quan CHEN,Hong GAO. Link quality based path delay analysis in wireless sensor networks [J]. Journal on Communications, 2014, 35(6): 100-109.
[8]	. Spectrum access scheme of MAC layer for real-time traffic in cognitive radio network [J]. Journal on Communications, 2014, 35(4): 5-43.
[9]	Rui-fang LI,Quan LIU,Ren-fa LI. Spectrum access scheme of MAC layer for real-time traffic in cognitive radio network [J]. Journal on Communications, 2014, 35(4): 35-43.
[10]	Ji WANG,Wei-dong BAO,Xiao-min ZHU. Fault-tolerant scheduling algorithm for real-time tasks in virtualized cloud [J]. Journal on Communications, 2014, 35(10): 171-180.
[11]	. Fault-tolerant scheduling algorithm for real-time tasks in virtualized cloud [J]. Journal on Communications, 2014, 35(10): 20-180.
[12]	. RSPEED：the reliability and real-time routing based on uncertain delay in wireless sensor network [J]. Journal on Communications, 2013, 34(8): 15-119.
[13]	Quan CHEN,Hong GAO. RSPEED：the reliability and real-time routing based on uncertain delay in wireless sensor network [J]. Journal on Communications, 2013, 34(8): 110-119.
[14]	Lei HAN,Ji-qiang LIU,Zhen HAN,Xue-ye WEI. Pre-distribution asymmetric key management scheme for mobile ad hoc networks [J]. Journal on Communications, 2012, 33(10): 26-34.
[15]	Ling-xi PENG,Dong-qing XIE,Ying-fang FU,Wei XIONG,Yu-li SHEN. Automated intrusion response system model based on danger theory [J]. Journal on Communications, 2012, 33(1): 136-144.