Today, we celebrate that Yonghui Li successfully defended his PhD dissertation “Design and Formal Analysis of Real-Time Memory Controllers” and became Dr. Li. The thesis defines a dynamically scheduled real-time memory controller architecture, which is implemented as a SystemC simulation model. It then continues by analyzing the worst-case response time and minimum guaranteed bandwidth using three different formal frameworks. The first framework is a mathematical formulation of both the actual and worst-case timing behavior as a set of equations and proofs of their correctness. These equations are also implemented in an open-source tool. The drawback of this kind of mathematical formulation is that it takes a long time to derive and prove correct. The second analysis approach addresses this by shifting the effort of the user from performance analysis to modeling the memory controller as a mode-controlled data-flow graph, which can be analyzed with existing tools. This approach is faster, but only bounds the minimum guaranteed bandwidth and not the worst-case response time. This limitation is overcome by the final approach, which is to model the memory controller using timed automata and bound its worst-case performance using a model checker. So, in summary, one controller architecture and three approaches to analyse its worst-case performance. This work hence gives unique insight into the strengths and weaknesses of different modeling and analysis approaches in terms of accuracy, expressiveness, memory consumption, and computation time.
The defense itself was well-prepared and confident and the committee seemed to really like the work. I am also really pleased with how it came out and I would like to thank Yonghui for the years of hard work that went into creating it. It was a pleasure to work with you during these years and I wish you all the best in your future career.
Yonghui Li is on a roll! Two months ago he received the best paper award at ESTIMEDIA for his work on modelling and analysis of a dynamically scheduled DRAM controller using mode-controlled data-flow graphs. Now, he just had a paper entitled “Modeling and Verification of Dynamic Command Scheduling for Real-Time Memory Controllers” that models and analyses the same memory controller using timed atomata. A key highlight of this work is that it quantitatively compares data-flow analysis, timed automata, and two other approaches from Yonghui’s 2015 article in Real-Time Systems in terms of guaranteed bandwidth and worst-case execution time. This gives interesting insights into what these different approaches can and cannot model and what the impact of those limitations are on the performance guarantees. This work was the result of a fruitful collaboration with Kai Lampka from Uppsala University in Sweden.
We won the Best Paper Award at the 13th IEEE Symposium on Embedded Systems for Real-Time Multimedia (ESTIMedia) for our paper “Mode-Controlled Data-Flow Modeling of Real-Time Memory Controllers“. The paper was first-authored by Yonghui Li and was a successful collaboration with Orlando Moreira (previously with ST-Ericsson, currently with Intel) and two of his PhD students at Eindhoven University of Technology. We are happy that our work was well-received and hope the community will like the paper.
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.
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.
The Memory Team is proud to release another open-source tool to the community. This tool is called RTMemController and contains a mathematical formalization of the dynamic command scheduler introduced in Yonghui Li’s paper Dynamic Command Scheduling for Real-Time Memory Controllers that will be presented at ECRTS. The tool is capable of determining worst-case and average-case execution times of memory transactions of different transaction sizes and with varying degrees of bank interleaving.
An important driver for releasing this tool is to promote transparency and fair comparisons between work in the field. Longer term development plans for the tool may involve adding support for a memory controller front-end with different transaction schedulers, adding support for more memory generations (currently DDR3 is supported), and making the output compatible with DRAMPower to enable chaining the tools.
The official website of RTMemController is found here. Also check out the paper that describes the scheduling algorithm and its formalization.
Today, we congratulate Yonghui Li on an accepted paper at ECRTS. The paper is entitled Dynamic Command Scheduling for Real-Time Memory Controllers and presents both an architecture and analysis for a dynamically scheduled SDRAM controller supporting different transaction sizes and memory map configurations. This is Yonghui’s first accepted paper and we are proud to see that it got very good reviews from one of the most competitive conferences in the field. Now the work begins on preparing a camera-ready version and making the scheduling algorithm publicly available for comparisons in community.
The memory team welcomes Yonghui Li who just embarked on the four year quest towards a PhD degree in the context of the T-CREST project. We wish him the best of luck on this endeavor and look forward to working together.