5

乗算の前に行列を転置すると、キャッシュの局所性のために操作が大幅に高速化されると聞きました。そこで、単純な C++ プログラムを作成して、行優先順序でテストしました (コンパイルには C++11 とブーストが必要です)。

結果は驚くべきものです: 7.43 秒対 0.94 秒。しかし、なぜそれが高速化するのか理解できません。実際、2 番目のバージョン (最初に転置) では、乗算コードはストライド 1 パターンを介してデータにアクセスし、最初のバージョンよりも局所性がはるかに優れています。ただし、行列 B を転置するには、データに非連続的にアクセスする必要があり、多くのキャッシュ ミスも発生します。メモリの割り当てとデータのコピーのオーバーヘッドも無視できないはずです。では、なぜ 2 番目のバージョンはコードをそれほど高速化するのでしょうか?

#include <iostream>
#include <vector>
#include <boost/timer/timer.hpp>
#include <random>

std::vector<int> random_ints(size_t size)
{
    std::vector<int> result;
    result.reserve(size);
    std::random_device rd;
    std::mt19937 engine(rd());
    std::uniform_int_distribution<int> dist(0, 100);
    for (size_t i = 0; i < size; ++i)
        result.push_back(dist(engine));
    return result;
}

// matrix A: m x n; matrix B: n x p; matrix C: m x n;
std::vector<int> matrix_multiply1(const std::vector<int>& A, const std::vector<int>& B, size_t m, size_t n, size_t p)
{
    boost::timer::auto_cpu_timer t;
    std::vector<int> C(m * p);
    for (size_t i = 0; i < m; ++i)
    {
        for (size_t j = 0; j < p; ++j)
        {
            for (size_t k = 0; k < n; ++k)
            {
                C[i * m + j] += A[i * m + k] * B[k * n + j];
                // B is accessed non-sequentially
            }
        }
    }
    return C;
}

// matrix A: m x n; matrix B: n x p; matrix C: m x n;
std::vector<int> matrix_multiply2(const std::vector<int>& A, const std::vector<int>& B, size_t m, size_t n, size_t p)
{
    boost::timer::auto_cpu_timer t;
    std::vector<int> C(m * p), B_transpose(n * p);

    // transposing B
    for (size_t i = 0; i < n; ++i)
    {
        for (size_t j = 0; j < p; ++j)
        {
            B_transpose[i + j * p] = B[i * n + j];
            // B_transpose is accessed non-sequentially
        }
    }

    // multiplication
    for (size_t i = 0; i < m; ++i)
    {
        for (size_t j = 0; j < p; ++j)
        {
            for (size_t k = 0; k < n; ++k)
            {
                C[i * m + j] += A[i * m + k] * B_transpose[k + j * p];
                // all sequential access
            }
        }
    }
    return C;
}

int main()
{
    const size_t size = 1 << 10;
    auto A = random_ints(size * size);
    auto C = matrix_multiply1(A, A, size, size, size);
    std::cout << C.front() << ' ' << C.back() << std::endl; // output part of the result
    C = matrix_multiply2(A, A, size, size, size);
    std::cout << C.front() << ' ' << C.back() << std::endl; // compare with output of algorithm 1
    return 0;
}
4

1 に答える 1

-2

乗算は転置よりも多くのアクセスを伴うため、実行時間の大半を占めます。

for ループ ヘッダーを見るだけで、これは非常に明確にわかります。

// transpose
for (size_t i = 0; i < n; ++i)
    for (size_t j = 0; j < p; ++j)
        ...

// multiplication
for (size_t i = 0; i < m; ++i)
    for (size_t j = 0; j < p; ++j)
        for (size_t k = 0; k < n; ++k)
            ...

ネストを追加すると、2 番目は明らかにはるかに多くの作業になります。

于 2013-10-25T03:55:44.783 に答える