C语言实现矩阵乘法（包括使用SIMD）

驰宇

Matrix Multiplication

Github 链接
如何运行这个项目？

最简单的方法：使用CLion运行。
或者：
mkdir build
cd build
cmake ..
make
./matrix_multiplication如果有错误，请编辑`CMakeLists.txt`, 降低CMAKE的最低版本要求。
algorithms

Traditional

任何人都能想到的最简单的解决方案。
int algorithm1(ARRAY_TYPE** m1, ARRAY_TYPE** m2, ARRAY_TYPE** r, int x1, int y1, int x2, int y2){
    for (int i = 0; i < x1; ++i) {
        for (int j = 0; j < y2; ++j) {
            r[j] = 0;
            for (int k = 0; k < y1; ++k) {
                r[j] += m1[k] * m2[k][j];
            }
        }
    }
    return 0;
}
memory friendly

我们做了一些研究，发现如果我们改变循环顺序，它会保持正确性，同时速度会提高，因为缓存命中率会增加
int algorithm3(ARRAY_TYPE** m1, ARRAY_TYPE** m2, ARRAY_TYPE** r, int x1, int y1, int x2, int y2){
    for (int i = 0; i < x1; ++i) {
        for (int j = 0; j < y2; ++j) {
            r[j] = 0;
        }
    }

    for (int i = 0; i < x1; ++i) {
        for (int k = 0; k < y1; ++k){
            for (int j = 0; j < y2; ++j) {
                r[j] += m1[k] * m2[k][j];
            }
        }
    }


    return 0;
}SIMD

下面写的算法和matrix中算法的区别在于我们在后者中使用了loop unrolling的方法来减少循环次数。
注意： 要运行该方法，需要编译中使用： `-march=native `。具体查看`CMakeLists.txt`
int algorithm2( ARRAY_TYPE **a,  ARRAY_TYPE **bb, ARRAY_TYPE **c, int size){
    ARRAY_TYPE** b = malloc(sizeof(ARRAY_TYPE*) * size);
    for (int i = 0; i < size; ++i) {
        b = malloc(sizeof(ARRAY_TYPE) * size);
        for (int j = 0; j < size; j++) {
            b[j] = bb[j];
            c[j] = 0;
        }
    }

    for (int i = 0; i < size; ++i) {
        for (int j = 0; j < size; j+=8) {
            __m256 m_a =  _mm256_loadu_ps(a + j);
            for (int k = 0; k < size; k++) {
                __m256 m_b =  _mm256_loadu_ps(b[k] + j);
                __m256 m_c = _mm256_mul_ps(m_a, m_b);
                c[k] += m_c[0];
                c[k] += m_c[1];
                c[k] += m_c[2];
                c[k] += m_c[3];
                c[k] += m_c[4];
                c[k] += m_c[5];
                c[k] += m_c[6];
                c[k] += m_c[7];
            }

        }

    }
}Result

method: 1 total consume: 3338 ms
method: 1 total time_taken only multiply: 2450 ms
================
method: 2 total consume: 1718 ms
method: 2 total time_taken only multiply: 897 ms
================
method: 3 total consume: 2261 ms
method: 3 total time_taken only multiply: 1426 ms
================ "total consume" and "total time taken only multiply" 有什么区别？?
最后一个只需要乘法过程所花费的时间。 为了进行多次测试，我们每次都需要做同样的准备工作，这些工作很耗时，但这些时间不应该计入乘法所需的时间。 理想情况下，一种准备工作将进行多次。 例如，不是为每个操作都创建矩阵，而是使用预先生成的矩阵。
Test

我写了简单的测试函数来测试它们。 这些函数可以在测试目录中找到。
Implement

目前实现的SIMD算法只能对边长为8的倍数的方阵进行运算，未来可以对任意矩阵进行乘法运算。
Issues

为了显示SIMD算法的优秀，需要在Cmake中指定`-O1`或以上。 `-O0` 是 cmake 中的默认值吗？
GitHub

Github 链接