Loading...
10 results
Search Results
Now showing 1 - 10 of 10
- Cache Persistence-Aware Memory Bus Contention Analysis for Multicore SystemsPublication . Aftab Rashid, Syed; Nelissen, Geoffrey; Tovar, EduardoMemory bus contention strongly relates to the number of main memory requests generated by tasks running on different cores of a multicore platform, which, in turn, depends on the content of the cache memories during the execution of those tasks. Recent works have shown that due to cache persistence the memory access demand of multiple jobs of a task may not always be equal to its worst-case memory access demand in isolation. Analysis of the variable memory access demand of tasks due to cache persistence leads to significantly tighter worst-case response time (WCRT) of tasks.In this work, we show how the notion of cache persistence can be extended from single-core to multicore systems. In particular, we focus on analyzing the impact of cache persistence on the memory bus contention suffered by tasks executing on a multi-core platform considering both work conserving and non-work conserving bus arbitration policies. Experimental evaluation shows that cache persistence-aware analyses of bus arbitration policies increase the number of task sets deemed schedulable by up to 70 percentage points in comparison to their respective counterparts that do not account for cache persistence.
- HopliteRT*: Real-Time NoC for FPGAPublication . Ribot González, Yilian; Nelissen, GeoffreyWith the increasing number of computation nodes integrated in multi and many-core platforms, network-on-chips (NoCs) emerged as a new communication medium in systems-on-chips (SoCs). HopliteRT is a new NoC design that was recently proposed to address the needs of real-time systems whilst respecting the constraints of field-programmable gate array (FPGA) platforms. In this article, we: 1) introduce priority-based routing in HopliteRT; 2) change the network topology in order to improve the packets’ worst-case traversal time (WCTT); 3) identify a flaw in the existing timing analysis of HopliteRT; and 4) develop a new timing analysis that is proven correct. We also show by means of experiments that the modifications of HopliteRT proposed in this article allows for at least 2× improvement on the worst and average case traversal time of high priority packets, without impacting the quality of service of low-priority packets. The timing properties of high priority flows are greatly improved for negligible additional hardware costs. The proposed NoC has been implemented in Verilog and synthesized for a Xilinx Virtex-7 FPGA platform.
- Response-Time Analysis of Limited-Preemptive Parallel DAG Tasks under Global SchedulingPublication . Nasri, Mitra; Nelissen, Geoffrey; Brandenburg, Björn B.Most recurrent real-time applications can be modeled as a set of sequential code segments (or blocks) that must be (repeatedly) executed in a specific order. This paper provides a schedulability analysis for such systems modeled as a set of parallel DAG tasks executed under any limited-preemptive global job-level fixed priority scheduling policy. More precisely, we derive response-time bounds for a set of jobs subject to precedence constraints, release jitter, and execution-time uncertainty, which enables support for a wide variety of parallel, limited-preemptive execution models (e.g., periodic DAG tasks, transactional tasks, generalized multi-frame tasks, etc.). Our analysis explores the space of all possible schedules using a powerful new state abstraction and state-pruning technique. An empirical evaluation shows the analysis to identify between 10 to 90 percentage points more schedulable task sets than the state-of-the-art schedulability test for limited-preemptive sporadic DAG tasks. It scales to systems of up to 64 cores with 20 DAG tasks. Moreover, while our analysis is almost as accurate as the state-of-the-art exact schedulability test based on model checking (for sequential non-preemptive tasks), it is three orders of magnitude faster and hence capable of analyzing task sets with more than 60 tasks on 8 cores in a few seconds.
- A Holistic Memory Contention Analysis for Parallel Real-Time Tasks under Partitioned SchedulingPublication . Casini, Daniel; Biondi, Alessandro; Nelissen, Geoffrey; Buttazzo, GiorgioWhen adopting multi-core systems for safety-critical applications, certification requirements mandate bounding the delays incurred in accessing shared resources. This is the case of global memories, whose access is often regulated by memory controllers optimized for average-case performance and not designed to be predictable. As a consequence, worst-case bounds on memory access delays often result to be too pessimistic, drastically reducing the advantage of having multiple cores. This paper proposes a fine-grained analysis of the memory contention experienced by parallel tasks running on a multi-core platform. To this end, an optimization problem is formulated to bound the memory interference by leveraging a three-phase execution model and holistically considering multiple memory transactions issued during each phase. Experimental results show the advantage in adopting the proposed approach on both synthetic task sets and benchmarks.
- ResilienceP Analysis: Bounding Cache Persistence Reload Overhead for Set-Associative CachesPublication . Aftab Rashid, Syed; Nelissen, Geoffrey; Tovar, EduardoThis work presents different approaches to calculate CPRO for set-associative caches. The PCB-ECB approach uses PCBs of the task under analysis and ECBs of all other tasks in the system to provide sound estimates of CPRO for set-associative caches. The resilienceP analysis then removes some of the pessimism in the PCB-ECB approach by considering the resilience of PCBs during CPRO calculations. We show that using the state-of-the-art (SoA) resilience analysis to calculate resilience of PCBs may result in underestimating the CPRO tasks may suffer. Finally, we have also presented a multi-set alike resilienceP analysis that highlights the pessimism in the resilienceP analysis and provides some insights on how it can be removed.
- Bounding Cache Persistence Reload Overheads for Set-Associative CachesPublication . Rashid, Syed Aftab; Nelissen, Geoffrey; Tovar, EduardoCache memories have a strong impact on the response time of tasks executed on modern computing platforms. For tasks scheduled under fixed-priority preemptive scheduling (FPPS), the worst-case response time (WCRT) analyses that account for cache persistence between jobs along with cache related preemption delays (CRPDs) have been shown to dominate analyses that only consider CRPDs. Yet, the existing approaches that analyze cache persistence in the context of WCRT analysis can only support direct-mapped caches. In this work, we analyze cache persistence in the context of WCRT analysis for set-associative caches. The main contributions of this work are: (i) to propose a solution to find persistent cache blocks (PCBs) of tasks considering set-associative caches, (ii) to present three different approaches to calculate cache persistence reload overheads (CPROs), i.e., the memory overhead due to eviction of PCBs of tasks, under set-associative caches, and (iii) an experimental evaluation showing that our proposed approaches result in up to 22 percentage points higher task set schedulability than the state-of-the-art approaches.
- Improved memory contention analysis for the 3-Phase task modelPublication . Arora, Jatin; Rashid, Syed Aftab; Nelissen, Geoffrey; Maia, Cláudio; Tovar, EduardoIn multiprocessor-based real-time systems, main memory is identified as a major bottleneck in the worst-case timing analysis of tasks. Phased execution models such as the 3-phase task model, i.e., that divides the execution of tasks into distinct computation and memory phases, have shown to be a good candidate to tackle the memory contention problem. The 3-phase execution model in particular has gained much attention from both academia and industry as it limits when tasks can access main memory to pre-defined phases. Information on when those phases may happen and their length can then be leveraged to build a fine-grained memory contention analysis. However, the existing work that focus on the memory contention analysis for 3-phase tasks may overestimate the memory contention caused by interfering write requests. This yields pessimistic bounds on the total memory contention suffered by tasks which in turn leads to pessimistic worst-case execution time (WCET) and worst-case response time (WCRT) bounds. In this work, we improve the state-of-the-art memory contention analysis for 3-phase tasks by (i) tightly bounding the memory contention that can be suffered due to write requests; and (ii) providing a new memory contention-aware WCET analysis.
- Design and implementation of an FPGA-based NoC for Real Time SystemsPublication . Ribot, Yilian; Nelissen, GeoffreyIn order to communicate, cores of a multi-core platform traditionally relied on shared busses. However, with the increasing number of computation nodes integrated in multi- and many-core platforms, Network-on-Chips (NoCs) emerged as a new alternative communication medium in Systems-on-Chips (SoCs). Hoplite-RT is a new NoC design that was recently proposed. Hoplite-RT is a compact design easy to analyze and with a low-cost implementation that was specifically tailored for FPGA. In this work, we introduce priority-based routing to Hoplite-RT and change the network topology so as to improve its timing behavior, i.e., its Worst-Case Traversal Time (WCTT).
- From Code to Weakly Hard Constraints: A Pragmatic End-to-End Toolchain for Timed CPublication . Natarajan, Saranya; Nasri, Mitra; Broman, David; Brandenbur, Björn B.; Nelissen, GeoffreyComplex real-time systems are traditionally developed in several disjoint steps: (i) decomposition of applications into sets of recurrent tasks, (ii) worst-case execution time estimation, and (iii) schedulability analysis. Each step is already in itself complex and error-prone, and the composition of all three poses a nontrivial integration problem. In particular, it is challenging to obtain an end-to-end analysis of timing properties of the whole system due to practical differences between the interfaces of tools for extracting task models, execution time analysis, and schedulability tests. To address this problem, we propose a seamless and pragmatic end-to-end compilation and timing analysis toolchain, where source programs are written in a real-time extension of C, called Timed C. The toolchain automatically translates timing primitives into executable code, measures execution times, and verifies temporal correctness using an extended schedulability test for non-preemptive generalized multiframe task sets. Novel aspects of our approach are: (i) both soft and firm tasks can be expressed at the programming language level and stated timing requirements are automatically verified by the schedulability test, and (ii) the schedulability test outputs per-job response-time information that enables a new approach to sensitivity analysis. Specifically, we perform a weakly hard sensitivity analysis that determines the worst-case execution time margins for the strongest still-satisfied (M;K) constraint, where M = m_1 + … + m_N denotes the number of deadline misses across the entire task set, and K = {k_1; … ; k_N} is the set of windows of interest of the different tasks. The toolchain is implemented as a source-to-source compiler, freely available as open source, and conveniently distributed as a Docker container.
- Schedulability Analysis for 3-Phase Tasks with Partitioned Fixed-Priority SchedulingPublication . Arora, Jatin; Maia, Cláudio; Rashid, Syed Aftab; Nelissen, Geoffrey; Tovar, EduardoMulticore platforms are being increasingly adopted in Cyber-Physical Systems (CPS) due to their advantages over single-core processors, such as raw computing power and energy efficiency. Typically, multicore platforms use a shared memory bus that connects the cores to the off-chip main memory. This sharing of memory bus may cause tasks running on different cores to compete for access to the main memory whenever data/instructions are need to be read/written from/to the main memory. Such competition is problematic, as it may cause variations in the execution time of tasks in a non-deterministic way. To reduce the complexity of analysing this problem, the 3-phase task model was proposed that divides tasks' executions into distinct memory and execution phases. The distinctive memory phases are then scheduled to eliminate/minimize main memory contention between concurrently executing tasks. However, 3-phase tasks running on different cores may still compete to access the shared memory bus/main memory in order to execute memory phases. This paper presents a partitioned scheduling-based approach that allows one to derive memory bus contention-aware worst-case response time of tasks that follow the 3-phase task model. In particular, the bus-contention analysis is derived by considering two memory access models, i.e., (i) dedicated memory access model, where a core having allowed to access the main memory via memory bus is permitted to execute more than one memory phase, and (ii) fair memory access model, that restrict each core to execute only one memory phase in its allocated bus access. Both these models represent different system and application requirements, and the resulting bus contention of tasks may vary depending on the considered model. To evaluate the effectiveness of the proposed bus contention analysis, we compare its performance against an existing analysis in the state-of-the-art by performing (i) case-study experiments, using benchmarks from the Mälardalen Benchmark suite, and (ii) empirical evaluation using synthetic task sets. Results show that our proposed analysis can improve task set schedulability of 3-phase tasks by up to 88 percentage points.