3

我正在寻找一种算法来解决以下问题：

有n能够通过多播进行通信的软件组件。此外，还有一个带有m对象的池。每个 sw 组件都知道该池包含什么。对象具有不同的值。根据我想将对象分配给 sw 组件的值。这意味着：必须首选具有较大值的对象，必须忽略具有较低值的对象（例如，当所有 sw 组件不能获取更多对象时）。

非常重要的是，没有对象被分发超过一次。当一个对象被分配给一个 sw 组件时，它不能被分配给另一个 sw 组件。

此外，我想将整个事情实现为分布式算法，这意味着没有执行该分布的中央单元。

有任何想法吗？

4

1 回答 1

0
  1. 一种解决方案是实现互斥算法（一个非常简单的算法是面包店算法），每个 sw 在轮到它时获取最高的对象。（这就像写入文件的互斥）
  2. 另一种将涉及节点之间的大量通信。让我们假设 N>=M 的一般情况。假设每个 sw 采用 n/m 个组件，然后他采用最高值并将其余的 x 个组件多播到 x sw，但附加值是这些组件*casted 的最大值。然后，接收 sw 将查看它们的值是否大于接收的值，并将交换它并从列表中删除该值，但插入旧值。然后它将计算出最大值的组件转换为相同的 x sw 组件。这个想法是 sw 的集合 X 将相互通信，直到每个节点都有不同的值。您将拥有一些这样的 X 组。当然，这个算法必须改进，所以每个 sw 都有不同的值，并证明这会发生，这样你就可以确定了。

但是你想要和想法，所以我给了你 2。希望它有帮助。该算法的实现将在 OpenMPI 中（使用 C 或 C++）。至少我在 OpenMPI 中实现了我的分布式算法（和 Lam MPI，但现在它已经过时了）。

于 2012-07-07T17:39:28.863 回答