State of the art in parallel data structures [closed]

Question

I'm currently evaluating how I could implement several algorithms on a parallel computer with a large number of nodes, each also equipped with a powerful GPU. It turns out that for many algorithms, it would be useful to "just" have a datastructure that is distributed over many nodes and on whose elements you can run a function in the style of a for-each kernel.

In the end, it could for example boil-down to a distributed implementation of C++'s STL. It would also mean, that you could just impelement the algorithm in a familiar mean and would (mostly) not need to bother about parallel details. It would also be cool to have Python bindings: Write some high-level python code and the low-level distributed stuff happens magically.

I did some research about existing projects in this direction:

• There's for example STAPL but I could not really find significantly more information, and did not get a response on my email.
• There are linear algebra packages such as Trilinos and PETSc, but they are mostly designed for linear algebra and they are also huge frameworks which need significant effort to be incorporated into own projects.
• GPU support is generally poor (I'm aware that you can not straight forward use a GPU for general purpose data structures.)

Are there any serious efforts on distributed general purpose data structures that could be used as a basis for parallelization of existing code? I would be happy to get some references, papers or search words.

Answer 1

I'm working on a project related to your question, trying to take one implementation of a parallel process and make it 'future proof' by abstracting away as much as possible the specifics of particular parallel architectures and setups. From my research it appears there's no fully-automated parallelism that will efficiently fit any arbitrary algorithm or data type, but there are some tools that can help parallelize existing serial code.

For purely Python solutions, there is the Anaconda Accelerate package, which includes Python bindings to CUDA libraries e.g. cuBLAS, cuFFT, cuSPARSE, cuRAND.

The Kokkos package within Trilinos provides something like that, though it's a set of C++ libraries so maybe not what you're looking for. As long as you're careful about how to define memory and execution spaces it's possible to quickly compile parallelized code for various architectures without needing to specifically target a particular architecture. So long as your functors and arrays are sensibly defined it's trivial to switch from CUDA to, say, Pthreads, though your performance will vary depending on how cleverly you've defined your memory and execution spaces. This package is particularly well-suited to sparse matrix operations and is most often built into molecular dynamics simulations (so far as I can tell).

If your arrays are dense you might consider looking at the Halide language project. The goal of that language is to separate the algorithm from the scheduling, so you can write the algorithm once then focus on tuning the schedule to optimize for various parallel architectures. It is primarily used for image analysis but is appropriate for many other dense array operations.

Answer 2

I've had the same question recently. One interesting development are the HSA specifications targeting heterogeneous hardware that are supposedly implemented in GCC 6.1 (I haven't tried it yet). Sounds like the idea is to unify memory access and floating point operations across heterogeneous devices with one programming model.

Answer 3

You may want to look into using Julia. Using Julia on multiple nodes is quite trivial using the machine files (which I document in a blog post, but essentially you just pass in the list of nodes you're using and now your parallel commands will work on all of them). It's also very easy to get it to work with GPUs (which you can do separately on each machine using the parallel functions from the first post) and multiple GPUs per node.

Also, Julia has Distributed Arrays which are arrays where only parts of the array are on a single node. Then you can use Julia's fancy iteration syntax for i in eachindex(A) and it will only iterate over the indices which are contained on the node, for each node. As long as you enforce type-stability it will compile to the same assembly as C/Fortran code (which you can check with @code_llvm).

There's also work being done to mix Julia's threads with multiprocesses: 1 process per node and the parallel commands automatically parallelize to each node, and each node threads over its cores. This is still experimental, but since it's all written in Julia, if you know Julia then it's easy to contribute (or make a package for it).