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.

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.

Memory Team has Two Papers Accepted at DATE 2015

The notifications from the DATE conference are in and the Memory Team scores 2 out of 2, just like in 2014. The first paper entitled “A Generic, Scalable and Globally Arbitrated Memory Tree for Shared DRAM Access in Real-Time Systems” was first-authored by Manil and is a collaboration with Jamie Garside and Neil Audsley from University of York. The paper proposes a memory interconnect for shared memory architectures in many-core systems. A main architectural feature is that the interconnect is heavily pipelined enabling it to be synthesized at high frequencies even with a large number of clients. Another highlight is that it has global arbitration that can be programmed to behave like several different arbitration mechanisms, such as TDM, CCSP and FBSP.

The second paper “Retention Time Measurements and Modelling of Bit Error Rates of WIDE I/O DRAM in MPSoCs”was first-authored by our colleagues at Kaiserslautern University of Technology in collaboration with Sven Goossens from our Memory Team. This paper looks into the thermal behavior of 3D-stacked WIDE I/O DRAM and compares its impact on retention time and bit error rates to conventional 2D DRAM chips.

Accepted Paper at CODES/ISSS 2013

Our paper “A Reconfigurable Real-Time SDRAM Controller for Mixed Time-Criticality Systems” has been accepted at CODES/ISSS 2013. The paper is first-authored by Sven Goossens and builds on the work of Jasper Kuijsten, a graduated master student from the Memory Team. In this paper, we present a new architecture of our real-time memory controller that supports predictable and composable run-time reconfiguration on use-case transitions, which allows trade-offs between guaranteed bandwidth, response time and power. It also presents a methodology for offering composable service to memory clients by means of composable memory patterns, an extension to our existing pattern-based approach. Lastly, a reconfigurable Time-Division Multiplexing (TDM) arbiter and an associated reconfiguration protocol are proposed. The TDM slot allocations can be changed at run time, while the predictable and composable performance guarantees offered to active memory clients are unaffected by the reconfiguration. The SDRAM controller has been implemented as a TLM-level SystemC model, and in synthesizable VHDL for use on an FPGA platform.