Article Accepted in IEEE Transactions on Computers

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.

Anna Minaeva Successfully Defends Dissertation

Today, Anna Minaeva successfully defended her PhD dissertation entitled “Scalable Scheduling Algorithms for Embedded Systems with Real-Time Requirements” and earned the right to call herself a doctor. The reviewers were pleased with the dissertation and she confidently answered their questions.

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.

Article Accepted in Journal of Systems and Software

Congratulations to Anna Minaeva for having her article “Scalable and Efficient Configuration of Time-Division Multiplexed Resources” accepted in Journal of Systems and Software. The article is an extension of our conference paper “An Efficient Configuration Methodology for Time-Division Multiplexed Single Resources” that was presented at the Real-Time and Embedded Technology and Applications Symposium (RTAS) earlier this year. The original conference paper addresses the problem of configuring a Time-Division Multiplexing (TDM) arbiter that provides access to a single shared resource, such as a memory, in a way the satisfies the bandwidth and latency requirements of all memory clients. This is achieved using an optimized Integer Linear Programming (ILP) formulation.

The newly accepted article extends the problem scope to consider more complex system with a larger number of memory clients and a longer TDM frame. For large problems, the previous ILP formulation takes unpractically long to solve, which is addressed by using it as a building block in a Branch and Price framework to improve its scalability. This approach decomposes the problem into smaller sub-problems and uses more sophisticated exploration methods to navigate the search-space, enabling the number of clients to be increased by up to a factor of 8 compared to the original ILP formulation.

Temporary Contract with CISTER

My contract with Czech Technical University in Prague has run its course. However, the good people at the CISTER/INESC TEC research unit at the Polytechnic Institute of Porto, my former employer, was quick to offer me a temporary contract until a new long-term plan is in place. At my new job, I will continue my research on real-time embedded systems, just like before, as well as preparing project proposals to fund future research. I thank CISTER for the opportunity and look forward work with them again!

Paper Accepted at RTAS 2015

We just had a paper accepted at the Real-Time and Embedded Technology and Applications Symposium (RTAS) in Seattle. The paper is entitled “An Efficient Configuration Methodology for Time-Division Multiplexed Single Resources” and presents an ILP-based methodology to allocate TDM slots to resource clients, such that bandwidth and latency constraints are satisfied while resource utilization is minimized. A heuristic algorithm is furthermore proposed to determine the number of TDM slots in the schedule. This paper is a collaboration both with colleagues here at CTU Prague and with Andrew Nelson from Eindhoven University of Technology.

For the camera-ready version of the paper, please click here.

Back in Prague

I am now back from my two month research visit at Airbus Group Innovations. During my stay, I primarily worked on two things:

  1. 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.
  2. 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.

New position at Czech Technical University in Prague

Today I start a new position as a Postdoctoral Researcher in the Department of Control Engineering at the Faculty of Electrical Engineering at the Czech Technical University in Prague. More specifically, I am in the Industrial Informatics group, led by Prof. Zdenek Hanzalek. Although a new country and a new workplace implies quite a change for me, little will change for those that I collaborate with. I will still do research on real-time systems and I will continue to supervise my students in Eindhoven and Porto. However, my research direction will change slightly within the scope of real-time systems to align with the interests of my new group and to make the most of my stay here.

Invited Presentations in Northern, Southern, and Central Europe

The next two weeks involves quite a marketing effort, as I will give three invited presentations about real-time memory controllers in northern, southern, and central Europe, respectively. Tomorrow, I will present our work at the Faculty of Information Technology at Czech Technical University in Prague. On Friday, I will meet with Karl-Erik Arzen and Enrico Bini at the Department of Control at Lund’s Institute of Technology and share my story. Lastly, next week Wednesday, I present at the ReTiS Lab at Scuola Superiore Sant’Anna. I thank all these institutes for the opportunity to present and I hope they will enjoy the story.