我已经实现了一个迭代算法,其中每次迭代都涉及一个前序树遍历(有时称为向下累积),然后是一个后序树遍历(向上累积)。对每个节点的每次访问都涉及计算和存储要用于下一次访问的信息(在后续的后序遍历或后续迭代中)。
在前序遍历过程中,每个节点都可以独立处理,只要它与根之间的所有节点都已经被处理过。处理后,每个节点需要将一个元组(特别是两个浮点数)传递给它的每个子节点。在后序遍历中,每个节点都可以独立处理,只要它的所有子树(如果有的话)都已经被处理过。处理后,每个节点需要将一个浮点数传递给它的父节点。
树的结构是静态的,在算法过程中是不变的。但是,在向下遍历的过程中,如果被传递的两个浮点数都为零,则不需要处理该节点下的整个子树,可以开始对该节点的向上遍历。(必须保留子树,因为在后续迭代中传递的浮点数可能在该节点处变为非零并且遍历将恢复)。
每个节点的计算强度在树上是相同的。每个节点的计算是微不足道的:只需对长度等于节点上的子节点数的数字列表进行一些求和和乘/除。
正在处理的树是不平衡的:一个典型的节点会有 2 个叶子加上 0-6 个额外的子节点。因此,简单地将树划分为一组相对平衡的子树是不明显的(对我来说)。此外,这些树旨在消耗所有可用的 RAM:我可以处理的树越大越好。
我的串行实现仅在我的小测试树上就达到了每秒 1000 次迭代的量级;对于“真正的”树,我预计它可能会减慢一个数量级(或更多?)。鉴于该算法需要至少 1 亿次迭代(可能高达 10 亿次)才能达到可接受的结果,我想并行化该算法以利用多个内核。我对并行编程的经验为零。
鉴于我的算法的性质,推荐的并行化模式是什么?