Nested parallelism with algorithmic skeletons

Alireza Majidi, Nathan Thomas, Timmie Smith, Nancy Amato, Lawrence Rauchwerger

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


Nested parallelism is a natural way to express programs for hierarchical systems. It enables a compositional programming approach that can then be mapped onto the system hierarchy. In this paper, we present nested algorithm composition in the STAPL Skeleton Library (SSL) which uses a nested dataflow model as its internal representation. We show how a high level program specification using SSL allows for asynchronous computation and improved locality. We study both the specification and performance of the stapl implementation of Kripke, a mini-app developed by Lawrence Livermore National Laboratory. Kripke has multiple levels of parallelism and a number of data layouts, making it an excellent test bed to exercise the effectiveness of a nested parallel programming approach. Performance results are provided for six different nesting orders of the benchmark demonstrating the flexibility and performance of nested algorithmic skeleton composition in stapl.

Original languageEnglish (US)
Title of host publicationLanguages and Compilers for Parallel Computing - 31st International Workshop, LCPC 2018, Revised Selected Papers
EditorsMary Hall, Hari Sundar
Number of pages17
ISBN (Print)9783030346263
StatePublished - 2019
Externally publishedYes
Event31st International Workshop on Languages and Compilers for Parallel Computing, LCPC 2018 - Salt Lake City, United States
Duration: Oct 9 2018Oct 11 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11882 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference31st International Workshop on Languages and Compilers for Parallel Computing, LCPC 2018
Country/TerritoryUnited States
CitySalt Lake City


  • Algorithmic skeletons
  • Dataflow
  • Kripke mini-app
  • Nested parallelism
  • Sweep algorithm

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Nested parallelism with algorithmic skeletons'. Together they form a unique fingerprint.

Cite this