Anna Minaeva, who recently received her PhD degree, just had a journal article entitled “Efficient Heuristic and Exact Approach for Control Performance Optimization in Time-Triggered Periodic Scheduling” accepted for publication in IEEE Transactions on Computers. This article is the result of a HiPEAC collaboration grant that Anna was awarded back in 2016 to visit the group of Samarjit Chakraborty at TU Munich. I am very happy to see that this grant resulted in a joint publication in a prestigious journal and hope to collaborate with Samarjit again in the future.
The article addresses the problem of generating a time-triggered schedule for a number of independently developed automotive applications on a number of shared resources, such that their control performance only suffers minimal degradation. The three main contributions are: 1) a constraint programming model that solves the problem optimally, exploiting properties of the problem to reduce the computation time; 2) a fast heuristic called Flexi that only has a minor impact on the optimality of the solution; and 3) an experimental evaluation of the scalability and efficiency of the proposed approaches on a case study, in addition to several synthetic datasets. The results show that the heuristic provides a solution on average 5 times faster, finding a feasible solution in 31% more problem instances than the optimal approach within a time limit, while only sacrificing 0.5% of the control performance quality for the largest dataset.
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.
A paper “Memory Bandwidth Regulation for Multiframe Task Sets” has been accepted at RTCSA 2018. This paper aims to reduce cost of real-time systems where the worst-case execution times of tasks vary from job to job, according to known patterns. This kind of execution behavior can be captured by the multi-frame task model. However, this model is optimistic and unsafe for multi-cores with shared memory controllers, since it ignores memory contention, and existing approaches to stall analysis based on memory regulation are very pessimistic if straight-forwardly applied.
This paper remedies this by adapting existing stall analyses for memory-regulated systems to the multi-frame model. Experimental evaluations with synthetic task sets show up to 85% higher scheduling success ratio for our analysis, compared to the frame-agnostic analysis, enabling higher platform utilization without compromising safety. We also explore implementation aspects, such as how to speed up the analysis and how to trade off accuracy with tractability.
We celebrate the acceptance of our paper “Mixed-criticality Scheduling with Dynamic Memory Bandwidth Regulation” at RTCSA. This paper is the next step in my research collaboration with CISTER on mixed-criticality systems.
The paper aims to safely reduce the cost of mixed-criticality multi-core systems by addressing inefficient usage of memory bandwidth. This is achieved by combining per-core memory access regulation with the well-established Vestal model, which improves on the state-of-the-art in two respects: 1) We allow the memory access budgets of the cores to be dynamically adjusted, when the system undergoes a mode change, reflecting the different needs in each mode, for better schedulability. 2) We devise memory regulation-aware and stall-aware schedulability analysis for such systems, based on AMC-max. By comparison, the state-of-the-art offered no option of dynamic adjustment of core budgets, and only offered regulation-aware schedulability analysis based on AMC-rtb, which is inherently more pessimistic. Finally, 3) we consider different task assignment and bandwidth allocation heuristics, to assess the improvement from the dynamic memory budgets and new analysis. Our results show improvements in schedulability ratio of up to 9.1% over the state-of-the-art.
We are pleased to announce that our paper “Worst-case Stall Analysis for Multicore Architectures with Two Memory Controllers” has been accepted at ECRTS 2018. This paper represents another successful collaboration with my former colleagues from CISTER.
The paper addresses the problem that increasing bandwidth requirements have resulted in platform architectures with multiple memory controllers, for which existing analyses to compute worst-case memory stall time are not safe. This work presents a new worst-case memory stall analysis for a memory-regulated multi-core architecture with two memory controllers. This stall analysis can be integrated into the schedulability analysis of systems under fixed-priority partitioned scheduling. Five heuristics for assigning tasks and memory budgets to cores in a stall-cognisant manner are also proposed. We experimentally quantify the cost in terms of extra stall for letting all cores benefit from the memory space offered by both controllers, and also evaluate the five heuristics for different system characteristics.
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.
Two articles that were submitted to a Journal of Systems Architecture Special Issue on High-performance and Real-time Embedded Systems have now appeared online. The first article is called “T-CREST: Time-predictable Multi-Core Architecture for Embedded Systems” and summarizes the work done in the recently concluded FP7 STREP project T-CREST, where me and my students worked on time-predictable memory controllers.
The second article is entitled “Dataflow Formalisation of Real-Time Streaming Applications on a Composable and Predictable Multi-Processor SOC” and shows how data-flow graphs can be used to model streaming applications mapped to the CompSoc platform and predict its minimum throughput. The basic idea is to start from a data-flow graph of the application and add additional nodes and edges that capture the mapping and timing behavior of all hardware components software libraries, and schedulers in the system. The approach is verified by comparing the predicted performance to the actual performance of an application executing on a CompSoc instance on an FPGA. The article clearly demonstrates the potential of modeling systems in which the behavior of all hardware and software components are known.
I have recently accepted an invitation to speak at the First TCRTS Workshop on Certifiable Multicore Avionics Systems (CMAS), which takes place on April 13 and is co-located with RTAS 2015 in Seattle. The presentation is made in collaboration with Jan Nowotsch at Airbus Group Innovations, where I was a Visiting Researcher during two months last year. The title of the presentation is Towards Certifiable Resource Sharing in Safety-Critical Multi-Core Real-Time Systems and discusses current problems and state-of-the-art methods for resource sharing in real-time multi-core platforms. The abstract of the presentation is found below:
The proliferation of multi-core platforms has had great impact on embedded computing. Multiple cores exploiting task-level parallelism offer performance far beyond what is possible with a single core, while staying within an acceptable power envelope. Since resources, such as interconnect and memories, are often shared between cores, the platforms have also become increasingly cost efficient. However, resource sharing results in interference between concurrently executing applications, which causes problems in real-time systems where such interference must be either bounded or completely eliminated. As a result, safety-critical systems, for example in the avionics domain, have not yet been able to capitalize on the benefits of multi-core platforms due to stringent certification requirements.
This presentation discusses the state-of-the-art in resource sharing in multi-core systems and its application to safety-critical real-time systems. First, a survey of efforts to build time-predictable resources, such as interconnects and memory controllers, is provided. Then, software-based interference mitigation mechanisms and analyses for these resources in commercial-of-the-shelf platforms are discussed. This is followed by an overview of the approach proposed by Airbus Group Innovations to manage interference and compute worst-case execution times of applications running on a Freescale P4080 multi-core platform. The presentation is concluded by highlighting open issues and future directions towards certifiable resource sharing in safety-critical multi-core real-time systems.
Update: The slides are available here.
I am now back from my two month research visit at Airbus Group Innovations. During my stay, I primarily worked on two things:
- Performance analysis of memory accesses in two COTS multi-core platforms. My work extended existing analysis to include the configuration of the memory controller. In particular, the existing setup was improved to enable evaluation of rank-level parallelism within a memory controller, channel parallelism between memory controllers, and different mapping options of cores to memory channels.
- I familiarized myself with the certification process for the avionics domain by reading and discussing key standardization documents, e.g. DO-178C for software certification, DO-254 for hardware certification, and DO-297 for integrated modular avionics. I also read several position papers from the Certification Authorities Software Team, most importantly about partitioning guidelines and certification of dual-core platforms. Lastly, I read the ARINC 653 standard, which details the application interface commonly used in avionics systems.
Thanks to Jan Nowotsch and Stefan Schneele for making the visit possible and to my office mates for providing a fun environment to work and learn in.
Today, I start a two month stay as Visiting Researcher at Airbus Group Innovations in Ottobrunn, Germany. I will be working together with Jan Nowotsch on topics related to performance analysis of memory accesses in COTS multi-core platforms. During my stay, I look forward to meeting new people learning more about real-time systems in the avionics domain.