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

Venue: Proceedings of the 22nd International Conference on Languages and Compilers for Parallel Computing
DOI: 10.1007/978-3-642-13374-9_2
Link to Publication

Abstract:
We present the design and implementation of the staplpList, 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 1000 processors and that pList compares favorably with other dynamic data structures such as the pVector. 

@inproceedings{Tanase-tsp-2009, 
 address = {Berlin, Heidelberg}, 
 author = {Tanase, Gabriel and Xu, Xiabing and Buss, Antal and Harshvardhan and Papadopoulos, Ioannis and Pearce, Olga and Smith, Timmie and Thomas, Nathan and Bianco, Mauro and Amato, Nancy M. and Rauchwerger, Lawrence}, 
 booktitle = {Proceedings of the 22nd International Conference on Languages and Compilers for Parallel Computing}, 
 doi = {10.1007/978-3-642-13374-9_2}, 
 isbn = {3642133738}, 
 location = {Newark, DE}, 
 numpages = {15}, 
 pages = {16–30}, 
 publisher = {Springer-Verlag}, 
 series = {LCPC\'09}, 
 title = {The STAPL Plist}, 
 url = {https://doi.org/10.1007/978-3-642-13374-9_2}, 
 year = {2009} 
}