c - 如何优化矩阵初始化和转置以使用 C 运行得更快

Question

这个矩阵的维度是40000*40000。我应该考虑程序的空间和时间局部性，但我不知道如何优化这段代码。它在我的电脑上花费了大约 50 多秒，这对我们小组来说是不能接受的。 block 的大小现在是 500。有人可以帮我改进这段代码吗？

void      InitializeMatrixRowwise(){
    int i,j,ii,jj;
    double x;
    x = 0.0;
    for (i = 0; i < DIMENSION; i += BLOCKSIZE)
    {
        for (j = 0; j < DIMENSION; j += BLOCKSIZE)
        {
            for (ii = i; ii < i+BLOCKSIZE && ii < DIMENSION; ii++)
            {
                for (jj = j; jj < j+BLOCKSIZE && jj < DIMENSION; jj++)
                {
                    if (ii >= jj)
                    {
                        Matrix[ii][jj] = x++;
                    }
                    else
                        Matrix[ii][jj] = 1.0;
                 }
             }
         }
     }
 }




void        TransposeMatrixRowwise(){
int column,row,i,j;
double temp;
for (row = 0; row < DIMENSION; row += BLOCKSIZE)
{
    for (column = 0; column < DIMENSION; column += BLOCKSIZE)
    {
        for (i = row; i < row + BLOCKSIZE && i < DIMENSION; i++)
        {
            for (j = column; j < column + BLOCKSIZE && j < DIMENSION; j++)
            {
                if (i > j)
                {
                    temp = Matrix[i][j];
                    Matrix[i][j] = Matrix[j][i];
                    Matrix[j][i] = temp;
                 }
             }
         }
     }
 }
 }

Answer 1

您的转置函数看起来可能比必要的更复杂，因此可能比必要的慢。但是，我创建了两个版本的代码，在“全尺寸”(40k x 40k 阵列，500 x 500 block )上插入了时间，一个使用你的转置函数，另一个使用这个更简单的算法:

static void TransposeMatrixRowwise(void)
{
    for (int row = 0; row < DIMENSION; row++)
    {
        for (int col = row + 1; col < DIMENSION; col++)
        {
            double temp = Matrix[row][col];
            Matrix[row][col] = Matrix[col][row];
            Matrix[col][row] = temp;
        }
    }
}

这看起来简单多了；它只有两个嵌套循环而不是四个，但时间证明要差得多——31.5 秒对 14.7 秒。

# Simple transpose
# Count    = 7
# Sum(x1)  =  220.87
# Sum(x2)  = 6979.00
# Mean     =   31.55
# Std Dev  =    1.27 (sample)
# Variance =    1.61 (sample)
# Min      =   30.41
# Max      =   33.54

# Complex transpose
# Count    = 7
# Sum(x1)  =  102.81
# Sum(x2)  = 1514.00
# Mean     =   14.69
# Std Dev  =    0.82 (sample)
# Variance =    0.68 (sample)
# Min      =   13.59
# Max      =   16.21

性能差异的原因几乎可以肯定是由于引用的位置。更复杂的算法一次处理两个独立的内存块，而更简单的算法遍历更多的内存，导致更多的页面未命中和更慢的性能。

因此，虽然您可以使用不同的 block 大小(它不需要与用于生成矩阵的 block 大小相同)调整转置算法，但基于这些测量结果毫无疑问 越复杂的算法越有效。

我还在 1/10 比例下进行了检查——4k x 4k 矩阵，50 x 50 block 大小——以确保转置的输出相同(大约 152 MiB 的文本)。我没有用超过 100 倍的数据以全尺寸保存数据。对于 1/10 比例下的两个版本，1/10 比例下的时间要好得多——不到 1/100 倍:

< Initialization: 0.068667
< Transposition: 0.063927
---
> Initialization: 0.081022
> Transposition: 0.039169
4005c4005
< Print transposition: 3.901960
---
> Print transposition: 4.040136

JFTR:在运行 macOS High Sierra 10.13.1、2.7 GHz Intel Core i7 CPU 和 16 GB 2133 MHz LPDDR3 RAM 的 2016 MacBook Pro 上进行测试。编译器是 GCC 7.2.0(自制)。浏览器正在运行(但大部分时间处于非事件状态)并且在后台播放音乐，因此机器没有闲置，但我认为这些不会显着影响数字。