Parallel Scan as a Multidimensional Array Problem
A. Šinkarovs and S.-B. Scholz, “Parallel scan as a multidimensional array problem,” in Proceedings of the 8th ACM SIGPLAN international workshop on libraries, languages and compilers for array programming, Jun. 2022, pp. 1–11. doi: 10.1145/3520306.3534500.
Abstract
For many algorithms, it is challenging to identify a suitable parallel version, as the design space is typically very large. In this paper we demonstrate how rank-polymorphic array languages can be used as a tool to explore such design spaces through concise high-level specifications. If input data can be organised into a multi-dimensional array, and the algorithm can be stated as a recursive traversal over sub-arrays, array languages offer a lot of expressive power. The reason for this is that array shapes can be used to guide recursive traversals. Conciseness of specifications comes from array reshapes that move the desired elements into canonical hyperplanes. As a case study, we discuss several variants of implementing prefix sums (also known as scans) in SaC. We demonstrate how small code adjustments suffice to change the concurrency pattern exposed to the compiler. It turns out that variability that is typically achieved by generic inductive data types such as binary trees is a special case of what is offered by the array paradigm.