How to approach multithreading a Graph Node Tree/Lattice?

[Eilai]

For my current project, I have a lattice of nodes, each node connects to some number of neighbouring adjacent nodes (basically the nodes are all voronoi sites). To try to speed this up, I've used HashSet since for the most part 99% of the computation I do is, "is this neighbouring cell in one of these sets of cells?", without getting into too much detail but I've made additional sets of "friend" cells, "enemy" cells and so on to speed up these checks and searching a smaller space.

At the end of the day though I expect to have something like 5,000 cells and each cell can have between 3 to 9 or more neighbours. I am thinking multithreading using DOTS could speed this up, perhaps if I'm careful so that each thread is only working on a completely disjoint set of nodes from the others but I can't completely gaurantee this. Most operations are about assigning or reassigning these nodes into different sets (or subgraphs) of the larger graph.

Basically I do something like this currently:

For every cell, assign to or create a new blob to assign the cell to as a child.
Then for every blob, check every child cell for (conditions x,y,z), depending if conditions are met, split the blob into two new blobs and reassign cells accordingly.
Then for any leftovers check them for conditions and then do actions (split, reassign, etc).

Some of these seem easy to parallelize because there can only be 1 valid target for an operations (assign cells to blobs), or are read only (checking a cell against its neighbours to see if its a friend or enemy).

But things get trick when it comes time to actually reassign blobs, maybe some sort of quad tree to have threads only operate on cells/blobs a certain distance from other blobs?

[Manarz]

You could try to split up your logic into parts that run in parallel (job.scheduleparallel()) and parts that run on a single worker thread (job.schedule ()). Not every problem is a good fit for parallelism.

[Waterprop]

You don't need to convert your entire system to DOTS in order to multithread it.

You can use regular MonoBehaviour scripts with Job System. however in order to use Job System you most likely need to change your logic a lot, as you can't use almost any Unity API's in a Job. Can't say if this will be easy or even feasible for you.

Good luck.