Nested parallelism exists in scientific codes that are searching multi-dimensional spaces. However, implementations of nested parallelism often have overhead and load balance issues. The Orbital Analysis code we present exhibits a sparse search space, significant load imbalances, and stopping when the first solution is reached. All these aspects of the algorithm exacerbate the problem of using nested parallelism effectively. In this paper, we present an inspector executor strategy for chunking such computations into parallel wavefronts. The presented shared memory parallelization is no longer nested and exhibits significantly less load imbalance. We evaluate this approach on an Orbital analysis code, and we improve the execution time from the original implementation by an order of magnitude. As part of a Graduate Computer Science course in Parallel Programming models, we show how the approach can be implemented in parallel Perl, Python, Chapel, Pthreads, and OpenMP. Future work includes investigating how to automate and generalize the parallelization approach.
Many problems have multiple layers of parallelism. The outer-level may consist of few and coarse-grained tasks. Next, each of these tasks may also be rich in parallelism, and be split into a number of fine-grained tasks, which again may consist of even finer subtasks, and so on. Here we argue and demonstrate by examples that utilizing multiple layers of parallelism may give much better scaling than if one restricts oneself to only one level of parallelism. Two non-trivial issues for multi-level parallelism are load balancing and implementation. In this paper we provide an algorithm for finding good distributions of threads to tasks and discuss how to implement nested parallelism in OpenMP. Exploiting the full computational power of always deeper hierarchical multiprocessor machines requires a very careful distribution of threads and data among the underlying non-uniform architecture. The emergence of multi-core chips and NUMA machines makes it important to minimize the number of remote memory accesses, to favor cache affinities, and to guarantee fast completion of synchronization steps. By using the BubbleSched platform as a threading backend for the GOMP OpenMP compiler, we are able to easily transpose affinities of thread teams into scheduling hints using abstractions called bubbles. We then propose a scheduling strategy suited to nested OpenMP parallelism. The resulting preliminary performance evaluations show an important improvement of the speedup on a typical NAS OpenMP benchmark application. In this work we present a microbenchmark methodology forassessing the overheads associated with nested parallelism in OpenMP.Our techniques are based on extensions to the well known EPCC microbenchmarksuite that allow measuring the overheads of OpenMPconstructs when they are effected in inner levels of parallelism. Themethodology is simple but powerful enough and has enabled us to gaininteresting insight into problems related to implementing and supportingnested parallelism. We measure and compare a number of commercialand freeware compilation systems. Our general conclusion is that whilenested parallelism is fortunately supported by many current implementations,the performance of this support is rather problematic. Thereseem to exist issues which have not yet been addressed effectively, asmost OpenMP systems do not exhibit a graceful reaction when made toexecute inner levels of concurrency.