Dynamic Cluster Selection DAG Scheduling for Clustered Many-Core Processor Considering Inter-Cluster Communication

The advancement of embedded systems, such as autonomous driving systems, has led to a need for platforms that can cope with severe real-time constraints. In this context, research on real-time scheduling of Directed Acyclic Graph (DAG) using clustered many-core processors has been actively conducted. Clustered many-core processors are suitable for systems with severe real-time constraints due to their structure with low memory contention. However, improper selection of clusters can result in a significant volume of inter-cluster communication, which introduces considerable overhead. Despite its importance, reducing inter-cluster communication has not been extensively studied, and when studied, the focus has often been limited to specific clustered architectures. Furthermore, in DAG scheduling, inter-cluster communication occurs when a single node uses multiple clusters and when different clusters are used between nodes, respectively. For example, in embedded systems such as autonomous driving systems, where a single node may be processed by multiple cores and modeled in a DAG, reduction of inter-cluster communication both within a node and between nodes should be aimed at. To address this issue, this paper proposes the dynamic cluster selection DAG scheduling method considering the reduction of inter-cluster communication. The proposed method dynamically selects the clusters to be used based on the number of cores remaining in each cluster and information on the clusters used by dependent jobs. The proposed method is independent of cluster architectures used and can be used on various clustered many-core processors. Through experiments using two task sets and 12 cluster architectures with DAG modeling autonomous driving systems, we analyzed inter-cluster communication occurrences and response times. When compared to three baseline cluster selection methods—the index-based approach, the best-fit strategy for the number of cores within a cluster, and the worst-fit strategy for the number of cores within a cluster—our proposed method achieves significant reductions. Specifically, it reduces the average number of inter-cluster communication occurrences within a node by up to 96%, 65%, and 59%, respectively. Similarly, the average number of inter-cluster communication occurrences between nodes is reduced by up to 53%, 61%, and 59%, respectively. Furthermore, the average maximum response time is reduced by up to 31%, 32%, and 23%, respectively. The results show that for all cluster architectures, the proposed method is able to suppress the occurrence of inter-cluster communication well both within a node and between nodes of the DAG and suppress response times.