1

在 C/MPI 中如何实现二叉树?特别是,我如何在处理器上收集树的缺失部分?

假设我想在 N 个子矩形中划分一个矩形,N 是进程的总数。

我从两个子矩形的划分开始(沿着一个方向和一个由某个规则给出的位置,在这里没关系)。左侧矩形分配给进程 [0,mid_process],右侧子矩形分配给其他进程。

然后我在这两个子矩形内递归地执行此操作,直到我最终在当前子矩形中只剩下一个进程。

通过这样做,每个进程都将拥有树的“本地”部分,该部分由从自身到根节点的路径组成。

然而,稍后,一旦树被构建,我希望每个进程(即每个最终的子矩形)识别哪些是它的相邻进程。

假设我在本地拥有整棵树,这可以通过遍历树来完成,对于每片叶子,查看其空间范围并将其边界与我们正在寻找邻居的子矩形的边界进行比较。

这件事是我不确定我如何发送和接收树的缺失部分。

分解和关联树的示例

此处的图显示了 11 个进程及其关联的二叉树之间的分解示例。

假设我是进程 2。在本地,我在内存中的树包含以下节点:[root]、[0-4]、[2-4]、[2],其中 [] 中的数字是进程的等级。进程 [2] 的邻居是 [0]、1、[3]、[4]、[5]、[8]。

4

0 回答 0