如何使用C语言优化矩阵初始化和转置以获得更快的运行速度

Question

如何使用C语言优化矩阵初始化和转置以获得更快的运行速度

3

这个矩阵的尺寸为40000*40000。我原本应该考虑程序的空间和时间局部性，但我不知道如何优化这段代码。它在我的电脑上需要50多秒的时间，这对我们的团队来说是不能接受的。目前块的大小为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;
                 }
             }
         }
     }
 }
 }

- Cecilia Ren

你使用的编译器和标志是什么？可能的第一步是尝试一些基于编译器的优化，另一件事情是确保整数存储在寄存器中而不是缓存/内存中，可能需要使用内联汇编。 - Unh0lys0da

您需要在会话期间仅进行一次50秒以上的初始化，还是需要多次进行？ - Déjà vu

1

如果矩阵中的元素是 double 类型，则一个大小为 40k x 40k 的矩阵大约使用 12.8 GiB 的空间，如果是 float 类型的元素，则使用的空间将减半。这非常庞大；即使假设您有足够的物理内存将其全部保存在内存中，初始化这么多数据也需要时间。 - Jonathan Leffler

当我在2016年的MacBook Pro上使用定时测试工具对您的代码进行40k x 40k的计时测试，块大小为500 x 500时，使用16 GiB 2133 MHz LPDDR3 RAM和2.7 GHz Intel Core i7处理器，结果显示Matrix (40000x40000, blocks 500x500) / Initialization: 10.597134 / Transposition: 22.087354，总共花费了将近33秒，这与您测量的结果完全相当。使用块大小子单元的代码潜在地会导致对内存的顺序访问较少，但通过其他机制获得相同的结果绝非易事。我尝试了一种方法，但产生了不同的结果。 - Jonathan Leffler

实际上，根据需求，元素必须是双倍的。 - Cecilia Ren

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jonathan Leffler · Accepted Answer

您的转置函数似乎比必要的更加复杂，因此可能比必要的更慢。然而，我创建了两个版本的代码，并在“完整大小”（40k x 40k数组，带有500 x 500块）上插入了时间，一个使用您的转置函数，另一个使用这个简单得多的算法：

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

性能差异的原因几乎肯定是由于引用局部性。更复杂的算法一次处理两个独立的内存块，而简单的算法则需要涉及更多的内存，导致更多的页面缺失和较慢的性能。

因此，虽然你可能能够通过使用不同的块大小来调整转置算法（它不必与生成矩阵时使用的块大小相同），但根据这些测量结果，毫无疑问更复杂的算法更高效。

我还进行了1/10比例的检查——4k x 4k矩阵，50 x 50块大小——以确保转置的输出相同（大约152 MiB的文本）。我没有保存超过100倍数据的全尺寸数据。在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英特尔Core i7 CPU和16 GB 2133 MHz LPDDR3 RAM的2016 MacBook Pro。编译器是GCC 7.2.0（自制）。有一个浏览器正在运行（但大部分时间处于闲置状态），背景中播放着音乐，因此机器并不空闲，但我认为这些不会显著影响数字。