Streams and nested parallelism in Accelerate

Rob Everest
University of New South Wales

Traditional parallel array programming languages leverage the implicit parallelism available in collective operations over arrays. As part of our work on Accelerate, a GPU programming language embedded in Haskell, we have added sequences as a complement arrays. By allowing the user to work with sequences explicitly they are able to more efficiently stream data in and out of Accelerate programs, as well as more easily handle large sources of data.

The strongest benefit, however, comes from the fact that with this structure it is possible to express a limited form of nested parallelism. This limited form lacks some of the disadvantages associated with other nested data parallel languages. Namely, the space complexity of an algorithm using sequences is proportional to the number of processors, as opposed to the degree of parallelism available in the algorithm.