Tag: resource sharing

Article Accepted in IEEE Transactions on Computers

Posted on by bennyakesson

Anna Minaeva, who recently received her PhD degree, just had a journal article entitled “Control Performance Optimization for Application Integration on Automotive Architectures” 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

Posted on by bennyakesson

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.

Invited Presentation at CMAS 2015

Posted on by bennyakesson

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.

Paper Accepted at RTAS 2015

Posted on by bennyakesson

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.

Paper Accepted at DSD 2013

Posted on by bennyakesson

Sahar Foroutan had a paper entitled “A General Framework for Average-Case Performance Analysis of Shared Resources” accepted at DSD 2013. This paper is a result of her six month collaboration visit in Eindhoven last year. The two main contributions of the paper are: 1) a general model for resource sharing based on queuing theory that can be used with different arbiters and that captures architectural features of the shared resource, such as pipelining and arbitration delay, and 2) three arbiter models for time-division multiplexing, static-priority arbitration, and round-robin, respectively, that assume general distributions (G/G/1) and fits within the framework.

Successful Collaboration Lands Paper at PADL 2013

Posted on by bennyakesson

Another successful collaboration has resulted in an accepted publication at the Fifteenth International Symposium on Practical Aspects of Declarative Languages (PADL). The title of the paper is “A Declarative Compositional Timing Analysis for Multicores Using the Latency-Rate Abstraction” and it was written together with Vitor Rodrigues, Simão Melo de Sousa, and Mário Florido from Universidade do Porto and Universidade da Beira Interior. The paper discusses the theory and declarative implementation of timing analysis for multi-cores using abstract interpretation. To manage the state-space explosion of possible interleavings of requests from different cores to shared resources, the latency-rate abstraction is proposed and proven to be sound in the context of the proposed analysis. The resulting loss of precision is then evaluated for a simple system where a memory is shared using TDM arbitration.