Paper about Data-Flow Modeling of Memory Controllers at ESTIMEDIA

Yonghui Li is having a good month. Last week he was notified that his journal article was accepted by the Real-Time Systems journal. This week, his paper “Mode-Controlled Data-Flow Modeling of Real-Time Memory Controllers” was accepted for presentation at the 13th IEEE Symposium on Embedded Systems for Real-Time Multimedia (ESTIMedia), a symposium that is a part of the Embedded Systems week in Amsterdam.

The paper is a collaboration with Orlando Moreira (previously with ST-Ericsson, currently with Intel) and his PhD students and continues Yonghui’s work on design and analysis of dynamically scheduled memory controllers. This work presents a mode-controlled data-flow model of the memory controller, which is used to derive bounds on the worst-case bandwidth for requests with variable sizes. An important difference with Yonghui’s earlier work is that this paper extends an existing model of computation to capture the memory controller and uses existing tools to do the analysis. This contrasts to his previous work where the analysis was done from scratch and required a lot of manual proofs. Examining this trade-off between modeling and analysis effort and quality of the results is a red thread through all of Yonghui’s work and is expected to be the main topic of his thesis.

Accepted Article about Dynamic Command Scheduling in Real-Time Systems Journal

Today, we congratulate Yonghui Li on his first accepted journal article. The article is entitled “Architecture and Analysis of a Dynamically-Scheduled Real-Time Memory Controller” and has been accepted in the Real-Time Systems journal. The work extends his paper “Dynamic Command Scheduling for Real-Time Memory Controllers” that was presented at ECRTS 2014. The previous conference paper introduced a back-end architecture and scheduling algorithm for a dynamically scheduled SDRAM controller supporting variable transaction sizes and different degrees of bank interleaving. The properties of the back-end was extensively analyzed and worst-case execution times (WCET) of scheduled transactions was derived using two different methods with varying complexity and accuracy.

The newly accepted article extends this work by proposing a corresponding memory controller front-end, along with a complete response time analysis for memory transactions of variable sizes. A key feature of the front-end is that it features a non-work-conserving TDM arbiter, which provides static information about the order in which transactions of different sizes are scheduled, allowing the response time analysis to leverage the flexible WCET analysis of the back-end to provide tighter bounds. In addition, it is shown in which order memory clients with different request sizes should be served to minimize the total response time. The results demonstrate that dynamic command scheduling significantly outperforms our semi-static (pattern-based) approach in the average case, while it performs equally well or better in the worst-case with only a few exceptions.

Article Accepted in IEEE Transactions on Computer

The spree of accepted journal articles continues as Sven Goossens’ article entitled “Power/Performance Trade-offs in Real-Time SDRAM Command Scheduling” was accepted for publication in IEEE Transactions on Computers. The article contains a detailed discussion about the trade-offs between bandwidth, execution time, and power when DRAM requests are scheduled by a real-time memory controller under a close-page policy. The results cover a wide range of memories ranging from DDR2/3/4 to LPDDR1/2/3 for different request sizes and amounts of bank parallelism. Other key contributions of the article are: 1) publicly available heuristic and optimal algorithms for generation of memory patters that covers all aforementioned memories, 2) a simple abstraction that quickly captures the differences between the different DRAM generations allowing algorithms and analyses to be easily adapted to cover all of them, and 3) a pairwise bank-group interleaving scheme for DDR4 that exploits bank grouping for improved performance.

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!

Article Accepted in Science of Computer Programming

The past two months have been very good to us with five journal articles being accepted in something resembling a ketchup-effect. The most recent addition is an article entitled “Certifying Execution Time in Multicores” that was accepted by the Elsevier journal Science of Computer Programming. In essence, this article is a summary of the PhD dissertation of Vitor Rodrigues, whom I collaborated with over the past years. My main contribution to this work is proposing the latency-rate model as an abstraction of the service provided by a shared resource, such as a memory. We incorporated this model into Vitors timing analysis tool based on abstract interpretation to enable scalable timing analysis of multi-core platforms with shared resources.

ACM TECS Accepts Another Journal Article

ACM Transaction of Embedded Computing Systems (TECS) recently informed us that our article “Maximizing the Number of Good Dies for Streaming Applications in NoC-based MPSoCs under Process Variation” has been accepted for publication. This work nicely summarizes the dissertation of Davit Mirzoyan from his four year PhD studies at Delft University of Technology under the supervision of Kees Goossens and myself.

The article addresses design of real-time systems for streaming applications constrained by a throughput requirement with reduced design margins, referred to as better than worst-case design. The first contribution is a complete modeling framework that captures a streaming application mapped to a NoC-based multiprocessor system with voltage-frequency islands under process-induced die-to-die and within-die frequency variations. The framework is used to analyze the impact of variations in the frequency of hardware components on application throughput at the system level. The second contribution is a methodology to use the proposed framework and estimate the impact of reducing circuit design margins on the number of good dies that satisfy the throughput requirement of a real-time streaming application. It is shown on both synthetic and real applications that the proposed design approach can increase the number of good dies by up to 9.6% and 18.8% for designs with and without fixed SRAM and IO blocks, respectively.

Article Accepted in Real-Time Systems Journal

A journal article entitled “A Framework for Memory Contention Analysis in Multi-Core Platforms” has been accepted for publication in Real-Time Systems. This article is a collaboration with Dakshina Dasari and Vincent Nelis and is a result from the time I spent with the CISTER-ISEP Research Unit in Porto.

The article proposes a unified framework to bound memory interference in multi-core platforms for a variety of different arbiters, such as time-division multiplexing (TDM), fixed priority, and an unspecified work-conserving arbiter. Our framework clearly demarcates the arbiter-dependent and independent stages in the analysis of interference. The arbiter-dependent phase takes the arbiter and the task memory-traffic pattern as inputs and produces a model of the availability of the bus to a given task. Then, based on the availability of the bus, the arbiter-independent phase determines the worst-case request-release scenario that maximizes the interference experienced by the tasks due to memory contention. We experimentally evaluate the quality of the analysis by comparison with a state-of-the-art TDM analysis approach and consistently showing a considerable reduction in maximum interference.

IEEE Senior Membership Awarded

I was just notified that my application for Senior Membership in the IEEE was granted and that I have been elevated to Senior Member. The notification states that “IEEE Senior Membership is an honor bestowed only to those who have made significant contributions to the profession“, which is comforting appreciation of my work. I want to thank the IEEE Senior Members and Fellows that supported my application by giving their recommendations.

Two Articles Appeared in Journal of Systems Architecture

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.

Invited Presentation at CMAS 2015

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.