根据 Wikipedia 的说法，“令人尴尬的并行”问题是将问题分成多个并行任务只需很少或根本不需要努力的问题。光线追踪通常被用作示例，因为原则上每条光线都可以并行处理。
显然，有些问题更难并行化。有些甚至可能是不可能的。我想知道这些更难的情况使用了哪些术语以及标准示例是什么。
我可以提出“令人讨厌的顺序”作为可能的名称吗？
问问题
8868 次
20 回答
73
本质上是顺序的。
例子：女性的数量不会减少怀孕的时间。
于 2009-04-30T12:17:52.623 回答
27
“令人尴尬的并行”问题的对立面不止一个。
完全顺序
一个相反的问题是不可并行化的问题，即不能通过使用多个处理器来实现加速的问题。已经发布了一些建议，但我会提出另一个名称：一个完美的顺序问题。
示例：I/O-bound问题，“计算 f 1000000 (x 0 )”类型的问题，计算某些加密哈希函数。
沟通密集型
另一个相反的问题是需要大量并行通信的可并行化问题（通信密集型问题）。此类问题的实现只能在具有高带宽、低延迟互连的超级计算机上正确扩展。将此与令人尴尬的并行问题进行对比，即使在互连非常差的系统（例如农场）上，这些问题的实现也能高效运行。
一个通信密集型问题的显着例子：求解A x = b哪里A是一个大而密集的矩阵。事实上，这个问题的一个实现是用来编译TOP500排名的。这是一个很好的基准，因为它强调了单个 CPU 的计算能力和互连的质量（由于通信强度）。
在更实际的术语中，任何使用离散时间步长求解规则网格上的偏微分方程系统的数学模型（想想：天气预报，计算机碰撞测试）都可以通过域分解并行化。这意味着，每个 CPU 负责网格的一部分，并且在每个时间步长结束时，CPU 会在区域边界上与“邻居”CPU 交换它们的结果。这些交流使这类问题成为交流密集型的。
于 2010-08-23T19:08:54.597 回答
13
我很难不发布这个...因为我知道它不会在讨论中添加任何内容..但是对于那里的所有南方公园粉丝
“超级连载！”
于 2009-04-30T12:19:45.973 回答
12
“固执连载”？
于 2009-04-30T12:17:26.293 回答
10
与令人尴尬的并行相反的是阿姆达尔定律，它说某些任务不能并行，并且完全并行任务所需的最短时间由该任务的纯顺序部分决定。
于 2009-04-30T14:43:50.527 回答
9
顺序过程的“标准示例”：
- 生孩子：“速成计划之所以失败，是因为它们的理论基础是，如果有九名妇女怀孕，一个月就能生一个孩子。” ——归功于维尔纳·冯·布劳恩
- 将 pi、e、sqrt(2) 和其他无理数计算到数百万位：大多数算法是顺序的
- 导航：从A点到Z点，必须先经过一些中间点B、C、D等。
- 牛顿法：您需要每个近似值才能计算下一个更好的近似值
- 质询-响应认证
- 重点加强
- 哈希链
- 哈希现金
于 2010-07-19T20:28:54.133 回答
5
P-complete（但这还不确定）。
于 2009-04-30T13:27:27.230 回答
5
我使用“羞辱顺序”
保罗
于 2012-06-06T02:57:04.787 回答
2
“格拉登利顺序”
于 2009-04-30T12:09:12.053 回答
2
这一切都与数据依赖性有关。令人尴尬的并行问题是解决方案由许多独立部分组成的问题。与这种性质相反的问题将是具有大量数据依赖性的问题，其中几乎没有什么可以并行完成。 退化依赖?
于 2009-04-30T12:24:38.023 回答
2
我最常听到的术语是“紧密耦合”，因为每个进程必须经常交互和通信才能共享中间数据。基本上，每个进程都依赖于其他进程来完成它们的计算。
例如，矩阵处理通常涉及在每个数组分区的边缘共享边界值。
这与令人尴尬的并行（或松散耦合）问题形成对比，其中问题的每个部分都是完全独立的，不需要（或很少） IPC。考虑主/从并行性。
于 2009-06-25T02:44:47.750 回答
2
吹嘘顺序。
于 2009-06-25T02:46:37.233 回答
2
我一直更喜欢“可悲的顺序”，即快速排序中的分区步骤。
于 2009-06-25T02:47:18.137 回答
2
如果有人应该推测遇到自然的、不可救药的顺序问题会是什么样子，请尝试
幸福的顺序
反击'尴尬的平行'。
于 2012-09-25T10:21:35.440 回答
0
“完全连载？”
科学家们更多地考虑可以做的事情而不是不能做的事情，这不应该让你感到惊讶。特别是在这种情况下，并行化的替代方法是像往常一样做所有事情。
于 2009-04-30T12:11:14.060 回答
0
完全不可并行？几乎可并行化？
于 2009-04-30T13:59:45.453 回答
0
相反的是“令人不安的连续”。
于 2009-11-02T10:08:43.860 回答
0
考虑到并行性是在同一时间步 t 中完成许多工作的行为。相反的可能是时间顺序问题
于 2012-07-28T01:25:47.797 回答
-1
一个固有顺序问题的示例。这在 CAD 软件包和某些类型的工程分析中很常见。
具有节点之间数据依赖关系的树遍历。
想象一下遍历一个图并添加节点的权重。
你只是不能并行化它。
CAD 软件将零件表示为一棵树，要渲染到对象，您必须遍历树。出于这个原因，cad 工作站使用更少的内核和更快的速度，而不是许多内核。
谢谢阅读。
于 2010-08-31T01:48:24.463 回答
-4
你当然可以，但是我认为这两个“名字”都不是问题。从函数式编程的角度来看，您可以说“令人讨厌的顺序”部分是算法中或多或少独立的最小部分。
虽然“令人尴尬的并行”（如果没有真正采用并行方法）是不好的编码实践。
因此，如果良好的编码习惯总是将您的解决方案分解为独立的部分，即使您当时没有利用并行性，我认为给这些东西一个名字是没有意义的。
于 2009-04-30T12:16:14.843 回答