文章基本信息

标题：Polynomial-Time Fence Insertion for Structured Programs
本地全文：下载
作者：Mohammad Taheri ; Arash Pourdamghani ; Mohsen Lesani 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：146
页码：1-17
DOI：10.4230/LIPIcs.DISC.2019.34
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Fence Insertion; Synchronization; Concurrent Programming