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.DISC.2019.34
URN: urn:nbn:de:0030-drops-113412
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11341/
Go to the corresponding LIPIcs Volume Portal

Taheri, Mohammad ; Pourdamghani, Arash ; Lesani, Mohsen

Polynomial-Time Fence Insertion for Structured Programs

pdf-format:
LIPIcs-DISC-2019-34.pdf (1.0 MB)

Abstract

To enhance performance, common processors feature relaxed memory models that reorder instructions. However, the correctness of concurrent programs is often dependent on the preservation of the program order of certain instructions. Thus, the instruction set architectures offer memory fences. Using fences is a subtle task with performance and correctness implications: using too few can compromise correctness and using too many can hinder performance. Thus, fence insertion algorithms that given the required program orders can automatically find the optimum fencing can enhance the ease of programming, reliability, and performance of concurrent programs. In this paper, we consider the class of programs with structured branch and loop statements and present a greedy and polynomial-time optimum fence insertion algorithm. The algorithm incrementally reduces fence insertion for a control-flow graph to fence insertion for a set of paths. In addition, we show that the minimum fence insertion problem with multiple types of fence instructions is NP-hard even for straight-line programs.

BibTeX - Entry

@InProceedings{taheri_et_al:LIPIcs:2019:11341,
  author =	{Mohammad Taheri and Arash Pourdamghani and Mohsen Lesani},
  title =	{{Polynomial-Time Fence Insertion for Structured Programs}},
  booktitle =	{33rd International Symposium on Distributed Computing (DISC 2019)},
  pages =	{34:1--34:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-126-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{146},
  editor =	{Jukka Suomela},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11341},
  URN =		{urn:nbn:de:0030-drops-113412},
  doi =		{10.4230/LIPIcs.DISC.2019.34},
  annote =	{Keywords: Fence Insertion, Synchronization, Concurrent Programming}
}

Keywords: Fence Insertion, Synchronization, Concurrent Programming
Collection: 33rd International Symposium on Distributed Computing (DISC 2019)
Issue Date: 2019
Date of publication: 08.10.2019

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