A Social-Aware Federated Real-Time Scheduling Algorithm for Unrelated Multiprocessor Platforms
Typ
Examensarbete för masterexamen
Master's Thesis
Master's Thesis
Program
Computer systems and networks (MPCSN), MSc
High-performance computer systems (MPHPC), MSc
High-performance computer systems (MPHPC), MSc
Publicerad
2022
Författare
Wilkins, David
Hammargren, Oskar
Modellbyggare
Tidskriftstitel
ISSN
Volymtitel
Utgivare
Sammanfattning
Real-time systems are commonly found in the modern world, ranging from aerospace control systems to health-care equipment. Real-time systems operate under strict timing constraints, meaning each program (i.e. task) must complete before a given deadline. Thus, a Real-time scheduling algorithm needs to schedule each task such that all deadlines are guaranteed to be met. Due to the sophistication of many
modern real-time applications, the workload of real-time tasks are ever increasing. This creates a demand for multiprocessor platforms that can distribute the workload among several processors. Furthermore, many multiprocessor platforms
are heterogeneous, meaning they include processors of different types that offers different capabilities to different task. This allows hardware to be specialized for
different types of tasks. An example of such a platform is the ARM’s big.LITTLE architecture, which combines high-performance processing unit with power-efficient processors.
However, scheduling real-time tasks on multiprocessors is a difficult problem. One approach to this problem is federated scheduling, which divides tasks into two categories, light or heavy. Light tasks can meet their deadline using only one processor, while heavy tasks need more than one processors to meet their deadline. Thus, federated scheduling assigns a cluster of processors to each heavy task. The light tasks are then assigned to the remaining processors. This assignment problem is an intractable problem since every possible task-to-processor assignment need to be considered in order to find the optimal solution.
The current state-of-the-art in federated scheduling on heterogeneous platforms has a limitation. Namely, each task takes its preferred processors disregarding whether these processors were critical to other tasks. We fills this gap by providing a social-aware processor assignment algorithm. This algorithm gives each processor to the tasks that needs it the most. Our social-aware processor assignment algorithm is empirically evaluated through simulation. The performance of our algorithm is compared with the current state-of-the-art. The simulation show that our social-aware algorithm performs better in most cases.
Beskrivning
Ämne/nyckelord
real-time scheduling , resource allocation , social-awareness , federated scheduling , bin-packing , heterogeneous platforms , unrelated platforms , computer science