License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ECRTS.2022.12
URN: urn:nbn:de:0030-drops-163293
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16329/
Go to the corresponding LIPIcs Volume Portal

Nelissen, Geoffrey ; Marcè i Igual, Joan ; Nasri, Mitra

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

pdf-format:
LIPIcs-ECRTS-2022-12.pdf (3 MB)

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.

BibTeX - Entry

@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/opus/volltexte/2022/16329},
  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}
}

Keywords: schedulability analysis, response time analysis, moldable gang tasks, rigid gang tasks, schedule abstraction graph, multiprocessor, non-preemptive
Collection: 34th Euromicro Conference on Real-Time Systems (ECRTS 2022)
Issue Date: 2022
Date of publication: 28.06.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI