DROPS

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}
}

Search Results

Documents authored by Marcè i Igual, Joan

Response-Time Analysis for Non-Preemptive Periodic Moldable Gang Tasks

Abstract

Cite as

Thanks for your feedback!

Could not send message