与"令人尴尬的平行"相反的是什么？

Question

根据维基百科的说法,一个"令人尴尬的并行"问题是很难或根本不需要将问题分成许多并行任务.通常引用光线追踪作为示例,因为原则上每条光线可以并行处理.

显然,一些问题要难以并行化.有些甚至可能是不可能的.我想知道使用什么术语以及这些更难的案例的标准示例是什么.

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

Answer 1

本质上是顺序的.

例子:女性人数不会减少怀孕时间.

Answer 2

与"令人尴尬的并行"问题不止一个相反.

完美顺序

一个相反的是不可并行化的问题,即,通过利用多于一个处理器不能实现加速的问题.已经发布了一些建议,但我提出了另一个名称:完全连续的问题.

示例:I/O绑定问题,"计算f ^1000000(x ₀)"类型的问题,计算某些加密哈希函数.

通讯密集

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

的通信密集型问题的显着的例子:求解A x = b,其中A是一个大的,致密的基质.事实上,问题的实现用于编译TOP500排名.这是一个很好的基准,因为它强调了各个CPU的计算能力和互连质量(由于通信强度).

更实际的是,任何使用离散时间步长(思考:天气预报,计算机模拟碰撞测试)在规则网格上求解偏微分方程组的数学模型都可以通过域分解来并行化.这意味着,每个CPU负责处理网格的一部分,并且在每个时间步骤结束时,CPU将区域边界上的结果与"邻居"CPU交换.这些交流使这类问题变得沟通密集.

Answer 3

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

"超级连续!"

Answer 4

"顽固地连载"？

Answer 5

与尴尬平行相反的是Amdahl定律,它表示某些任务不能并行,并且完全并行任务所需的最短时间由该任务的纯顺序部分决定.

Answer 6

顺序过程的"标准示例":

• 生孩子:"​​崩溃计划失败,因为他们的理论基础是,有九名女性怀孕,你可以一个月生孩子." - 归功于Werner von Braun
• 将pi,e,sqrt(2)和其他无理数计算为数百万位数:大多数算法是连续的
• 导航:要从A点到Z点,首先必须经过一些中间点B,C,D等.
• 牛顿法:你需要每个近似值来计算下一个更好的近似值
• 质询 - 响应认证
• 关键加强
• 哈希链
• 的Hashcash

Answer 7

P-complete(但目前还不确定).

Answer 8

我使用“屈辱地顺序”

保罗