并行性的理论上限是多少？

Question

我想知道计算并行化的理论上限。

假设我们有一个过程需要1个内核来完成T。

• 如果由于串行瓶颈（通常是从磁盘读取）而导致该过程完全无法并行化，那么无论我们如何使用内核，都将需要T秒。
• 如果处理为perfectly parallelizable，我们可以使用T/K内核在K秒内完成它。
• 如果要完成N个等效过程，其中N >> K，那么我们应该并行运行多个过程，而不是并行处理任何给定的过程。无论哪种情况，完全可并行化的过程都将花费NT/K时间，但是包含串行瓶颈的作业可能会花费NT时间。

理论上，是否有任何“超可并行化”的计算工作负载每个都需要[[少于 T/K秒才能完成K个内核？换句话说，当有更多内核可用时，实际上需要较少总时间的工作负载。在这种情况下，实际上最好将最后一种情况下的每个作业与N进程并行化。

Answer 1

是的，这是一大类重要的问题：那些受I / O约束的问题。

假设您有10,000个进程实例，每个实例大约需要9秒的I / O和1秒的CPU /处理时间。现在说您有一千个处理器。如果仅将10,000个问题实例分布在1,000个处理器中，则完成时间（完成所有处理器上所有工作的总时间）将花费大约100秒（每个处理器10个进程，每个处理器10秒，每个处理器100秒）。相反，如果并行运行所有10,000个进程，则生成时间将接近10秒。

这也适用于进程内。想象一个过程有10个阶段，这些阶段全部受I / O约束并且完全独立。如果每个阶段花费10秒，则在一个内核上运行该过程的总时间为100秒。如果跨10个内核并行处理，则时间将接近10秒。对于您的“超级可并行化”过程而言，这可能是一个不错的选择，这不仅将从将过程分配到不同的机器中受益，而且还可以使各个过程并行化。

因此，一种情况是您有大量作业，每个作业执行大量不相关的I / O绑定操作。如果按顺序运行所有内容，那么您将花费大量时间等待I / O，即使只是考虑单个进程，也是如此。