Exploit the data level parallelism and schedule dependent tasks on the multi-core processors

With the growing use of multi-core processors in the market, efficient and effective task parallelization strategies are on huge demand, so are the task scheduling algorithms. The scalability and efficiency of the existing algorithms on multi-core task scheduling need to be improved. To schedule real-time tasks on a multi-core processor, any pair of inter-dependent tasks must be executed following their original execution order. The directed acyclic graph (DAG) is commonly used to study the internal structure of a program. In this work, we investigated the property of the data dependency to eliminate the unnecessary execution constraints, and improved the DAG model by incorporating the temporal prop-erty of these dependencies. Based on such a model, we proposed a dynamic decomposed scheduling (DDS) strategy. With DDS, the dependent tasks could be released and executed earlier before the completion of their precedent tasks without producing any data hazards. The experiments were conducted on both synthesized tasks and real industrial embedded applications, the results show that DDS has a good performance in multi-core task schedul-ing, and it outperforms the state-of-the-art scheduling algorithms including the decom-posed scheduling, the global scheduling, and the federated scheduling.(c) 2021 Elsevier Inc. All rights reserved.

Automated summary

With the increasing use of multi-core processors, there is a high demand for efficient task parallelization strategies and scheduling algorithms. The existing algorithms for multi-core task scheduling need improvement in terms of scalability and efficiency. This study investigates the property of data dependency and proposes a dynamic decomposed scheduling strategy to improve the DAG model. Experimental results demonstrate that the proposed strategy, DDS, outperforms state-of-the-art scheduling algorithms.