multithreading - 并行遍历图形

Question

我正在为考试做修改(仍然)，并且遇到了一个困扰我的问题(在下面发布)。总而言之，我认为问题是“想想必须遍历图并对其找到的对象进行一些工作的any_old_process，包括添加更多工作。”。我的问题是，可以并行处理哪种数据结构以实现问题中规定的目标？

The role of a garbage collector (GC) is to reclaim unused memory.Tracing collectors must identify all live objects by traversing graphsof objects induced by aggregation relationships. In brief, the GC hassome work-list of tasks to perform. It repeatedly (a) acquires a task(e.g. an object to inspect), (b) performs the task (e.g. marks theobject unless it is already marked), and (c) generates further tasks(e.g. adds the children of an unmarked task to the work-list). It isdesirable to parallelise this operation.

In a single-threadedenvironment, the work-list is usually a single LIFO stack. What wouldyou have to do to make this safe for a parallel GC? Would this be asensible design for a parallel GC? Discuss designs of data structureto support a parallel GC that would scale better. Explain why youwould expect them to scale better.

Answer 1

图的自然数据结构是一个图，即可以引用其他元素的一组图元素(节点)。但是，为了更好地缓存重用，可以将元素放置/分配在一个或多个数组(通常是向量)中，以便将相邻元素尽可能地靠近内存。通常，每个元素或一组元素都应具有互斥量(spin_mutex)以保护对其的访问，该争用意味着其他某个线程正在忙于处理它，因此无需等待。但是，如果可能的话，最好对标志/状态字段执行原子操作以将元素标记为无锁访问。例如，最简单的数据结构可以如下:

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

给定这种数据结构以及描述GC工作方式的方式，它非常适合像 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
    }
}

问题中的数据结构是否是任务的组织方式。我建议使用窃取工作的调度程序(例如 tbb或 cilk)。关于这个主题，有很多论文。简单来说，每个工作线程都有自己的但共享的双端队列任务，当双端队列为空时，一个线程从其他双端队列中窃取任务。

可伸缩性来自每个任务可以添加可以在prarallel中工作的其他任务的属性。