为什么转置 512x512 矩阵比转置 513x513 矩阵慢得多？

为什么转置 512x512 矩阵比转置 513x513 慢

在对不同大小的矩阵进行实验后，出现了转置矩阵的一个奇特现象：转置维度为 2^ 的矩阵n 在计算上比转置维度为 2^n 1 的计算成本更高。当 n 等于 512 时，差异变得显着。

为转置运算提供的代码如下：

#define SAMPLES 1000
#define MATSIZE 512

#include <time.h>
#include <iostream>
int mat[MATSIZE][MATSIZE];

void transpose()
{
   for ( int i = 0 ; i < MATSIZE ; i++ )
   for ( int j = 0 ; j < MATSIZE ; j++ )
   {
       int aux = mat[i][j];
       mat[i][j] = mat[j][i];
       mat[j][i] = aux;
   }
}

int main()
{
   //initialize matrix
   for ( int i = 0 ; i < MATSIZE ; i++ )
   for ( int j = 0 ; j < MATSIZE ; j++ )
       mat[i][j] = i+j;

   int t = clock();
   for ( int i = 0 ; i < SAMPLES ; i++ )
       transpose();
   int elapsed = clock() - t;

   std::cout << "Average for a matrix of " << MATSIZE << ": " << elapsed / SAMPLES;
}

通过更改 MATSIZE 宏，可以修改矩阵的大小。以下基准说明了明显的差异：

• 大小 512：平均 2.46 毫秒
• 大小 513：平均 0.75 毫秒

缓存争用和关键步幅

此异常背后的原因在于缓存行为以及缓存争用的概念。以下是细分：

• 缓存由集合和行组成。在任何给定时刻，仅访问一组，并且可以使用该组内的任何线路。总缓存大小由行数乘以每行大小决定。
• 要计算特定内存地址所属的集合，请使用以下公式：set = ( address / lineSize ) % numberOfsets.
• 当多个内存地址访问同一个集合时，就会出现缓存冲突。在这种情况下，集合中最近最少使用的行将被新检索的数据覆盖。
• 关键步长，表示导致缓存冲突的内存访问次数，计算公式为： criticalStride = numberOfSets * lineSize。
• 对于具有 8kb 缓存的 64x64 矩阵，关键步幅将与矩阵的行完美对齐，从而导致转置期间过多的缓存重新加载。
• 但是，当矩阵大小增加到 65x65 时，关键步幅不再完美对齐，从而减少缓存冲突的频率并提高性能。

因此，由于缓存争用，对于维度为 2^n 倍数的矩阵，转置操作会明显变慢。

以上是为什么转置 512x512 矩阵比转置 513x513 矩阵慢得多？的详细内容。更多信息请关注PHP中文网其他相关文章！