如何计算并行任务的时间估计？

Question

我需要计算完成一定数量的任务所需的总时间。详情：

• 总共 5 个任务。每个的时间估计（以秒为单位）：

  [30, 10, 15, 20, 25]

• 并发：一次 3 个任务

在并发情况下，如何计算处理所有任务所需的总时间？我知道这将需要至少与最长的任务（25秒）一样长，但是是否有一个公式/方法来计算粗略的总估计，这将随着添加的更多任务而扩展？

Answer 1

如果您不介意做一些近似，那可能会很简单。如果完成任务所需的时间大致相同，您可以使用任务持续时间的平均值作为基础（此处为 20 秒）。

假设系统始终充满任务，任务时长足够小，任务数量足够多，并发度足够高，那么：

estimated_duration = average_task_duration * nb_tasks / nb_workers

其中

nb_workers

是并发线程数。

这里有一些 Python 代码展示了这个想法：

from random import random
from time import sleep, monotonic
from concurrent.futures import ThreadPoolExecutor

def task(i: int, duration: float):
  sleep(duration)

def main():
  nb_tasks = 20
  nb_workers = 3
  average_task_duration = 2.0
  expected_duration = nb_tasks * average_task_duration / nb_workers

  durations = [average_task_duration + (random() - 0.5) for _ in range(nb_tasks)]

  print(f"Starting work... Expected duration: {expected_duration:.2f} s")
  start = monotonic()
  with ThreadPoolExecutor(max_workers=nb_workers) as executor:
    for i, d in enumerate(durations):
      executor.submit(task, i, d)
  stop = monotonic()

  print(f"Elapsed: {(stop - start):.2f} s")


if __name__ == "__main__":
  main()

如果这些假设不能满足您的情况，那么您最好按照 Jerôme 的建议使用 Bin Packing 算法。

Answer 2

您可以通过使用最小堆来表示工作队列来计算总时间，按照您实际打算运行的任何顺序加载所有任务（例如，按优先级，或者，如果最小化总运行时间，则从最长到最短），并查看最长的运行工作时间是多少。下面是一个如何在 Python 中工作的示例：

import heapq

def calculate_runtime(sorted_task_lengths: List[int], concurrency: int) -> int:
   worker_heap = [0] * concurrency
   for task_length in sorted_task_lengths:
      # Push the new task onto the worker with the least amount of work
      heapq.heappush(worker_heap, heapq.heappop(worker_heap) + task_length)
   return max(worker_heap)

# Here the task lengths are sorted in descending order
calculate_runtime(sorted([30, 10, 15, 20, 25], reverse=True), 3)