什么是相对的"令人尴尬的平行"?

Question

根据维基百科，一个"令人尴尬的平行"问题是一个很少或没有努力需要单独的问题进入一些并行任务。光线跟踪的是经常被援引作为一个例子，因为每一线可能，在原则上，可以并行处理。

显然，有些问题更难以并行.有些人可能甚至是不可能的。我想知道什么条件是使用什么标准的实例是，用于这些困难情况。

我可以提出"令人讨厌的顺序"作为一个可能的名字吗？

Answer 1

固有顺序。

示例：女性人数不会减少怀孕时间。

Answer 2

与“令人尴尬的平行”相反，有一个以上的对立面。问题

完全顺序

一个相反的是不可并行化的问题，也就是说，没有加速可以通过使用多个处理器来实现。已经发布了一些建议，但我提出了另一个名称：完全顺序问题。

示例： I / O绑定问题，“计算f ^百万（X <子> 0 ）＆QUOT;问题的类型，计算某些加密哈希函数。

通信密集型

另一个相反的问题是可并行化的问题，需要大量并行通信（通信密集型问题）。这种问题的实现只能在具有高带宽，低延迟互连的超级计算机上正确扩展。将此与令人尴尬的并行问题进行对比，即使在互连非常差的系统上也能高效运行（例如农场）。

通信密集型问题的显着示例：求解 A x = b 其中 A 是一个大而密集的矩阵。事实上，该问题的实现用于编译 TOP500 排名。这是一个很好的基准，因为它强调了各个CPU的计算能力和互连质量（由于通信强度）。

在更实际的术语中，任何使用离散时间步长在常规网格上求解偏微分方程组的数学模型（想想：天气预报， in silico 崩溃测试），可以通过域名分解来并行化。这意味着，每个CPU负责网格的一部分，并且在每个时间步骤结束时，CPU在区域边界上用“邻居”交换它们的结果。的CPU。这些交流使这类问题变得沟通密集。

Answer 3

我很难不发布这个...因为我知道它不会在讨论中添加任何内容..但是对于那里的所有南方球迷来说

“超级连续！”

Answer 4

“Stubbornly serial”？

Answer 5

与尴尬平行的相反的是 Amdahl定律，其中指出某些任务不可能是并行，并且完全并行任务所需的最短时间由该任务的纯顺序部分决定。

Answer 6

"标准范例"的顺序处理：

• 做一个婴儿："崩溃的程序失败，因为它们是基于理论认为，有九名妇女怀孕，可以得到婴儿一个月。" --归因于维尔纳*冯*布朗
• 计算pi、e、sqrt(2)，以及其他不合理的人数数以百万计的数字：大多数的算法，顺序
• 导航：为获得从A到Z，你必须先通过一些中间点，B，C，D，等等。
• 牛顿的方法：你需要每一个近似为计算下一个、更好的逼近
• 挑战响应的认证
• 加强关键
• 哈希链
• Hashcash

Answer 7

P-complete（但目前还不确定）。

Answer 8

我使用“Humiliatingly Sequential”

保

Answer 9

“Gladdengly Sequential”

Answer 10

这一切都与数据依赖关系有关。令人尴尬的并行问题是解决方案由许多独立部分组成的问题。与这种性质相反的问题是具有大量数据依赖性的问题，其中几乎没有什么可以并行完成。 退行性依赖？

Answer 11

我最常听到的术语是“紧密耦合”，因为每个进程必须经常交互和通信才能共享中间数据。基本上，每个过程都依赖于其他过程来完成计算。

例如，矩阵处理通常涉及在每个阵列分区的边缘共享边界值。

这与令人尴尬的并行（或松散耦合）问题相反，问题的每个部分都是完全自包含的，并且不需要（或很少）IPC。想想主/工并行性。

Answer 12

夸张地顺序。

Answer 13

我总是喜欢“悲伤地顺序”ala quicksort中的分区步骤。

Answer 14

如果有人想推测出自然的，不可避免的连续问题会是什么样的，那么试试

幸福顺序

反击'令人尴尬的并行'。

Answer 15

“完全连续？”

科学家们更多地考虑可以做什么而不是做不到的事情，这不应该让你感到惊讶。特别是在这种情况下，并行化的替代方案正在按照通常的方式执行所有操作。

Answer 16

完全不可并行化？ Pessimally parallelizable？

Answer 17

相反的是“令人不安的连续”。

Answer 18

考虑到并行性是在同一时间步骤t中完成许多工作的行为。相反的可能是时间顺序问题

Answer 19

一个固有顺序问题的例子。 这在CAD软件包和某些工程分析中很常见。

树遍历节点之间的数据依赖性。

想象一下遍历图表并添加节点权重。

你无法将其并行化。

CAD软件将零件表示为树，并且要渲染到对象，您必须遍历树。 出于这个原因，cad工作站使用更少的核心和更快，而不是许多核心。

感谢阅读。

Answer 20

你当然可以，但我认为这两个'名字'都不是问题。 从功能编程的角度来看，你可以说'恼人的顺序'部分是算法中最小或多或少独立的部分。

虽然“令人尴尬的并行”如果没有真正采用并行方法则是错误的编码实践。

因此，如果良好的编码实践始终将您的解决方案制成独立的部分，即使您当时没有利用并行性，我也不会认为这些事情是一个名称。