2

关于工作平衡的快速问题。

并行处理文件。可以说文件的大小是处理它需要多长时间的近似度量。所有文件都是事先知道的。

我们有 N 个可以处理文件的节点。如何分发这些文件,以便每个节点的工作量最接近平均水平。

想法很简单,我有几个想法,但它确实看起来像是一些经典问题,已经存在最佳解决方案。
我只是不知道它叫什么。

有人知道吗?

谢谢!

编辑:好的,对不起,我省略了很多信息。我正在研究 MPI 实施。标准主从系统。一个主节点检查目标目录,选择需要处理的文件,然后将文件分配给从属 MPI 任务,以便它们可以并行完成自己的工作。

从节点数量小于32。
目标文件数量小于10000。

4

4 回答 4

2

您正在询问经典的多处理器调度问题。维基百科文章是算法基本概述的良好开端(http://en.wikipedia.org/wiki/Multiprocessor_scheduling)。

于 2011-07-30T14:22:22.247 回答
1

这是一个想法。按降序对 (filename, size) 对进行排序。然后,从最大的文件开始,将每个文件分配给文件累积权重最低的节点(随心所欲地打破平局)。“一个给我,一个给你”的方法。

需要 O(MlogM) 来对 M 文件记录进行排序,需要 O(M*N) 来分发(有人仔细检查一下),但我认为算法给出了很好的 - 最优的?- 结果。

编辑:在查看了另一张海报提供的链接后,事实证明这是 LPT 方法,它在 P 中,但在尽可能接近平均尺寸方面并不是最优的。

于 2011-07-30T14:22:46.500 回答
0

我一直在尝试使用递归分治算法并行化约简函数,并决定让提交给节点的作业数量满足不等式

l >= n / P^2

其中 l 是作业数量,n 是原始工作负载的大小,P 是“节点”、工作人员、处理器的数量,无论您想如何称呼它们。

对于大多数计算机和移动设备上的情况,n 将比 P 大许多数量级。您要确保单个工作的数量不会太大,以至于您将所有时间都花在将它们划分并发送给工人。

于 2011-07-30T14:07:10.733 回答
0

如果所有工作单元的长度都是事先已知的(可估计的),这基本上就变成了装箱问题(https://en.wikipedia.org/wiki/Bin_packing_problem)。这可以通过“首次拟合”和“最佳拟合”算法启发式地解决(参见链接)。

于 2011-09-06T13:05:46.440 回答