Lazy tree splitting

Nested data-parallelism (NDP) is a declarative style for program-ming irregular parallel applications. NDP languages provide lan-guage features favoring the NDP style, efficient compilation of NDP programs, and various common NDP operations like paral-lel maps, filters, and sum-like reductions. In this paper, we describe the implementation of NDP in Parallel ML (PML), part of the Man-ticore project. Managing the parallel decomposition of work is one of the main challenges of implementing NDP. If the decomposi-tion creates too many small chunks of work, performance will be eroded by too much parallel overhead. If, on the other hand, there are too few large chunks of work, there will be too much sequential processing and processors will sit idle. Recently the technique of Lazy Binary Splitting was proposed for dynamic parallel decomposition of work on flat arrays, with promising results. We adapt Lazy Binary Splitting to parallel pro-cessing of binary trees, which we use to represent parallel arrays in PML. We call our technique Lazy Tree Splitting (LTS). One of its main advantages is its performance robustness: per-program tuning is not required to achieve good performance across varying plat-forms. We describe LTS-based implementations of standard NDP operations, and we present experimental data demonstrating the scalability of LTS across a range of benchmarks