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