并行任务分配的等负载

我有大量的独立任务需要运行，我希望将它们分布在并行系统上，以便每个处理器执行相同数量的工作并最大限度地提高效率。并行任务分配的等负载

我想知道是否有一个通用的方法来找到解决这个问题，或者可能只是一个很好的解决我的确切问题。

我有T = 150个任务，我想运行，每个任务需要的时间是t = T。也就是说，task1需要1个单位时间，task2需要2个单位时间... task150需要150个单位时间。假设我有n = 12个处理器，假设开始和清理任务所需的时间可以忽略不计，那么在工作人员之间分配工作负载的最佳方式是什么？

来源

2017-02-23 Ryan T Woodall

您使用的是哪种语言？ – bc004346

我认为这是* Bin包装问题*不是吗？ https://en.wikipedia.org/wiki/Bin_packing_problem我认为你可能从最长的工作开始，继续逐渐缩短工作时间，否则你可以完成除一个工作外的所有工作，只发现这是最长的工作。 –

将任务1和150给予处理器1（它获得151个单位的工作时间），给处理器2（获得151个工作时间单元）提供任务2和149，... 12个处理器中的每一个获取这些块中的6个，剩下6个大致相等的任务（任务73-78）完成。给每一个处理器。这不是所述的装箱问题，或者如果是，它是一个很容易解决的问题。 –

尽管我@ HighPerformanceMark的巧妙方法最初的热情，我决定其实这使用GNU并行与-j 12使用12个内核和模拟1个单位的工作与睡眠1秒标杆。

首先，我产生的职位列表与建议：

paste <(seq 1 72) <(seq 150 -1 79)

，看起来像这样：

然后我通过列表分为GNU并行，拿起剩下的并行末端6个作业：

paste <(seq 1 72) <(seq 150 -1 79) | parallel -k -j 12 --colsep '\t' 'sleep {1} ; sleep {2}' 
sleep 73 & 
sleep 74 & 
sleep 75 & 
sleep 76 & 
sleep 77 & 
sleep 78 & 
wait

Th在16分钟24秒运行。

然后我用我的有些简单的方法，这只是先运行大的工作，所以你不太可能会留下任何大的末，从而得到不平衡的CPU负载，因为只是一个大的工作需要运行和你的CPU的其余什么都没有做：

time parallel -j 12 sleep {} ::: $(seq 150 -1 1)

而这15分48秒运行一次，因此它实际上要快。

我认为，与其他方法的问题是，第6轮12对工作后，有6个职位离开的时间代价78秒，所以有效地6个CPU坐在那里什么都不做最长78秒。如果任务数量可以被CPU数量整除，那么不会发生，但是150不会被12除。

来源

2017-02-24 16:42:15

并行任务分配的等负载

回答

相关问题