Possible projects

As the outcome of our survey, we have to select a project to spend the remaining 4 months on. This is a list of such proposals.

All current languages we have investigated seems to implement some kind of fusion and avoid uncoalesced memory accesses (Accelerate and Nikola)

Branch divergence

In the paper "Financial Software on GPUs: Between Haskell and Fortran" presents a technique for limiting branch divergence. A project could involve implementing sequential loops in Accelerate and limit branch divergence using this technique. It could also be implemented in Nikola or in a small toy language.

The implementation of the technique is not well described in the paper. We find it problematic for several reasons:

• We would have to predict which branches to take before invoking the kernels. We are not sure this can be done on the GPU, and we thus might have to compute the (arbitrarily complex) conditions on the CPU.
• What if there are several branches in the same kernel?
• If we shuffle the index space, the memory operations might not be performed in an order where we can guarantee coalesced access
• It seems like we would have to split each kernel up into several kernels, and the kernel invocation overhead is also pretty high, so it might not be worthwhile.

Strength reduction

The paper also explains strength reduction. Same as above just for strength reduction instead of branch divergence.

GPU backend for Feldspar

We have previously talked about the possibility of a GPU backend for Feldspar, but as we have excluded Feldspar from our survey we haven't really any knowledge about how feasible this would be.

Flattening transformation

Perform flattening transformation in Accelerate or Nikola.

We know that the flattening transformation would be possible, but we don't really know if it is desirable to have in these languages.