| dc.description.abstract | We present the design and implementation of the Standard Template Adap-
tive Parallel Library (stapl) pList, a parallel container that has the properties of
a sequential list, but allows for scalable concurrent access when used in a paral-
lel program. The 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 (pViews) that can
be used by generic pAlgorithms.
The pList provides Standard Template Library (stl) equivalent methods, such
as insert, erase, and splice, additional methods such as split, and efficient asyn-
chronous (non-blocking) variants of some methods for improved parallel performance.
List related algorithms such as list ranking, Euler Tour (ET), and its applications to
compute tree based functions can be computed efficiently and expressed naturally
using the pList.
Lists are not usually considered useful in parallel algorithms because they do
not allow random access to its elements. Instead, they access elements through a
serializing traversal of the list. Our design of the pList, which consists of a collec-
tion of distributed lists (base containers), provides almost random access to its base
containers. The degree of parallelism supported can be tuned by setting the number of base containers. Thus, a key feature of the pList is that it offers the advantages
of a classical list while enabling scalable parallelism.
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, and list related algorithms such as list ranking and ET technique
operating on pLists provide good scalability on more than 16, 000 processors. We
also show that the pList compares favorably with other dynamic data structures
such as the pVector that explicitly support random access. | en |
