algorithm - 算法应该并行化有哪些提示？

Question

到目前为止，我的经验告诉我，即使使用多核处理器，并行化算法也不会总是显着加快速度。事实上，有时它会减慢速度。有哪些好的提示可以通过并行化显着加快算法速度？

（当然，考虑到过早优化的警告及其与邪恶的相关性）

score 5 · Accepted Answer

为了从并行化中获得最大的好处，一个任务应该能够被分解成类似大小的粗粒度块，这些块是独立的（或大部分是独立的），并且几乎不需要块之间的数据通信或同步。

细粒度并行化几乎总是会增加开销，并且无论可用物理内核的数量如何，都会有有限的加速。

[对此需要注意的是，那些没有非常大的架构。“核心”的数量（例如连接机器 64,000 个核心）。这些非常适合可以分解为分配给特定拓扑（如矩形网格）的相对简单的动作的计算。]

score 3 · Accepted Answer

如果您可以将工作分成独立的部分，那么它可能会很好地并行化。

还要记住Amdahl 定律，它清醒地提醒我们，通过向大多数程序添加更多内核，我们对性能提升的期望是多么少。

score 2 · Accepted Answer

首先，查看已故 Jim Gray 的这篇论文：

实际上，这将根据您在问题中所写的内容消除一些误解。显然，如果你的问题集越难以被离散化，它就越困难。

score 2 · Accepted Answer

任何时候你的计算依赖于以前的计算，这不是一个并行问题。线性图像处理、蛮力方法和遗传算法之类的东西都很容易并行化。

一个很好的类比是，你可以做些什么来让一群朋友同时做不同的部分？例如，如果不同的人可以在不同的部分工作，将宜家家具放在一起可能会很好地并行，但滚动墙纸可能不会，因为您需要按顺序制作墙壁。

score 1 · Accepted Answer

如果您正在进行大型矩阵计算，例如涉及有限元模型的模拟，这些通常可以直接分解为更小的部分。假设您正在处理非常大的矩阵，则矩阵向量乘法可以很好地从并行化中受益。除非存在导致代码运行缓慢的真正性能瓶颈，否则可能没有必要为并行处理而烦恼。

score 0 · Accepted Answer

好吧，如果你需要很多锁才能让它工作，那么它可能是那些不能很好并行化的困难算法之一。算法中是否有任何部分可以分解成不需要相互接触的独立部分？

6 回答 6