logo标签列表

“尴尬并行”的反义词是什么？

multithreadingconcurrencyterminologyparallel-processingmulticore
38
根据维基百科的定义，"embarrassingly parallel"问题指的是将问题分成多个并行任务所需的工作量非常少或几乎为零。光线追踪通常被引用为一个例子，因为每个光线在原则上都可以被并行处理。
显然，有些问题要实现并行化要困难得多，甚至可能是不可能的。我想知道这些更难的情况下使用的术语和标准示例是什么。
我能提出“令人烦恼的顺序”作为可能的名称吗？
1
如果“尴尬并行”意味着很容易看出如何并行化它，那么相反的情况可能是(a)似乎应该可以并行化，但实际上却非常难以做到，或者(b)很容易看出它无法并行化。分别的术语可以是(a)“第二类尴尬并行”，(b)“可敬的非并行”。 - Evgeni Sergeev
20个回答
75

天性具有序列性

例如：女性的数量不会影响妊娠期的长度。

1
我是凭空想出来的，但我真的怀疑我在这里创造了一个术语。有许多连续的工作流程的例子，例如，在雇用人员之前你不能真正解雇员工，在客户下订单之前你不能(或者至少不应该)发货等等。 - Brian Rasmussen
12
是的，但是N个女人可以在与一个女人生一个到八个孩子所需的同样时间内生育N个孩子。 - user85109
6
“固有的串行性”这个术语已经由复杂性理论家在研究NC等并行计算类别时使用了一段时间。 - Dave
我认为这是错误的。我相信相应的短语是“令人不安的串行”。固有地并不是尴尬的适当反义词。 - user82238
2
@Blank：所以“令人不安”是“尴尬”的反义词吗？话虽如此，我在很多地方看到了“固有的顺序性”，我相信这是最常用的习语。它也很好地描述了这个事实，因为这种串行性确实固有于这些算法中。 - Konrad Rudolph
显示剩余3条评论
27

一个“尴尬并行”问题的相反面不止一个。

完全顺序

一个相反的问题是一个不可并行化问题，即无法通过使用多个处理器来实现speedup的问题。已经发布了几个建议，但我想提出另一个名称：一个完全顺序问题。

例如：I/O-bound问题，“计算f1000000(x0)”类型的问题，计算某些cryptographic hash functions。

通信密集型

另一个相反的问题是需要大量并行通信的可并行化问题（通信密集型问题）。这样一个问题的实现只能在具有高带宽、低延迟互连的超级计算机上正确扩展。与“尴尬并行”问题相比，这些问题的实现甚至可以在互连非常差的系统上高效运行（例如farms）。

一个典型的通信密集问题是解决A x = b，其中A是一个大而密集的矩阵。实际上，该问题的一种实现被用于编译TOP500排名。这是一个很好的基准，因为它强调了单个CPU的计算能力和互连质量（由于通信密集度）。
更实际地说，任何使用离散时间步进（例如：天气预报，in silico 碰撞测试）在规则网格上解决偏微分方程组的数学模型，都可以通过domain decomposition进行并行化。这意味着每个CPU负责网格的一部分，并且在每个时间步结束时，CPU与“邻居”CPU交换其在区域边界上的结果。这些交换使得这类问题具有通信密集性。
这个答案值得更多的强调。 - Pi Delport
3
具有讽刺意味的是，虽然Top500排名被广泛批评在HPC社区中，因为它没有提供良好的通信练习。例如，阻塞可以非常有效地加速矩阵乘法。仅涉及邻居交换的问题也是相对较轻的通信者。天真的n体引力模拟将是通信密集型的一个例子-FFT也不错，因为高维FFT通常使用全对全实现。 - markhahn
@markhahn 确实。另一个例子（虽然不是基于浮点运算）：Graph500基准测试非常注重通信。 - Bolo
13

我很难忍住不发这个帖子……因为我知道它对讨论没有任何实际贡献……但是这里向所有南方公园的粉丝致敬。

“超级认真！”

1
不要忘记包含Lisp。 - temp2290
12
“顽固串行”？
10

“令人尴尬地并行”的相反概念是阿姆达尔定律，该定律指出某些任务无法并行，并且完全并行任务所需的最短时间由任务纯顺序部分决定。

4
阿姆达尔定律描述了在具有给定并行级别的算法中，多个处理器的加速限制。我认为它并没有直接说明可并行性本身。 - bubaker
9

“标准例子”的连续过程：

  • 生孩子：“紧急计划会失败，因为它们基于这样一种理论：只要有九个女人怀孕，你就可以在一个月内得到一个婴儿。”——沃纳·冯·布朗归属
  • 计算π、e、sqrt(2)和其他无理数的百万位数字：大多数算法都是顺序的。
  • 导航：要从A点到达Z点，必须先经过一些中间点B、C、D等。
  • 牛顿法：需要每个近似值才能计算下一个更好的近似值。
  • 挑战-响应身份验证
  • 密钥强化
  • 哈希链
  • 哈希现金
5

P-完全问题（但目前尚不确定）。

5
我使用“羞辱性顺序”。
保罗。
4
如果有人猜测自然而然、不可避免地出现的连续问题会是什么样子，可以试着用“幸福的连续”来对抗“尴尬的并行”。
2
我听到最多的术语是“紧密耦合”，每个进程必须经常交互和通信，以共享中间数据。基本上，每个进程都依赖其他进程完成计算。
例如，矩阵处理通常涉及在每个数组分区的边缘共享边界值。
这与极其并行（或松散耦合）的问题形成对比，其中问题的每个部分都完全自包含，不需要（或几乎不需要）IPC。考虑主/从并行性。
1
这实际上是迄今为止最好的答案，因为它抓住了问题的核心：一切都与数据流图有关。 - markhahn
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接