Analysis of task scheduling for multi-core embedded systems

Abstract: This thesis performs a research on scheduling algorithms for parallel applications.The main focus is their usage on multi-core embedded systems’ applications.A parallel application can be described by a directed acyclic graph.A directed acyclic graph is a mathematical model that represents the parallelapplication as a set of nodes or tasks and a set of edges or communicationmessages between nodes.In this thesis scheduling is limited to the management of multiple coreson a multi-core platform for the execution of application tasks. Tasks aremapped onto the cores and their start times are determined afterwards. Atoolchain is implemented to develop and schedule parallel applications on aEpiphany E16 developing board, which is a low-cost board with a 16 core chipcalled Epiphany. The toolchain is limited to the usage of offline schedulingalgorithms which compute a schedule before running the application.The programmer has to draw a directed acyclic graph with the main attributesof the application. The toolchain then generates the code for the targetwhich automatically handles the inter-task communication. Some metrics areestablished to help evaluate the performance of applications on the target platform,such as the execution time and the energy consumption. Measurementson the Epiphany E16 developing board are performed to estimate the energyconsumption of the multi-core chip as a function of the number of idle cores.A set of 12 directed acyclic graphs are used to verify that the toolchainworks correctly. They cover different aspects: join nodes, fork nodes, morethan one entry node, more than one exit node, different tasks weights anddifferent communication costs.A use case is given, the development of a brake-by-wire demonstrationplatform. The platform aims to use the Epiphany board. Three experimentsare performed to analyze the performance of parallel computing for the usecase. Three brake-by-wire applications are implemented, one for a single coresystem and two for a multi-core system. The parallel application scheduledwith a list-based algorithm requires 266% more time and 1346% more energythan the serial application. The parallel application scheduled with a taskduplication algorithm requires 46% less time and 134% more energy than theserial application.The toolchain system has proven to be a useful tool for developing parallelapplications since it automatically handles the inter-task communication.However, future work can be done to automatize the decomposition of serialapplications from the source code. The conclusion is that this communicationsystem is suitable for coarse granularity, where the communication overheaddoes not affect so much. Task duplication is better to use for fine granularitysince inter-core communication is avoided by doing extra computations.