Composing algorithmic skeletons to express high-performance scientific applications

Mani Zandifar, Mustafa Abdul Jabbar, Alireza Majidi, David Keyes, Nancy Marie Amato, Lawrence Rauchwerger

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Algorithmic skeletons are high-level representations for parallel programs that hide the underlying parallelism details from program specification. These skeletons are defined in terms of higher-order functions that can be composed to build larger programs. Many skeleton frameworks support efficient implementations for stand-alone skeletons such as map, reduce, and zip for both shared-memory systems and small clusters. However, in these frameworks, expressing complex skeletons that are constructed through composition of fundamental skeletons either requires complete reimplementation or suffers from limited scalability due to required global synchronization. In the stapl Skeleton Framework, we represent skeletons as parametric data flow graphs and describe composition of skeletons by point-to-point dependencies of their data flow graph representations. As a result, we eliminate the need for reimplementation and global synchronizations in composed skeletons. In this work, we describe the process of translating skeleton-based programs to data flow graphs and define rules for skeleton composition. To show the expressivity and ease of use of our framework, we show skeleton-based representations of the NAS EP, IS, and FT benchmarks. To show reusability and applicability of our framework on real-world applications we show an NBody application using the FMM (Fast Multipole Method) hierarchical algorithm. Our results show that expressivity can be achieved without loss of performance even in complex real-world applications.

Original languageEnglish (US)
Title of host publicationICS 2015 - Proceedings of the 29th ACM International Conference on Supercomputing
PublisherAssociation for Computing Machinery
Pages415-424
Number of pages10
ISBN (Electronic)9781450335591
DOIs
StatePublished - Jun 8 2015
Externally publishedYes
Event29th ACM International Conference on Supercomputing, ICS 2015 - Newport Beach, United States
Duration: Jun 8 2015Jun 11 2015

Publication series

NameProceedings of the International Conference on Supercomputing
Volume2015-June

Other

Other29th ACM International Conference on Supercomputing, ICS 2015
CountryUnited States
CityNewport Beach
Period6/8/156/11/15

Keywords

  • Algorithmic skeletons
  • Data flow programming
  • Distributed systems
  • High-performance computing
  • Patterns

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint Dive into the research topics of 'Composing algorithmic skeletons to express high-performance scientific applications'. Together they form a unique fingerprint.

  • Cite this

    Zandifar, M., Abdul Jabbar, M., Majidi, A., Keyes, D., Amato, N. M., & Rauchwerger, L. (2015). Composing algorithmic skeletons to express high-performance scientific applications. In ICS 2015 - Proceedings of the 29th ACM International Conference on Supercomputing (pp. 415-424). (Proceedings of the International Conference on Supercomputing; Vol. 2015-June). Association for Computing Machinery. https://doi.org/10.1145/2751205.2751241