18 Search Results for "Nelissen, Geoffrey"

Document
DOI: 10.4230/OASIcs.NG-RES.2026.2
Schedulability Analysis of OpenMP Applications Under Heuristic Task-To-Thread Mapping

Authors: Mohammad Samadi, Tiago Carvalho, Luís Miguel Pinho, and Sara Royuela

Published in: OASIcs, Volume 140, 7th Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2026)

Abstract
Task-to-thread mapping is a key process in parallel applications to achieve the best possible performance. This process is even more challenging when it is required to meet the schedulability and timing requirements of critical systems. In these systems, mapping tasks to threads is usually carried out using static scheduling (i.e., offline mapping) to improve system schedulability, with several approaches being presented in the literature. Nevertheless, there has been little analysis on the impact that these static mapping approaches have on the schedulability of applications exploiting OpenMP, a model increasingly seen as a suitable mechanism to leverage the potential of parallel and heterogeneous processor architectures. This paper, therefore, performs a throughout evaluation of the recently presented heuristic task-to-thread mapping working with different heuristics through allocation and dispatching phases, compared with state-of-the-art, in terms of schedulability. This process is performed using a state-of-the-art schedulability analysis methodology through an integration of our simulator and an existing schedulability toolset. This evaluation allows for identifying the static heuristic mapping approaches that achieve tighter schedulability analysis than other methods in the literature.
Cite as

Mohammad Samadi, Tiago Carvalho, Luís Miguel Pinho, and Sara Royuela. Schedulability Analysis of OpenMP Applications Under Heuristic Task-To-Thread Mapping. In 7th Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2026). Open Access Series in Informatics (OASIcs), Volume 140, pp. 2:1-2:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{samadi_et_al:OASIcs.NG-RES.2026.2,
  author =	{Samadi, Mohammad and Carvalho, Tiago and Pinho, Lu{\'\i}s Miguel and Royuela, Sara},
  title =	{{Schedulability Analysis of OpenMP Applications Under Heuristic Task-To-Thread Mapping}},
  booktitle =	{7th Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2026)},
  pages =	{2:1--2:12},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-415-4},
  ISSN =	{2190-6807},
  year =	{2026},
  volume =	{140},
  editor =	{Ali, Hazem Ismail and Kurunathan, Harrison},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.NG-RES.2026.2},
  URN =		{urn:nbn:de:0030-drops-254204},
  doi =		{10.4230/OASIcs.NG-RES.2026.2},
  annote =	{Keywords: OpenMP, task-to-thread mapping, heuristics, response time, schedulability}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2025.2
Multi-Objective Memory Bandwidth Regulation and Cache Partitioning for Multicore Real-Time Systems

Authors: Binqi Sun, Zhihang Wei, Andrea Bastoni, Debayan Roy, Mirco Theile, Tomasz Kloda, Rodolfo Pellizzoni, and Marco Caccamo

Published in: LIPIcs, Volume 335, 37th Euromicro Conference on Real-Time Systems (ECRTS 2025)

Abstract
Memory bandwidth regulation and cache partitioning are widely used techniques for achieving predictable timing in real-time computing systems. Combined with partitioned scheduling, these methods require careful co-allocation of tasks and resources to cores, as task execution times strongly depend on available allocated resources. To address this challenge, this paper presents a 0-1 linear program for task-resource co-allocation, along with a multi-objective heuristic designed to minimize resource usage while guaranteeing schedulability under a preemptive EDF scheduling policy. Our heuristic employs a multi-layer framework, where an outer layer explores resource allocations using Pareto-pruned search, and an inner layer optimizes task allocation by solving a knapsack problem using dynamic programming. To evaluate the performance of the proposed optimization algorithm, we profile real-world benchmarks on an embedded AMD UltraScale+ ZCU102 platform, with fine-grained resource partitioning enabled by the Jailhouse hypervisor, leveraging cache set partitioning and MemGuard for memory bandwidth regulation. Experiments based on the benchmarking results show that the proposed 0-1 linear program outperforms existing mixed-integer programs by finding more optimal solutions within the same time limit. Moreover, the proposed multi-objective multi-layer heuristic performs consistently better than the state-of-the-art multi-resource-task co-allocation algorithm in terms of schedulability, resource usage, number of non-dominated solutions, and computational efficiency.
Cite as

Binqi Sun, Zhihang Wei, Andrea Bastoni, Debayan Roy, Mirco Theile, Tomasz Kloda, Rodolfo Pellizzoni, and Marco Caccamo. Multi-Objective Memory Bandwidth Regulation and Cache Partitioning for Multicore Real-Time Systems. In 37th Euromicro Conference on Real-Time Systems (ECRTS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 335, pp. 2:1-2:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{sun_et_al:LIPIcs.ECRTS.2025.2,
  author =	{Sun, Binqi and Wei, Zhihang and Bastoni, Andrea and Roy, Debayan and Theile, Mirco and Kloda, Tomasz and Pellizzoni, Rodolfo and Caccamo, Marco},
  title =	{{Multi-Objective Memory Bandwidth Regulation and Cache Partitioning for Multicore Real-Time Systems}},
  booktitle =	{37th Euromicro Conference on Real-Time Systems (ECRTS 2025)},
  pages =	{2:1--2:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-377-5},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{335},
  editor =	{Mancuso, Renato},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2025.2},
  URN =		{urn:nbn:de:0030-drops-235807},
  doi =		{10.4230/LIPIcs.ECRTS.2025.2},
  annote =	{Keywords: Multi-objective optimization, memory bandwidth regulation, cache partitioning, partitioned scheduling, real-time systems}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2025.17
Theoretical Foundations of Utility Accrual for Real-Time Systems

Authors: Jian-Jia Chen, Junjie Shi, Mario Günzel, Georg von der Brüggen, Kuan-Hsun Chen, and Peter Bella

Published in: LIPIcs, Volume 335, 37th Euromicro Conference on Real-Time Systems (ECRTS 2025)

Abstract
Providing guaranteed quantification of properties of soft real-time systems is important in practice to ensure that a system performs correctly most of the time. We study utility accrual for real-time systems, in which the utility of a real-time job is defined as a time utility function with respect to its response time. Essentially, we answer the fundamental questions: Does the utility accrual of a periodic real-time task in the long run converge to a single value? If yes, to which value? We first show that concrete problem instances exist where evaluating the utility accrual by simulating the scheduling algorithm or conducting scheduling experiments in a long run is erroneous. Afterwards, we show how to construct a Markov chain to model the interactions between the scheduling policy, the probabilistic workload of a periodic real-time task, the service provided by the system to serve the task, and the effect on the utility accrual. For such a Markov chain, we also provide the theoretical fundamentals to determine whether the utility accrual converges in the long run and the derivation of the utility accrual if it converges.
Cite as

Jian-Jia Chen, Junjie Shi, Mario Günzel, Georg von der Brüggen, Kuan-Hsun Chen, and Peter Bella. Theoretical Foundations of Utility Accrual for Real-Time Systems. In 37th Euromicro Conference on Real-Time Systems (ECRTS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 335, pp. 17:1-17:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ECRTS.2025.17,
  author =	{Chen, Jian-Jia and Shi, Junjie and G\"{u}nzel, Mario and von der Br\"{u}ggen, Georg and Chen, Kuan-Hsun and Bella, Peter},
  title =	{{Theoretical Foundations of Utility Accrual for Real-Time Systems}},
  booktitle =	{37th Euromicro Conference on Real-Time Systems (ECRTS 2025)},
  pages =	{17:1--17:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-377-5},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{335},
  editor =	{Mancuso, Renato},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2025.17},
  URN =		{urn:nbn:de:0030-drops-235950},
  doi =		{10.4230/LIPIcs.ECRTS.2025.17},
  annote =	{Keywords: Soft Real-Time Systems, Utility Accrual, Markov Chains, Dismiss Points}
}
Document
DOI: 10.4230/LITES.10.1.3
Limited-Preemption EDF Scheduling for Multi-Phase Secure Tasks

Authors: Benjamin Standaert, Fatima Raadia, Marion Sudvarg, Sanjoy Baruah, Thidapat Chantem, Nathan Fisher, and Christopher Gill

Published in: LITES, Volume 10, Issue 1 (2025). Leibniz Transactions on Embedded Systems, Volume 10, Issue 1

Abstract
Safety-critical embedded systems such as autonomous vehicles typically have only very limited computational capabilities on board that must be carefully managed to provide required enhanced functionalities. As these systems become more complex and inter-connected, some parts may need to be secured to prevent unauthorized access, or isolated to ensure correctness. We propose the multi-phase secure (MPS) task model as a natural extension of the widely used sporadic task model for modeling both the timing and the security (and isolation) requirements for such systems. Under MPS, task phases reflect execution using different security mechanisms which each have associated execution time costs for startup and teardown. We develop corresponding limited-preemption EDF scheduling algorithms and associated pseudo-polynomial schedulability tests for constrained-deadline MPS tasks. In doing so, we provide a correction to a long-standing schedulability condition for EDF under limited-preemption. Evaluation shows that the proposed tests are efficient to compute for bounded utilizations. We empirically demonstrate that the MPS model successfully schedules more task sets compared to non-preemptive approaches.
Cite as

Benjamin Standaert, Fatima Raadia, Marion Sudvarg, Sanjoy Baruah, Thidapat Chantem, Nathan Fisher, and Christopher Gill. Limited-Preemption EDF Scheduling for Multi-Phase Secure Tasks. In LITES, Volume 10, Issue 1 (2025). Leibniz Transactions on Embedded Systems, Volume 10, Issue 1, pp. 3:1-3:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@Article{standaert_et_al:LITES.10.1.3,
  author =	{Standaert, Benjamin and Raadia, Fatima and Sudvarg, Marion and Baruah, Sanjoy and Chantem, Thidapat and Fisher, Nathan and Gill, Christopher},
  title =	{{Limited-Preemption EDF Scheduling for Multi-Phase Secure Tasks}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{3:1--3:27},
  ISSN =	{2199-2002},
  year =	{2025},
  volume =	{10},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES.10.1.3},
  URN =		{urn:nbn:de:0030-drops-230799},
  doi =		{10.4230/LITES.10.1.3},
  annote =	{Keywords: real-time systems, limited-preemption scheduling, trusted execution environments}
}
Document
DOI: 10.4230/OASIcs.NG-RES.2025.5
SP-IMPact: A Framework for Static Partitioning Interference Mitigation and Performance Analysis

Authors: Diogo Costa, Gonçalo Moreira, Afonso Oliveira, José Martins, and Sandro Pinto

Published in: OASIcs, Volume 128, Sixth Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2025)

Abstract
Modern embedded systems are evolving toward complex, heterogeneous architectures to accommodate increasingly demanding applications. Driven by industry SWAP-C (Size, Weight, Power, and Cost) constraints, this shift has led to the consolidation of multiple systems onto single hardware platforms. Static Partitioning Hypervisors (SPHs) offer a promising solution to partition hardware resources and provide spatial isolation between critical workloads. However, shared hardware resources like the Last-Level Cache (LLC) and system bus can introduce significant temporal interference between virtual machines (VMs), negatively impacting performance and predictability. Over the past decade, academia and industry have focused on developing interference mitigation techniques, such as cache partitioning and memory bandwidth reservation. Configuring these techniques, however, is complex and time-consuming. Cache partitioning requires careful balancing of cache sections across VMs, while memory bandwidth reservation requires tuning bandwidth budgets and periods. With numerous possible configurations, testing all combinations is impractical and often leads to suboptimal configurations. Moreover, there is a gap in understanding how these techniques interact, as their combined use can result in compounded or conflicting effects on system performance. Static analysis solutions that estimate worst-case execution times (WCET) and upper bounds on execution times provide some guidance for configuring interference mitigation techniques. While useful in identifying potential interference effects, these tools often fail to capture the full complexity of modern multi-core systems, as they typically focus on a limited set of shared resources and neglect other sources of contention, such as IOMMUs and interrupt controllers. To address these challenges, we introduce SP-IMPact, an open-source framework designed to analyze and guide the configuration of interference mitigation techniques, through the deployment of diverse VM configurations and setups, and assessment of hardware-level contention (leveraging SPHs). It supports two mitigation techniques: (i) cache coloring and (ii) memory bandwidth reservation, while also evaluating the interactions between these techniques and their cumulative impact on system performance. By providing insights on real hardware platforms, SP-IMPact helps to optimize the configuration of these techniques in mixed-criticality systems, ensuring both performance and predictability.
Cite as

Diogo Costa, Gonçalo Moreira, Afonso Oliveira, José Martins, and Sandro Pinto. SP-IMPact: A Framework for Static Partitioning Interference Mitigation and Performance Analysis. In Sixth Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2025). Open Access Series in Informatics (OASIcs), Volume 128, pp. 5:1-5:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{costa_et_al:OASIcs.NG-RES.2025.5,
  author =	{Costa, Diogo and Moreira, Gon\c{c}alo and Oliveira, Afonso and Martins, Jos\'{e} and Pinto, Sandro},
  title =	{{SP-IMPact: A Framework for Static Partitioning Interference Mitigation and Performance Analysis}},
  booktitle =	{Sixth Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2025)},
  pages =	{5:1--5:15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-366-9},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{128},
  editor =	{Yomsi, Patrick Meumeu and Wildermann, Stefan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.NG-RES.2025.5},
  URN =		{urn:nbn:de:0030-drops-229911},
  doi =		{10.4230/OASIcs.NG-RES.2025.5},
  annote =	{Keywords: Virtualization, Contention, Multi-core Interference, Mixed-Criticality Systems, Arm}
}
Document
DOI: 10.4230/OASIcs.NG-RES.2025.4
H-MBR: Hypervisor-Level Memory Bandwidth Reservation for Mixed Criticality Systems

Authors: Afonso Oliveira, Diogo Costa, Gonçalo Moreira, José Martins, and Sandro Pinto

Published in: OASIcs, Volume 128, Sixth Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2025)

Abstract
Recent advancements in fields such as automotive and aerospace have driven a growing demand for robust computational resources. Applications that were once designed for basic Microcontroller Units (MCUs) are now deployed on highly heterogeneous System-on-Chip (SoC) platforms. While these platforms deliver the necessary computational performance, they also present challenges related to resource sharing and predictability. These challenges are particularly pronounced when consolidating safety-critical and non-safety-critical systems, the so-called Mixed-Criticality Systems (MCS) to adhere to strict Size, Weight, Power, and Cost (SWaP-C) requirements. MCS consolidation on shared platforms requires stringent spatial and temporal isolation to comply with functional safety standards (e.g., ISO 26262). Virtualization, mainly leveraged by hypervisors, is a key technology that ensures spatial isolation across multiple OSes and applications; however ensuring temporal isolation remains challenging due to contention on shared resources, such as main memory, caches, and system buses, which impacts real-time performance and predictability. To mitigate this problem, several strategies (e.g., cache coloring and memory bandwidth reservation) have been proposed. Although cache coloring is typically implemented on state-of-the-art hypervisors, memory bandwidth reservation approaches are commonly implemented at the Linux kernel level or rely on dedicated hardware and typically do not consider the concept of Virtual Machines that can run different OSes. To fill the gap between current memory bandwidth reservation solutions and the deployment of MCSs that operate on a hypervisor, this work introduces H-MBR, an open-source VM-centric memory bandwidth reservation mechanism. H-MBR features (i) VM-centric bandwidth reservation, (ii) OS and platform agnosticism, and (iii) reduced overhead. Empirical results evidenced no overhead on non-regulated workloads, and negligible overhead (<1%) for regulated workloads for regulation periods of 2 µs or higher.
Cite as

Afonso Oliveira, Diogo Costa, Gonçalo Moreira, José Martins, and Sandro Pinto. H-MBR: Hypervisor-Level Memory Bandwidth Reservation for Mixed Criticality Systems. In Sixth Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2025). Open Access Series in Informatics (OASIcs), Volume 128, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{oliveira_et_al:OASIcs.NG-RES.2025.4,
  author =	{Oliveira, Afonso and Costa, Diogo and Moreira, Gon\c{c}alo and Martins, Jos\'{e} and Pinto, Sandro},
  title =	{{H-MBR: Hypervisor-Level Memory Bandwidth Reservation for Mixed Criticality Systems}},
  booktitle =	{Sixth Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2025)},
  pages =	{4:1--4:15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-366-9},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{128},
  editor =	{Yomsi, Patrick Meumeu and Wildermann, Stefan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.NG-RES.2025.4},
  URN =		{urn:nbn:de:0030-drops-229905},
  doi =		{10.4230/OASIcs.NG-RES.2025.4},
  annote =	{Keywords: Virtualization, Multi-core Interference, Mixed-Criticality Systems, Arm, Memory Bandwidth Reservation}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2024.16
Analysis of TSN Time-Aware Shapers Using Schedule Abstraction Graphs

Authors: Srinidhi Srinivasan, Geoffrey Nelissen, Reinder J. Bril, and Nirvana Meratnia

Published in: LIPIcs, Volume 298, 36th Euromicro Conference on Real-Time Systems (ECRTS 2024)

Abstract
IEEE Time-Sensitive Networking (TSN) is one of the main solutions considered by the industry to support time-sensitive communication in data-intensive safety-critical and mission-critical applications such as autonomous driving and smart manufacturing. IEEE TSN standardizes several mechanisms to support real-time traffic on Ethernet networks. Time-Aware Shapers (TAS) (IEEE 802.1Qbv) is the standardized mechanisms of TSN that is usually considered to provide the most deterministic behavior for packet forwarding. TAS regulates when traffic classes may forward incoming packets to the egress of a TSN switch using gates that are opened and closed according to a time-triggered schedule. State-of-the-art solutions to configure or analyze TAS do not allow for multiple traffic classes to have their TAS gates opened at the same time according to any arbitrary schedule. In this paper, we present the first response-time analysis for traffic shaped with TAS where no restriction is enforced on the gate schedule. The proposed analysis is exact. It is a non-trivial variant of the schedule abstraction graph analysis framework [Nasri and Brandenburg, 2017]. Experiments confirm the usefulness of the proposed analysis and show that it is promising for doing design-space exploration where non-conventional TAS gates configurations are investigated to, for instance, improve average-case performance without degrading the worst-case.
Cite as

Srinidhi Srinivasan, Geoffrey Nelissen, Reinder J. Bril, and Nirvana Meratnia. Analysis of TSN Time-Aware Shapers Using Schedule Abstraction Graphs. In 36th Euromicro Conference on Real-Time Systems (ECRTS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 298, pp. 16:1-16:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{srinivasan_et_al:LIPIcs.ECRTS.2024.16,
  author =	{Srinivasan, Srinidhi and Nelissen, Geoffrey and Bril, Reinder J. and Meratnia, Nirvana},
  title =	{{Analysis of TSN Time-Aware Shapers Using Schedule Abstraction Graphs}},
  booktitle =	{36th Euromicro Conference on Real-Time Systems (ECRTS 2024)},
  pages =	{16:1--16:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-324-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{298},
  editor =	{Pellizzoni, Rodolfo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2024.16},
  URN =		{urn:nbn:de:0030-drops-203198},
  doi =		{10.4230/LIPIcs.ECRTS.2024.16},
  annote =	{Keywords: TSN, Time-Aware Shapers, TAS, SAG, Schedule Abstraction, latency}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2023.18
Replication-Based Scheduling of Parallel Real-Time Tasks

Authors: Federico Aromolo, Geoffrey Nelissen, and Alessandro Biondi

Published in: LIPIcs, Volume 262, 35th Euromicro Conference on Real-Time Systems (ECRTS 2023)

Abstract
Multiprocessors have become the standard computing platform for real-time embedded systems. To efficiently leverage the computational power of such platforms, software tasks are often characterized by an internal structure where concurrent subtasks can execute in parallel on different processors. Existing strategies for the scheduling of parallel real-time tasks on multiprocessor platforms, such as partitioned, global, and federated scheduling, were inspired by earlier techniques that were not conceived to explicitly support parallel tasks, thus carrying advantages but also well-known limitations. This paper introduces replication-based scheduling, a specialized scheduling paradigm for parallel real-time DAG tasks. Replication-based scheduling leverages the internal structure of the parallel tasks to assign replicas of the subtasks to different processors, while ensuring that exactly one replica of each subtask will be executed at runtime for every task instance. This approach aims at preserving the advantages of partitioned scheduling while simplifying the timing analysis. The replication-based scheduling framework is first defined, together with a strategy for implementing replication-based scheduling in real-time operating systems. Then, offline allocation strategies for subtask replicas and a response-time analysis are presented. In the provided experiments, the schedulability achieved with replication-based scheduling is compared with that of existing techniques for the scheduling of parallel real-time tasks on multiprocessors.
Cite as

Federico Aromolo, Geoffrey Nelissen, and Alessandro Biondi. Replication-Based Scheduling of Parallel Real-Time Tasks. In 35th Euromicro Conference on Real-Time Systems (ECRTS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 262, pp. 18:1-18:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{aromolo_et_al:LIPIcs.ECRTS.2023.18,
  author =	{Aromolo, Federico and Nelissen, Geoffrey and Biondi, Alessandro},
  title =	{{Replication-Based Scheduling of Parallel Real-Time Tasks}},
  booktitle =	{35th Euromicro Conference on Real-Time Systems (ECRTS 2023)},
  pages =	{18:1--18:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-280-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{262},
  editor =	{Papadopoulos, Alessandro V.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2023.18},
  URN =		{urn:nbn:de:0030-drops-180477},
  doi =		{10.4230/LIPIcs.ECRTS.2023.18},
  annote =	{Keywords: Real-Time Systems, Scheduling Algorithms, Schedulability Analysis, Parallel Tasks}
}
Document
Artifact
DOI: 10.4230/DARTS.8.1.5
Response-Time Analysis for Self-Suspending Tasks Under EDF Scheduling (Artifact)

Authors: Federico Aromolo, Alessandro Biondi, and Geoffrey Nelissen

Published in: DARTS, Volume 8, Issue 1, Special Issue of the 34th Euromicro Conference on Real-Time Systems (ECRTS 2022)

Abstract
This artifact provides the means to validate and reproduce the experimental results presented in the related paper "Response-Time Analysis for Self-Suspending Tasks Under EDF Scheduling". The paper introduces a response-time analysis for constrained-deadline self-suspending tasks scheduled under EDF on a uniprocessor system, based on a model transformation from self-suspending sporadic tasks to sporadic tasks with jitter. In the experimental evaluation presented in the paper, the performance of the proposed analysis approach for self-suspending tasks is compared with that of existing suspension-oblivious and suspension-aware analysis techniques.
Cite as

Federico Aromolo, Alessandro Biondi, and Geoffrey Nelissen. Response-Time Analysis for Self-Suspending Tasks Under EDF Scheduling (Artifact). In Special Issue of the 34th Euromicro Conference on Real-Time Systems (ECRTS 2022). Dagstuhl Artifacts Series (DARTS), Volume 8, Issue 1, pp. 5:1-5:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Article{aromolo_et_al:DARTS.8.1.5,
  author =	{Aromolo, Federico and Biondi, Alessandro and Nelissen, Geoffrey},
  title =	{{Response-Time Analysis for Self-Suspending Tasks Under EDF Scheduling (Artifact)}},
  pages =	{5:1--5:2},
  journal =	{Dagstuhl Artifacts Series},
  ISSN =	{2509-8195},
  year =	{2022},
  volume =	{8},
  number =	{1},
  editor =	{Aromolo, Federico and Biondi, Alessandro and Nelissen, Geoffrey},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DARTS.8.1.5},
  URN =		{urn:nbn:de:0030-drops-165012},
  doi =		{10.4230/DARTS.8.1.5},
  annote =	{Keywords: Real-Time Systems, Schedulability Analysis, Self-Suspending Tasks, EDF Scheduling}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2022.12
Response-Time Analysis for Non-Preemptive Periodic Moldable Gang Tasks

Authors: Geoffrey Nelissen, Joan Marcè i Igual, and Mitra Nasri

Published in: LIPIcs, Volume 231, 34th Euromicro Conference on Real-Time Systems (ECRTS 2022)

Abstract
Gang scheduling has long been adopted by the high-performance computing community as a way to reduce the synchronization overhead between related threads. It allows for several threads to execute in lock steps without suffering from long busy-wait periods or be penalized by large context-switch overheads. When combined with non-preemptive execution, gang scheduling significantly reduces the execution time of threads that work on the same data by decreasing the number of memory transactions required to load or store the data. In this work, we focus on two main types of gang tasks: rigid and moldable. A moldable gang task has a presumed known minimum and maximum number of cores on which it can be executed at runtime, while a rigid gang task always executes on the same number of cores. This work presents the first response-time analysis for non-preemptive moldable gang tasks. Our analysis is based on the notion of schedule abstraction; a new approach for response-time analysis with the promise of high accuracy. Our experiments on periodic rigid gang tasks show that our analysis is 4.9 times more successful in identifying schedulable tasks than the existing utilization-based test for rigid gang tasks.
Cite as

Geoffrey Nelissen, Joan Marcè i Igual, and Mitra Nasri. Response-Time Analysis for Non-Preemptive Periodic Moldable Gang Tasks. In 34th Euromicro Conference on Real-Time Systems (ECRTS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 231, pp. 12:1-12:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{nelissen_et_al:LIPIcs.ECRTS.2022.12,
  author =	{Nelissen, Geoffrey and Marc\`{e} i Igual, Joan and Nasri, Mitra},
  title =	{{Response-Time Analysis for Non-Preemptive Periodic Moldable Gang Tasks}},
  booktitle =	{34th Euromicro Conference on Real-Time Systems (ECRTS 2022)},
  pages =	{12:1--12:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-239-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{231},
  editor =	{Maggio, Martina},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2022.12},
  URN =		{urn:nbn:de:0030-drops-163293},
  doi =		{10.4230/LIPIcs.ECRTS.2022.12},
  annote =	{Keywords: schedulability analysis, response time analysis, moldable gang tasks, rigid gang tasks, schedule abstraction graph, multiprocessor, non-preemptive}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2022.13
Response-Time Analysis for Self-Suspending Tasks Under EDF Scheduling

Authors: Federico Aromolo, Alessandro Biondi, and Geoffrey Nelissen

Published in: LIPIcs, Volume 231, 34th Euromicro Conference on Real-Time Systems (ECRTS 2022)

Abstract
The self-suspending task model proved to be particularly effective in capturing the timing behavior of real-time systems characterized by complex execution patterns, such as computation offloading to hardware accelerators, inter-core synchronization by means of multiprocessor locking protocols, and highly parallel computation. Most of the existing results for the timing analysis of self-suspending tasks do not support the widely adopted Earliest Deadline First (EDF) scheduling algorithm, being instead primarily focused on fixed-priority scheduling. This paper presents a response-time analysis for constrained-deadline self-suspending tasks scheduled under EDF on a uniprocessor system. The proposed analysis is based on a model transformation from self-suspending sporadic tasks to sporadic tasks with jitter, which can then be analyzed using a state-of-the-art analysis method for EDF scheduling. Experimental results are presented to compare the performance of the proposed technique in terms of schedulability ratio with that of the pessimistic suspension-oblivious approach and with a less general technique for task sets with implicit deadlines.
Cite as

Federico Aromolo, Alessandro Biondi, and Geoffrey Nelissen. Response-Time Analysis for Self-Suspending Tasks Under EDF Scheduling. In 34th Euromicro Conference on Real-Time Systems (ECRTS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 231, pp. 13:1-13:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{aromolo_et_al:LIPIcs.ECRTS.2022.13,
  author =	{Aromolo, Federico and Biondi, Alessandro and Nelissen, Geoffrey},
  title =	{{Response-Time Analysis for Self-Suspending Tasks Under EDF Scheduling}},
  booktitle =	{34th Euromicro Conference on Real-Time Systems (ECRTS 2022)},
  pages =	{13:1--13:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-239-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{231},
  editor =	{Maggio, Martina},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2022.13},
  URN =		{urn:nbn:de:0030-drops-163306},
  doi =		{10.4230/LIPIcs.ECRTS.2022.13},
  annote =	{Keywords: Real-Time Systems, Schedulability Analysis, Self-Suspending Tasks, EDF Scheduling}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2021.5
nDimNoC: Real-Time D-dimensional NoC

Authors: Yilian Ribot González, Geoffrey Nelissen, and Eduardo Tovar

Published in: LIPIcs, Volume 196, 33rd Euromicro Conference on Real-Time Systems (ECRTS 2021)

Abstract
The growing demand of powerful embedded systems to perform advanced functionalities led to a large increase in the number of computation nodes integrated in Systems-on-chip (SoC). In this context, network-on-chips (NoCs) emerged as a new standard communication infrastructure for multi-processor SoCs (MPSoCs). In this work, we present nDimNoC, a new D-dimensional NoC that provides real-time guarantees for systems implemented upon MPSoCs. Specifically, (1) we propose a new router architecture and a new deflection-based routing policy that use the properties of circulant topologies to ensure bounded worst-case communication delays, and (2) we develop a generic worst-case communication time (WCCT) analysis for packets transmitted over nDimNoC. In our experiments, we show that the WCCT of packets decreases when we increase the dimensionality of the NoC using nDimNoC’s topolgy and routing policy. By implementing nDimNoC in Verilog and synthesizing it for an FPGA platform, we show that a 3D-nDimNoC requires ≈5-times less silicon than routers that use virtual channels (VC). We computed the maximum operating frequency of a 3D-nDimNoC with Xilinx Vivado. Increasing the number dimensions in the NoC improves WCCT at the cost of a more complex routing logic that may result in a reduced operating clock frequency.
Cite as

Yilian Ribot González, Geoffrey Nelissen, and Eduardo Tovar. nDimNoC: Real-Time D-dimensional NoC. In 33rd Euromicro Conference on Real-Time Systems (ECRTS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 196, pp. 5:1-5:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ribotgonzalez_et_al:LIPIcs.ECRTS.2021.5,
  author =	{Ribot Gonz\'{a}lez, Yilian and Nelissen, Geoffrey and Tovar, Eduardo},
  title =	{{nDimNoC: Real-Time D-dimensional NoC}},
  booktitle =	{33rd Euromicro Conference on Real-Time Systems (ECRTS 2021)},
  pages =	{5:1--5:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-192-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{196},
  editor =	{Brandenburg, Bj\"{o}rn B.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2021.5},
  URN =		{urn:nbn:de:0030-drops-139363},
  doi =		{10.4230/LIPIcs.ECRTS.2021.5},
  annote =	{Keywords: Real-Time Embedded Systems, Systems-on-Chips, Network-on-Chips, Worst-Case Communication Time}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2019.21
Response-Time Analysis of Limited-Preemptive Parallel DAG Tasks Under Global Scheduling

Authors: Mitra Nasri, Geoffrey Nelissen, and Björn B. Brandenburg

Published in: LIPIcs, Volume 133, 31st Euromicro Conference on Real-Time Systems (ECRTS 2019)

Abstract
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.
Cite as

Mitra Nasri, Geoffrey Nelissen, and Björn B. Brandenburg. Response-Time Analysis of Limited-Preemptive Parallel DAG Tasks Under Global Scheduling. In 31st Euromicro Conference on Real-Time Systems (ECRTS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 133, pp. 21:1-21:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{nasri_et_al:LIPIcs.ECRTS.2019.21,
  author =	{Nasri, Mitra and Nelissen, Geoffrey and Brandenburg, Bj\"{o}rn B.},
  title =	{{Response-Time Analysis of Limited-Preemptive Parallel DAG Tasks Under Global Scheduling}},
  booktitle =	{31st Euromicro Conference on Real-Time Systems (ECRTS 2019)},
  pages =	{21:1--21:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-110-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{133},
  editor =	{Quinton, Sophie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2019.21},
  URN =		{urn:nbn:de:0030-drops-107587},
  doi =		{10.4230/LIPIcs.ECRTS.2019.21},
  annote =	{Keywords: parallel DAG tasks, global multiprocessor scheduling, schedulability analysis, non-preemptive jobs, precedence constraints, worst-case response time, OpenMP}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2018.9
A Response-Time Analysis for Non-Preemptive Job Sets under Global Scheduling

Authors: Mitra Nasri, Geoffrey Nelissen, and Björn B. Brandenburg

Published in: LIPIcs, Volume 106, 30th Euromicro Conference on Real-Time Systems (ECRTS 2018)

Abstract
An effective way to increase the timing predictability of multicore platforms is to use non-preemptive scheduling. It reduces preemption and job migration overheads, avoids intra-core cache interference, and improves the accuracy of worst-case execution time (WCET) estimates. However, existing schedulability tests for global non-preemptive multiprocessor scheduling are pessimistic, especially when applied to periodic workloads. This paper reduces this pessimism by introducing a new type of sufficient schedulability analysis that is based on an exploration of the space of possible schedules using concise abstractions and state-pruning techniques. Specifically, we analyze the schedulability of non-preemptive job sets (with bounded release jitter and execution time variation) scheduled by a global job-level fixed-priority (JLFP) scheduling algorithm upon an identical multicore platform. The analysis yields a lower bound on the best-case response-time (BCRT) and an upper bound on the worst-case response time (WCRT) of the jobs. In an empirical evaluation with randomly generated workloads, we show that the method scales to 30 tasks, a hundred thousand jobs (per hyperperiod), and up to 9 cores.
Cite as

Mitra Nasri, Geoffrey Nelissen, and Björn B. Brandenburg. A Response-Time Analysis for Non-Preemptive Job Sets under Global Scheduling. In 30th Euromicro Conference on Real-Time Systems (ECRTS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 106, pp. 9:1-9:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{nasri_et_al:LIPIcs.ECRTS.2018.9,
  author =	{Nasri, Mitra and Nelissen, Geoffrey and Brandenburg, Bj\"{o}rn B.},
  title =	{{A Response-Time Analysis for Non-Preemptive Job Sets under Global Scheduling}},
  booktitle =	{30th Euromicro Conference on Real-Time Systems (ECRTS 2018)},
  pages =	{9:1--9:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-075-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{106},
  editor =	{Altmeyer, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2018.9},
  URN =		{urn:nbn:de:0030-drops-89941},
  doi =		{10.4230/LIPIcs.ECRTS.2018.9},
  annote =	{Keywords: global multiprocessor scheduling, schedulability analysis, non-preemptive tasks, worst-case response time, best-case response time}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2018.26
On Strong and Weak Sustainability, with an Application to Self-Suspending Real-Time Tasks

Authors: Felipe Cerqueira, Geoffrey Nelissen, and Björn B. Brandenburg

Published in: LIPIcs, Volume 106, 30th Euromicro Conference on Real-Time Systems (ECRTS 2018)

Abstract
Motivated by an apparent contradiction regarding whether certain scheduling policies are sustainable, we revisit the topic of sustainability in real-time scheduling and argue that the existing definitions of sustainability should be further clarified and generalized. After proposing a formal, generic sustainability theory, we relax the existing notion of (strongly) sustainable scheduling policy to provide a new classification called weak sustainability. Proving weak sustainability properties allows reducing the number of variables that must be considered in the search of a worst-case schedule, and hence enables more efficient schedulability analyses and testing regimes even for policies that are not (strongly) sustainable. As a proof of concept, and to better understand a model for which many mistakes were found in the literature, we study weak sustainability in the context of dynamic self-suspending tasks, where we formalize a generic suspension model using the Coq proof assistant and provide a machine-checked proof that any JLFP scheduling policy is weakly sustainable with respect to job costs and variable suspension times.
Cite as

Felipe Cerqueira, Geoffrey Nelissen, and Björn B. Brandenburg. On Strong and Weak Sustainability, with an Application to Self-Suspending Real-Time Tasks. In 30th Euromicro Conference on Real-Time Systems (ECRTS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 106, pp. 26:1-26:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{cerqueira_et_al:LIPIcs.ECRTS.2018.26,
  author =	{Cerqueira, Felipe and Nelissen, Geoffrey and Brandenburg, Bj\"{o}rn B.},
  title =	{{On Strong and Weak Sustainability, with an Application to Self-Suspending Real-Time Tasks}},
  booktitle =	{30th Euromicro Conference on Real-Time Systems (ECRTS 2018)},
  pages =	{26:1--26:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-075-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{106},
  editor =	{Altmeyer, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2018.26},
  URN =		{urn:nbn:de:0030-drops-89773},
  doi =		{10.4230/LIPIcs.ECRTS.2018.26},
  annote =	{Keywords: real-time scheduling, sustainability, self-suspending tasks, machine-checked proofs}
}
  • Refine by Type
  • 18 Document/PDF
  • 6 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 5 2025
  • 1 2024
  • 1 2023
  • 3 2022
  • Show More...

  • Refine by Author
  • 10 Nelissen, Geoffrey
  • 4 Brandenburg, Björn B.
  • 3 Aromolo, Federico
  • 3 Biondi, Alessandro
  • 3 Chen, Jian-Jia
  • Show More...

  • Refine by Series/Journal
  • 10 LIPIcs
  • 3 OASIcs
  • 1 DARTS
  • 4 LITES

  • Refine by Classification
  • 14 Computer systems organization → Real-time systems
  • 8 Software and its engineering → Real-time schedulability
  • 4 Computer systems organization → Embedded software
  • 3 Computer systems organization → Real-time system specification
  • 1 Computer systems organization → Embedded and cyber-physical systems
  • Show More...

  • Refine by Keyword
  • 3 Real-Time Systems
  • 3 Schedulability Analysis
  • 3 schedulability analysis
  • 2 Arm
  • 2 EDF Scheduling
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact