均衡加载以并行分配任务 [英] Equal loading for parallel task distribution

问题描述

我有很多想运行的独立任务，我希望将它们分布在并行系统上，以便每个处理器执行相同的工作量，并最大程度地提高效率.

I have a large number of independent tasks I would like to run, and I would like to distribute them on a parallel system such that each processor does the same amount of work, and maximizes my efficiency.

我想知道是否存在一种通用的方法来找到该问题的解决方案，或者可能只是一种解决我确切问题的好方法.

I would like to know if there is a general approach to finding a solution to this problem, or possibly just a good solution to my exact problem.

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

I have T=150 tasks I would like to run, and the time each task will take is t=T. That is, task1 takes 1 one unit of time, task2 takes 2 units of time... task150 takes 150 units of time. Assuming I have n=12 processors, what is the best way to divide the work load between workers, assuming the time it takes to begin and clean up tasks is negligible?

推荐答案

尽管我最初对@HighPerformanceMark的巧妙方法很感兴趣，但我还是决定使用 GNU Parallel 和-j 12来对它进行基准测试，以使用12核心并模拟了1个工作单元，其中睡眠时间为1秒.

Despite my initial enthusiasm for @HighPerformanceMark's ingenious approach, I decided to actually benchmark this using GNU Parallel with -j 12 to use 12 cores and simulated 1 unit of work with 1 second of sleep.

首先，我按照以下建议生成了一份作业列表:

First I generated a list of the jobs as suggested with:

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

看起来像这样:

1   150
2   149
3   148
...
...
71  80
72  79

然后，我将列表传递到 GNU Parallel 中，并在并行结束时选择剩下的6个作业:

Then I pass the list into GNU Parallel and pick up the remaining 6 jobs at the end in parallel:

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

运行时间为16分钟24秒.

That runs in 16 mins 24 seconds.

然后，我使用了一种较为简单的方法，即首先运行大型作业，因此您不太可能在最后留下任何大型作业，从而不会导致CPU负载不平衡，因为只需要运行一项大型作业，并且您其余的CPU无关:

Then I used my somewhat simpler approach, which is just to run big jobs first so you are unlikely to be left with any big ones at the end and thereby get imbalance in CPU load because just one big job needs to run and the rest of your CPUs have nothing to do:

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

而且运行时间为15分48秒，因此实际上更快.

And that runs in 15 minutes 48 seconds, so it is actually faster.

我认为另一种方法的问题在于，在前6轮12对作业之后，剩下6个作业中最长的作业耗时78秒，因此实际上6个CPU在这里闲置了78秒.如果将任务数除以CPU数，则不会发生，但150不能除以12.

I think the problem with the other approach is that after the first 6 rounds of 12 pairs of jobs, there are 6 jobs left the longest of which takes 78 seconds, so effectively 6 CPUs sit there doing nothing for 78 seconds. If the number of tasks was divisible by the number of CPUs, that would not occur but 150 doesn't divide by 12.

这篇关于均衡加载以并行分配任务的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！