TU Berlin

Internet Network ArchitecturesPublications by Type: Conference and Workshop Papers


zur Navigation

Es gibt keine deutsche Übersetzung dieser Webseite.

Publications by Type: Conference and Workshop Publications

see also conference papers, workshop papers, demos, and posters. (under construction)

Laws of Order: Expensive Synchronization in Concurrent Algorithms Cannot be Eliminated
Zitatschlüssel AHGKMV-LOESCACBE-11
Autor Attiya, Hagit and Hendler, Danny and Guerraoui, Rachid and Kuznetsov, Petr and Michael, Maged M. and Vechev, Martin
Buchtitel Proceedings of Symposium on Principles of Programming Languages (POPL '11)
Seiten 487–498
Jahr 2011
ISBN 978-1-4503-0490-0
DOI http://dx.doi.org/10.1145/1926385.1926442
Ort Austin, TX, USA
Adresse New York, NY, USA
Monat January
Verlag ACM
Organisation SIGACT / SIGPLAN
Zusammenfassung Building correct and efficient concurrent algorithms is known to be a difficult problem of fundamental importance. To achieve efficiency, designers spend significant time trying to remove unnecessary and costly synchronization. However, not only is this manual trial-and-error process ad-hoc and error-prone, but it often leaves designers pondering the question of: is it inherently impossible to eliminate certain synchronization, or is it that I was unable to eliminate it on this attempt and I should keep trying? In this paper we respond to this question. We prove that it is impossible to build correct concurrent implementations of classic and ubiquitous specifications such as sets, queues, stacks, mutual exclusion and read-modify-write operations, that completely eliminate certain expensive synchronization. More specifically, we prove that one cannot avoid the use of: i) read-after-write (RAW), where a write to shared variable A is followed by a read to a different shared variable B or ii) atomic write-after-read (AWAR), where an atomic operation reads and then writes to shared locations. Unfortunately, enforcing any of these two patterns is expensive on virtually all mainstream processor architectures today. To enforce RAW, memory ordering–also called fence or barrier–instructions must be used. To enforce AWAR, atomic instructions such as compare-and-swap (or equivalent) are required. However, fences and atomic instructions are typically substantially slower–around 50 times–than regular instructions! Although designers of concurrent algorithms frequently struggle to avoid RAW and AWAR, their attempts are often futile. Our result explains exactly in which cases avoiding RAWand AWAR is impossible. Failure to use such synchronization will mean that the algorithm is incorrect and there is no need to even attempt to verify its correctness. On the flip side, our result indicates on which data structures designers can focus their efforts on.
Link zur Publikation Download Bibtex Eintrag



Schnellnavigation zur Seite über Nummerneingabe