Mai*_*tor 10 algorithm parallel-processing big-o
我刚读了一篇关于矩阵乘法突破的文章; 一个算法是O(n ^ 2.373).但我猜矩阵乘法是可以并行化的东西.那么,如果我们开始生产千分之一核处理器,这会变得无关紧要吗？事情会怎样改变？
Jer*_*fin 11
并行执行不会改变特定算法的复杂性的基础 - 最好的情况是,您只需花费一些给定大小的时间,然后除以核心数.这可以通过常数因子减少给定大小的时间,但是对算法的复杂性没有影响.
同时,并行执行也有时会改变它要使用特定任务的算法(一个或多个).一些在串行代码中运行良好的算法不能很好地分解为并行任务.对于实际大小的问题,具有更高复杂性的其他人可能更快,因为它们并行运行得更好.
对于极大量的内核,计算本身的复杂性可能变得次要,只需从所有内核获取必要的数据即可进行计算.big-O的大多数计算都没有将这些影响考虑在内进行串行计算,但对于并行计算而言,它可能变得非常重要,特别是对于某些并行机器模型而言,它们不能统一访问所有节点.
如果量子计算有一天会变得实用,那么是的,算法的复杂性会发生变化.
同时,并行化算法,使用固定数量的处理器,justs将其运行时间成比例(在最好的情况下,当每个处理器执行的任务之间没有依赖关系时).这意味着,将运行时间除以常量,因此复杂性保持不变.
根据Amdahl定律,对于相同大小的问题,随着核心数量的增加(理论上),并行化将达到收益递减的程度.实际上,从某种程度的并行化,并行化的开销实际上会降低程序的性能.
然而,根据Gustafson定律,随着问题规模的增加,核心数量的增加实际上有所帮助.这是集群计算背后的动机.由于我们拥有更强的计算能力,因此我们可以在并行化的帮助下以更大的规模或更高的精度解决问题.
我们学习的算法可能是也可能不是可以兼容的.有时,必须使用单独的算法来并行有效地执行相同的任务.无论哪种方式,必须对并行情况重新分析Big-O表示法,以考虑并行化对算法时间复杂度的影响.