Name
Title | ||
|---|---|---|
A Study of Utilization Bound and Run-Time Overhead for Cluster Scheduling in Multiprocessor Real-Time Systems |
Abstract | ||
|---|---|---|
Cluster scheduling, where processors are grouped into clusters and the tasks that are allocated to one cluster are scheduled by a global scheduler, has attracted attention in multiprocessor real-time systems research recently. In this paper, by adopting optimal global schedulers within each cluster, first we investigate the worstcase utilization bound for cluster scheduling. Specifically, for a system with m homogeneous clusters where each cluster has k processors, we show that the worstcase achievable system utilization is (⌊k/α⌋·m+1)/(⌊k/α⌋+1) · k, where a is the maximum utilization for the periodic tasks considered. By focusing on an efficient optimal global scheduler, namely the boundary-fair (Bfair) algorithm, we propose a period-aware partitioning heuristic aiming at reducing the scheduling overhead. Simulation results show that the percentage of task sets that can be scheduled is significantly improved under cluster scheduling even for small-size clusters (e.g., k = 2). Moreover, the proposed period-aware partitioning heuristic markedly reduces the scheduling overhead of cluster scheduling with Bfair. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1109/RTCSA.2010.15 | RTCSA |
Keywords | Field | DocType |
processor scheduling,global scheduler,utilization bound,run-time overhead,maximum utilization,multiprocessor real time systems,optimal global scheduler,period aware partitioning heuristic,homogeneous cluster,multiprocessing systems,efficient optimal global scheduler,small-size cluster,optimal global schedulers,multiprocessor real-time systems,cdot k,cluster scheduling,run time overhead,scheduling overhead,boundary fair algorithm,lfloor k,real-time systems,real time systems,schedules,scheduling algorithm,scheduling | Cluster (physics),Heuristic,Multiprocessor scheduling,Fair-share scheduling,Computer science,Scheduling (computing),Parallel computing,Real-time computing,Multiprocessing,Schedule,Periodic graph (geometry),Distributed computing | Conference |
ISSN | ISBN | Citations |
1533-2306 | 978-1-4244-8480-5 | 3 |
PageRank | References | Authors |
0.41 | 23 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Xuan Qi | 1 | 58 | 3.35 |
| Da-Kai Zhu | 2 | 1405 | 66.97 |
| Hakan Aydin | 3 | 1218 | 61.97 |