title: Techniques for Efficient Performance Analysis and Memory Optimization in Mapping Dataflow Models of Computation onto Embedded Systems
Creators: name: Letras, Martin
Publisher: name: Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU)
Year: 2024

description: The power of modern multi-core and many-core platforms is an excellent fit for meeting the performance needs of embedded software applications. However, there are many ways to map these applications to a specific multi-core or many-core architecture, leading to a large design space that requires extensive analysis. This analysis is needed to weigh the trade-offs of a set of design goals that need to be optimized. Therefore, there is a need for efficient design methods that can identify the Pareto-optimal application mappings while considering well-defined design constraints. This thesis proposes approaches to address these challenges and integrate them into SYSTEMCODESIGNER’s Electronic System Level (ESL) design flow. The contributions presented in this thesis aim to facilitate the definition of dataflow applications by combining the model-based design of dataflow applications with block diagrams in MATLAB/Simulink to define the input application for the subsequent steps of the SYSTEMCODESIGNER methodology. Additionally, Design Space Exploration (DSE) methods were proposed to accelerate the exploration of mappings of dataflow-based applications to multi-core and many-core architectures. Compared to other DSE approaches, the methods proposed in this dissertation improve the quality of the found Pareto fronts. Chapter 3 presents a framework for automatically converting periodic discrete block-based MATLAB/Simulink models into data-driven SystemC Models of Computation (SysteMoC) models. The main goal is to integrate MATLAB/Simulink as a front-end for the ESL design flow of SYSTEMCODESIGNER. The proposed conversion method offers a significant advantage over other state-of- the-art works by providing complete coverage of periodic discrete MATLAB/Simulink models that automatically generate executable program code for each generated actor without requiring an explicit library definition. This conversion method was employed to define input applications in Chapters 4 and 5 of this thesis, enabling the multi-objective DSE approaches to optimize the cost, throughput, and memory requirements of periodic discrete block diagrams. Furthermore, the proposed fully automated framework enhances productivity and reduces the risk of manual errors when coding dataflow-based actor networks. Finally, the proposed conversion method proved to be correct by reproducing the same sequence of values at each output port with the same sequence of values at each input port of the original block diagram and the corresponding SysteMoC actor network. Chapter 4 presents two methods for fast throughput evaluation to accelerate the DSE of mappings from fine-grained dataflow specifications to homogeneous Multi-Processor System-on-a-Chip (MPSoC) architectures. These approaches consider and avoid the overhead in evaluating implementations through measurement-based compilation-in-the-loop evaluations. The first approach is a fast decision tree-based throughput estimator suitable for small graphs. The second approach is a model-based throughput analysis that uses max-plus algebra to analyze large data flow graphs with hundreds of actors. Both methods use a hybrid evaluation to combine their estimation methods (decision trees and max-plus algebra analysis) with measurements on the target hardware. In this way, when comparing different Pareto points in the Pareto fronts obtained with both approaches, real throughput values are used instead of approximate values, which can be subject to estimation errors. The hybrid DSE approach uses adaptive objective functions to enable fast multi-objective exploration of the search space for throughput and cost-optimal mappings of a dataflow-based application to a multi-core architecture. Accordingly, the presented DSE uses a model-based analysis (max-plus algebra) or a decision tree-based estimator –a fast but approximate approach– for throughput evaluation in the early stages of exploration. This leads to a faster initial evaluation than performing time-consuming measurements on the target platform. To achieve high accuracy in the end of the exploration, the probability of evaluating the throughput of each candidate solution is gradually increased by measurement over the exploration time. To this end, the probability of using guidance is varied over time by performing fast but approximate throughput evaluations using model-based analysis or decision tree-based instead of expensive but highly accurate throughput measurements. In this way, the approaches presented reduce the bottleneck in the DSE evaluation loop. Chapter 5 presents a DSE approach that efficiently explores the vast design space of mapping actors and communication channels to cores and memories in a realistic many-core architecture while optimizing the quality of implementations in the quality space composed of the period, cost accounted as the number of utilized cores, and memory footprint. As a first contribution, Chapter 5 introduces the concept of Multi-Reader Buffers (MRBs) and provides a memory-efficient implementation of multi-cast actors and their replacement as a graph transformation. Rather than replicating produced tokens for all readers, an MRB stores each produced token only once, which stays alive until the last reader has consumed it. MRB replacement provides minimal buffer implementations obtained by replacing all multi-cast actors in an application with MRBs. However, replacing multi-cast actors with MRBs may increase the execution period – i.e., reduce the throughput – due to communication contention when accessing shared data. To properly examine these trade-offs, the second contribution presented in Chapter 5 proposed a multi-objective DSE approach that selectively decides the replacement of multi-cast actors with MRBs and explores actor and channel mappings to trade memory footprint, core cost, and period of schedules. It is shown that the quality of found solutions improves when selectively replacing multi-cast actors with MRBs within a range of 28 % to 90 % in solution quality measured by a hypervolume indicator when compared to approaches that always employ MRBs to reduce the memory footprint. Moreover, the third contribution of Chapter 5 of this thesis consisted of the definition and comparison of two scheduling approaches that are used to determine a periodic schedule for the actors as well as the read/write accesses to buffers for each explored design point during the DSE: First, an Integer Linear Program (ILP) formulation that delivers the exact minimum period given an application binding. This ILP formulation performs well in terms of solution times for small to mid-sized applications. The second is a fast heuristic approach named Communication-aware Periodic Scheduling on Heterogeneous Many-Cores (CAPS-HMS) that performs particularly well when tackling large applications. It has been shown that for the small and mid-sized applications used in the experiments, the proposed CAPS-HMS is only slightly inferior by 7 % in terms of hypervolume compared to the ILP. But for large applications and the complexity of the target architecture, the ILP solution times can become prohibitively long. In contrast, the fast CAPS-HMS outperforms the ILP by 67 % in hypervolume for the largest test application. In its current form, the proposed heuristic CAPS-HMS is limited in assuming a fixed priority for each task to be scheduled. As a remedy and potential future work, the DSE might also determine and optimize the priority of each task to find the best priorities. This could reduce the gap between scheduling using an exact ILP formulation and scheduling using CAPS-HMS for small applications and also further improve the quality of found solutions for mid to large-size applications.