Schedulability Analysis of Parallel Tasks Under Global Limited Preemption on Heterogeneous Multi-Cores

Han Meiling; Sun Shining; Deng Qingxu

doi:10.7544/issn1000-1239.202220711

Journal of Computer Research and Development > 2023 > 60(5): 992-1001. > DOI: 10.7544/issn1000-1239.202220711

Han Meiling, Sun Shining, Deng Qingxu. Schedulability Analysis of Parallel Tasks Under Global Limited Preemption on Heterogeneous Multi-Cores[J]. Journal of Computer Research and Development, 2023, 60(5): 992-1001. DOI: 10.7544/issn1000-1239.202220711

Citation:

PDF (1401 KB)

Schedulability Analysis of Parallel Tasks Under Global Limited Preemption on Heterogeneous Multi-Cores

1.
School of Modern Posts, Nanjing University of Posts and Telecommunications, Nanjing 210023
2.
School of Computer Science and Engineering, Northeastern University, Shenyang 110819

Funds: This work was supported by the National Natural Science Foundation of China (62002173, 62072085) and the Natural Science Research Start-up Foundation of Recruiting Talents of Nanjing University of Posts and Telecommunications (NY219167).

More Information

Author Bio:
Han Meiling: born in 1988. PhD, lecturer. Member of CCF. Her main research interest is embedded real-time scheduling theory

Sun Shining: born in 2001. PhD candidate. His main research interest is embedded real-time scheduling theory

Deng Qingxu: born in 1970. PhD, professor, PhD supervisor. Distinguished member of CCF. His main research interests include cyber-physical systems, embedded systems, and real-time systems
Received Date: August 15, 2022
Revised Date: February 27, 2023
Available Online: March 27, 2023

Graphical Abstract

Abstract

Abstract

The heterogeneous multi-core architecture takes advantage of the strengths of different architectures to execute specific types of workloads and is typically more energy-efficient and faster. However, it is very difficult to migrate to large-scale heterogeneous platforms, and large-scale parallelism will lead to a high level of complexity in software scheduling. Although there have been related studies on the DAG task model, the research on the limited preemption scheduling strategy based on the DAG task model still has some shortcomings. In this paper, we present a worst-case response time (WCRT) analysis method for typed DAG tasks on heterogeneous multi-cores under global fixed priority limited preemption scheduling, in which each vertex of the DAG is allowed to execute on only one type of core. We present a method for analyzing the schedulability of multiple DAG tasks under global fixed-priority preemption scheduling based on the latest schedulability analysis of a single DAG task. First, a method to analyze the upper bound workload of higher priority tasks is proposed. Following that, a method for analyzing the upper bound workload of lower priority tasks is proposed. A pseudo-polynomial analysis method is proposed for analyzing the upper bound of WCRT of each typed DAG task based on the state-of-the-art method for single typed DAG task analysis. The results of our experiments with randomly generated workloads indicate that our proposed method is capable of analyzing a task set in a reasonable amount of time. In addition, the results of the scheduler meet all expectations.
- response time analysis,
- heterogeneous multi-cores,
- parallel task model,
- embedded real-time systems,
- schedulability analysis

FullText(HTML)

References (24)

References

[1]	OpenMP. OpenMP application program interface version 4.5[EB/OL]. [2022-11-20].https://www.openmp.org/
[2]	OpenCL. Open standard for parallel programming of heterogeneous systems [EB/OL]. [2022-11-20] .https://www.khronos.org/opencl/
[3]	CUDA. Free tools and trainings for develpers: CUDA zone[EB/OL]. [2022-11-20].https://developer.nvidia.com/cuda-zone
[4]	Han Meiling, Guan Nan, Sun Jinghao, et al. Response time bounds for typed DAG parallel tasks on heterogeneous multi-cores[J]. IEEE Transactions on Parallel Distributed Systems, 2019, 30(11): 2567−2581 doi: 10.1109/TPDS.2019.2916696
[5]	Capodieci N, Cavicchioli R, Bertogna M, et al. Limited-preemption scheduling on multiprocessors[C]//Proc of the 22nd Int Conf on Real-Time Networks and Systems. New York: ACM, 2014: 225−234
[6]	Thekkilakattil A, Davis R I, Dobrin R, et al. Multiprocessor fixed priority scheduling with limited preemptions[C]// Proc of the 23rd Int Conf on Real Time and Networks Systems. New York: ACM, 2015: 13−22
[7]	Zhou Quan, Li Guohui, Li Jianjun, et al. Response time analysis for tasks with fixed preemption points under global scheduling[J]. ACM Transactions on Embedded Computing Systems, 2019, 18(5): 1−23
[8]	Mitra A, Geoffrey N, Gerhard F. An analysis of lazy and eager limited preemption approaches under DAG-based global fixed priority scheduling[C]// Proc of the 20th IEEE Int Symp on Real-Time Distributed Computing. Piscataway, NJ: IEEE, 2017: 193−202
[9]	Serrano M A, Melani A, Bertogna M, et al. Response time analysis of DAG tasks under fixed priority scheduling with limited preemptions [C]//Proc of the 19th Design, Automation & Test in Europe Conf & Exhibition. Piscataway, NJ: IEEE, 2016: 1066−1071
[10]	Li Chunglun, Li Qingying. Scheduling jobs with release dates, equal processing times, and inclusive processing set restrictions[J]. Journal of the Operational Research Society, 2015, 66(3): 516−523 doi: 10.1057/jors.2014.22
[11]	Li Chunglun, Lee K. A note on scheduling jobs with equal processing times and inclusive processing set restrictions[J]. Journal of the Operational Research Society, 2016, 67(1): 83−86 doi: 10.1057/jors.2015.56
[12]	Jia Zhaohong, Li Kai, Leung J Y T. Effective heuristic for makespan minimization in parallel batch machines with non-identical capacities[J]. International Journal of Production Economics, 2015, 169: 1−10 doi: 10.1016/j.ijpe.2015.07.021
[13]	Li Shuguang. Parallel batch scheduling with inclusive processing set restrictions and non-identical capacities to minimize makespan[J]. European Journal of Operational Research, 2017, 260(1): 12−20 doi: 10.1016/j.ejor.2016.11.044
[14]	Leung Y T, Li Chunglun. Scheduling with processingset restrictions: A survey[J]. International Journal of Production Economics, 2008, 116(2): 251−262 doi: 10.1016/j.ijpe.2008.09.003
[15]	Leung Y T, Li Chunglun. Scheduling with processing set restrictions: A literature update[J]. International Journal of Production Economics, 2016, 175(8): 1−11
[16]	Baruah S, Bonifaci V, Marchetti-Spaccamela A, et al. A generalized parallel task model for recurrent real-time processes [C]// Proc of the 33rd IEEE Real-Time Systems Symp. Piscataway, NJ: IEEE, 2012: 63−72
[17]	Fonseca J, Nelissen G, Nélis V. Improved response time analysis of sporadic DAG tasks for global FP scheduling [C]//Proc of the 25th Int Conf on Real-Time Networks and Systems. Piscataway, NJ: IEEE, 2017: 28−37
[18]	Guan Nan, Han Meiling, Gu Chuancai, et al. Bounding carry-in interference to improve fixed priority global multiprocessor scheduling analysis[C]// Proc of the 21st IEEE Int Conf on Embedded and Real-Time Computing Systems and Applications. Piscataway, NJ: IEEE, 2015: 11−20
[19]	Han Meiling, Zhang Tianyu, Lin Yuhan, et al. Federated scheduling for typed DAG tasks scheduling analysis on heterogeneous multi-cores[J]. Journal of Systems Architecture, 2021, 112: 101870 doi: 10.1016/j.sysarc.2020.101870
[20]	Peng Xuemei, Han Meiling, Deng Qingxu. Response time analysis of typed DAG tasks for G-FP scheduling [C]// Proc of the 5th Int Symp on Dependable Software Engineering: Theories, Tools, and Applications. Berlin: Springer, 2019: 56−71
[21]	Yang Kecheng, Yang Ming, Anderson J H. Reducing response-time bounds for DAG-based task systems on heterogeneous multicore platforms [C]//Proc of the 24th Int Conf on Real-Time Networks and Systems. New York: ACM, 2016: 349−358
[22]	OpenAMP. Introduction to OpenAMP library[EB/OL]. [2022-11-20].https://www.openampproject.org/docs/whitepapers/Introduction_to_OpenAMPlib_v1.1a.pdf
[23]	Bini E, Buttazzo G C. Measuring the performance of schedulability tests[J]. Real-Time Systems, 2005, 30(1): 129−154
[24]	Cordeiro D, Mounié G, Perarnau S, et al. Random graph generation for scheduling simulations [C/OL]// Proc of the 3rd Int ICST Conf on Simulation Tools and Techniques (SIMUTools 2010). ICST, 2010[2018-03-10].https://hal.science/hal-00471255/

[1]	Fu Ning, Du Chenglie, Li Jianliang, Liu Zhiqiang, Peng Han. Analysis and Verification of AADL Hierarchical Schedulers[J]. Journal of Computer Research and Development, 2015, 52(1): 167-176. DOI: 10.7544/issn1000-1239.2015.20130722
[2]	Zhu Yi, Xiao Fangxiong, Zhou Hang, Zhang Guangquan. Method for Modeling and Analyzing Software Energy Consumption of Embedded Real-Time System[J]. Journal of Computer Research and Development, 2014, 51(4): 848-855.
[3]	Wu Xiaodong, Han Jianjun, Wang Tianjiang. Energy-Aware Scheduling of Hard Real-Time Tasks in VFD-Based Multi-Core Systems[J]. Journal of Computer Research and Development, 2012, 49(5): 1018-1027.
[4]	Ding Wanfu, Guo Ruifeng, Qin Chenggang, Guo Fengzhao. A Fault-Tolerant Scheduling Algorithm with Software Fault Tolerance in Hard Real-Time Systems[J]. Journal of Computer Research and Development, 2011, 48(4): 691-698.
[5]	Han Jianjun, Wu Xiaodong, Li Qinghua. Energy-Efficient Real-Time Scheduling Algorithm with Accrual Utility under Energy Bounds[J]. Journal of Computer Research and Development, 2011, 48(2): 327-337.
[6]	Chen Yan, Xu Xiaofeng, Li Xiaochao, Guo Donghui. Race Condition and Its Analysis Approach of Real-time Embedded Systems[J]. Journal of Computer Research and Development, 2010, 47(7): 1201-1210.
[7]	Li Renfa, Liu Yan, and Xu Cheng. A Survey of Task Scheduling Research Progress on Multiprocessor System-on-Chip[J]. Journal of Computer Research and Development, 2008, 45(9): 1620-1629.
[8]	Shen Zhuowei and Wang Yun. A Schedulability Analysis Algorithm for EDF-Based End-to-End Real-Time Systems[J]. Journal of Computer Research and Development, 2006, 43(5): 813-820.
[9]	Xing Jiansheng, Liu Junxiang, Wang Yongji. Schedulability Test Performance Analysis of Rate Monotonic Algorithm and Its Extended Ones[J]. Journal of Computer Research and Development, 2005, 42(11): 2025-2032.
[10]	Zhu Xiangbin and Tu Shiliang. Analysis and Research of a Window-Constrained Real-Time System with Constraints[J]. Journal of Computer Research and Development, 2005, 42(8): 1445-1451.