Heterogeneity-driven end-to-end synchronized scheduling for precedence constrained tasks and messages on networked embedded systems

• Introduce a completely heterogeneous network topology for accurate analysis on message and route.
• Make both the computation time and communication time relate to the specific processor.
• Consider the processor and route selection both from “upward” and “downward” comprehensively.
• Synchronize tasks and messages by the task earliest start time and the link finish time.
• End-to-end synchronized scheduling for tasks and messages for processor and route selection synchronously.

Scheduling for a directed acyclic graph (DAG) on networked embedded systems is to maximize concurrency and minimize inter-processor communication for minimum end-to-end worst-case response time (WCRT). Time accuracy and synchronization are critical for scheduling on heterogeneous networked embedded systems, where computing and networking are both heterogeneous and deeply jointed. Most algorithms use the upward rank value for task prioritization, and the earliest finish time for processor selection. In order to obtain accurate and efficient schedules in heterogeneous networked systems, the above approaches can be improved. Moreover, synchronization with tasks and messages is critical for end-to-end WCRT. However, task scheduling and message scheduling are isolated in most approaches in communication contention environments. In this paper, a heterogeneity-driven task scheduling algorithm called Heterogeneous Selection Value (HSV) based on the classic model, and a heterogeneity-driven end-to-end synchronized scheduling algorithm called Heterogeneous Selection Value on Communication Contention (HSV_CC) based on the communication contention model are proposed to address the above problems. Both benchmark and extensive experimental evaluation demonstrate significant performance improvement of the proposed algorithms.