Optimizing Efficiency and Performance: PhD Thesis Defense on Energy- and Time-aware Scheduling for High-Performance Embedded Systems

Yesterday, I participated in the PhD defense committee of Julius Röder, a PhD student in the Parallel Computing Systems group at the University of Amsterdam. The thesis “Energy- and Time-aware Scheduling for Heterogeneous High-Performance Embedded Systems” addresses the relevant problem of optimizing non-functional behavior, such as timing and energy consumption, of heterogeneous high-performance embedded systems. The goal of this optimization Is to reduce energy consumption, thereby also reducing carbon footprint and extending battery-life, as well as ensuring that real-time requirements of applications are satisfied, even at high resource utilizations. To this end, the thesis contributes a discussion on setups used for energy measurements, as well as experiments and a statistical analysis that demonstrate the Importance of sampling frequency on the accuracy of such measurements. The bulk of the thesis proposes heuristic algorithms, both conventional and based on reinforcement learning, for mapping and scheduling applications modelled as directed acyclic graphs (DAG) on heterogeneous platforms. The applications are assumed to be available In different versions, with different non-functional behavior, for the different types of processing elements In the heterogeneous architecture, which enables trade-offs between timing and energy. A key strength of the thesis is that theory is combined with a practical component; the scheduling algorithms are implemented and evaluated on a heterogeneous multi-core systems, where timing and energy behavior are carefully measured and analyzed.

In presence of family, friends, and colleagues, Julius confidently defended his PhD thesis and earned the right to call himself a doctor. Congratulations Julius with this great achievement!

Another Article in Real-time Systems Journal

An article entitled “Response Time Analysis of Multiframe Mixed-Criticality Systems with Arbitrary Deadlines” has been accepted for publication in Real-time Systems journal. This work is first authored by Ishfaq Hussain and is another collaboration with my former colleagues at CISTER. The article extends our RTNS 2019 paper “Response Time Analysis of Multiframe Mixed-Criticality Systems” that received both an Outstanding Paper Award and a Best Student Paper Award. The RTNS paper presented a schedulability analysis for the multi-frame mixed-criticality model, extending the static and dynamic analysis techniques for mixed-criticality scheduling and the schedulability analysis for multi-frame task systems.

The accepted journal article extends the RTNS paper by generalizing the proposed schedulability analyses from a constrained-deadline task model to the more general, but also more complex, model with arbitrary deadlines. The corresponding optimal priority assignment for our schedulability analysis is also identified. In experiments with synthetic workloads, the proposed analyses are compared in terms of scheduling success ratio, against the frame-agnostic analyses for the corresponding variants of the Vestal model.

Paper Accepted at GPCE 2020

A paper entitled “PReGO: a Generative Methodology for Satisfying Real-Time Requirements on COTS-based Systems – Definition and Experience Report” was accepted for publication at the 19th International Conference on Generative Programming: Concepts & Experiences (GPCE). This is my first paper in collaboration with my new colleagues at the University of Amsterdam, and it describes work done in the TeamPlay project, a three-year research project funded by the EU Horizon 2020 research and innovation programme.

The paper addresses the problem of satisfying real-time requirements in industrial systems using unpredictable hardware and software, which limit or entirely prevent the application of established real-time analysis techniques. To this end, we propose PReGO, a generative methodology for satisfying real-time requirements in industrial commercial-off-the-shelf (COTS) systems. We report on our experience in applying PReGO to a use-case: a Search & Rescue application running on a fixed-wing drone with COTS components, including an NVIDIA Jetson board and a stock Ubuntu/Linux. We empirically evaluate the impact of each integration step and demonstrate the effectiveness of our methodology in meeting real-time application requirements in terms of deadline misses and energy consumption.

Journal Article Presented at ECRTS 2019

Today, Ali presented our Real-time Systems article “Uneven Memory Regulation for Scheduling IMA Applications on Multi-core Platforms” in the Journal-to-conference (J2C) session at ECRTS.

This article addresses the problem of resource sharing in mixed-criticality systems through temporal isolation by extending the state-of-the-art Single-Core Equivalence (SCE) framework in three ways: 1) we extend the theoretical toolkit for the SCE framework by considering EDF and server-based scheduling, instead of partitioned fixed-priority scheduling, 2) we support uneven memory access budgets on a per-server basis, rather than just on a per-core basis, and 3) we formulate an Integer-Linear Programming Model (ILP) guaranteed to find a feasible mapping of a given set of servers to processors, including their execution time and memory access budgets, if such a mapping exists. Our experiments with synthetic task sets confirm that considerable improvement in schedulability can result from the use of per-server memory access budgets under the SCE framework.

Overall, I greatly appreciate that key conferences in the real-time community are starting to allow journal articles to be presented. This increases the exposure of these works that are often longer and better edited. It is also helpful for researchers at the institutes where conference publications are not considered a relevant KPI. You can argue the validity of this reasoning in areas of computer science where conferences are highly competitive with 20-30% acceptance rates, but it is reality for some researchers. An interesting thing with the MODELS conference is that they collaborate with the SOSYM journal such that some accepted articles in the journal gets a full slot at the conference. This is a nice way to highlight good articles and to appreciate the work done by both authors and reviewers.

Paper Accepted at DATE 2018

Another paper written with my former colleagues at CISTER has been accepted. The paper is entitled “Mixed-criticality Scheduling with Memory Bandwith Regulation” and appear at DATE 2018. The paper considers the problem that existing schedulability analyses for mixed-criticality multi-core systems do not consider task interference in shared platform resources, such as memories, potentially making them optimistic and unsafe. We address this issue by formulating a schedulability analysis for mixed-criticality fixed-priority-scheduled multi-core systems using per-core memory access regulation. We also propose multiple heuristics for memory bandwidth allocation and task-to-core assignment. The analysis and heuristics are implemented in a tool and evaluated through extensive experiments.

Article Accepted in IEEE Transactions on Computers

Anna Minaeva had an article entitled “Time-Triggered Co-Scheduling of Computation and Communication with Jitter Requirements” accepted in IEEE Transactions on Computers. The article considers the problem of efficiently co-scheduling task execution and communication in multi-core automotive platforms. Most existing works typically deal with zero-jitter scheduling, which results in lower resource utilization, but has lower memory requirements. In contrast, this article focuses on jitter-constrained scheduling that puts constraints on the tasks jitter, increasing schedulability over zero-jitter scheduling.

The contributions of this article are: 1) Integer Linear Programming and Satisfiability Modulo Theory model exploiting problem-specific information to reduce the formulations complexity to schedule small applications. 2) A heuristic approach, employing three levels of scheduling scaling to real-world use-cases with 10000 tasks and messages. 3) An experimental evaluation of the proposed approaches on a case-study and on synthetic data sets showing the efficiency of both zero-jitter and jitter-constrained scheduling. It shows that up to 28% higher resource utilization can be achieved by having up to 10 times longer computation time with relaxed jitter requirements.

Paper Accepted at ECRTS 2017

Our paper “Mixed-criticality Scheduling with Dynamic Redistribution of Shared Cache” has been accepted at ECRTS 2017, marking the end of yet another succesful collaboration with my former colleagues at CISTER. The paper proposes an extension of Vestal’s model for mixed-criticality multi-core systems that 1) accounts for the per-task partitioning of the last-level cache, and 2) supports dynamic reassignment of cache portions initially reserved for lower-criticality tasks to the higher-criticality tasks when switching to high-criticality mode. A schedulability analysis based on partitioned EDF is presented that is aware of the cache resources assigned to each task and leverages the dynamic reconfiguration to improve schedulability. We also propose heuristics for partitioning the cache in low- and high-criticality mode. Experimental result indicate tangible improvements in schedulability compared to a baseline cache-aware arrangement where there is no redistribution of cache resources from low- to high-criticality tasks in the event of a mode change.

Two Papers Accepted at ECRTS 2016!

Two papers have been accepted for presentation at the 28th Euromicro Conference on Real-Time Systems (ECRTS 2016) in Toulouse, France. The first paper is entitled “Cache-Persistence-Aware Response-Time Analysis for Fixed-Priority Preemptive Systems” as is a collaboration with Syed Aftab Rashid, Geoffrey Nelissen, and Eduardo Tovar from CISTER and Damien Hardy and Isabelle Puaut from University of Rennes. This paper presents a WCRT analysis for single-core fixed-priority preemptive systems that exploits persistent cache blocks that are known to be in the cache to reduce WCRT.

The title of the second paper is “Contention-Free Execution of Automotive Applications on a Clustered Many-Core Platform” that was written together with Borislav Nikolic and Vincent Nelis from CISTER, Matthias Becker and Thomas Nolte from MRTC, and Dakshina Dasari from Bosch. This work presents a contention-free execution framework for automotive applications on many-core platforms, which combines privatization of memory banks together with defined access phases to shared memory resources. An Integer Linear Programming (ILP) formulation is presented to find the optimal time-triggered schedule for execution as well as for accesses to shared memory. Additionally, a heuristic solution is presented that generates the schedule in a fraction of the time required by the ILP.

Accepted Article about Dynamic Command Scheduling in Real-Time Systems Journal

Today, we congratulate Yonghui Li on his first accepted journal article. The article is entitled “Architecture and Analysis of a Dynamically-Scheduled Real-Time Memory Controller” and has been accepted in the Real-Time Systems journal. The work extends his paper “Dynamic Command Scheduling for Real-Time Memory Controllers” that was presented at ECRTS 2014. The previous conference paper introduced a back-end architecture and scheduling algorithm for a dynamically scheduled SDRAM controller supporting variable transaction sizes and different degrees of bank interleaving. The properties of the back-end was extensively analyzed and worst-case execution times (WCET) of scheduled transactions was derived using two different methods with varying complexity and accuracy.

The newly accepted article extends this work by proposing a corresponding memory controller front-end, along with a complete response time analysis for memory transactions of variable sizes. A key feature of the front-end is that it features a non-work-conserving TDM arbiter, which provides static information about the order in which transactions of different sizes are scheduled, allowing the response time analysis to leverage the flexible WCET analysis of the back-end to provide tighter bounds. In addition, it is shown in which order memory clients with different request sizes should be served to minimize the total response time. The results demonstrate that dynamic command scheduling significantly outperforms our semi-static (pattern-based) approach in the average case, while it performs equally well or better in the worst-case with only a few exceptions.

RTMemController v1.0 Released

The Memory Team is proud to release another open-source tool to the community. This tool is called RTMemController and contains a mathematical formalization of the dynamic command scheduler introduced in Yonghui Li’s paper Dynamic Command Scheduling for Real-Time Memory Controllers that will be presented at ECRTS. The tool is capable of determining worst-case and average-case execution times of memory transactions of different transaction sizes and with varying degrees of bank interleaving.

An important driver for releasing this tool is to promote transparency and fair comparisons between work in the field. Longer term development plans for the tool may involve adding support for a memory controller front-end with different transaction schedulers, adding support for more memory generations (currently DDR3 is supported), and making the output compatible with DRAMPower to enable chaining the tools.

The official website of RTMemController is found here. Also check out the paper that describes the scheduling algorithm and its formalization.