我刚刚读到一篇关于矩阵乘法突破的文章；O(n^2.373) 的算法。但我猜矩阵乘法是可以并行化的。那么，如果我们开始生产千核处理器，这会变得无关紧要吗？事情会如何变化？
问问题
2873 次
3 回答
13
并行执行不会改变特定算法的复杂性的基础——充其量，您只是将时间用于某个给定的大小，然后除以内核数。这可以将给定大小的时间减少一个常数因子，但对算法的复杂性没有影响。
同时，并行执行有时确实会改变您要用于特定任务的算法。一些在串行代码中运行良好的算法只是不能很好地分解为并行任务。对于实际规模的问题，具有更高复杂性的其他可能会更快，因为它们并行运行得更好。
对于极其大量的内核，计算本身的复杂性可能变得次要，而不仅仅是从所有内核获取必要的数据以进行计算。big-O 的大多数计算都没有考虑到串行计算的这些影响，但它对于并行计算可能变得非常重要，特别是对于某些不能对所有节点进行统一访问的并行机器模型。
于 2012-06-23T06:42:16.047 回答
10
如果有一天量子计算变得实用，那么是的，算法的复杂性将会改变。
与此同时，使用固定数量的处理器并行化算法，只需按比例划分其运行时间（在最好的情况下，当每个处理器执行的任务之间没有依赖关系时）。这意味着，将运行时间除以一个常数，因此复杂性保持不变。
于 2012-06-23T23:25:27.107 回答
5
根据阿姆达尔定律，对于相同大小的问题，并行化将随着核心数量的增加（理论上）达到收益递减的点。实际上，从一定程度的并行化来看，并行化的开销实际上会降低程序的性能。
然而，根据古斯塔夫森定律，核心数量的增加实际上会随着问题规模的增加而有所帮助。这就是集群计算背后的动机。随着我们拥有更多的计算能力，我们可以在并行化的帮助下解决更大规模或更精确的问题。
我们按原样学习的算法可能是并行化的，也可能不是并行化的。有时，必须使用单独的算法来有效地并行执行相同的任务。无论哪种方式，必须针对并行情况重新分析 Big-O 表示法，以考虑并行化对算法时间复杂度的影响。
于 2012-06-23T06:45:38.283 回答