矩阵乘法的并行分布式算法

Question

当我查找矩阵乘法算法的维基百科页面时，问题就出现了

\n\n

它说：

\n\n

\n

该算法有一个关键路径长度的\xce\x98((log n)^2)步骤，这意味着在具有无限数量处理器的理想机器上需要那么多时间；因此，它在任何真实计算机上都有最大可能的加速\xce\x98(n3/((log n)^2))。

\n

\n\n

（引用来自“并行和分布式算法/共享内存并行性”部分。）

\n\n

由于假设有无限个处理器，乘法运算应该在 中完成O(1)。然后将所有元素相加，这也应该是一个常数时间。因此，最长的关键路径应该是O(1) 而不是 \xce\x98((log n)^2)。

\n\n

我想知道 O 和 \xce\x98 之间是否有区别，我错在哪里？

\n\n

---

\n\n

问题已经解决，非常感谢@Chris Beck。答案应该分为两部分。

\n\n

首先，一个低级错误是我没有计算求和的时间。求和进行运算O(log(N))（_{考虑二进制加法）}。

\n\n

其次，正如克里斯指出的那样，重要的问题需要O(log(N))处理器花费时间。最重要的是，最长的关键路径应该是O(log(N)^2)而不是O(1)。

\n\n

对于 O 和 \xce\x98 的混淆，我在Big_O_Notation_Wikipedia中找到了答案。

\n\n

\n

Big O 是比较函数时最常用的渐近表示法，尽管在许多情况下 Big O 可以替换为 Big Theta \xce\x98 以获得渐近更紧的界限。

\n

\n\n

---

\n\n

我最后的结论是错误的。这O(log(N)^2)不会发生在求和和处理器处，而是发生在我们分割矩阵时。感谢@displayName 提醒我这一点。此外，Chris对非平凡问题的回答对于研究并行系统仍然非常有用。感谢下面所有暖心回答者！

\n

Answer 1

这个问题有两个方面，解决了这个问题就会得到完整的回答。

\n

\n
• 为什么我们不能通过投入足够数量的处理器来将运行时间降低到 O(1)？
\n
• 矩阵乘法的关键路径长度如何等于\xce\x98(log ² n)？
\n

\n

一一追问。

\n\n

无限数量的处理器

\n

对这一点的简单回答是理解两个术语，即。任务粒度和任务依赖性。

\n

\n
• 任务粒度 -意味着任务分解的精细程度。即使您有无限的处理器，问题的最大分解仍然是有限的。
\n
• 任务依赖性 -意味着哪些步骤只能按顺序执行。就像，除非您已经阅读过输入，否则您无法修改它。因此，修改始终先于读取输入，并且不能与其并行完成。
\n

\n

因此，对于具有四个步骤的进程A, B, C, D，例如D 依赖于 C，C 依赖于 B 并且 B 依赖于 A，那么单个处理器的工作速度将与 2 个处理器一样快，将与 4 个处理器一样快，将工作速度与无限处理器一样快。

\n

这解释了第一点。

\n\n

并行矩阵乘法的关键路径长度

\n

\n
1. 如果您必须将大小为 的方阵划分n X n为四个大小的块[n/2] X [n/2]，然后继续划分直到达到单个元素（或大小为 的矩阵），则这种树状1 X 1设计的层数为O(log ( n))。
\n
2. 因此，对于并行矩阵乘法，由于我们必须递归地划分不是一个而是两个大小为 n 的矩阵，直到它们的最后一个元素，因此需要O(log ² n)时间。
\n
3. 事实上，这个界限更严格，不仅仅是O(log ² n)，而是\xce\x98(log ² n)。
\n

\n

Big O 和 Theta 之间的区别在于，Big O 只告诉我们一个过程不会超出 Big O 提到的范围，而 Theta 告诉我们函数不仅有上限，而且还有下限Theta 中提到的内容。因此，实际上，函数复杂度图将夹在同一个函数之间，并乘以两个不同的常数，如下图所示，或者换句话说，函数将以相同的速率增长：

\n

\n

^{图片取自：http://xlinux.nist.gov/dads/Images/thetaGraph.gif}

\n

因此，我想说，对于您的情况，您可以忽略该符号，并且您在两者之间并没有“严重”错误。

\n\n

总而言之...

\n

我想定义另一个术语，称为“加速”或“并行性”。它被定义为最佳顺序执行时间（也称为工作）与并行执行时间的比率。您链接到的维基百科页面上已经给出的最佳顺序访问时间是O(n ³ )。并行执行时间为O(log ² n)。

\n

因此，加速比 = O(n ³ /log ² n)。

\n

尽管加速看起来如此简单明了，但由于移动数据固有的通信成本，在实际情况下实现它非常困难。

\n