The STAPL pList

Gabriel Tanase, Xiabing Xu, Antal Buss, Harshvardhan, Ioannis Papadopoulos, Olga Pearce, Timmie Smith, Nathan Thomas, Mauro Bianco, Nancy M. Amato, Lawrence Rauchwerger

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

Abstract

We present the design and implementation of the stapl pList, a parallel container that has the properties of a sequential list, but allows for scalable concurrent access when used in a parallel program. The Standard Template Adaptive Parallel Library (stapl) is a parallel programming library that extends C++ with support for parallelism. stapl provides a collection of distributed data structures (pContainers) and parallel algorithms (pAlgorithms) and a generic methodology for extending them to provide customized functionality. stapl pContainers are thread-safe, concurrent objects, providing appropriate interfaces (e.g., views) that can be used by generic pAlgorithms. The pList provides stl equivalent methods, such as insert, erase, and splice, additional methods such as split, and efficient asynchronous (non-blocking) variants of some methods for improved parallel performance. We evaluate the performance of the stapl pList on an IBM Power 5 cluster and on a CRAY XT4 massively parallel processing system. Although lists are generally not considered good data structures for parallel processing, we show that pList methods and pAlgorithms (p-generate and p-partial-sum) operating on pLists provide good scalability on more than 103 processors and that pList compares favorably with other dynamic data structures such as the pVector.

Original languageEnglish (US)
Title of host publicationLanguages and Compilers for Parallel Computing - 22nd International Workshop, LCPC 2009, Revised Selected Papers
Pages16-30
Number of pages15
DOIs
StatePublished - Jul 14 2010
Externally publishedYes
Event22nd International Workshop on Languages and Compilers for Parallel Computing, LCPC 2009 - Newark, DE, United States
Duration: Oct 8 2009Oct 10 2009

Publication series

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

Conference

Conference22nd International Workshop on Languages and Compilers for Parallel Computing, LCPC 2009
CountryUnited States
CityNewark, DE
Period10/8/0910/10/09

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'The STAPL pList'. Together they form a unique fingerprint.

  • Cite this

    Tanase, G., Xu, X., Buss, A., Harshvardhan, Papadopoulos, I., Pearce, O., Smith, T., Thomas, N., Bianco, M., Amato, N. M., & Rauchwerger, L. (2010). The STAPL pList. In Languages and Compilers for Parallel Computing - 22nd International Workshop, LCPC 2009, Revised Selected Papers (pp. 16-30). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5898 LNCS). https://doi.org/10.1007/978-3-642-13374-9_2