The Standard Template Adaptive Parallel Library (STAPL)
is a parallel programming framework that extends C++ and STL with
support for parallelism. STAPL provides a collection of parallel data
structures (pContainers) and algorithms (pAlgorithms) and a generic
methodology for extending them to provide customized functionality.
STAPL pContainers are thread-safe, concurrent objects, i.e., shared objects
that provide parallel methods that can be invoked concurrently.
They also provide appropriate interfaces that can be used by generic
pAlgorithms. In this work we present the design and implementation of
the STAPL associative pContainers: pMap, pSet, pMultiMap, pMultiSet,
pHashMap, and pHashSet. These containers provide optimal insert, search,
and delete operations for a distributed collection of elements based on
keys. Their methods include counterparts of the methods provided by the
STL associative containers, and also some asynchronous (non-blocking)
variants that can provide improved performance in parallel. We evaluate
the performance of the STAPL associative pContainers on an IBM Power5
cluster, an IBM Power3 cluster, and on a linux-based Opteron cluster,
and show that the new pContainer asynchronous methods, generic
pAlgorithms (e.g., pfind) and a sort application based on associative
pContainers, all provide good scalability on more than 10^3 processors.