DROPS

Document

DOI: 10.4230/LIPIcs.CONCUR.2018.23

GPU Schedulers: How Fair Is Fair Enough?

Authors: Tyler Sorensen, Hugues Evrard, and Alastair F. Donaldson

Published in: LIPIcs, Volume 118, 29th International Conference on Concurrency Theory (CONCUR 2018)

Abstract

Blocking synchronisation idioms, e.g. mutexes and barriers, play an important role in concurrent programming. However, systems with semi-fair schedulers, e.g. graphics processing units (GPUs), are becoming increasingly common. Such schedulers provide varying degrees of fairness, guaranteeing enough to allow some, but not all, blocking idioms. While a number of applications that use blocking idioms do run on today's GPUs, reasoning about liveness properties of such applications is difficult as documentation is scarce and scattered. In this work, we aim to clarify fairness properties of semi-fair schedulers. To do this, we define a general temporal logic formula, based on weak fairness, parameterised by a predicate that enables fairness per-thread at certain points of an execution. We then define fairness properties for three GPU schedulers: HSA, OpenCL, and occupancy-bound execution. We examine existing GPU applications and show that none of the above schedulers are strong enough to provide the fairness properties required by these applications. It hence appears that existing GPU scheduler descriptions do not entirely capture the fairness properties that are provided on current GPUs. Thus, we present two new schedulers that aim to support existing GPU applications. We analyse the behaviour of common blocking idioms under each scheduler and show that one of our new schedulers allows a more natural implementation of a GPU protocol.

Cite as

Tyler Sorensen, Hugues Evrard, and Alastair F. Donaldson. GPU Schedulers: How Fair Is Fair Enough?. In 29th International Conference on Concurrency Theory (CONCUR 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 118, pp. 23:1-23:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{sorensen_et_al:LIPIcs.CONCUR.2018.23,
  author =	{Sorensen, Tyler and Evrard, Hugues and Donaldson, Alastair F.},
  title =	{{GPU Schedulers: How Fair Is Fair Enough?}},
  booktitle =	{29th International Conference on Concurrency Theory (CONCUR 2018)},
  pages =	{23:1--23:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-087-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{118},
  editor =	{Schewe, Sven and Zhang, Lijun},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2018.23},
  URN =		{urn:nbn:de:0030-drops-95619},
  doi =		{10.4230/LIPIcs.CONCUR.2018.23},
  annote =	{Keywords: GPU scheduling, Blocking synchronisation, GPU semantics}
}

Document

Invited Talk

DOI: 10.4230/LIPIcs.CONCUR.2017.1

Forward Progress on GPU Concurrency (Invited Talk)

Authors: Alastair F. Donaldson, Jeroen Ketema, Tyler Sorensen, and John Wickerson

Published in: LIPIcs, Volume 85, 28th International Conference on Concurrency Theory (CONCUR 2017)

Abstract

The tutorial at CONCUR will provide a practical overview of work undertaken over the last six years in the Multicore Programming Group at Imperial College London, and with collaborators internationally, related to understanding and reasoning about concurrency in software designed for acceleration on GPUs. In this article we provide an overview of this work, which includes contributions to data race analysis, compiler testing, memory model understanding and formalisation, and most recently efforts to enable portable GPU implementations of algorithms that require forward progress guarantees.

Cite as

Alastair F. Donaldson, Jeroen Ketema, Tyler Sorensen, and John Wickerson. Forward Progress on GPU Concurrency (Invited Talk). In 28th International Conference on Concurrency Theory (CONCUR 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 85, pp. 1:1-1:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{donaldson_et_al:LIPIcs.CONCUR.2017.1,
  author =	{Donaldson, Alastair F. and Ketema, Jeroen and Sorensen, Tyler and Wickerson, John},
  title =	{{Forward Progress on GPU Concurrency}},
  booktitle =	{28th International Conference on Concurrency Theory (CONCUR 2017)},
  pages =	{1:1--1:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-048-4},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{85},
  editor =	{Meyer, Roland and Nestmann, Uwe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2017.1},
  URN =		{urn:nbn:de:0030-drops-78055},
  doi =		{10.4230/LIPIcs.CONCUR.2017.1},
  annote =	{Keywords: GPUs, concurrency, formal verification, memory models, data races}
}

Search Results

Documents authored by Sorensen, Tyler

GPU Schedulers: How Fair Is Fair Enough?

Abstract

Cite as

Forward Progress on GPU Concurrency (Invited Talk)

Abstract

Cite as

Thanks for your feedback!

Could not send message