Multithreading – traversing graphics in parallel

I'm revising the exam (still) and have a sad problem (as shown below) To sum up, I think the problem is "think that any_old_process must traverse the graph and do some work on the objects it finds, including adding more work." My question is, what data structures can be parallelized to achieve the goals proposed in the question?

Solution

The natural data structure of a graph is a graph, that is, a group of graphic elements (nodes) that can reference other elements However, for better cache reuse, you can place / allocate elements in one or more arrays (usually vectors) to put adjacent elements in memory as much as possible Usually, each element or group of elements should have a spin_mutex to protect access to it. Contention means that other threads are busy processing it, so they don't need to wait However, if possible, it is best to perform atomic operations on the flag / status field to mark the element as accessed without locking For example, the simplest data structure can be:

struct object {
    vector<object*> references;
    atomic<bool> is_visited; // for simplicity,or epoch counter
                             // if nothing resets it to false
    void inspect();          // processing method
};
vector<object> objects;      // also for simplicity,if it can be for real
                             // things like `parallel_for` would be perfect here

In view of the description of this data structure and GC working mode, it is fully suitable for recursive parallelism such as divide and conquer pattern:

void object::inspect() {
    if( ! is_visited.exchange(true) ) {
        for( object* o : objects )   // alternatively it can be `parallel_for` in some variants
            cilk_spawn o->inspect(); // for Cilk or `task_group::run` for TBB or PPL
        // further processing of the object
    }
}

If the data structure in the problem is the organization of the task I recommend a job stealing scheduler (such as TBB or cilk) There are many papers on this subject In short, each worker thread has its own but shared task copy. When deque is empty, one thread steals another's task

Scalability comes from the fact that each task can add some properties of other tasks that can work in parallel