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].
The article makes for an interesting technical read, and points to some very important issues, such as debugging in a multicore environment.
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.
I had the good fortune to be in Dybvig’s compilers class in the mid 2000s. The way it was presented really brought the concepts to life and made it enjoyable.
[1] https://dl.acm.org/doi/10.1145/2807591.2807651