License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ECRTS.2017.14
URN: urn:nbn:de:0030-drops-71642
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7164/
Go to the corresponding LIPIcs Volume Portal

Nguyen, Viet Anh ; Hardy, Damien ; Puaut, Isabelle

Cache-Conscious Offline Real-Time Task Scheduling for Multi-Core Processors

pdf-format:
LIPIcs-ECRTS-2017-14.pdf (0.9 MB)

Abstract

Most schedulability analysis techniques for multi-core architectures assume a single Worst-Case Execution Time (WCET) per task, which is valid in all execution conditions. This assumption is too pessimistic for parallel applications running on multi-core architectures with local instruction or data caches, for which the WCET of a task depends on the cache contents at the beginning of its execution, itself depending on the task that was executed before the task under study.

In this paper, we propose two scheduling techniques for multi-core architectures equipped with local instruction and data caches. The two techniques schedule a parallel application modeled as a task graph, and generate a static partitioned non-preemptive schedule. We propose an optimal method, using an Integer Linear Programming (ILP) formulation, as well as a heuristic method based on list scheduling. Experimental results show that by taking into account the effect of private caches on tasks' WCETs, the length of generated schedules is significantly reduced as compared to schedules generated by cache-unaware scheduling methods. The observed schedule length reduction on streaming applications is 11% on average for the optimal method and 9% on average for the heuristic method.

BibTeX - Entry

@InProceedings{nguyen_et_al:LIPIcs:2017:7164,
  author =	{Viet Anh Nguyen and Damien Hardy and Isabelle Puaut},
  title =	{{Cache-Conscious Offline Real-Time Task Scheduling for Multi-Core Processors}},
  booktitle =	{29th Euromicro Conference on Real-Time Systems (ECRTS 2017)},
  pages =	{14:1--14:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-037-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{76},
  editor =	{Marko Bertogna},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7164},
  URN =		{urn:nbn:de:0030-drops-71642},
  doi =		{10.4230/LIPIcs.ECRTS.2017.14},
  annote =	{Keywords: Real-time scheduling, Cache-conscious scheduling, Many-core architectures, ILP, Static list scheduling}
}

Keywords: Real-time scheduling, Cache-conscious scheduling, Many-core architectures, ILP, Static list scheduling
Collection: 29th Euromicro Conference on Real-Time Systems (ECRTS 2017)
Issue Date: 2017
Date of publication: 23.06.2017

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