Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Colocation of Potential Parallelism in a Distributed Adaptive Run-Time System for Parallel Haskell Read chapter Read first chapter

2019 | OriginalPaper | Chapter

High-Performance Defunctionalisation in Futhark

Authors : Anders Kiel Hovgaard, Troels Henriksen, Martin Elsman

Published in: Trends in Functional Programming

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

General-purpose massively parallel processors, such as GPUs, have become common, but are difficult to program. Pure functional programming can be a solution, as it guarantees referential transparency, and provides useful combinators for expressing data-parallel computations. Unfortunately, higher-order functions cannot be efficiently implemented on GPUs by the usual means. In this paper, we present a defunctionalisation transformation that relies on type-based restrictions on the use of expressions of functional type, such that we can completely eliminate higher-order functions in all cases, without introducing any branching. We prove the correctness of the transformation and discuss its implementation in Futhark, a data-parallel functional language that generates GPU code. The use of these restricted higher-order functions has no impact on run-time performance, and we argue that we gain many of the benefits of general higher-order functions, without in most practical cases being hindered by the restrictions.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
previous chapter Improving Haskell
Footnotes
1
In the actual implementation, the target language does include application of first-order functions, but in our theoretical work we just inline the functions for simplicity.
 
Literature
1.
Andreetta, C., et al.: FinPar: a parallel financial benchmark. ACM Trans. Arch. Code Optim. (TACO) 13(2), 18:1–18:27 (2016)
2.
Annenkov, D.: Adventures in formalisation: financial contracts, modules, and two-level type theory. Ph.D. thesis, University of Copenhagen, April 2018
3.
Blelloch, G.E.: Programming parallel algorithms. Commun. ACM (CACM) 39(3), 85–97 (1996)CrossRef
4.
Chakravarty, M.M., Keller, G., Lee, S., McDonell, T.L., Grover, V.: Accelerating Haskell array codes with multicore GPUs. In: Workshop on Declarative Aspects of Multicore Programming, DAMP 2011. ACM, January 2011
5.
Chakravarty, M.M., Leshchinskiy, R., Jones, S.P., Keller, G., Marlow, S.: Data parallel Haskell: a status report. In: Workshop on Declarative Aspects of Multicore Programming, DAMP 2007. ACM, January 2007
6.
7.
Che, S., et al.: Rodinia: a benchmark suite for heterogeneous computing. In: IEEE International Symposium on Workload Characterization, IISWC 2009, October 2009
8.
Claessen, K., Sheeran, M., Svensson, B.J.: Expressive array constructs in an embedded GPU kernel programming language. In: Workshop on Declarative Aspects of Multicore Programming, DAMP 2012. ACM, January 2012
9.
Elliott, C.: Functional images. In: The Fun of Programming. Cornerstones of Computing Series. Palgrave, March 2003CrossRef
10.
Elliott, C., Finne, S., de Moor, O.: Compiling embedded languages. J. Funct. Program. 13(2), 455–481 (2003)CrossRef
11.
Elsman, M.: Polymorphic equality–no tags required. In: Second International Workshop on Types in Compilation (TIC 1998), March 1998
12.
Elsman, M.: Static interpretation of modules. In: Proceedings of the ACM SIGPLAN International Conference on Functional Programming, ICFP 1999. ACM Press, September 1999
13.
Elsman, M.: Type-specialized serialization with sharing. In: Sixth Symposium on Trends in Functional Programming (TFP 2005), September 2005
14.
Elsman, M., Henriksen, T., Annenkov, D., Oancea, C.E.: Static interpretation of higher-order modules in Futhark: functional GPU programming in the large. Proc. ACM Program. Lang. 2(ICFP), 97:1–97:30 (2018)CrossRef
15.
16.
Girard, J.Y.: Interpretation Fonctionnelle et Elimination des Coupures de l’Arithmetique d’Ordre Superieur. In: Proceedings of the Second Scandinavian Logic Symposium, pp. 63–92. North-Holland (1971)
17.
Henriksen, T.: Design and implementation of the Futhark programming language. Ph.D. thesis, DIKU, University of Copenhagen, November 2017
18.
Henriksen, T., Elsman, M., Oancea, C.E.: Size slicing: a hybrid approach to size inference in Futhark. In: Proceedings of the 3rd ACM SIGPLAN International Workshop on Functional High-Performance Computing, FHPC 2014. ACM (2014)
19.
Henriksen, T., Elsman, M., Oancea, C.E.: Modular acceleration: tricky cases of functional high-performance computing. In: Proceedings of the 7th ACM SIGPLAN International Workshop on Functional High-Performance Computing, FHPC 2018. ACM, New York, September 2018
20.
Henriksen, T., Serup, N.G., Elsman, M., Henglein, F., Oancea, C.E.: Futhark: purely functional GPU-programming with nested parallelism and in-place array updates. In: Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2017, pp. 556–571. ACM, June 2017
21.
Henriksen, T., Thorøe, F., Elsman, M., Oancea, C.E.: Incremental flattening for nested data parallelism. In: Proceedings of the 24th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2019. ACM (2019)
22.
Holk, E., Newton, R., Siek, J., Lumsdaine, A.: Region-based memory management for GPU programming languages: enabling rich data structures on a spartan host. In: Proceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications, OOPSLA 2014, pp. 141–155. ACM, New York, October 2014
23.
Hovgaard, A.K.: Higher-order functions for a high-performance programming language for GPUs. Master’s thesis, Department of Computer Science, Faculty of Science, University of Copenhagen, Universitetsparken 5, DK-2100 Copenhagen, May 2018
24.
Hughes, J.: Why functional programming matters. Comput. J. 32(2), 98–107 (1989)CrossRef
25.
26.
Jones, M.P.: Composing fractals. J. Funct. Program. 14(6), 715–725 (2004)CrossRef
27.
Kennedy, A.J.: Functional pearl: pickler combinators. J. Funct. Program. 14(6), 727–739 (2004)CrossRef
28.
Najd, S., Lindley, S., Svenningsson, J., Wadler, P.: Everything old is new again: quoted domain-specific languages. In: Proceedings of the ACM Workshop on Partial Evaluation and Program Manipulation, PEPM 2016. ACM, January 2016
29.
Peterson, J., Jones, M.: Implementing type classes. In: Proceedings of the ACM SIGPLAN 1993 Conference on Programming Language Design and Implementation, PLDI 1993, pp. 227–236. ACM, New York (1993)
30.
31.
Reynolds, J.C.: Definitional interpreters for higher-order programming languages. In: Proceedings of the ACM Annual Conference-Volume 2, pp. 717–740. ACM (1972)
32.
Stratton, J.A., et al.: Parboil: a revised benchmark suite for scientific and commercial throughput computing. Technical report, University of Illinois at Urbana-Champaign, IMPACT-12-01 (2012)
33.
Taha, W., Sheard, T.: MetaML and multi-stage programming with explicit annotations. Theor. Comput. Sci. 248(1), 211–242 (2000). PEPM 1997CrossRef
34.
Metadata
Title
High-Performance Defunctionalisation in Futhark
Authors
Anders Kiel Hovgaard
Troels Henriksen
Martin Elsman
Copyright Year
2019
Book
Trends in Functional Programming

Print ISBN: 978-3-030-18505-3

Electronic ISBN: 978-3-030-18506-0

Copyright Year: 2019

DOI
https://doi.org/10.1007/978-3-030-18506-0_7

Premium Partner

    Image Credits