DocumentCode :
2086120
Title :
pCOMPATS: Period-Compatible Task Allocation and Splitting on Multi-core Processors
Author :
Kandhalu, A. ; Lakshmanan, K. ; Junsung Kim ; Rajkumar, R.
Author_Institution :
Dept. of Electr. & Comput. Eng., Carnegie Mellon Univ., Pittsburgh, PA, USA
fYear :
2012
fDate :
16-19 April 2012
Firstpage :
307
Lastpage :
316
Abstract :
Extensive research is underway to build chips with potentially hundreds of cores. In this paper, we consider the problem of scheduling periodic real-time tasks on multi-core processors. We develop a task partitioning algorithm called Period-Compatible-Allocation and Task-Splitting (pCOMPATS) for fixed-priority scheduling of preemptive hard real-time tasks where the utilization of each of the tasks is less than 50%. pCOMPATS clusters compatible tasks together with task splitting to improve the achievable utilization. We show that as the number of cores increases, the least upper bound on schedulable utilization achieved using pCOMPATS approaches 100% per core. To the best of our knowledge, this is the first result that shows that the utilization bound improves as the number of processing cores in the system increases. We refer to tasks having utilization greater than or equal to 50% as heavy tasks and provide a task-partitioning algorithm called pCOMPATS-HT for allocating such tasks. We show that the upper bound on schedulable utilization when tasks are scheduled using pCOMPATS-HT is at most 72%. We also evaluate the performance of pCOMPATS and other well-known partitioning techniques, and show that using pCOMPATS provides much better schedulable utilization in the average case. We characterize the overhead of pCOMPATS using measurements on an Intel Core i7 processor running Linux/RK. The overheads are seen to be low on the platform, making pCOMPATS to be practical. Our results are especially useful in the context of future many-core processors with dozens to hundreds of cores per processor.
Keywords :
Linux; multiprocessing systems; processor scheduling; resource allocation; Intel Core i7 processor; Linux-RK; compatible task clustering; fixed priority scheduling; multicore processors; pCOMPATS performance; period compatible task allocation and splitting; periodic real-time task scheduling; preemptive hard real-time task; schedulable utilization; task partitioning algorithm; Equations; Job shop scheduling; Multicore processing; Partitioning algorithms; Processor scheduling; Real time systems; Resource management; Multi-core; Real-Time; Scheduling; Utilization;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Real-Time and Embedded Technology and Applications Symposium (RTAS), 2012 IEEE 18th
Conference_Location :
Beijing
ISSN :
1080-1812
Print_ISBN :
978-1-4673-0883-0
Type :
conf
DOI :
10.1109/RTAS.2012.18
Filename :
6200061
Link To Document :
بازگشت