如何将一个包含n个元素的向量分配到p个处理器上

Question

假设我有一个包含n个元素的向量，并且我想要将它分配到p个进程中，其中n不一定是p的倍数。每个进程都有一个从0到p-1的排名。如何确定每个进程上将有多少元素，以便数据尽可能均匀地分布？

例如，如果n=14，p=4，我希望分配如[3, 3, 4, 4]或[3, 4, 3, 4]等，但不是[3, 3, 3, 5]或[4, 4, 4, 2]。

我希望有一个函数f(n, p, r)，它返回给我具有排名r的进程的元素数量。

- Charles Brunet

---

一个经典的农民/工人方法怎么样？MPI示例：http://www.inf.ed.ac.uk/teaching/courses/ppls/farm.c - matcheek

不适用于我的情况。我需要将图像的行分发进行处理，因此农民/工人方法不是解决方案。 - Charles Brunet

从上面的问题陈述中，您事先不知道执行时间，因为这取决于数据，因此一个农民，许多工人（也称为“任务包”）的方法似乎是一个理想的解决方案，是的，您可以从矩阵中获取每一行并在单独的处理器上运行它。您的代码示例将更好地解释问题。 - matcheek

Answer 1

Does

(n + r) / p

work for you?

- zxc

---

哇！比我想象中的还要简单。 - Charles Brunet

这是我从阅读 Stack Overflow 中学到的最好的东西。我很惊讶之前居然没见过这个。 - Jonathan Dursi

Answer 2

这似乎是装箱问题的一个特例。有一些非常好的近似算法，但在理论上它是NP难题。

如果您不想阅读维基页面，我可以简化成几行。如果您想深入了解可能更好的解决方案，或者对近似方案的分析有兴趣，请自行查看。

步骤1：按优先级对元素进行排序。
步骤2：获取具有最高优先级的元素，并将其放置在负担最轻的进程上。
步骤3：如果您有更多的元素，请返回步骤1。否则返回。

- user684934

---

不，我知道有解决我的问题的方法。只是我不记得具体是什么了。 - Charles Brunet