2. 矩阵乘法并行化

任务说明

实现一个线程池并行的矩阵乘法：给定两个 N×N 方阵 A 和 B，计算 C = A × B。将输出矩阵 C 的每个元素作为一个独立任务提交到线程池，每个任务计算一个 C[i][j] = Σ A[i][k]·B[k][j]。同时提供串行版本作为基准，通过计时对比验证并行加速效果。

核心实现

#include <vector>
#include <thread>
#include <atomic>
#include <functional>
#include <queue>
#include <mutex>
#include <condition_variable>
#include <chrono>
#include <iostream>
#include <random>

// ---------- 线程池 ----------
class ThreadPool {
public:
    ThreadPool(size_t threads) : stop(false) {
        for (size_t i = 0; i < threads; ++i)
            workers.emplace_back([this] {
                for (;;) {
                    std::function<void()> task;
                    {
                        std::unique_lock<std::mutex> lock(queue_mutex);
                        cv.wait(lock, [this] { return stop || !tasks.empty(); });
                        if (stop && tasks.empty()) return;
                        task = std::move(tasks.front());
                        tasks.pop();
                    }
                    task();
                }
            });
    }
    ~ThreadPool() {
        {
            std::unique_lock<std::mutex> lock(queue_mutex);
            stop = true;
        }
        cv.notify_all();
        for (auto &w : workers) w.join();
    }
    template<class F>
    void enqueue(F&& f) {
        {
            std::unique_lock<std::mutex> lock(queue_mutex);
            tasks.emplace(std::forward<F>(f));
        }
        cv.notify_one();
    }
private:
    std::vector<std::thread> workers;
    std::queue<std::function<void()>> tasks;
    std::mutex queue_mutex;
    std::condition_variable cv;
    bool stop;
};

// ---------- 矩阵乘法 ----------
using Matrix = std::vector<std::vector<double>>;

// 串行版本
Matrix matmul_serial(const Matrix& A, const Matrix& B) {
    size_t n = A.size();
    Matrix C(n, std::vector<double>(n, 0.0));
    for (size_t i = 0; i < n; ++i)
        for (size_t j = 0; j < n; ++j)
            for (size_t k = 0; k < n; ++k)
                C[i][j] += A[i][k] * B[k][j];
    return C;
}

// 线程池并行版本：每个输出元素一个任务
Matrix matmul_parallel(const Matrix& A, const Matrix& B, size_t num_threads) {
    size_t n = A.size();
    Matrix C(n, std::vector<double>(n, 0.0));
    ThreadPool pool(num_threads);
    for (size_t i = 0; i < n; ++i) {
        for (size_t j = 0; j < n; ++j) {
            pool.enqueue([&A, &B, &C, i, j, n] {
                double sum = 0.0;
                for (size_t k = 0; k < n; ++k)
                    sum += A[i][k] * B[k][j];
                C[i][j] = sum;
            });
        }
    }
    return C;  // 注意：析构时等待所有任务完成
}

// ---------- 主程序 ----------
int main() {
    const size_t N = 256;
    const size_t THREADS = std::thread::hardware_concurrency();

    // 随机初始化
    std::mt19937 rng(42);
    std::uniform_real_distribution<double> dist(0.0, 1.0);
    Matrix A(N, std::vector<double>(N)), B(N, std::vector<double>(N));
    for (auto& row : A) for (auto& v : row) v = dist(rng);
    for (auto& row : B) for (auto& v : row) v = dist(rng);

    // 串行计时
    auto t0 = std::chrono::high_resolution_clock::now();
    Matrix C_serial = matmul_serial(A, B);
    auto t1 = std::chrono::high_resolution_clock::now();
    double serial_ms = std::chrono::duration<double, std::milli>(t1 - t0).count();

    // 并行计时
    auto t2 = std::chrono::high_resolution_clock::now();
    Matrix C_parallel = matmul_parallel(A, B, THREADS);
    auto t3 = std::chrono::high_resolution_clock::now();
    double parallel_ms = std::chrono::duration<double, std::milli>(t3 - t2).count();

    // 正确性校验
    double max_diff = 0.0;
    for (size_t i = 0; i < N; ++i)
        for (size_t j = 0; j < N; ++j)
            max_diff = std::max(max_diff, std::abs(C_serial[i][j] - C_parallel[i][j]));

    std::cout << "矩阵规模: " << N << "x" << N << ", 线程数: " << THREADS << "\n";
    std::cout << "串行耗时: " << serial_ms << " ms\n";
    std::cout << "并行耗时: " << parallel_ms << " ms\n";
    std::cout << "最大误差: " << max_diff << " (应接近0)\n";
    return 0;
}

编译与运行

g++ -O2 -std=c++11 -pthread matmul.cpp -o matmul
./matmul

验证方法

程序输出包含三项指标：串行耗时、并行耗时、最大误差。判定标准：

• 正确性：最大误差小于 1e-9，说明并行结果与串行一致；
• 性能：并行耗时明显低于串行耗时（通常加速 2~6 倍，取决于 CPU 核心数）；
• 可复现性：固定随机种子 42，每次运行结果一致。

关键设计说明

• 任务粒度：每个输出元素 C[i][j] 作为一个独立任务，任务间无数据竞争（各自写不同位置），无需加锁；
• 同步机制：ThreadPool 析构函数会等待所有已入队任务执行完毕，因此 matmul_parallel 返回时结果已完整写入；
• 性能对比：串行与并行使用相同的矩阵数据和相同的计算顺序，仅调度方式不同，保证对比公平性。