Accelerating Nested Data Parallelism: Preserving Regularity

Abstract

In the world of parallel programming, the data parallel style is well suited for the GPUs. However nested data parallelism forms a difficult problem to solve, under the condition that we produce fast code. However, we need nested data parallelism for expressiveness in algorithms. In this thesis, we use Accelerate, a domain specific language embedded in Haskell, to investigate this problem. We look at the gridding algorithm, which is related to data processing for radio telescopes but also contains nested data parallelism. A vital component of those calculations is performing fast Fourier transformations, so we look specifically at different ways to speeds these up. We benchmarked these and found that, if we can stick to arrays that have the same shape called regular arrays, we obtain a good speed-up. We discuss the cases of when we can stay regular, also in intermediate calculations. We present two analysis compilers can use to remain regular. We call these the Independence and Shape analysis. We also implemented these in the Accelerate compiler. Finally, we show benchmarks of the gridding algorithm, that can use these analyses to stay regular. We conclude that this a step in the right direction for solving nested data parallelism, but that there are still other factors to consider.