Balancing parallelism and time predictability for scheduling of real-time parallel tasks on multiprocessors

dc.contributor.authorPaulsson, Amanda
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.date.accessioned2023-12-20T07:20:53Z
dc.date.available2023-12-20T07:20:53Z
dc.date.issued2023
dc.date.submitted2023
dc.description.abstractAs technology has advanced, real-time systems have become more common. An essential part of real-time systems is that each computational component, referred to as a task, must finish executing within a time frame, a deadline. Due to the importance of deadlines being met, scheduling tasks is crucial in real-time systems. As the demand for these systems has increased and the programs have become more advanced, a need for more computational capacity has arisen. This is because the research area of real-time systems has expanded to multiprocessor systems, with parallel execution of tasks-based applications. One of the challenges with scheduling task sets on multiprocessor systems is to find the upper-bound on the entire execution time of the parallel application. This is a challenge because different ordering of the same set of parallel tasks, on the same system, can result in different end-to-end completion time of the application. An example of this is when a task finishes executing before its worst-case execution time, resulting in a different scheduling order of the following tasks. A reordering that leads to a longer total execution time of the program is called a timing anomaly. The state-of-the-art solutions work around timing anomalies by introducing pessimism to the upper-bound calculations, causing some task sets to be deemed unschedulable although they are schedulable. The pessimism is largely due to the fact that the internal structure of the task sets is not considered, and the dependencies between the tasks are not evaluated. This thesis aims to eliminate timing anomalies by introducing additional dependencies, called dispatch constraints, between tasks. Such additional dependencies would remove unpredictability when scheduling and therefore also the need for pessimism when calculating the execution time. The goal is for these additional dependencies to limit the number of ways the parallel tasks can be scheduled (i.e. limit the level of parallelism), while simultaneously utilizing as much of the multiprocessor resources as possible. To find the balance between restricting the level of parallelism and utilizing the computational power a heuristic method will be used for selecting the source and destination tasks to which the dispatch constraints will be added. The heuristics developed for this are evaluated and compared with the state-of-the-art.
dc.identifier.coursecodeDATX05
dc.identifier.urihttp://hdl.handle.net/20.500.12380/307446
dc.language.isoeng
dc.setspec.uppsokTechnology
dc.titleBalancing parallelism and time predictability for scheduling of real-time parallel tasks on multiprocessors
dc.type.degreeExamensarbete för masterexamensv
dc.type.degreeMaster's Thesisen
dc.type.uppsokH
local.programmeComputer systems and networks (MPCSN), MSc
Ladda ner
Original bundle
Visar 1 - 1 av 1
Hämtar...
Bild (thumbnail)
Namn:
CSE 23-96 AP.pdf
Storlek:
1.38 MB
Format:
Adobe Portable Document Format
Beskrivning:
License bundle
Visar 1 - 1 av 1
Hämtar...
Bild (thumbnail)
Namn:
license.txt
Storlek:
2.35 KB
Format:
Item-specific license agreed upon to submission
Beskrivning: