如何使序列化并行运行

Question

伙计们， 如果我有一个树结构，并且我想序列化树和子节点。如何并行地对每个节点进行序列化。 如果我给每个节点分配一个独立的任务，输出的数据就会乱序。 并发序列化有某种模式吗？

编辑：如果结构不是树，而是 DAG？如何处理这个结构？如何序列化DAG并使序列化并发。

Answer 1

这是递归并行性或 Fork/Join 并行性的理想问题。

在树的每个级别，生成一个任务以将每个节点序列化到临时缓冲区，然后等待这些任务并加入缓冲区。例如（假设是二叉树）

std::string serialize_tree(tree t)
{
     std::future<std::string> left_rep=std::async(serialize_tree,tree.left_node);
     std::future<std::string> right_rep=std::async(serialize_tree,tree.right_node);
     return left_rep.get()+right_rep.get(); // plus any further formatting
}

显然，您需要检查空树或叶节点或其他什么，但这应该给您一个想法。

编辑：要处理 DAG，您可以将与异步调用的依赖项关联的未来传递给异步调用，因此每个任务都会显式等待它需要完成的任务。

Answer 2

从你非常简短的描述来看，不清楚你有什么限制，所以我会笼统地回答。

如果您想并行处理树中的节点，同时希望保持处理结果有序，您可以这样做。

1. 按照您希望获得结果的顺序为每个节点指定一个 1-N 的数字。
2. 将节点与指定的编号一起提供给一些可以并行处理事物的“机器”。这里有很多选项如何做事。
3. 等待所有完成，然后根据分配的编号对结果进行排序。

这里通过在整个链中保留 #1 中给出的数字来保持顺序。

步骤#2 可能是一个线程池支持的类，您只需将项目（数字节点对）添加到其中。

Answer 3

大多数构建工具编译软件时都会在 DAG 上运行并行作业。在单线程/进程环境中，经典的解决方案是使用拓扑排序对任务进行排序然后按该顺序处理作业。

然而，在多线程/进程环境中，您必须确保节点的任务在其依赖项完成之前不会被处理。这意味着您必须维护一个包含阻塞工作人员的队列。您还必须维护队列中的节点已准备就绪的不变式（它们的依赖项已完成处理）。

一种可能的实现是为每个节点维护一个依赖计数器；当其依赖项之一完成时，减少计数器。如果计数器达到 0，则将该节点插入队列。