Analysis of task scheduling for multi-coreembedded 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 parallel application as a set of nodes or tasks and a set of edges or communication messages between nodes. In this thesis scheduling is limited to the management of multiple cores on a multi-core platform for the execution of application tasks. Tasks are mapped onto the cores and their start times are determined afterwards. A toolchain is implemented to develop and schedule parallel applications on a Epiphany E16 developing board, which is a low-cost board with a 16 core chip called Epiphany. The toolchain is limited to the usage of offline scheduling algorithms which compute a schedule before running the application. The programmer has to draw a directed acyclic graph with the main attributes of the application. The toolchain then generates the code for the target which automatically handles the inter-task communication. Some metrics are established to help evaluate the performance of applications on the target platform, such as the execution time and the energy consumption. Measurements on the Epiphany E16 developing board are performed to estimate the energy consumption 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 toolchain works correctly. They cover different aspects: join nodes, fork nodes, more than one entry node, more than one exit node, different tasks weights and different communication costs. A use case is given, the development of a brake-by-wire demonstration platform. The platform aims to use the Epiphany board. Three experiments are performed to analyze the performance of parallel computing for the use case. Three brake-by-wire applications are implemented, one for a single core system and two for a multi-core system. The parallel application scheduled with a list-based algorithm requires 266% more time and 1346% more energy than the serial application. The parallel application scheduled with a task duplication algorithm requires 46% less time and 134% more energy than the serial application. The toolchain system has proven to be a useful tool for developing parallel applications since it automatically handles the inter-task communication. However, future work can be done to automatize the decomposition of serial applications from the source code. The conclusion is that this communication system is suitable for coarse granularity, where the communication overhead does not affect so much. Task duplication is better to use for fine granularity since inter-core communication is avoided by doing extra computations.