Balancing parallelism and time predictability for scheduling of real-time parallel tasks on multiprocessors
| dc.contributor.author | Paulsson, Amanda | |
| dc.contributor.department | Chalmers tekniska högskola / Institutionen för data och informationsteknik | sv |
| dc.contributor.department | Chalmers University of Technology / Department of Computer Science and Engineering | en |
| dc.contributor.examiner | Jonsson, Jan | |
| dc.contributor.supervisor | Pathan, Risat | |
| dc.date.accessioned | 2023-12-20T07:20:53Z | |
| dc.date.available | 2023-12-20T07:20:53Z | |
| dc.date.issued | 2023 | |
| dc.date.submitted | 2023 | |
| dc.description.abstract | As 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.coursecode | DATX05 | |
| dc.identifier.uri | http://hdl.handle.net/20.500.12380/307446 | |
| dc.language.iso | eng | |
| dc.setspec.uppsok | Technology | |
| dc.title | Balancing parallelism and time predictability for scheduling of real-time parallel tasks on multiprocessors | |
| dc.type.degree | Examensarbete för masterexamen | sv |
| dc.type.degree | Master's Thesis | en |
| dc.type.uppsok | H | |
| local.programme | Computer systems and networks (MPCSN), MSc |