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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 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.
References
Andreetta, C., et al.: FinPar: a parallel financial benchmark. ACM Trans. Arch. Code Optim. (TACO) 13(2), 18:1–18:27 (2016)
Annenkov, D.: Adventures in formalisation: financial contracts, modules, and two-level type theory. Ph.D. thesis, University of Copenhagen, April 2018
Blelloch, G.E.: Programming parallel algorithms. Commun. ACM (CACM) 39(3), 85–97 (1996)
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
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
Charguéraud, A.: Pretty-big-step semantics. In: Felleisen, M., Gardner, P. (eds.) ESOP 2013. LNCS, vol. 7792, pp. 41–60. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-37036-6_3
Che, S., et al.: Rodinia: a benchmark suite for heterogeneous computing. In: IEEE International Symposium on Workload Characterization, IISWC 2009, October 2009
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
Elliott, C.: Functional images. In: The Fun of Programming. Cornerstones of Computing Series. Palgrave, March 2003
Elliott, C., Finne, S., de Moor, O.: Compiling embedded languages. J. Funct. Program. 13(2), 455–481 (2003)
Elsman, M.: Polymorphic equality–no tags required. In: Second International Workshop on Types in Compilation (TIC 1998), March 1998
Elsman, M.: Static interpretation of modules. In: Proceedings of the ACM SIGPLAN International Conference on Functional Programming, ICFP 1999. ACM Press, September 1999
Elsman, M.: Type-specialized serialization with sharing. In: Sixth Symposium on Trends in Functional Programming (TFP 2005), September 2005
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)
Elsman, M., Henriksen, T., Oancea, C.E.: Parallel Programming in Futhark. Department of Computer Science, University of Copenhagen, November 2018. https://futhark-book.readthedocs.io
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)
Henriksen, T.: Design and implementation of the Futhark programming language. Ph.D. thesis, DIKU, University of Copenhagen, November 2017
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)
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
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
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)
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
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
Hughes, J.: Why functional programming matters. Comput. J. 32(2), 98–107 (1989)
Johnsson, T.: Lambda lifting: transforming programs to recursive equations. In: Jouannaud, J.-P. (ed.) FPCA 1985. LNCS, vol. 201, pp. 190–203. Springer, Heidelberg (1985). https://doi.org/10.1007/3-540-15975-4_37
Jones, M.P.: Composing fractals. J. Funct. Program. 14(6), 715–725 (2004)
Kennedy, A.J.: Functional pearl: pickler combinators. J. Funct. Program. 14(6), 727–739 (2004)
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
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)
Poulsen, C.B., Mosses, P.D.: Flag-based big-step semantics. J. Log. Algebr. Methods Program. 88, 174–190 (2017)
Reynolds, J.C.: Definitional interpreters for higher-order programming languages. In: Proceedings of the ACM Annual Conference-Volume 2, pp. 717–740. ACM (1972)
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)
Taha, W., Sheard, T.: MetaML and multi-stage programming with explicit annotations. Theor. Comput. Sci. 248(1), 211–242 (2000). PEPM 1997
Tait, W.W.: Intensional interpretations of functionals of finite type. J. Symb. Log. 32, 198–212 (1967)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Hovgaard, A.K., Henriksen, T., Elsman, M. (2019). High-Performance Defunctionalisation in Futhark. In: Pałka, M., Myreen, M. (eds) Trends in Functional Programming. TFP 2018. Lecture Notes in Computer Science(), vol 11457. Springer, Cham. https://doi.org/10.1007/978-3-030-18506-0_7
Download citation
DOI: https://doi.org/10.1007/978-3-030-18506-0_7
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-18505-3
Online ISBN: 978-3-030-18506-0
eBook Packages: Computer ScienceComputer Science (R0)
