Manil Dev Gomony just had a journal article entitled “A Globally Arbitrated Memory Tree for Mixed-Time-Criticality Systems” accepted in the high-impact journal IEEE Transactions on Computers. This article extends a conference paper published at DATE in 2015 that was called “A Generic, Scalable and Globally Arbitrated Memory Tree for Shared DRAM Access in Real-Time Systems” that was published in collaboration with Jamie Garside and Neil Audsley from University of York. The original paper explained the design and efficient hardware implementation of a transaction arbiter for real-time systems that could be configured to behave like any of five well-known arbiters, i.e. TDM, Round Robin, Credit-Controlled Static Priority, Priority-Based Scheduler, and Frame-Based Static Priority. The key feature of the arbiter is that it is distributed, which means that accounting and enforcement is not done in a single centralized location, allowing it to scale to systems with many resource clients without negatively impacting the maximum frequency at which it operates.
The journal article extends the original conference paper by adding more detail and examples on the design of the memory tree, as well as improving positioning. However, it also extends the scope of the work to consider more complex Mixed-Time-Criticality systems where some clients are more concerned about average-case than worst-case performance. It also considers that the requirements of the clients may be diverse, i.e. that some may have high bandwidth requirements and are latency-tolerant, while others have low bandwidth requirements, but are latency-critical. This is diversity of requirements is addressed by showing how the memory tree supports the transaction arbiter to be chosen individually per client rather than once for the entire system. For example, some real-time clients may be configured by non-work-conserving TDM arbitration to get predictable bandwidth and latency while enjoying complete temporal isolation from other clients, which simplifies integration and certification. Other clients sharing the same resource, may be scheduled using e.g. using a work-conserving Frame-Based Static Priority scheduler to reflect an interest in low average latency while still distinguishing their relative latency-sensitivity. The memory tree supports any combination of the mechanisms discussed above, but we provide a formal analysis of the mixed arbitration algorithm explained above. The article demonstrates the benefits of this approach on a VHDL hardware implementation, as well as its cost in terms of area and power compared to centralized non-mixed arbitration policies by means of ASIC synthesis.
Our new book “Memory Controllers for Mixed-Time-Criticality Systems: Architectures, Methodologies and Trade-offs” is now available for pre-order at Springer. The book is based on the excellent PhD thesis of Sven Goossens and discusses the design and FPGA implementation of a real-time memory controller for mixed-criticality systems. The controller can provide complete temporal isolation to its clients as well as hard bounds on the worst-case response time of transactions and the bandwidth offered by the memory. In addition, it provides competitive average-case performance for soft real-time and best-effort applications using a conservative open-page policy. The design is highly configurable and the book carefully quantifies the trade-offs between bandwidth, response time, and power that this enables. To facilitate the discussion about power, the book also presents the power model that came out of the PhD dissertation of Karthik Chandrasekar and gives an up-to-date description of the open-source DRAMPower tool that implements it.
Update: The contents of the book are now available on SpringerLink
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.
After successfully defending his dissertation “A Reconfigurable Mixed-Time-Criticality SDRAM Controller“, Sven Goossens earned himself a PhD degree and the right to call himself a doctor. The work proposes a pattern-based SDRAM controller targeting mixed-time-criticality systems, i.e. systems where some memory clients need firm worst-case guarantees on bandwidth and latency, while other clients only care about average-case performance. A new memory controller architecture is designed to address this mix of requirements and it is implemented both as a cycle-accurate SystemC simulation model and as synthesizable RTL code for generating FPGA instances. A unique feature of this memory controller is its conservative open-page policy that leaves rows open in the memory banks as long as possible to exploit locality and boost average-case performance, but closes them just in time to avoid reducing the worst-case performance.
The work also parameterizes the concept of memory patterns by allowing the number of banks and the number of bursts per bank to be chosen when the patterns are generated. This allows patterns with different degrees of bank-level parallelism to be created for six different generations of DRAM for any request size, enabling the user to make a trade-off between worst-case bandwidth, worst-case response time, and power consumption. To generate efficient memory patterns, the work proposes an integer linear programming formulation that provides optimal patterns, as well as a near-optimal heuristic that runs in a fraction of the time. In addition to generating predictable memory patterns that provide bounded bandwidth and execution times, composable read and write patterns can be generated with negligible performance loss. These patterns have equal length and can be used to provide complete temporal isolation between memory clients when combined with a non-work-conserving Time-Division Multiplexing (TDM) arbiter in the front-end. The memory patterns are generated offline at design time, but are programmed at run-time when the memory controller is initialized. Lastly, the proposed controller supports run-time reconfiguration of its TDM arbiter, allowing it to be safely reprogrammed when applications dynamically start and stop at run-time without sacrificing the worst-case guarantees of applications that keep running.
I would like to thank Sven for the five years of hard work. It has been a pleasure to work with such a versatile and independent young researcher who seems to be succesful at whatever he attempts, be it design, analysis, writing papers, or hardware/software implementation in more or lesss any language. He has also been an excellent member of the Memory Team and the larger CompSoC Team, never passing on an opportunity to use his skills to support other members of the team. At the end of January, Sven starts his new career with Intrinsic-ID in Eindhoven. We wish him the best of luck with his new job and hope to stay in touch.
Last year, my PhD student Hazem Ali got a HiPEAC collaboration grant sponsoring a three month visit in the Electronic Systems group at Eindhoven University of Technology, hosted by Dr. Sander Stuijk. The topic of the joint research is related to the borderland between data-flow and traditional real-time analysis. On page 15 in the latest issue of the HiPEAC Newsletter, you can read more about his stay.
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.
Today, Manil Dev Gomony has successfully defended his PhD thesis entitled “Scalable and Bandwidth-Efficient Memory Subsystem Design for Real-Time Systems“. The thesis proposes an architecture for a real-time memory subsystem that scales well in terms of area and maximum synthesizable frequency with an increasing number of memory clients. This subsystem architecture comprises a memory interconnect called Globally Arbitrated Memory Tree (GAMT) a Multi-Channel Memory Controller (MCMC), as well as a technique to couple those components and have a single point of arbitration for both resources. The thesis also proposes a design flow for automatically choosing the memory device, mapping clients to memory channel, and configure arbiters to satisfy client requirements.
Among Manil’s achievements, we specifically highlight two achievements with respect to publishing. First of all, he had a paper accepted at the DATE conference every year during his PhD. Secondly, none of his publications were ever rejected anywhere. This shows that Manil managed to publish in competitive forums in his field and that his work was well-received. Currently, Manil works as a Researcher at Bell Laboratories of Alcatel-Lucent in Belgium. We wish him the best of luck in his future career!
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 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.