多线程的矩阵乘法是否比单线程的慢？

Question

我写了一些Naive GEMM代码，但它比等效的单线程GEMM代码慢得多。

使用200x200矩阵，单线程：7ms，多线程：108ms，CPU：3930k，在线程池中有12个线程。

    template <unsigned M, unsigned N, unsigned P, typename T>
    static Matrix<M, P, T> multiply( const Matrix<M, N, T> &lhs, const Matrix<N, P, T> &rhs, ThreadPool & pool )
    {
        Matrix<M, P, T> result = {0};

        Task<void> task(pool);
        for (auto i=0u; i<M; ++i)
            for (auto j=0u; j<P; j++)
                task.async([&result, &lhs, &rhs, i, j](){
                    T sum = 0;
                    for (auto k=0u; k < N; ++k)
                        sum += lhs[i * N + k] * rhs[k * P + j];
                    result[i * M + j] = sum;
            });

        task.wait();

        return std::move(result);
    }

- aCuria

---

我希望你测量了至少5秒的长时间重复运行，并且平均运行时间在7毫秒和128毫秒之间？否则，你的计时可能会不准确且没有太多意义。 - IvoTops

Answer 1

我没有使用GEMM的经验，但是您的问题似乎与所有多线程场景中出现的问题有关。

使用多线程时，您会引入几个潜在的开销，其中最常见的通常是：

1. 创建/清除起始/结束线程
2. 当（线程数）>（CPU核心数）时进行上下文切换
3. 锁定资源，等待获取锁
4. 缓存同步问题

2.和3.可能不在您的示例中发挥作用：您正在12个(超线程)核心上使用12个线程，而您的算法不涉及锁。

然而，1.可能与您的情况有关：您总共创建了40000个线程，每个线程都要乘以200个值并加上。我建议尝试一下更少的细粒度线程，也许只在第一个循环之后分割。将问题分成不必要的小块永远是一个好主意。

此外，4.在您的情况下非常重要。虽然您没有遇到写入数组结果时的竞争条件（因为每个线程都在写入自己的索引位置），但您很可能会引发大量的缓存同步开销。

"为什么?"您可能会想，因为您正在写入内存中的不同位置。这是因为典型的CPU缓存以缓存行组织，当前的Intel和AMD CPU型号的缓存行长度为64字节。这是可以用于从缓存传输到缓存，并在更改时使用的最小大小。现在,所有CPU核心都在读写相邻的内存单元，每当您只写入4个字节（或8个字节，具体取决于您使用的数据类型的大小）时，这会导致所有核心之间的64字节的同步。

如果内存不是问题，则可以简单地将每个输出数组元素用“虚拟”数据进行“填充”，以便每个缓存行仅有一个输出元素。如果您使用4字节数据类型，则这意味着跳过每1个真实数据元素15个数组元素。当您使线程不那么细粒度时，缓存问题也会得到改善，因为每个线程将访问自己的连续内存区域，几乎不干扰其他线程的内存。

编辑：Herb Sutter（C++大师之一）的更详细描述可在此处找到：http://www.drdobbs.com/parallel/maximize-locality-minimize-contention/208200273

编辑2：顺便提一下，建议在返回语句中避免使用std::move，因为这可能会妨碍返回值优化和复制省略规则，标准现在要求这些自动发生。请参见在多个返回语句的情况下使用`std::move`是否明智？

- Piotr99

---

对于＃1，我在程序运行期间保持线程活动状态，因此创建成本是一次性的。至于启动和结束线程，成本是调用条件变量唤醒线程和每个线程使用互斥锁从任务容器中获取任务。话虽如此，通过采取您的建议仅在第一个循环后拆分，时间大大改善（500x500矩阵上为40ms，而单线程版本为114ms）。尽管如此，它并没有达到我希望的12倍加速。 - aCuria

Answer 2

多线程意味着始终需要同步、上下文切换和函数调用。所有这些都会累加并消耗 CPU 周期，而这些周期可以用在主要任务本身上。

如果你只有一个三层嵌套循环，你就能节省掉所有这些步骤，并且可以直接在计算中内联处理，而不是通过子程序进行处理，其中必须设置一个栈，调用线程，切换到不同的线程，返回结果并切换回主线程。

多线程仅在这些成本与主要任务相比较小的情况下才有用。我想，当矩阵大于只有 200x200 时，您将看到更好的多线程结果。

- Olaf Dietsche

Answer 3

通常情况下，多线程适用于花费大量时间的任务，最好是因为复杂性而非设备访问。你展示给我们的循环执行时间太短了，无法有效地并行化。

你必须记住，线程创建会带来很多开销。同步也会带来一些开销，但相对较少。

- Dariusz