nach oben

The Journal of Supercomputing

Erschienen in:

27.02.2018

Pardis: a process calculus for parallel and distributed programming in Haskell

verfasst von: Christopher Blöcker, Ulrich Hoffmann

Erschienen in: The Journal of Supercomputing | Ausgabe 4/2018

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Parallel programming and distributed programming involve substantial amounts of boilerplate code for process management and data synchronisation. This leads to increased bug potential and often results in unintended non-deterministic program behaviour. Moreover, algorithmic details are mixed with technical details concerning parallelisation and distribution. Process calculi are formal models for parallel and distributed programming but often leave details open, causing a gap between formal model and implementation. We propose a fully deterministic process calculus for parallel and distributed programming and implement it as a domain-specific language in Haskell to address these problems. We eliminate boilerplate code by abstracting from the exact notion of parallelisation and encapsulating it in the implementation of our process combinators. Furthermore, we achieve correctness guarantees regarding process composition at compile time through Haskell’s type system. Our result can be used as a high-level tool to implement parallel and distributed programs.

Vorheriger Artikel Language-based vectorization and parallelization using intrinsics, OpenMP, TBB and Cilk Plus

Nächster Artikel Actor model of Anemone functional language

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

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

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+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

To be precise, there is an undefined value \(\bot _a\) for every type a, e.g. we have \(Bool = \left\{ \bot _{Bool}, false, true \right\} \). We omit the type index since it shall be clear from context.

NFData stands for normal form data and values of data types with an instance of NFData can be fully evaluated. Haskell’s evaluation strategy is lazy evaluation, i.e. values are only evaluated if they are needed. However, through NFData we can enforce full evaluation in parallel to benefit from parallelisation.

Roughly speaking, a closure is a data structure that contains an executable computation together with inputs for that computation.

We assume there is a way to obtain a node but omit node management for brevity.

Note that there is a difference between Pardis processes and Cloud Haskell processes.

https://github.com/chrisbloecker/pardis.

Belikov E, Deligiannis P, Totoo P, Aljabri M, Loidl HW (2013) A survey of high-level parallel programming models. Technical Report HW-MACS-TR-0103, Department of Computer Science, Heriot-Watt University

Bocchino RL Jr, Adve VS, Adve SV, Snir M (2009) Parallel programming must be deterministic by default. In: Proceedings of the First USENIX Conference on Hot Topics in Parallelism, HotPar’09, USENIX Association, Berkeley, CA, USA, pp 4–4. http://dl.acm.org/citation.cfm?id=1855591.1855595

Chakravarty MM, Keller G, Lee S, McDonell TL, Grover V (2011) Accelerating Haskell array codes with multicore GPUs. In: Proceedings of the sixth workshop on declarative aspects of multicore programming, DAMP ’11, ACM, New York, NY, USA, pp 3–14. http://doi.acm.org/10.1145/1926354.1926358

Coutts D, LÃűh, A (2012) Deterministic parallel programming with Haskell. Comput Sci Eng 14(6):36–43

Epstein J, Black AP, Peyton-Jones S (2011) Towards Haskell in the cloud. In: Proceedings of the 4th ACM symposium on Haskell, Haskell ’11, ACM, New York, NY, USA, pp 118–129. http://doi.acm.org/10.1145/2034675.2034690

Gorlatch S (2004) Send-receive considered harmful: myths and realities of message passing. ACM Trans. Program. Lang. Syst. 26(1):47–56. https://doi.org/10.1145/963778.963780 MathSciNetCrossRef

Harris T, Marlow S, Peyton-Jones S, Herlihy M (2005) Composable memory transactions. In: Proceedings of the tenth ACM SIGPLAN symposium on principles and practice of parallel programming, PPoPP ’05, ACM, New York, NY, USA, pp 48–60. http://doi.acm.org/10.1145/1065944.1065952

Hoare CAR (1985) Communicating sequential processes. Prentice-Hall Inc, Upper Saddle RiverMATH

Hoare T, van Staden S (2012) The laws of programming unify process calculi. In: Proceedings of the 11th International Conference on Mathematics of Program Construction, MPC’12, Springer-Verlag, Berlin, Heidelberg, pp 7–22. http://dx.doi.org/10.1007/978-3-642-31113-0_2

10.

Hughes J (2000) Generalising monads to arrows. Sci. Comput. Program 37(1–3):67–111. https://doi.org/10.1016/S0167-6423(99)00023-4 MathSciNetCrossRefMATH

11.

Lee EA (2006) The problem with threads. Computer 39(5):33–42. https://doi.org/10.1109/MC.2006.180 CrossRef

12.

Marlow S (2012) Parallel and concurrent programming in Haskell. In: Proceedings of the 4th summer school conference on central European functional programming school, CEFP’11, Springer-Verlag, Berlin, Heidelberg, pp 339–401. http://dx.doi.org/10.1007/978-3-642-32096-5_7

13.

Marlow S, Maier P, Loidl HW, Aswad MK, Trinder P (2010) Seq no more: better strategies for parallel Haskell. In: Proceedings of the third ACM Haskell symposium on Haskell, Haskell ’10, ACM, New York, NY, USA, pp 91–102. http://doi.acm.org/10.1145/1863523.1863535

14.

Marlow S, Newton R, Peyton Jones S (2011) A monad for deterministic parallelism. In: Proceedings of the 4th ACM symposium on Haskell, Haskell ’11, ACM, New York, NY, USA, pp 71–82. http://doi.acm.org/10.1145/2034675.2034685

15.

Milner R (1982) A calculus of communicating systems. Springer-Verlag New York Inc, SecaucusMATH

16.

Peyton Jones S, Gordon A, Finne S (1996) Concurrent Haskell. In: Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on principles of programming languages, POPL ’96, ACM, New York, NY, USA, pp 295–308.http://doi.acm.org/10.1145/237721.237794

17.

Peyton Jones S, Washburn G, Weirich S (2004) Wobbly types: type inference for generalised algebraic data types. Technical Report of MS-CIS-05-26, University of Pennsylvania, Computer and Information Science Department, Levine Hall, 3330 Walnut Street, Philadelphia, Pennsylvania, 19104-6389

18.

Schmidt DA (1986) Denotational semantics: a methodology for language development. William C. Brown Publishers, Dubuque

19.

Schrijvers T, Peyton Jones S, Chakravarty M, Sulzmann M (2008) Type checking with open type functions. SIGPLAN Not 43(9):51–62. https://doi.org/10.1145/1411203.1411215 CrossRefMATH

20.

Stoy JE (1977) Denotational semantics: The Scott–Strachey approach to programming language theory. MIT Press, CambridgeMATH

21.

Trinder PW, Hammond K, Loidl HW, Peyton Jones SL (1998) Algorithm + strategy = parallelism. J Funct Program 8(1):23–60. https://doi.org/10.1017/S0956796897002967 MathSciNetCrossRefMATH

Titel: Pardis: a process calculus for parallel and distributed programming in Haskell
verfasst von: Christopher Blöcker
Ulrich Hoffmann
Publikationsdatum: 27.02.2018
Verlag: Springer US
Erschienen in: The Journal of Supercomputing / Ausgabe 4/2018
Print ISSN: 0920-8542
Elektronische ISSN: 1573-0484
DOI: https://doi.org/10.1007/s11227-018-2289-6

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"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Weitere Artikel der Ausgabe 4/2018

An efficient anonymous authentication protocol in multiple server communication networks (EAAM)

A tuning approach for iterative multiple 3d stencil pipeline on GPUs: Anisotropic Nonlinear Diffusion algorithm as case study

Parallel implementations of the 3D fast wavelet transform on a Raspberry Pi 2 cluster

A taxonomy of task-based parallel programming technologies for high-performance computing

Hybrid work stealing of locality-flexible and cancelable tasks for the APGAS library

The hierarchical Petersen network: a new interconnection network with fixed degree