Shen, Junjie (2017-12). A HIERARCHICAL SYSTEM VIEW AND ITS USE IN THE DATA DISTRIBUTION OF COMPOSED CONTAINERS IN STAPL. Master's Thesis. | Thesis individual record
abstract

In parallel programming, a concurrent container usually distributes its elements to
all processing units (locations) equally to maximize the processing ability. However,
this distribution strategy does not perform well when we apply nested parallel func-
tions on a composed concurrent container, such as a concurrent vector of vectors or
a concurrent map of lists. The distribution of the inner concurrent containers across
the system will mess up the locality of the elements in the composed containers,
generating a lot of inter-process communication when the nested parallel operations
are called to access the container's elements. As the hierarchy in modern high per-
formance computing (HPC) systems become large and complex, a large amount of
inter-process communication, especially those between two remote processing units
(such as two cores on different nodes), will have dramatic negative impact on the
performance of the parallel applications.

In this thesis, we introduce a hierarchical system view that represents the topol-
ogy of the processing units in a HPC system, and use it to guide the distribution of
the composed concurrent containers. It reduces the number of processing elements
involved in storing in the inner concurrent containers, which reduces memory usage
and improves construction time. It also reduces the amount of inter-process com-
munication by improving the locality of the elements when we apply nested parallel
functions on a composed concurrent container.
To evaluate our approach, we implement two concurrent associative multi-key
containers, multimap and multiset, in the Standard Template Adaptive Parallel Li-
brary (STAPL), and use the hierarchical system view on the distribution of composed
2D and 3D containers. Finally, we show great improvement on both the construction
time and the execution time of the nested parallel functions with various numbers
of cores and hierarchies.

etd chair
publication date
2017