multithreading - 用于将 nxn 矩阵与 $\Theta(n^2/lgn)$ 并行性相乘的多线程算法

Question

我想找到一种多线程算法，将 $n x n$ 矩阵乘以 n 向量，实现 $\Theta(n^2/lgn)$ 并行性，同时保持 $\Theta(n^2)$ 工作。

我知道一个非法的解决方案，但是关于如何使跨度下降到 $\Theta(lgn)$ 的任何提示？

Answer 1

在 CLRS 教科书中有一个名为 MAT-VEC 的程序实现了这个问题。但它的跨度是Theta of N。要将其拉低至对数跨度，您可以使用多线程分而治之策略替换内部 for 循环中的串行求和。为此，递归地划分范围并生成与另一侧平行的一侧，然后同步并返回左+右的总和值。