最大化在 C 中然后在 MIPS 汇编中对 24x24 矩阵进行三角化的性能和效率

Question

最近，我对计算机体系结构和性能领域产生了兴趣。话虽如此，我一直在选择一种“更简单”的汇编语言来真正尝试和学习东西“在幕后工作”的方式。即MIPS汇编。我觉得可以尝试和试验一些更高级的东西，因此我决定将编程与我对数学的兴趣结合起来。

我的目标很简单，给定一个 24x24（我不关心任何其他大小）矩阵 A，我想编写一个同样高效的算法尽可能找到矩阵的 上三角形式 。高效的意思是我希望最终达到一种状态，即我使用处理器的状态，我正在尽我所能地使用资源。 高缓存命中率、内存的高效使用（引用原则的局部性等）、性能运行解决方案等

最终我的目标是将 C 解决方案转换为 MIPS 汇编，并对其进行调整以适应我将尝试运行我的算法的处理器的内存子系统。关于处理器，当涉及到缓存、写缓冲区和内存时，我将有不同的选择，因为我可以使用不同的缓存大小、块大小、关联级别、内存访问时间等。这种情况下的性能将测量 三角化 24x24 矩阵所需的时间。

首先，我需要实际编写一些高级代码并实际解决那里的问题，然后再深入研究 MIPS 汇编。我“环顾四周”，最终想出了这个看似标准的解决方案。它不一定超快，我也不认为它是三角化 24x24 矩阵的最佳选择。我可以做得更好吗？

void triangularize(float **A, int N)
{
    int i, j, k;
    // Loop over the diagonal elements
    for (k = 0; k < N; k++)
    {
        // Loop over all the elements in the pivot row and right of the pivot ELEMENT
        for (j = k + 1; j < N; j++)
        {
            // divide by the pivot element
            A[k][j] = A[k][j] / A[k][k];
        }
    
        // Set the pivot elements
        A[k][k] = 1.0;

        // Loop over all elements below the pivot right an right of the pivot COLUMN
        for (i = k + 1; i < N; i++)
        {
            for (j = k + 1; j < N; j++)
            {
                A[i][j] = A[i][j] - A[i][k] * A[k][j];
            }
            A[i][k] = 0.0;
        }
    }
}

此外，在尝试将 C 代码转换为 MIPS 程序集时，我的下一步应该如何最大化性能和最小化成本（缓存命中率、处理内存时的 IO 成本等）获得闪电般快速高效的解决方案？

Answer 1

首先，将矩阵编码为 锯齿状数组（即 float**）通常效率不高，因为它会导致不必要的昂贵 间接寻址 并且数组在内存中可能不连续，导致更多 缓存未命中 甚至 缓存垃圾 在病态情况下。将矩阵复制到 连续展平数组 中当然更好。请考虑将您的矩阵存储为通常更高效的展平数组（尤其是在 MIPS 上）。可以使用 array[i*24+j] 而不是 array[i][j].

之类的东西来索引展平数组

此外，如果您不关心 24x24 以外的矩阵，那么您可以为 24x24 矩阵编写 专用代码 。这有助于编译器生成更高效的汇编代码（通常通过 展开循环 并使用更高效的指令，例如乘以常数）。

此外，除法通常很昂贵，尤其是在嵌入式 MIPS 处理器上。因此，您可以用逆乘法代替除法。例如：

float inv = 1.0f / A[k][k];

for (j = k + 1; j < N; j++)
    A[k][j] *= inv;

请注意，由于 floating-point 四舍五入，结果可能略有不同。如果您知道 NaN 或 Inf 等特殊值不会出现在矩阵中，您可以使用 -ffast-math 编译器标志来帮助它生成此类优化。

此外，手动展开循环可能会更快，因为并非所有编译器都（正确地）这样做。也就是说，循环展开的好处是 非常依赖于目标处理器 （此处未指定）。没有更多信息，很难知道这是否有用。例如，一些处理器每个周期可以执行多个 floating-point 操作，而另一些处理器甚至不能在本地执行（即没有硬件 FP 单元）：它们以某种方式用许多非常昂贵的指令进行模拟（像 GCC 这样的编译器可以运行在此类处理器上调用 addition/subtraction 等基本操作）。如果没有硬件 FP 单元，那么使用固定精度可能会更快。

最后，一些 MIPS 处理器有一个 128 位 SIMD 单元。使用它应该会显着加快执行速度。编译器应该能够大部分 auto-vectorize 你的代码，但你需要告诉他们你的目标处理器是否支持它（参见 GCC/Clang 的 -march 标志）。对于 fixed-size 矩阵，假设您编写了高效的代码，手动矢量化通常会导致执行速度更快（比 auto-vectorisation）。

最大化在 C 中然后在 MIPS 汇编中对 24x24 矩阵进行三角化的性能和效率

Maximizing the performance and efficiency of triangularizing a 24x24 matrix in C and then in MIPS assembly

c

algorithm

matrix

optimization

mips