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

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. (C) 2015 Elsevier Inc. All rights reserved.