Another paper written with my former colleagues at CISTER has been accepted. The paper is entitled “Mixed-criticality Scheduling with Memory Bandwith Regulation” and appear at DATE 2018. The paper considers the problem that existing schedulability analyses for mixed-criticality multi-core systems do not consider task interference in shared platform resources, such as memories, potentially making them optimistic and unsafe. We address this issue by formulating a schedulability analysis for mixed-criticality fixed-priority-scheduled multi-core systems using per-core memory access regulation. We also propose multiple heuristics for memory bandwidth allocation and task-to-core assignment. The analysis and heuristics are implemented in a tool and evaluated through extensive experiments.
Article Accepted in IEEE Transactions on Computers
Anna Minaeva had an article entitled “Time-Triggered Co-Scheduling of Computation and Communication with Jitter Requirements” accepted in IEEE Transactions on Computers. The article considers the problem of efficiently co-scheduling task execution and communication in multi-core automotive platforms. Most existing works typically deal with zero-jitter scheduling, which results in lower resource utilization, but has lower memory requirements. In contrast, this article focuses on jitter-constrained scheduling that puts constraints on the tasks jitter, increasing schedulability over zero-jitter scheduling.
The contributions of this article are: 1) Integer Linear Programming and Satisfiability Modulo Theory model exploiting problem-specific information to reduce the formulations complexity to schedule small applications. 2) A heuristic approach, employing three levels of scheduling scaling to real-world use-cases with 10000 tasks and messages. 3) An experimental evaluation of the proposed approaches on a case-study and on synthetic data sets showing the efficiency of both zero-jitter and jitter-constrained scheduling. It shows that up to 28% higher resource utilization can be achieved by having up to 10 times longer computation time with relaxed jitter requirements.
Hazem Ali Defends Dissertation
Paper Accepted at SCOPES 2017
Hazem had a paper entitled “Combining Dataflow Applications and Real-time Task Sets on Multi-core Platforms” accepted at the 2017 Workshop on Software and Compilers for Embedded Systems (SCOPES). This paper is a short overview of his PhD dissertation, which will be defended in Porto on May 23, and explains an approach to map and schedule a multi-/many-core system containing both applications described as traditional real-time task sets and synchronous data-flow graphs. Hazem’s approach is to convert the data-flow graph into a periodic real-time task set to unify the models before mapping, which enables him to leverage existing real-time analysis techniques and schedulers. However, converting a complex data-flow graph into a periodic task set may result in a large number of tasks, resulting in long analysis times. To mitigate this problem, he proposes a slack-based merging algorithm that allows the number of tasks to be reduced by carefully sacrificing parallelism in the data-flow graph, subject to its latency and throughput constraints. Lastly, the resulting unified real-time task set is mapped to a multi-/many-core platform interconnected by a TDM NoC using a sensitive-path-first algorithm, which first allocates tasks derived from the original data-flow graph that have the highest impact on its execution and schedulability. It is also able to exploit parallelism in graph during mapping.
We hope you enjoy the paper and wish Hazem all the best for his upcoming defense.
Paper Accepted at ECRTS 2017
Our paper “Mixed-criticality Scheduling with Dynamic Redistribution of Shared Cache” has been accepted at ECRTS 2017, marking the end of yet another succesful collaboration with my former colleagues at CISTER. The paper proposes an extension of Vestal’s model for mixed-criticality multi-core systems that 1) accounts for the per-task partitioning of the last-level cache, and 2) supports dynamic reassignment of cache portions initially reserved for lower-criticality tasks to the higher-criticality tasks when switching to high-criticality mode. A schedulability analysis based on partitioned EDF is presented that is aware of the cache resources assigned to each task and leverages the dynamic reconfiguration to improve schedulability. We also propose heuristics for partitioning the cache in low- and high-criticality mode. Experimental result indicate tangible improvements in schedulability compared to a baseline cache-aware arrangement where there is no redistribution of cache resources from low- to high-criticality tasks in the event of a mode change.
Paper Accepted at RTAS
A paper entitled “Partitioning and Analysis of the Network-on-Chip on a COTS Many-Core Platform” was recently accepted for publication at RTAS. This paper was a collaboration with former colleagues at the CISTER Research Unit, as well as friends from MDH in Sweden. The paper addresses the issue of interference between applications in many-core platforms interconnected using rate-regulated Networks-on-Chip (NoC), such as the Kalray MPPA. The main contributions of the paper are 1) a partitioning strategy for reducing contention on the NoC, 2) an analysis technique to determine the Worst-Case Traversal Time of packages under the proposed strategy, and 3) a method to determine parameters for the NoCs rate regulators to get minimal WCTT and ensure that buffers never overflow. The benefits of the proposed approach is evaluated both using simulation and by experiments on a Kalray MPPA. Furthermore, an industrial case study from the automotive domain shows the tightness of the proposed analysis.
Yonghui Li Defends Dissertation
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.
Outstanding Paper Award at ECRTS
I am pleased to announce that our paper “Cache-Persistence-Aware Response-Time Analysis for Fixed-Priority Preemptive Systems” got an Outstanding Paper Award at the Euromicro Conference on Real-Time Systems (ECRTS) in Toulouse. We are glad that the work was well-received and hope that the community will enjoy reading the paper.
Article Accepted in IEEE Transactions on Computers
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.
Journal Article Accepted in ACM TODAES
We just received the good news that Hazem’s article “ Reducing the Complexity of Dataflow Graphs using Slack-based Merging” has been accepted for publication in ACM Transactions on Design Automation of Electronic Systems (TODAES). The article addresses an important problem when working with synchronous data-flow (SDF) graphs, namely that the size of the graph explodes when transforming it to its equivalent homogeneous (HSDF) representation, which prevents any design or analysis algorithms requiring this transformation as a first step from scaling to larger graphs. In the scope of Hazem’s work, this has caused problems when converting an SDF graph into a set of independent periodic real-time tasks.
This article proposes a heuristic algorithm to reduce the size of the resulting HSDF graph prior to analysis by merging actors in the graph, thereby speeding up analysis algorithms using the resulting graph. Three key properties of the algorithm are: 1) it cannot violate the latency or throughput requirements of the original graph, 2) it cannot cause deadlock in the resulting merged graph, and 3) only HSDF actors corresponding to firings of the same SDF actor can be merged to enable the resulting merged graph to be efficiently used by mapping algorithms. The behavior of the algorithm is evaluated with applications from the SDF3 benchmark suite and it is compared to results of an optimal exhaustive merging algorithm for smaller graphs.