A Social-Aware Federated Real-Time Scheduling Algorithm for Unrelated Multiprocessor Platforms

dc.contributor.authorWilkins, David
dc.contributor.authorHammargren, Oskar
dc.contributor.departmentChalmers tekniska högskola / Institutionen för data och informationstekniksv
dc.contributor.departmentChalmers University of Technology / Department of Computer Science and Engineeringen
dc.contributor.examinerJonsson, Jan
dc.contributor.supervisorPathan, Risat
dc.description.abstractReal-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.
dc.subjectreal-time scheduling
dc.subjectresource allocation
dc.subjectfederated scheduling
dc.subjectheterogeneous platforms
dc.subjectunrelated platforms
dc.subjectcomputer science
dc.titleA Social-Aware Federated Real-Time Scheduling Algorithm for Unrelated Multiprocessor Platforms
dc.type.degreeExamensarbete för masterexamensv
dc.type.degreeMaster's Thesisen
local.programmeComputer systems and networks (MPCSN), MSc
local.programmeHigh-performance computer systems (MPHPC), MSc
Ladda ner
Original bundle
Visar 1 - 1 av 1
Bild (thumbnail)
CSE 22-70 Wilkins Hammargren.pdf
1.54 MB
Adobe Portable Document Format
License bundle
Visar 1 - 1 av 1
Bild (thumbnail)
1.64 KB
Item-specific license agreed upon to submission