Efficient lock‐step synchronization in task‐parallel languages. (1st July 2019)

• Record Type: Journal Article
• Authors: Utture, Akshay; Nandivada, V Krishna
• Is Part Of: Software, practice & experience. Volume 49:Number 9(2019)
• Page Start: 1379
• Page End: 1401
• Publication Date: 2019-07-01
• Subjects: lock‐step synchronization -- task‐parallel languages -- runtime optimizations; Computer software -- Periodicals; Computer programming -- Periodicals; Computer programs -- Periodicals; 005.3
• DOI: 10.1002/spe.2726
• Languages: English
• ISSNs: 0038-0644

Abstract

Summary: Many modern task‐parallel languages allow the programmer to synchronize tasks using high‐level constructs like barriers, clocks, and phasers. While these high‐level synchronization primitives help the programmer express the program logic in a convenient manner, they also have their associated overheads. In this paper, we identify the sources of some of these overheads for task‐parallel languages like X10 that support lock‐step synchronization, and propose a mechanism to reduce these overheads. We first propose three desirable properties that an efficient runtime (for task‐parallel languages like X10, HJ, Chapel, and so on) should satisfy, to minimize the overheads during lock‐step synchronization. We use these properties to derive a scheme to called uClocks to improve the efficiency of X10 clocks; uClocks consists of an extension to X10 clocks and two related runtime optimizations. We prove that uClocks satisfies the proposed desirable properties. We have implemented uClocks for the X10 language+runtime and show that the resulting system leads to a geometric mean speedup of 5.36× on a 16‐core Intel system and 11.39× on a 64‐core AMD system, for benchmarks with a significant number of synchronization operations.