Research On Multiple DAGs Scheduling Of Heterogeneous Networked Embedded Systems For Automotive

Modern automobile electronic systems are distributed embedded systems where computing and networking are both heterogeneous and deeply jointed.The scheduling problems of automobile electronic systems are different and more complicated than general heterogeneous distributed systems and traditional embedded systems due to the heterogeneity,networking and complexity of them.Modern automobile electronic systems are also heterogeneous networked systems with characteristic of safety-critical,including time and performance-critical,time mixed-criticality and reliability mixed-criticality.Therefore,we propose several scheduling theories and methods for high performance,hard real-time and high reliability from the point of functional safety of automobile to guarantee safe operation of vehicle and safety of civilians inside and outside of car.Tasks with precedence constraints have been increasingly complicated in many function applications of heterogeneous networked automobile electronic systems.The AUTOSAR specification also pointed the integration design of computing systems and networking systems from the point of functional level.Multiple functional applications of automobile electronic systems are abstracted into multiple Directed Acyclic Graphs(DAGs)in this paper.We make some study of multiple DAGs scheduling on heterogeneous networked embedded system for automobile,namely,the scheduling theories and methods for performance,real-time and reliability under the driven of heterogeneity,mixed-criticality and reliability target respectively.The main works and innovations are given as follows.(1)Multiple DAGs static scheduling theories and methods for high performance under heterogeneity-driven are proposed1)For the problem of using average computation cost in upward rank value for single DAG task scheduling of heterogeneous computing environments,the Heterogeneous Priority Rank Value(HPRV)is defined as task prioritizing to get more accurate computation cost value.For the problem of merely considering "downward"for processor assignment by using Earliest Finish Time(EFT),the Heterogeneous Selecting Value(HSV)is defined as processor assignment by considering both“downward”and "upward",and a single DAG task scheduling algorithm called HSV is proposed to adapt to the computing heterogeneity of systems.2)For the problem of also using average communication cost in upward rank value for single DAG task and message scheduling of computing environments jointed with heterogeneous networking,the communication cost is located to the concrete processor to get more accurate communication cost value.For the problem of scheduling task and message independently,a single DAG task and message synchronized scheduling algorithm called HSV_CC is proposed to adapt to the automobile electronic systems where computing and networking are deeply jointed.3)For the problem of being prone to local monotonicity and higher unfairness in heterogeneous computing environments,an algorithm called Fairness on Multiple DAGs Static Task Scheduling(F_MDSTS)is proposed based on fair policy with HPRV.An algorithm called Fairness on Multiple DAGs Static Task and Message Scheduling(F_MDSTMS)is proposed to achieve synchronized scheduling task and message with high performance and fairness.Experiments show that the proposed algorithm could meet the high performance and fairness requirements of static scheduling on heterogeneous networked automobile electronic systems with time and performance-critical.(2)Multiple DAGs dynamic scheduling theories and methods for hard real-time under mixed-criticality-driven are proposed1)For the problem of blocked on tasks when the processors are busy,an algorithm called Fairness on Multiple DAGs Dynamic Task Scheduling(F_MDDTS)which can cancel the tasks that have been assigned to processors but haven’t been scheduled to achieve high performance scheduling is proposed.An algorithm called Criticality on Multiple DAGs Dynamic Task Scheduling(C_MDDTS)is proposed to ensure the real-time of higher criticality applications.An algorithm called Mixed-Criticality on Multiple DAGs Dynamic Task Scheduling(MC_MDDTS)is also proposed based on the joint of F_MDDTS and C_MDDTS to ensure hard real-time of higher criticality applications and activity of lower criticality applications.2)For the problem of increased communication cost,an algorithm called Fairness on Multiple DAGs Dynamic Task and Message Scheduling(F_MDDTMS)is proposed based on minimum Communication Overhead Weight(COW)to minimizing communication cost.Two algorithms called Criticality on Multiple DAGs Dynamic Task and Message Scheduling(C_MDDTMS)and Mixed-Criticality on Multiple DAGs Dynamic Task and Message Scheduling(MC_MDDTMS)are proposed to tuning a reasonable balance between performance and real-time;Experiments show that the proposed algorithm could meet the hard real-time and high performance requirements for dynamic scheduling on heterogeneous networked automobile electronic systems with time mixed-criticality.(3)Multiple DAGs fault-tolerant theories and methods for high reliability under reliability target-driven are proposed1)The task reliability model is determined and the DAG computing reliability model is constructed by analyzing precedence constraints with tasks of DAG.For the problem of there being only one backup copy to tolerate one fault or ε backup copies to tolerate ε faults for each task,the lower limit of task replication algorithm,greedy and economical algorithms are presented with task replication strategy to accurately quantization each task’s replicas.2)The link reliability,communication path reliability and message primary set are determined on the basis of task replication strategy by considering the synchronization feature of task and message,such that the message reliability model and DAG communication reliability model are constructed.For the problem of using fixed replication of messages or redundancy links in communication reliability and fault-tolerant of heterogeneous networked automobile electronic systems,the lower limit of message replication algorithm,greedy and economical algorithms are proposed with message replication strategy to accurately quantization each message’s replicas.3)An algorithm called Optional Strategy on Multiple DAGs Processor Assignment(OSMDPA)is proposed based on DAG computing reliability model and fault-tolerance algorithms.An algorithm called Optional Strategy on Multiple DAGs Router Assignment(OSMDRA)is proposed based on DAG communication reliability model and fault-tolerance algorithms.An algorithm called Optional Strategy on Multiple DAGs Fault-Tolerant Scheduling(OSMDFTS)is proposed to achieve high-reliability fault-tolerance of automotive electronic systems based on above OSMDPA and OSMDRA algorithms.Experiments show that the proposed algorithm could meet the high reliability and high performance requirements for fault-tolerant scheduling on heterogeneous networked automobile electronic systems with reliability mixed-criticality.