DROPS

Document

DOI: 10.4230/LIPIcs.DISC.2019.34

Polynomial-Time Fence Insertion for Structured Programs

Authors: Mohammad Taheri, Arash Pourdamghani, and Mohsen Lesani

Published in: LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019)

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.

Cite as

Mohammad Taheri, Arash Pourdamghani, and Mohsen Lesani. Polynomial-Time Fence Insertion for Structured Programs. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 34:1-34:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{taheri_et_al:LIPIcs.DISC.2019.34,
  author =	{Taheri, Mohammad and Pourdamghani, Arash and Lesani, Mohsen},
  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 =	{Suomela, Jukka},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.34},
  URN =		{urn:nbn:de:0030-drops-113412},
  doi =		{10.4230/LIPIcs.DISC.2019.34},
  annote =	{Keywords: Fence Insertion, Synchronization, Concurrent Programming}
}

Search Results

Documents authored by Taheri, Mohammad

Polynomial-Time Fence Insertion for Structured Programs

Abstract

Cite as

Thanks for your feedback!

Could not send message