9 Search Results for "Tovar, Eduardo"

Document
DOI: 10.4230/LIPIcs.DISC.2024.39
The Power of Abstract MAC Layer: A Fault-Tolerance Perspective

Authors: Qinzi Zhang and Lewis Tseng

Published in: LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024)

Abstract
This paper studies the power of the "abstract MAC layer" model in a single-hop asynchronous network. The model captures primitive properties of modern wireless MAC protocols. In this model, Newport [PODC '14] proves that it is impossible to achieve deterministic consensus when nodes may crash. Subsequently, Newport and Robinson [DISC '18] present randomized consensus algorithms that terminate with O(n³ log n) expected broadcasts in a system of n nodes. We are not aware of any results on other fault-tolerant distributed tasks in this model. We first study the computability aspect of the abstract MAC layer. We present a wait-free algorithm that implements an atomic register. Furthermore, we show that in general, k-set consensus is impossible. Second, we aim to minimize storage complexity. Existing algorithms require Ω(n log n) bits. We propose two wait-free approximate consensus and two wait-free randomized binary consensus algorithms that only need constant storage complexity (except for the phase index). One randomized algorithm terminates with O(n log n) expected broadcasts. All our algorithms are anonymous, meaning that at the algorithm level, nodes do not need to have a unique identifier.
Cite as

Qinzi Zhang and Lewis Tseng. The Power of Abstract MAC Layer: A Fault-Tolerance Perspective. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 39:1-39:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{zhang_et_al:LIPIcs.DISC.2024.39,
  author =	{Zhang, Qinzi and Tseng, Lewis},
  title =	{{The Power of Abstract MAC Layer: A Fault-Tolerance Perspective}},
  booktitle =	{38th International Symposium on Distributed Computing (DISC 2024)},
  pages =	{39:1--39:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-352-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{319},
  editor =	{Alistarh, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.39},
  URN =		{urn:nbn:de:0030-drops-212677},
  doi =		{10.4230/LIPIcs.DISC.2024.39},
  annote =	{Keywords: Abstract MAC Layer, Computation Power, Consensus}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2024.2
SlackCheck: A Linux Kernel Module to Verify Temporal Properties of a Task Schedule

Authors: Michele Castrovilli and Enrico Bini

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

Abstract
The Linux Kernel offers several scheduling classes. From SCHED_DEADLINE down to SCHED_FIFO, SCHED_RR and SCHED_OTHER, the scheduling classes can provide different responsiveness to very diverse user workloads. Still, Linux does not offer any mechanism to take some action upon the violation of temporal constraints at runtime. The lack of such a feature is also due to the difficulty of extending the established notion of deadline to workloads which are not releasing periodic/sporadic jobs. Exploiting the notion of supply functions for any resource schedule, we implemented SlackCheck, a kernel module which is capable to verify at runtime if a given task is assigned a desired amount of resource or not. SlackCheck adds a constant-time check at every scheduling decision and leverages the recent availability of a Runtime Verification engine in the kernel.
Cite as

Michele Castrovilli and Enrico Bini. SlackCheck: A Linux Kernel Module to Verify Temporal Properties of a Task Schedule. In 36th Euromicro Conference on Real-Time Systems (ECRTS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 298, pp. 2:1-2:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{castrovilli_et_al:LIPIcs.ECRTS.2024.2,
  author =	{Castrovilli, Michele and Bini, Enrico},
  title =	{{SlackCheck: A Linux Kernel Module to Verify Temporal Properties of a Task Schedule}},
  booktitle =	{36th Euromicro Conference on Real-Time Systems (ECRTS 2024)},
  pages =	{2:1--2: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.2},
  URN =		{urn:nbn:de:0030-drops-203054},
  doi =		{10.4230/LIPIcs.ECRTS.2024.2},
  annote =	{Keywords: Linux scheduler, Runtime verification, bounded-delay resource partition, supply function, service curve, real-time calculus, network calculus}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2024.3
Reachability-Based Response-Time Analysis of Preemptive Tasks Under Global Scheduling

Authors: Pourya Gohari, Jeroen Voeten, and Mitra Nasri

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

Abstract
Global scheduling reduces the average response times as it can use the available computing cores more efficiently for scheduling ready tasks. However, this flexibility poses challenges in accurately quantifying interference scenarios, often resulting in either conservative response-time analyses or scalability issues. In this paper, we present a new response-time analysis for preemptive periodic tasks (or job sets) subject to release jitter under global job-level fixed-priority (JLFP) scheduling. Our analysis relies on the notion of schedule-abstraction graph (SAG), a reachability-based response-time analysis known for its potential accuracy and efficiency. Up to this point, SAG was limited to non-preemptive tasks due to the complexity of handling preemption when the number of preemptions and the moments they occur are not known beforehand. In this paper, we introduce the concept of time partitions and demonstrate how it facilitates the extension of SAG for preemptive tasks. Moreover, our paper provides the first response-time analysis for the global EDF(k) policy - a JLFP scheduling policy introduced in 2003 to address the Dhall’s effect. Our experiments show that our analysis is significantly more accurate compared to the state-of-the-art analyses. For example, we identify 12 times more schedulable task sets than existing tests for the global EDF policy (e.g., for systems with 6 to 16 tasks, 70% utilization, and 4 cores) with an average runtime of 30 minutes. We show that EDF(k) outperforms global RM and EDF by scheduling on average 24.9% more task sets (e.g., for systems with 2 to 10 cores and 70% utilization). Moreover, for the first time, we show that global JLFP scheduling policies (particularly, global EDF(k)) are able to schedule task sets that are not schedulable using well-known partitioning heuristics.
Cite as

Pourya Gohari, Jeroen Voeten, and Mitra Nasri. Reachability-Based Response-Time Analysis of Preemptive Tasks Under Global Scheduling. In 36th Euromicro Conference on Real-Time Systems (ECRTS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 298, pp. 3:1-3:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gohari_et_al:LIPIcs.ECRTS.2024.3,
  author =	{Gohari, Pourya and Voeten, Jeroen and Nasri, Mitra},
  title =	{{Reachability-Based Response-Time Analysis of Preemptive Tasks Under Global Scheduling}},
  booktitle =	{36th Euromicro Conference on Real-Time Systems (ECRTS 2024)},
  pages =	{3:1--3: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.3},
  URN =		{urn:nbn:de:0030-drops-203064},
  doi =		{10.4230/LIPIcs.ECRTS.2024.3},
  annote =	{Keywords: Response-time analysis, global scheduling, preemptive, job-level fixed-priority scheduling policy, multicore, schedule-abstraction graph}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2024.17
Response Time Analysis for Fixed-Priority Preemptive Uniform Multiprocessor Systems

Authors: Binqi Sun, Tomasz Kloda, and Marco Caccamo

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

Abstract
We present a response time analysis for global fixed-priority preemptive scheduling of constrained-deadline tasks upon a uniform multiprocessor where each processor can be characterized by a different speed. A fixed-priority scheduler assigns the jobs with the highest priorities to the fastest processors. Since determining whether all tasks can meet their deadlines is generally intractable even with identical processors, we propose two sufficient schedulability tests that calculate upper bounds on the task’s worst-case response time within polynomial and pseudo-polynomial time. The proposed tests leverage the linear programming model to upper bound the interference of the higher-priority tasks. Furthermore, we identify specific conditions and platforms upon which the problem can be solved more efficiently within linear time. These formulations are used to iteratively evaluate and refine possible solutions until a safe upper bound on the task’s worst-case response time is found. Additionally, we demonstrate that, with specific minor modifications, the proposed tests are compatible with Audsley’s optimal priority assignment. Experimental evaluations performed on synthetic task sets show that the proposed approach outperforms the state-of-the-art methods.
Cite as

Binqi Sun, Tomasz Kloda, and Marco Caccamo. Response Time Analysis for Fixed-Priority Preemptive Uniform Multiprocessor Systems. In 36th Euromicro Conference on Real-Time Systems (ECRTS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 298, pp. 17:1-17:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{sun_et_al:LIPIcs.ECRTS.2024.17,
  author =	{Sun, Binqi and Kloda, Tomasz and Caccamo, Marco},
  title =	{{Response Time Analysis for Fixed-Priority Preemptive Uniform Multiprocessor Systems}},
  booktitle =	{36th Euromicro Conference on Real-Time Systems (ECRTS 2024)},
  pages =	{17:1--17: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.17},
  URN =		{urn:nbn:de:0030-drops-203201},
  doi =		{10.4230/LIPIcs.ECRTS.2024.17},
  annote =	{Keywords: Real-time scheduling, Uniform multiprocessor, Response time analysis}
}
Document
Invited Paper
DOI: 10.4230/OASIcs.NG-RES.2024.3
DynaVLC - Towards Dynamic GTS Allocation in VLC Networks (Invited Paper)

Authors: Harrison Kurunathan, Miguel Gutiérrez Gaitán, Ramiro Sámano-Robles, and Eduardo Tovar

Published in: OASIcs, Volume 117, Fifth Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2024)

Abstract
Envisioned to deliver superior Quality of Service (QoS) by offering faster data rates and reduced latency in 6G communication scenarios, pioneering communication protocols like the IEEE 802.15.7 are poised to facilitate emerging application trends (e.g. metaverse). The IEEE 802.15.7 standard that supports visible light communication (VLC) provides determinism for time-critical reliable communication through its guaranteed time-slots mechanism of the contention-free period (CFP) while supporting non-time-critical communication through contention-access period (CAP). Nevertheless, the IEEE 802.15.7 MAC structure is fixed and statically defined at the beginning of the network creation. This rigid definition of the network can be detrimental when the traffic characteristics evolve dynamically, for example, due to environmental or user-driven workload conditions. To this purpose, this paper proposes a resource-aware dynamic architecture for IEEE 802.15.7 networks that efficiently adapts the superframe structure to traffic dynamics. Notably, this technique was shown to reduce the overall delay and throughput by up to 45% and 30%, respectively, when compared to the traditional IEEE 802.15.7 protocol performance under the same network conditions.
Cite as

Harrison Kurunathan, Miguel Gutiérrez Gaitán, Ramiro Sámano-Robles, and Eduardo Tovar. DynaVLC - Towards Dynamic GTS Allocation in VLC Networks (Invited Paper). In Fifth Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2024). Open Access Series in Informatics (OASIcs), Volume 117, pp. 3:1-3:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kurunathan_et_al:OASIcs.NG-RES.2024.3,
  author =	{Kurunathan, Harrison and Gait\'{a}n, Miguel Guti\'{e}rrez and S\'{a}mano-Robles, Ramiro and Tovar, Eduardo},
  title =	{{DynaVLC - Towards Dynamic GTS Allocation in VLC Networks}},
  booktitle =	{Fifth Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2024)},
  pages =	{3:1--3:11},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-313-3},
  ISSN =	{2190-6807},
  year =	{2024},
  volume =	{117},
  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.2024.3},
  URN =		{urn:nbn:de:0030-drops-197069},
  doi =		{10.4230/OASIcs.NG-RES.2024.3},
  annote =	{Keywords: IEEE 802.15.7, VLC networks, network tuning}
}
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.2018.2
Worst-case Stall Analysis for Multicore Architectures with Two Memory Controllers

Authors: Muhammad Ali Awan, Pedro F. Souto, Konstantinos Bletsas, Benny Akesson, and Eduardo Tovar

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

Abstract
In multicore architectures, there is potential for contention between cores when accessing shared resources, such as system memory. Such contention scenarios are challenging to accurately analyse, from a worst-case timing perspective. One way of making memory contention in multicores more amenable to timing analysis is the use of memory regulation mechanisms. It restricts the number of accesses performed by any given core over time by using periodically replenished per-core budgets. Typically, this assumes that all cores access memory via a single shared memory controller. However, ever-increasing bandwidth requirements have brought about architectures with multiple memory controllers. These control accesses to different memory regions and are potentially shared among all cores. While this presents an opportunity to satisfy bandwidth requirements, existing analysis designed for a single memory controller are no longer safe. This work formulates a worst-case memory stall analysis for a memory-regulated multicore with two memory controllers. This stall analysis can be integrated into the schedulability analysis of systems under fixed-priority partitioned scheduling. Five heuristics for assigning tasks and memory budgets to cores in a stall-cognisant manner are also proposed. We experimentally quantify the cost in terms of extra stall for letting all cores benefit from the memory space offered by both controllers, and also evaluate the five heuristics for different system characteristics.
Cite as

Muhammad Ali Awan, Pedro F. Souto, Konstantinos Bletsas, Benny Akesson, and Eduardo Tovar. Worst-case Stall Analysis for Multicore Architectures with Two Memory Controllers. In 30th Euromicro Conference on Real-Time Systems (ECRTS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 106, pp. 2:1-2:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{awan_et_al:LIPIcs.ECRTS.2018.2,
  author =	{Awan, Muhammad Ali and Souto, Pedro F. and Bletsas, Konstantinos and Akesson, Benny and Tovar, Eduardo},
  title =	{{Worst-case Stall Analysis for Multicore Architectures with Two Memory Controllers}},
  booktitle =	{30th Euromicro Conference on Real-Time Systems (ECRTS 2018)},
  pages =	{2:1--2:22},
  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.2},
  URN =		{urn:nbn:de:0030-drops-90025},
  doi =		{10.4230/LIPIcs.ECRTS.2018.2},
  annote =	{Keywords: multiple memory controllers, memory regulation, multicore}
}
Document
DOI: 10.4230/DARTS.4.2.5
Worst-case Stall Analysis for Multicore Architectures with Two Memory Controllers (Artifact)

Authors: Muhammad Ali Awan, Pedro F. Souto, Konstantinos Bletsas, Benny Akesson, and Eduardo Tovar

Published in: DARTS, Volume 4, Issue 2, Special Issue of the 30th Euromicro Conference on Real-Time Systems (ECRTS 2018)

Abstract
This artifact demonstrates the performance of the proposed worst-case memory stall analysis for a memory-regulated multicore with two memory controllers. The memory stall analysis is implemented in Java along with five different stall-cognisant bandwidth-to-core and task-to-core assignment heuristics. It evaluates the performance of these heuristics in terms of schedulability via experiments with synthetic task sets capturing different system characteristics. It also quantifies the cost in terms of extra stall for letting all cores benefit from the memory space offered by both controllers on the given multicore platform.
Cite as

Muhammad Ali Awan, Pedro F. Souto, Konstantinos Bletsas, Benny Akesson, and Eduardo Tovar. Worst-case Stall Analysis for Multicore Architectures with Two Memory Controllers (Artifact). In Special Issue of the 30th Euromicro Conference on Real-Time Systems (ECRTS 2018). Dagstuhl Artifacts Series (DARTS), Volume 4, Issue 2, pp. 5:1-5:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Article{awan_et_al:DARTS.4.2.5,
  author =	{Awan, Muhammad Ali and Souto, Pedro F. and Bletsas, Konstantinos and Akesson, Benny and Tovar, Eduardo},
  title =	{{Worst-case Stall Analysis for Multicore Architectures with Two Memory Controllers (Artifact)}},
  pages =	{5:1--5:3},
  journal =	{Dagstuhl Artifacts Series},
  ISSN =	{2509-8195},
  year =	{2018},
  volume =	{4},
  number =	{2},
  editor =	{Awan, Muhammad Ali and Souto, Pedro F. and Bletsas, Konstantinos and Akesson, Benny and Tovar, Eduardo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DARTS.4.2.5},
  URN =		{urn:nbn:de:0030-drops-89732},
  doi =		{10.4230/DARTS.4.2.5},
  annote =	{Keywords: multiple memory controllers, memory regulation, multicore}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2017.18
Mixed-Criticality Scheduling with Dynamic Redistribution of Shared Cache

Authors: Muhammad Ali Awan, Konstantinos Bletsas, Pedro F. Souto, Benny Akesson, and Eduardo Tovar

Published in: LIPIcs, Volume 76, 29th Euromicro Conference on Real-Time Systems (ECRTS 2017)

Abstract
The design of mixed-criticality systems often involves painful tradeoffs between safety guarantees and performance. However, the use of more detailed architectural models in the design and analysis of scheduling arrangements for mixed-criticality systems can provide greater confidence in the analysis, but also opportunities for better performance. Motivated by this view, we propose an extension of Vestal's model for mixed-criticality multicore systems that (i) accounts for the per-task partitioning of the last-level cache and (ii) supports the dynamic reassignment, for better schedulability, of cache portions initially reserved for lower-criticality tasks to the higher-criticality tasks, when the system switches to high-criticality mode. To this model, we apply partitioned EDF scheduling with Ekberg and Yi's deadline-scaling technique. Our schedulability analysis and scalefactor calculation is cognisant of the cache resources assigned to each task, by using WCET estimates that take into account these resources. It is hence able to leverage the dynamic reconfiguration of the cache partitioning, at mode change, for better performance, in terms of provable schedulability. We also propose heuristics for partitioning the cache in low- and high-criticality mode, that promote schedulability. Our experiments with synthetic task sets, 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.
Cite as

Muhammad Ali Awan, Konstantinos Bletsas, Pedro F. Souto, Benny Akesson, and Eduardo Tovar. Mixed-Criticality Scheduling with Dynamic Redistribution of Shared Cache. In 29th Euromicro Conference on Real-Time Systems (ECRTS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 76, pp. 18:1-18:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{awan_et_al:LIPIcs.ECRTS.2017.18,
  author =	{Awan, Muhammad Ali and Bletsas, Konstantinos and Souto, Pedro F. and Akesson, Benny and Tovar, Eduardo},
  title =	{{Mixed-Criticality Scheduling with Dynamic Redistribution of Shared Cache}},
  booktitle =	{29th Euromicro Conference on Real-Time Systems (ECRTS 2017)},
  pages =	{18:1--18:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-037-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{76},
  editor =	{Bertogna, Marko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2017.18},
  URN =		{urn:nbn:de:0030-drops-71710},
  doi =		{10.4230/LIPIcs.ECRTS.2017.18},
  annote =	{Keywords: Mixed Criticality Scheduling, Vestal Model, Dynamic Redistribution of Shared Cache, Shared Last-level Cache Analysis, Cache-aware Scheduling}
}
  • Refine by Author
  • 5 Tovar, Eduardo
  • 3 Akesson, Benny
  • 3 Awan, Muhammad Ali
  • 3 Bletsas, Konstantinos
  • 3 Souto, Pedro F.
  • Show More...

  • Refine by Classification
  • 5 Computer systems organization → Real-time systems
  • 2 Computer systems organization → Real-time operating systems
  • 2 Software and its engineering → Scheduling
  • 1 Computer systems organization → Real-time system architecture
  • 1 Networks → Network on chip
  • Show More...

  • Refine by Keyword
  • 3 multicore
  • 2 memory regulation
  • 2 multiple memory controllers
  • 1 Abstract MAC Layer
  • 1 Cache-aware Scheduling
  • Show More...

  • Refine by Type
  • 9 document

  • Refine by Publication Year
  • 5 2024
  • 2 2018
  • 1 2017
  • 1 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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