并行任务分配的等负载
Equal loading for parallel task distribution
我有大量独立任务想要 运行，我想将它们分布在一个并行系统上，以便每个处理器完成相同数量的工作，并最大限度地提高我的效率。
我想知道是否有找到解决此问题的通用方法，或者可能只是针对我的具体问题的一个好的解决方案。
我有 T=150 个任务运行，每个任务需要的时间是 t=T。即task1占用1个时间单位，task2占用2个时间单位……task150占用150个时间单位。假设我有 n=12 个处理器，在工作人员之间分配工作负载的最佳方法是什么，假设开始和清理任务所需的时间可以忽略不计？
尽管我最初对@HighPerformanceMark 的巧妙方法充满热情，但我还是决定使用 GNU Parallel 和 -j 12 来实际对其进行基准测试，以使用 12 个内核并模拟 1 个工作单元睡眠 1 秒。
首先，我按照建议生成了一份工作列表：
paste <(seq 1 72) <(seq 150 -1 79)
看起来像这样：
1 150
2 149
3 148
...
...
71 80
72 79
然后我将列表传递给 GNU Parallel 并在最后并行获取剩余的 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
16 分 24 秒后 运行 秒。
然后我使用了我更简单的方法，就是先 运行 大作业，这样你就不太可能在最后留下任何大作业，从而导致 CPU 负载不平衡因为只有一项大工作需要 运行 而您的其余 CPU 无事可做：
time parallel -j 12 sleep {} ::: $(seq 150 -1 1)
而且 运行 只用了 15 分 48 秒，所以实际上速度更快。
我认为另一种方法的问题在于，在前 6 轮 12 对作业之后，还剩下 6 个作业，其中最长的作业需要 78 秒，所以实际上有 6 CPUs 坐在那里78 秒内什么都不做。如果任务的数量可以被 CPU 的数量整除，那将不会发生，但是 150 不会除以 12。
我得到的解决方案与上面提到的类似。如果有人感兴趣，这是伪代码：
N_proc = 12.0
Jobs = range(1,151)
SerialTime = sum(Jobs)
AverageTime = SerialTime / N_proc
while Jobs remaining:
for proc in range(0,N_proc):
if sum(proc) < AverageTime:
diff = AverageTime - sum(proc)
proc.append( max( Jobs <= diff ) )
Jobs.pop( max( Jobs <= diff ) )
else:
proc.append( min(Jobs) )
Jobs.pop( min(Jobs) )
这对我来说似乎是最佳方法。我在许多不同的工作分配上尝试了 运行 次，它似乎在均匀分配工作方面做得不错，只要 N_proc << N_jobs.
这是对最大优先的略微修改，因为每个处理器首先尝试避免做比它更多的事情 "fair share"。如果它必须超过它的公平份额，那么它将尝试通过从队列中获取最小的剩余任务来保持接近公平答案。
我有大量独立任务想要 运行，我想将它们分布在一个并行系统上，以便每个处理器完成相同数量的工作，并最大限度地提高我的效率。
我想知道是否有找到解决此问题的通用方法，或者可能只是针对我的具体问题的一个好的解决方案。
我有 T=150 个任务运行，每个任务需要的时间是 t=T。即task1占用1个时间单位，task2占用2个时间单位……task150占用150个时间单位。假设我有 n=12 个处理器，在工作人员之间分配工作负载的最佳方法是什么，假设开始和清理任务所需的时间可以忽略不计？
尽管我最初对@HighPerformanceMark 的巧妙方法充满热情，但我还是决定使用 GNU Parallel 和 -j 12 来实际对其进行基准测试，以使用 12 个内核并模拟 1 个工作单元睡眠 1 秒。
首先，我按照建议生成了一份工作列表：
paste <(seq 1 72) <(seq 150 -1 79)
看起来像这样：
1 150
2 149
3 148
...
...
71 80
72 79
然后我将列表传递给 GNU Parallel 并在最后并行获取剩余的 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
16 分 24 秒后 运行 秒。
然后我使用了我更简单的方法，就是先 运行 大作业，这样你就不太可能在最后留下任何大作业，从而导致 CPU 负载不平衡因为只有一项大工作需要 运行 而您的其余 CPU 无事可做：
time parallel -j 12 sleep {} ::: $(seq 150 -1 1)
而且 运行 只用了 15 分 48 秒，所以实际上速度更快。
我认为另一种方法的问题在于，在前 6 轮 12 对作业之后，还剩下 6 个作业，其中最长的作业需要 78 秒，所以实际上有 6 CPUs 坐在那里78 秒内什么都不做。如果任务的数量可以被 CPU 的数量整除，那将不会发生，但是 150 不会除以 12。
我得到的解决方案与上面提到的类似。如果有人感兴趣，这是伪代码：
N_proc = 12.0
Jobs = range(1,151)
SerialTime = sum(Jobs)
AverageTime = SerialTime / N_proc
while Jobs remaining:
for proc in range(0,N_proc):
if sum(proc) < AverageTime:
diff = AverageTime - sum(proc)
proc.append( max( Jobs <= diff ) )
Jobs.pop( max( Jobs <= diff ) )
else:
proc.append( min(Jobs) )
Jobs.pop( min(Jobs) )
这对我来说似乎是最佳方法。我在许多不同的工作分配上尝试了 运行 次，它似乎在均匀分配工作方面做得不错，只要 N_proc << N_jobs.
这是对最大优先的略微修改，因为每个处理器首先尝试避免做比它更多的事情 "fair share"。如果它必须超过它的公平份额，那么它将尝试通过从队列中获取最小的剩余任务来保持接近公平答案。