If I understand correctly, one of the challenges faced by this graph application relates to the workload being irregular and known only as the computation visits new parts of the graph. There's some work in this direction that might be helpful [1].
48 karma · joined July 11, 2016
Even so, I encourage anyone reading this article to keep in mind that there is a massive amount of work dedicated to software support for multicore parallelism.
For anyone interested in digging deeper into multicore parallelism, I recommend taking a look at the CMU approach to teaching algorithms [1]. They teach parallel programming to second-year undergraduates by default, and the students even write parallel implementations, which can achieve good parallel speedups on a multicore system.
Moreover, they do it using either a parallel functional language or a parallel library in modern C++.
Importantly, they get this far by largely hiding details of exactly how parallel tasks are scheduled across cores. There's a scheduler that does it, much like there's a garbage collector that frees unused memory in a memory-managed language.
https://par.nsf.gov/servlets/purl/10079614
To my knowledge, the remaining cost could be decreased to approximately the same cost as a branch mispredict, but getting there would require changes to the chip hardware and software stack.
We've implemented Chunked Sequences as a package of C++ header files and provided source code on github. To the client, Chunked Sequence looks like STL deque, but with additional methods to allow split at a specified position and concatenate, both in logarithmic time. The operations which push and pop on the ends of the Chunked Sequence are approximately as fast as those of STL deque, and in certain use patterns much faster.