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.
During the past two years, I have been involved with setting up the Partnership Program Mastering Complexity (MasCot), funded NWO Domain Applied and Engineering Sciences together with ESI (TNO). After a long process of defining the key topics, writing the call, and aligning with applicants, four innovative research projects have finally been granted, allocating three million euros to research on software restructuring, testing, scheduling and design of cyber-physical systems. Congratulations to Andy Pimentel,Twan Basten, Jan Tretmans, Eelco Visser, and their collaborators for the accepted projects. I am looking forward to seeing the results!
The press release announcing my appointment as Professor at the University of Amsterdam is finally ready. Time to make them and ESI (TNO) proud!
The Chair of Design Methodologies for Cyber-Physical Systems focuses on two research areas.The first area considers design methodologies for cyber-physical systems in which abstraction, provided by models used for specification, analysis, simulation, or synthesis, play an essential role. While this area applies to cyber-physical systems in general, the second area focuses on design aspects of real-time systems. Together, these two areas capture much of my existing work in both academic (TU/e, CTU Prague, CISTER) and applied research (ESI) in different application domains and industries in which I have worked, e.g. avionics (Airbus), consumer electronics (Philips & NXP), and defense (Thales). They are also broad enough to sustain a long-term effort towards managing complexity of cyber-physical systems. For more information about the research, click the ‘Research‘ button in the menu at the top of the page.
My first mission will involve developing and teaching a course on Embedded Software and Systems, a course that is extremely relevant to our work at ESI. The course is primarily aimed at students following the Master in Software Engineering and teaches the fundamentals of embedded system development. This includes modelling systems using StateCharts, Petri Nets, Data-flow graphs, and Domain-Specific Languages, embedded hardware, functional and timing verification, and design-space exploration. I will also explain the industrial reality behind some of these aspects by drawing on my experience from projects at ESI.
During the course, the students will get practical experience with model-based engineering as they work in groups to program a LEGO Mindstorm Rover using Stateflow to autonomously follow a path, while avoiding obstacles. From this batch of students, I am hoping to find some promising ones that can help us make the next innovative steps in model-based engineering for complex cyber-physical systems for their thesis project.
After six days in Munich I have now left the MODELS 2019 conference. It has been an intense couple of days with three days of workshops and tutorials, and three days of main conference. Both the technical and social aspects of the conference were exceptionally well-organized, so kudos to the men and women who worked hard to make that happen.
2. A tutorial on StateCharts that improved my understanding of a model-of-computation I will be teaching at the University of Amsterdam in the near future. Thanks to Simon van Mierlo, Hans Vangheluwe, and Axel Terfloth for organizing this tutorial and for sharing their excellent material.
3. Meeting and discussing with representatives from BMW, Daimler, MAN, Continental, TTTech, and other automotive companies and hear more about automotive trends towards centralization of computation, first through domain controllers and then further towards integration of domains in automotive “supercomputers”. It was also interesting to see that the automotive industry is showing interest in service-oriented architectures as a paradigm for their platforms. In fact, a paper entitled “Model-Based Resource Analysis and Synthesis of Service-Oriented Automotive Software Architectures” from BMW got the Best Paper Award on the Practice and Innovation track for work in this direction. This confirms our belief that our current applied research on service-oriented architectures in the defense domain can be generalized to other domains.
4. Meeting and talking to people from both Flanders Make and CETIC, which are the Flemish and Wallonian equivalents of ESI (TNO). It was interesting to talk to them and learn about how what we do is similar and different, both in terms of technical scope and business models.
I hope to return to the MODELS conference again next year to present more of our work and have another opportunity to discuss with and learn from top academics and industrialists in the area of model-based engineering.
The dissertation considers applications with real-time requirements sharing resources, such as memories, cores, and networks, in distributed systems. Scheduling this type of application subject to resource and precedence constraints, among others, while maximizing system performance is a challenging problem. Existing approaches either propose exact solutions that cannot solve industrial-sized instances or propose heuristic algorithms without validating its efficiency with optimal solutions.
The dissertation addresses this problem through a three-stage approach, corresponding to three problems with gradually increasing complexity and accuracy of the model. The four main contributions of are: 1) Comparison of three formalisms to solve the problems optimally, Integer Linear Programming (ILP), Satisfiability Modulo Theory, and Constraint Programming, along with computation time improvements. To increase the scalability of the ILP approach, an optimal approach that wraps the ILP in a branch-and-price framework is presented. 2) For each problem, a scalable and efficient heuristic algorithm is presented that decomposes the problem to decrease its computation time. 3) The efficiency of the optimal and heuristic strategies are quantitatively and qualitatively compared. 4) The practical applicability of the proposed heuristic algorithms and optimal approaches is demonstrated on case studies of real systems in both the automotive and consumer electronics domains.
I wish Anna the best of luck in her future career and hope I will have the opportunity to work with her again.
The paper describes applied research from an industrial ESI project with goal of enabling continuous evolution of software in service-oriented architectures through automatic detection and correction of service incompatibilities. Towards this, the paper has three main contributions: 1) the state-of-the-art in the areas of specification of service interfaces, and detection and correction of incompatible service interactions is surveyed, 2) directions for a methodology to detect and correct incompatible interactions that is currently under development are discussed, and 3) the methodology is discussed in the context of a simplified industrial case study from the defense domain.
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.
The goal of this work is, like many other in this research line, is to reduce cost of mixed-criticality systems. This time, we achieve this by addressing the limitation that a server only has a single execution budget in all modes, despite that their computational requirements may vary significantly. More specifically, the three main contributions of the paper are: 1) a scheduling arrangement for uni-processor systems employing fixed-priority scheduling within periodic servers, whose budgets are dynamically adjusted at run-time in the event of a mode change, 2) a new schedulability analysis for such systems, and 3) heuristic algorithms for assigning budgets to servers in different modes and ordering the execution of the servers. Experiments with synthetic task sets demonstrate considerable improvements (up to 52.8%)
The paper “Response Time Analysis of Multiframe Mixed-Criticality Systems” has been accepted at RTNS 2019. This work is the next in our mixed-criticality research line, in collaboration with my former colleagues at CISTER. It continues our work on the multi-frame task model, also considered in our RTCSA paper this year. The multi-frame model describes tasks that have different worst-case execution times for each job, following a known pattern, which can be exploited to reduce the cost of the system. Existing schedulability analyses fail to leverage this characteristic, potentially resulting in pessimism and increased system cost.
In this paper, we present a schedulability analysis for the multi-frame mixed-criticality model. Our work extends both the analysis techniques for Static Mixed-Cricality scheduling (SMC) and Adaptive Mixed-Criticality scheduling (AMC), on one hand, and the schedulability analysis for multi-frame task systems on the other. Our proposed worst-case response time (WCRT) analysis for multi-frame mixed-criticality systems is considerably less pessimistic than applying the SMC, AMC-rtb and AMC-max tests obliviously to the WCET variation patterns. Experimental evaluation with synthetic task sets demonstrates up to 63.8% higher scheduling success ratio compared to the best of the frame-oblivious tests.