[2013-SOSP]Everything You AlwaysWanted to Know About Synchronization but Were Afraid to Ask.pdf

Everything You Always Wanted to Know About Synchronization but Were Afraid to Ask Tudor David, Rachid Guerraoui, Vasileios Trigonakis? School of Computer and Communication Sciences, E?cole Polytechnique Fe?de?rale de Lausanne (EPFL), Switzerland {tudor.david, rachid.guerraoui, vasileios.trigonakis}@epfl.ch Abstract This paper presents the most exhaustive study of syn- chronization to date. We span multiple layers, from hardware cache-coherence protocols up to high-level concurrent software. We do so on different types of architectures, from single-socket – uniform and non- uniform – to multi-socket – directory and broadcast- based – many-cores. We draw a set of observations that, roughly speaking, imply that scalability of synchroniza- tion is mainly a property of the hardware. 1 Introduction Scaling software systems to many-core architectures is one of the most important challenges in computing to- day. A major impediment to scalability is synchroniza- tion. From the Greek “syn”, i.e., with, and “khronos”, i.e., time, synchronization denotes the act of coordinat- ing the timeline of a set of processes. Synchronization basically translates into cores slowing each other, some- times affecting performance to the point of annihilating the overall purpose of increasing their number [3, 21]. A synchronization scheme is said to scale if its per- formance does not degrade as the number of cores in- creases. Ideally, acquiring a lock should for example take the same time regardless of the number of cores sharing that lock. In the last few decades, a large body of work has been devoted to the design, implemen- tation, evaluation, and application of synchronization schemes [1, 4, 6, 7, 10, 11, 14, 15, 26–29, 38–40, 43– 45]. Yet, the designer of a concurrent system still has ?Authors appear in alphabetical order. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distri