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
International Journal of Parallel Programming
Published in: International Journal of Parallel Programming 1/2018

23-05-2017

Functional Program Transformation for Parallelisation Using Skeletons

Authors: Venkatesh Kannan, G. W. Hamilton

Published in: International Journal of Parallel Programming | Issue 1/2018

Log in

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

search-config
loading …

Abstract

It can be challenging to use algorithmic skeletons in parallel program development as it is tedious to manually identify parallel computations in an algorithm and there may be mismatches between the algorithm and skeletons. Also, parallel programs defined using skeletons often employ inefficient intermediate data structures. In this paper, we present a program transformation method to address these issues by using an existing technique called distillation to reduce the use of intermediate data structures and an encoding technique to combine the inputs of a program into a single input whose structure matches that of the program. This facilitates automatic identification of skeletons that suit the algorithmic structure of the transformed program.
previous article Formalised Composition and Interaction for Heterogeneous Structured Parallelism

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

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
Literature
1.
Iwasaki, H., Hu, Z.: A new parallel skeleton for general accumulative computations. Int. J. Parallel Program. 32, 389–414 (2004)CrossRefMATH
2.
Skillicorn, D.B., Talia, D.: Models and languages for parallel computation. ACM Comput. Surv. 30, 123–169 (1998)CrossRef
3.
Hu, Z., Takeichi, M., Chin, W.-N.: Parallelization in calculational forms. In: ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. (1998)
4.
Matsuzaki, K., Kakehi, K., Iwasaki, H., Hu, Z., Akashi, Y.: A fusion-embedded skeleton library. In: International Conference on Parallel and Distributed Computing (EuroPar), Lecture Notes in Computer Science, vol. 3149, pp. 644–653. Springer-Verlag (2004)
5.
Hamilton, G.W., Jones, N.D.: Distillation with labelled transition systems. In: Proceedings of the ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation. (2012)
6.
Kannan, V., Hamilton, G.W.: Program transformation to identify parallel skeletons. In: Proceedings of the 24th Euromicro International Conference on Parallel, Distributed and Network-Based Processing. (2016)
7.
Kannan, V., Hamilton, G.W.: Program transformation to identify list-based parallel skeletons. In: International Workshop on Verification and Program Transformation, Electronic Proceedings in Theoretical Computer Science. (2016)
8.
Loogen, R.: Eden parallel functional programming with Haskell. In: Zsók, V., Horváth, Z., Plasmeijer, R. (eds.) Lecture Notes in Computer Science, Central European Functional Programming School, pp. 142–206. Springer, Berlin (2012)
9.
Hu, Z., Takeichi, M., Iwasaki, H.: Diffusion: calculating efficient parallel programs. In: ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation. (1999)
10.
Miller, G.L., Reif, J.H.: Parallel tree contraction and its application. In: Proceedings of the 26th Annual Symposium on Foundations of Computer Science. (1985)
11.
Morihata, A., Matsuzaki, K.: A practical tree contraction algorithm for parallel skeletons on trees of unbounded degree. In: Proceedings of the International Conference on Computational Science (ICCS). (2011)
12.
Backus, J.: Can programming be liberated from the Von Neumann style? A functional style and its algebra of programs. Commun. ACM 21, 613–641 (1978)MathSciNetCrossRefMATH
13.
Chin, W.-N., Takano, A., Hu, Z.: Parallelization via context preservation. In: International Conference on Computer Languages. (1998)
14.
Gibbons, J.: The third homomorphism theorem. J. Funct. Program. 6(4), 657–665 (1996)
15.
Morihata, A., Matsuzaki, K., Hu, Z., Takeichi, M.: The third homomorphism theorem on trees: downward & upward lead to divide-and-conquer. ACM SIGPLAN SIGACT Symp. Princ. Program. Lang. 44, 177–185 (2009)MATH
16.
Matsuzaki, K., Hu, Z., Takeichi, M.: Parallel skeletons for manipulating general trees. J. Parallel Comput. 32, 590–603 (2006)CrossRef
17.
Ahn, J., Han, T.: An analytical method for parallelisation of recursive functions. Parallel Process. Lett. 10, 87–98 (2001)CrossRef
Metadata
Title
Functional Program Transformation for Parallelisation Using Skeletons
Authors
Venkatesh Kannan
G. W. Hamilton
Publication date
23-05-2017
Publisher
Springer US
Published in
International Journal of Parallel Programming / Issue 1/2018
Print ISSN: 0885-7458
Electronic ISSN: 1573-7640
DOI
https://doi.org/10.1007/s10766-017-0510-5

Other articles of this Issue 1/2018

International Journal of Parallel Programming 1/2018 Go to the issue

Editorial

Guest Editorial: High-Level Parallel Programming with Algorithmic Skeletons

OriginalPaper

Formalised Composition and Interaction for Heterogeneous Structured Parallelism

OriginalPaper

The Missing Link! A New Skeleton for Evolutionary Multi-agent Systems in Erlang

OriginalPaper

Simultaneous CPU–GPU Execution of Data Parallel Algorithmic Skeletons

OriginalPaper

SkePU 2: Flexible and Type-Safe Skeleton Programming for Heterogeneous Parallel Systems

OriginalPaper

High-Level Programming for Many-Cores Using C++14 and the STL

Premium Partner

    Image Credits