Abstract
The main challenge faced by automatic parallelization tools in functional languages is the fact that parallelism is often hidden under the syntax of complex recursive functions. In this paper, we propose an algebraic framework for parallelizing – automatically – two special classes of recursive functions. We show that these classes are comprehensive enough to include several well-known instances. We have used our ideas to implement a source-to-source compiler in Python to parallelize Haskell code. We have applied this prototype onto six different recursive functions, achieving, on a 4-core machine, speedups of up to 2.7x.
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
References
Berthold, J., Marlow, S., Hammond, K., Al Zain, A.: Comparing and optimising parallel Haskell implementations for multicore machines. In: ADPNA. IEEE (2009)
Bondhugula, U., Baskaran, M., Krishnamoorthy, S., Ramanujam, J., Rountev, A., Sadayappan, P.: Automatic transformations for communication-minimized parallelization and locality optimization in the polyhedral model. In: Hendren, L. (ed.) CC 2008. LNCS, vol. 4959, pp. 132–146. Springer, Heidelberg (2008)
Bondhugula, U., Hartono, A., Ramanujam, J., Sadayappan, P.: A practical automatic polyhedral parallelizer and locality optimizer. In: PLDI. ACM (2008)
Brown, C., Danelutto, M., Hammond, K., Kilpatrick, P., Elliott, A.: Cost-directed refactoring for parallel erlang programs. Int. J. Parallel Programm. 42(4), 564–582 (2013)
Cole, M.: Parallel programming with list homomorphisms. Parallel Process. Lett. 5(02), 191–203 (1995)
Collins, A., Grewe, D., Grover, V., Lee, S., Susnea, A.: NOVA: a functional language for data parallelism. In: ARRAY. ACM (2014)
Feautrier, P.: Automatic parallelization in the polytope model. In: Perrin, G.-R., Darte, A. (eds.) The Data Parallel Programming Model. LNCS, vol. 1132, pp. 79–103. Springer, Heidelberg (1996)
Fisher, A.L., Ghuloum, A.M.: Parallelizing complex scans and reductions. In: PLDI. ACM (1994)
Golan, J.S.: Power Algebras over Semirings: With Applications in Mathematics and Computer Science. Mathematics and Its Applications, vol. 488, 1st edn. Springer, Basel (1999)
Golan, J.S.: Semirings and their Applications, 1st edn. Springer, Heidelberg (1999)
Govindarajan, R., Anantpur, J.: Runtime dependence computation and execution of loops on heterogeneous systems. In: CGO. IEEE/ACM (2013)
Hammond, K., Berthold, J., Loogen, R.: Automatic skeletons in template haskell. Parallel Process. Lett. 13(03), 413–424 (2003)
Hu, Z., Iwasaki, H., Takechi, M.: Formal derivation of efficient parallel programs by construction of list homomorphisms. Trans. Program. Lang. Syst. 19(3), 444–461 (1997)
Kogge, P.M., Stone, H.S.: A parallel algorithm for the efficient solution of a general class of recurrence equations. Trans. Comput. 22(8), 786–793 (1973)
Liu, Y., Hu, Z., Matsuzaki, K.: Towards systematic parallel programming over MapReduce. In: Namyst, R., Roman, J., Jeannot, E. (eds.) Euro-Par 2011, Part II. LNCS, vol. 6853, pp. 39–50. Springer, Heidelberg (2011)
Marlow, S., Maier, P., Loidl, H.W., Aswad, M.K., Trinder, P.W.: Seq no more: Better strategies for parallel Haskell. In: Haskell Symposium. ACM Press (2010)
Marlow, S., Peyton Jones, S., Singh, S.: Runtime support for multicore haskell. In: ICFP, pp. 65–78. ACM (2009)
Misailovic, S., Kim, D., Rinard, M.: Parallelizing sequential programs with statistical accuracy tests. Trans. Embed. Comput. Syst. 12(2), 88 (2013)
Morihata, A., Matsuzaki, K.: Automatic parallelization of recursive functions using quantifier elimination. In: Blume, M., Kobayashi, N., Vidal, G. (eds.) FLOPS 2010. LNCS, vol. 6009, pp. 321–336. Springer, Heidelberg (2010)
Morita, K., Morihata, A., Matsuzaki, K., Hu, Z., Takeichi, M.: Automatic inversion generates divide-and-conquer parallel programs. In: PLDI. ACM (2007)
Rotman, J.J.: Advanced Modern Algebra, 2nd edn. Prentice Hall, Upper Saddle River (2003)
Sato, S., Iwasaki, H.: Automatic parallelization via matrix multiplication. In: PLDI. ACM (2011)
Schlecht, S.J., Habets, E.A.P.: Connections between parallel and serial combinations of comb filters and feedback delay networks. In: IWAENC (2012)
Trifunovic, K., Nuzman, D., Cohen, A., Zaks, A., Rosen, I.: Polyhedral-model guided loop-nest auto-vectorization. In: PACT. IEEE (2009)
Wang, Z., Tournavitis, G., Franke, B., O’Boyle, M.F.P.: Integrating profile-driven parallelism detection and machine-learning-based mapping. Trans. Archit. Code Optim. 11(1), 2 (2014)
Zou, Y., Rajopadhye, S.: Scan detection and parallelization in “inherently sequential" nested loop programs. In: CGO. ACM (2012)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Rocha, R.C.O., Góes, L.F.W., Pereira, F.M.Q. (2016). An Algebraic Framework for Parallelizing Recurrence in Functional Programming. In: Castor, F., Liu, Y. (eds) Programming Languages. SBLP 2016. Lecture Notes in Computer Science(), vol 9889. Springer, Cham. https://doi.org/10.1007/978-3-319-45279-1_10
Download citation
DOI: https://doi.org/10.1007/978-3-319-45279-1_10
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-45278-4
Online ISBN: 978-3-319-45279-1
eBook Packages: Computer ScienceComputer Science (R0)