Top

International Journal of Parallel Programming

Published in:

01-06-2016

A Generic Implementation of Tree Skeletons

Authors: Shigeyuki Sato, Kiminori Matsuzaki

Published in: International Journal of Parallel Programming | Issue 3/2016

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

search-config

AI-assisted search

Off

Abstract

In data-parallel skeleton libraries, the implementation of skeletons is usually tightly-coupled with that of data structures. However, loose coupling between them like C++ STL will improve modularity and flexibility of skeletons and data structures. This flexibility is particularly valuable for tree skeletons. To achieve such loose coupling, we present an iterator-based interface of trees for tree skeletons. We have implemented tree skeletons on the basis of our interface; we present their design and implementation. This paper also reports the results of preliminary experiments.

previous article Relational Learning with GPUs: Accelerating Rule Coverage

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

http://sketo.ipl-lab.org/.

http://www.boost.org/doc/libs/release/libs/concept_check/.

Neither MPI-based implementation was able to run with a single process.

http://docs.oracle.com/javase/8/docs/api/java/util/Collection.html.

http://www.osl.iu.edu/research/pbgl/documentation/.

Bergstrom, L., Fluet, M., Rainey, M., Reppy, J., Rosen, S., Shaw, A.: Data-only flattening for nested data parallelism. In: Proceedings of PPoPP ’13, pp. 81–92. ACM (2013)

Blelloch, G.E.: Vector Models for Data-Parallel Computing. The MIT Press, Cambridge (1990)

Blelloch, G.E.: Prefix sums and their applications. In: Synthesis of Parallel Algorithms, chap. 1, Morgan Kaufmann Publishers (1993)

Celko, J.: Joe Celko’s Trees and Hierarchies in SQL for Smarties, 2nd edn. Morgan Kaufmann Publishers, Burlington (2012)

Cole, M.I.: Algorithmic Skeletons: Structured Management of Parallel Computation. MIT Press & Pitman, Cambridge (1989)MATH

Emoto, K., Hu, Z., Kakehi, K., Takeichi, M.: A compositional framework for developing parallel programs on two-dimensional arrays. Int. J. Parallel Program. 35(6), 615–658 (2007)CrossRefMATH

Emoto, K., Matsuzaki, K.: An automatic fusion mechanism for variable-length list skeletons in sketo. Int. J. Parallel Program. 42(4), 546–563 (2014). In Proc. HLPP ’13CrossRef

Gibbons, J., Cai, W., Skillicorn, D.B.: Efficient parallel algorithms for tree accumulations. Sci. Comput. Program. 23(1), 1–18 (1994)MathSciNetCrossRefMATH

Gregor, D., Lumsdaine, A.: Lifting sequential graph algorithms for distributed-memory parallel computation. In: Proceedings of OOPSLA ’05, pp. 423–437. ACM (2005)

10.

Harshvardhan, Fidel, A., Amato, N.M., Rauchwerger, L.: The STAPL parallel graph library. In: Languages and Compilers for Parallel Computing (LCPC ’12, Revised Selected Papers). Lecture Notes in Computer Science, vol. 7760, pp. 46–60. Springer (2013)

11.

Kakehi, K., Matsuzaki, K., Emoto, K.: Efficient parallel tree reductions on distributed memory environments. In: Computational Science—ICCS 2007. Lecture Notes in Computer Science, vol. 4488, pp. 601–608. Springer (2007)

12.

Matsuzaki, K.: Implementation of tree accumulations on distributed-memory parallel computers. In: Computational Science—ICCS 2007. Lecture Notes in Computer Science, vol. 4488, pp. 609–616. Springer (2007)

13.

Matsuzaki, K.: Parallel programming with tree skeletons. Ph.D. thesis, University of Tokyo (2007)

14.

Matsuzaki, K., Emoto, K.: Implementing fusion-equipped parallel skeletons by expression templates. In: Implementation and Application of Functional Languages (IFL ’09, Revised Selected Papers). Lecture Notes in Computer Science, vol. 6041, pp. 72–89. Springer (2010)

15.

Morihata, A., Matsuzaki, K.: A practical tree contraction algorithm for parallel skeletons on trees of unbounded degree. In: Proceedings of ICCS ’11, pp. 7–16. Elsevier (2011)

16.

Morihata, A., Matsuzaki, K.: Balanced trees inhabiting functional parallel programming. In: Proceedings of ICFP ’11, pp. 117–128. ACM (2011)

17.

Morihata, A., Matsuzaki, K., Hu, Z., Takeichi, M.: The third homomorphism theorem on trees. In: Proceedings of POPL ’09, pp. 177–185. ACM (2009)

18.

Nomura, Y., Emoto, K., Matsuzaki, K., Hu, Z., Takeichi, M.: Parallelization of XPath queries with tree skeletons. Comput. Softw. 24(3), 51–62 (2007). In Japanese

19.

Prokopec, A., Bagwell, P., Rompf, T., Odersky, M.: A generic parallel collection framework. In: Euro-Par 2011 Parallel Processing. Lecture Notes in Computer Science, vol. 6853, pp. 136–147. Springer (2011)

20.

Rabhi, F.A., Gorlatch, S. (eds.): Patterns and Skeleotns for Parallel and Distributed Computing. Springer, Berlin (2002)

21.

Reif, J.H.: List ranking and parallel tree contraction. In: Synthesis of Parallel Algorithms, chap. 3, Morgan Kaufmann Publishers (1993)

22.

Rodrigues, C., Jablin, T., Dakkak, A., Hwu, W.M.: Triolet: A programming system that unifies algorithmic skeleton interfaces for high-performance cluster computing. In: Proceedings of PPoPP ’14, pp. 247–258. ACM (2014)

23.

Skillicorn, D.B.: The Bird-Meertens formalism as a parallel model. In: Software for Parallel Computation. NATO ASI Series, vol. 106, pp. 120–133. Springer (1993)

24.

Skillicorn, D.B.: Parallel implementation of tree skeletons. J. Parallel Distrib. Comput. 39(2), 115–125 (1996)CrossRefMATH

25.

Skillicorn, D.B.: Structured parallel computation in structured documents. J. Univers. Comput. Sci. 3(1), 42–68 (1997)MATH

26.

Stroustrup, B., Sutton, A.: A Concept Design for the STL. Tech. Rep. N3351=12-0041, JTC1/SC22/WG21—The C++ Standards Committee (2012)

27.

Syme, D., Neverov, G., Margetson, J.: Extensible pattern matching via a lightweight language extension. In: Proceedings of ICFP ’07, pp. 29–40. ACM (2007)

28.

Tanase, G., Buss, A., Fidel, A., Harshvardhan, Papadopoulos, I., Pearce, O., Smith, T.G., Thomas, N., Xu, X., Mourad, N., Vu, J., Bianco, M., Amato, N.M., Rauchwerger, L.: The STAPL parallel container framework. In: Proceedings of PPoPP ’11, pp. 235–246. ACM (2011)

Title: A Generic Implementation of Tree Skeletons
Authors: Shigeyuki Sato
Kiminori Matsuzaki
Publication date: 01-06-2016
Publisher: Springer US
Published in: International Journal of Parallel Programming / Issue 3/2016
Print ISSN: 0885-7458
Electronic ISSN: 1573-7640
DOI: https://doi.org/10.1007/s10766-015-0365-6

Springer Professional

Abstract

Please log in to get access to your license.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 3/2016

BSP-Why: A Tool for Deductive Verification of BSP Algorithms with Subgroup Synchronisation

A Lock-Free Hash Trie Design for Concurrent Tabled Logic Programs

GridFOR: A Domain Specific Language for Parallel Grid-Based Applications

Editor’s Note: High-Level Parallel Programming and Applications (HLPP)

Automatic Task-Based Code Generation for High Performance Domain Specific Embedded Language

Pool Evolution: A Parallel Pattern for Evolutionary and Symbolic Computing

Premium Partner