The Problem-Based Benchmark Suite in Elixir

Hi! For the last few months, I worked in the implementation of the Problem-Based Benchmark Suite (PBBS) in Elixir, as part of my final CS BSc project. The PBBS is a set of problems designed to benchmark parallel implementations, and it is composed with problems such as sorting, ray tracing, remove duplicates, and word counting. One of the constraints is that the input data has to start on the same process, and the output has to end on that same process.

My goal is to compare parallel and sequential implementations of these problems in Elixir, and mostly analyze what kind of speedups are achievable in Elixir (comparing performance with other programming languages is a non-goal). I’ve implemented 8 of the 22 PBBS problems here: GitHub - lac-dcc/elixir-pbbs: Rewrite the Problem-Based Benchmark Suite in Elixir · GitHub

I’ve ran some experiments in an 40-core machine, and overall, results were mixed : for very cheap problems like removing duplicates from a list or histogram, speedups are very low, if at all (communication costs dominate). However, for more expensive problems like ray casting, where communication stops being the bottleneck, we can achieve pretty good speedups as we increase the level of parallelism.

The main strategies I used to implement the parallel algorithms was the use of Task.async, Task.async_stream, and in some cases, I found the use of :ets to be beneficial as a way to “broadcast” input to worker processes. Almost all of them are implemented in a divide-and-conquer manner: divide the problem to workers, each worker solves their part (but workers do not divide recursively to other workers), and merge the results at the end. This is the way that minimizes communication, but there might be better ways.

As a newcomer to the language and to the actor model - been programming in Elixir for only 8 months - I think that there’s probably a lot of room for improvement. So, I would like to ask for help on how to improve the the parallel implementations. Thanks in advance!