A HIERARCHICAL SYSTEM VIEW AND ITS USE IN THE DATA DISTRIBUTION OF COMPOSED CONTAINERS IN STAPL

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