nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

Scalable FIFO Channels for Programming via Communicating Sequential Processes

verfasst von : Nikita Koval, Dan Alistarh, Roman Elizarov

Erschienen in: Euro-Par 2019: Parallel Processing

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Traditional concurrent programming involves manipulating shared mutable state. Alternatives to this programming style are communicating sequential processes (CSP) and actor models, which share data via explicit communication. These models have been known for almost half a century, and have recently had started to gain significant traction among modern programming languages. The common abstraction for communication between several processes is the channel. Although channels are similar to producer-consumer data structures, they have different semantics and support additional operations, such as the select expression. Despite their growing popularity, most known implementations of channels use lock-based data structures and can be rather inefficient.

In this paper, we present the first efficient lock-free algorithm for implementing a communication channel for CSP programming. We provide implementations and experimental results in the Kotlin and Go programming languages. Our new algorithm outperforms existing implementations on many workloads, while providing non-blocking progress guarantee. Our design can serve as an example of how to construct general communication data structures for CSP and actor models.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Dataflow Execution of Hierarchically Tiled Arrays

Nächstes Kapitel TWA – Ticket Locks Augmented with a Waiting Array

CSP is broadly similar to the actor model [12], with key distinctions in terms of the basic assumptions regarding process identities and synchronization.

Go Concurrency Patterns: Pipelines and cancellation - The Go Blog (2014). https://blog.golang.org/pipelines

Akka (2018). https://akka.io/

Erlang Programming Language (2018). http://www.erlang.org/

Kotlin Coroutines (2018). https://github.com/Kotlin/kotlin-coroutines

Livelock bug in the Kotling Coroutine Implementation (2018). https://github.com/Kotlin/kotlinx.coroutines/issues/504

OpenJDK: Loom (2018). http://openjdk.java.net/projects/loom/

The Clojure Programming Language (2018). https://clojure.org/

The Go Programming Language (2018). https://golang.org/

The Rust Programming Language (2018). https://www.rust-lang.org/

10.

Abdallah, A.E.: Communicating Sequential Processes. The First 25 Years. Symposium on the Occasion of 25 Years of CSP, London, UK, 7–8 July 2004. Revised Invited Papers, vol. 3525. Springer, Heidelberg (2005). https://doi.org/10.1007/b136154CrossRef

11.

Afek, Y., Korland, G., Natanzon, M., Shavit, N.: Scalable producer-consumer pools based on elimination-diffraction trees. In: D’Ambra, P., Guarracino, M., Talia, D. (eds.) Euro-Par 2010. LNCS, vol. 6272, pp. 151–162. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15291-7_16CrossRef

12.

Agha, G.A.: Actors: a model of concurrent computation in distributed systems. Technical report, Massachusetts Inst of Tech Cambridge Artificial Intelligence Lab (1985)

13.

Hanson, D.R.: C Interfaces and Implementations: Techniques for Creating Reusable Software. Addison-Wesley Longman Publishing Co., Inc., Boston (1996)

14.

Harris, T.L., Fraser, K., Pratt, I.A.: A practical multi-word compare-and-swap operation. In: Malkhi, D. (ed.) DISC 2002. LNCS, vol. 2508, pp. 265–279. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-36108-1_18CrossRef

15.

Hendler, D., Incze, I., Shavit, N., Tzafrir, M.: Flat combining and the synchronization-parallelism tradeoff. In: Proceedings of the Twenty-Second Annual ACM Symposium on Parallelism in Algorithms and Architectures, pp. 355–364. ACM (2010)

16.

Hendler, D., Incze, I., Shavit, N., Tzafrir, M.: Scalable flat-combining based synchronous queues. In: Lynch, N.A., Shvartsman, A.A. (eds.) DISC 2010. LNCS, vol. 6343, pp. 79–93. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15763-9_8CrossRef

17.

Herlihy, M., Shavit, N.: The Art of Multiprocessor Programming. Morgan Kaufmann, San Francisco (2011)

18.

Hoare, C.A.R.: Communicating sequential processes. Commun. ACM 21(8), 666–677 (1978)CrossRef

19.

Izraelevitz, J., Scott, M.L.: Generality and speed in nonblocking dual containers. ACM Trans. Parallel Comput. 3(4), 22:1–22:37 (2017). https://doi.org/10.1145/3040220. http://doi.acm.org/10.1145/3040220CrossRef

20.

Kahn, G., MacQueen, D.: Coroutines and networks of parallel processes (1976)

21.

Koval, N., Alistarh, D., Elizarov, R.: Channel implementations in go and kotlin. https://doi.org/10.6084/m9.figshare.8586311

22.

Michael, M.M.: Hazard pointers: safe memory reclamation for lock-free objects. IEEE Trans. Parallel Distrib. Syst. 6, 491–504 (2004)CrossRef

23.

Michael, M.M., Scott, M.L.: Simple, fast, and practical non-blocking and blocking concurrent queue algorithms. In: Proceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing, pp. 267–275. ACM (1996)

24.

Morrison, A., Afek, Y.: Fast concurrent queues for x86 processors. In: ACM SIGPLAN Notices, vol. 48, pp. 103–112. ACM (2013)

25.

Odersky, M., et al.: The scala language specification (2007)

26.

Scherer III, W.N., Lea, D., Scott, M.L.: A scalable elimination-based exchange channel. In: SCOOL 2005, p. 83 (2005)

27.

Scherer III, W.N., Lea, D., Scott, M.L.: Scalable synchronous queues. In: Proceedings of the Eleventh ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pp. 147–156. ACM (2006)

28.

Scherer III, W., Scott, M.: Nonblocking concurrent objects with condition synchronization. In: Proceedings of the 18th International Symposium on Distributed Computing (2004)

29.

Shavit, N., Touitou, D.: Elimination trees and the construction of pools and stacks: preliminary version. In: Proceedings of the Seventh Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 54–63. ACM (1995)

30.

Shavit, N., Zemach, A.: Combining funnels: a dynamic approach to software combining. J. Parallel Distrib. Comput. 60(11), 1355–1387 (2000)CrossRef

31.

Sundell, H., Tsigas, P.: Lock-free and practical doubly linked list-based deques using single-word compare-and-swap. In: Higashino, T. (ed.) OPODIS 2004. LNCS, vol. 3544, pp. 240–255. Springer, Heidelberg (2005). https://doi.org/10.1007/11516798_18CrossRefMATH

Titel: Scalable FIFO Channels for Programming via Communicating Sequential Processes
verfasst von: Nikita Koval
Dan Alistarh
Roman Elizarov
Verlag: Springer International Publishing
Buch: Euro-Par 2019: Parallel Processing
Print ISBN: 978-3-030-29399-4

Electronic ISBN: 978-3-030-29400-7

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-030-29400-7_23

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"