可能重复:
这两个for循环中的哪一个在时间和缓存性能方面更有效

下面是两个几乎相同的程序,除了我切换i和j变量.它们都运行在不同的时间.有人能解释为什么会这样吗？

版本1

#include <stdio.h>
#include <stdlib.h>

main () {
  int i,j;
  static int x[4000][4000];
  for (i = 0; i < 4000; i++) {
    for (j = 0; j < 4000; j++) {
      x[j][i] = i + j; }
  }
}

版本2

#include <stdio.h>
#include <stdlib.h>

main () {
  int i,j;
  static int x[4000][4000];
  for (j = 0; j < 4000; j++) {
     for (i = 0; i < 4000; i++) {
       x[j][i] = i …

在对不同尺寸的方形矩阵进行一些实验后,出现了一种模式.转换一个大小的矩阵2^n2^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 ; …

我正在进行一些矩阵乘法基准测试,如前面提到的 为什么MATLAB在矩阵乘法中如此之快？

现在我有另一个问题,当乘以两个2048x2048矩阵时,C#和其他矩阵之间存在很大差异.当我尝试只乘2047x2047矩阵时,看起来很正常.还添加了一些其他的比较.

1024x1024 - 10秒.

1027x1027 - 10秒.

2047x2047 - 90秒.

2048x2048 - 300秒.

2049x2049 - 91秒.(更新)

2500x2500 - 166秒

对于2k×2k的情况,这是三分半钟的差异.

使用2dim数组

//Array init like this
int rozmer = 2048;
float[,] matice = new float[rozmer, rozmer];

//Main multiply code
for(int j = 0; j < rozmer; j++)
{
   for (int k = 0; k < rozmer; k++)
   {
     float temp = 0;
     for (int m = 0; m < rozmer; m++)
     {
       temp = temp + matice1[j,m] * matice2[m,k]; …

我有一个矩阵乘法代码,如下所示:

for(i = 0; i < dimension; i++)
    for(j = 0; j < dimension; j++)
        for(k = 0; k < dimension; k++)
            C[dimension*i+j] += A[dimension*i+k] * B[dimension*k+j];

这里,矩阵的大小由表示dimension.现在,如果矩阵的大小是2000,运行这段代码需要147秒,而如果矩阵的大小是2048,则需要447秒.所以虽然差别没有.乘法是(2048*2048*2048)/(2000*2000*2000)= 1.073,时间上的差异是447/147 = 3.有人可以解释为什么会发生这种情况吗？我预计它会线性扩展,但这不会发生.我不是要尝试制作最快的矩阵乘法代码,只是试图理解它为什么会发生.

规格:AMD Opteron双核节点(2.2GHz),2G RAM,gcc v 4.5.0

程序编译为 gcc -O3 simple.c

我也在英特尔的icc编译器上运行了这个,并看到了类似的结果.

编辑:

正如评论/答案中所建议的那样,我运行了维度= 2060的代码,需要145秒.

继承完整的计划:

#include <stdlib.h>
#include <stdio.h>
#include <sys/time.h>

/* change dimension size as needed */
const int dimension = 2048;
struct timeval tv; 

double timestamp()
{
        double t;
        gettimeofday(&tv, NULL);
        t = tv.tv_sec + (tv.tv_usec/1000000.0); …

我测试了memcpy()在i*4KB时注意速度急剧下降的速度.结果如下:Y轴是速度(MB /秒),X轴是缓冲区的大小memcpy(),从1KB增加到2MB.子图2和子图3详述了1KB-150KB和1KB-32KB的部分.

环境:

CPU:Intel(R)Xeon(R)CPU E5620 @ 2.40GHz

操作系统:2.6.35-22-通用#33-Ubuntu

GCC编译器标志:-O3 -msse4 -DINTEL_SSE4 -Wall -std = c99

我想它必须与缓存相关,但我无法从以下缓存不友好的情况中找到原因:

• 为什么我的程序在完全循环8192个元素时会变慢？

• 为什么转换512x512的矩阵要比转换513x513的矩阵慢得多？

由于这两种情况的性能下降是由不友好的循环引起的,这些循环将分散的字节读入高速缓存,浪费了高速缓存行的其余空间.

这是我的代码:

void memcpy_speed(unsigned long buf_size, unsigned long iters){
    struct timeval start,  end;
    unsigned char * pbuff_1;
    unsigned char * pbuff_2;

    pbuff_1 = malloc(buf_size);
    pbuff_2 = malloc(buf_size);

    gettimeofday(&start, NULL);
    for(int i = 0; i < iters; ++i){
        memcpy(pbuff_2, pbuff_1, buf_size);
    }   
    gettimeofday(&end, NULL);
    printf("%5.3f\n", ((buf_size*iters)/(1.024*1.024))/((end.tv_sec - \
    start.tv_sec)*1000*1000+(end.tv_usec - start.tv_usec)));
    free(pbuff_1);
    free(pbuff_2);
}

UPDATE

考虑到来自@ usr,@ ChrisW和@Leeor的建议,我更准确地重新测试了测试,下面的图表显示了结果.缓冲区大小从26KB到38KB,我每隔64B测试一次(26KB,26KB + …

我正在经历循环,发现访问循环有显着差异.我无法理解在两种情况下造成这种差异的原因是什么？

第一个例子:

执行时间处理时间; 8秒

for (int kk = 0; kk < 1000; kk++)
{
    sum = 0;
    for (int i = 0; i < 1024; i++)
        for (int j = 0; j < 1024; j++)
        {
            sum += matrix[i][j];
        }
}

第二个例子:

执行时间:23秒

for (int kk = 0; kk < 1000; kk++)
{
    sum = 0;
    for (int i = 0; i < 1024; i++)
        for (int j = 0; j < 1024; j++)
        {
            sum += matrix[j][i];
        }
} …

我最近一直关注内存分配,对基础知识我有点困惑.我无法绕过简单的东西.分配内存意味着什么？怎么了？我很感激这些问题的答案:

1. 正在分配的"记忆"在哪里？
   
2. 这个"记忆"是什么？阵列中的空间？或者是其他东西？
   
3. 当这个"记忆"被分配时会发生什么？
   
4. 当内存被解除分配时会发生什么？
   

5. 如果有人可以回答malloc在这些C++行中所做的事情,它也会对我有所帮助:

   char* x; 
   x = (char*) malloc (8);
   

   Run Code Online (Sandbox Code Playgroud)

谢谢.

(出于测试目的)我编写了一个简单的方法来计算nxn矩阵的转置

void transpose(const size_t _n, double* _A) {
    for(uint i=0; i < _n; ++i) {
        for(uint j=i+1; j < _n; ++j) {
            double tmp  = _A[i*_n+j];
            _A[i*_n+j] = _A[j*_n+i];
            _A[j*_n+i] = tmp;
        }
    }
}

当使用优化级别O3或Ofast时,我期望编译器展开一些循环,这将导致更高的性能,尤其是当矩阵大小是2的倍数(即,每次迭代可以执行双循环体)或类似时.相反,我测量的恰恰相反.2的权力实际上表明执行时间显着增加.

这些尖峰也是64的固定间隔,间隔128更明显,依此类推.每个尖峰延伸到相邻的矩阵大小,如下表所示

size n  time(us)
1020    2649
1021    2815
1022    3100
1023    5428
1024    15791
1025    6778
1026    3106
1027    2847
1028    2660
1029    3038
1030    2613

我使用gcc版本4.8.2编译但是同样的事情发生在clang 3.5上,所以这可能是一些通用的东西？

所以我的问题基本上是:为什么执行时间周期性增加？是否有一些通用的东西与任何优化选项一起出现(就像clang和gcc一样)？如果是这样的优化选项导致了这个？

这怎么可能如此重要,即使O0版本的程序在512的倍数时优于03版本？

编辑:注意此(对数)图中峰值的大小.转换具有优化的1024x1024矩阵实际上花费的时间与在没有优化的情况下转置1300x1300矩阵一样多.如果这是一个缓存故障/页面错误问题,那么有人需要向我解释为什么内存布局对于程序的优化版本是如此显着不同,它失败的功能为2,只是为了恢复高性能稍大的矩阵.缓存故障是否应该创建更多类似步骤的模式？为什么执行时间会再次下降？(为什么优化会创建以前不存在的缓存错误？)

编辑:以下应该是gcc生成的汇编代码

没有优化(O0):

_Z9transposemRPd:
.LFB0:
    .cfi_startproc
    push    rbp …

问题

我正在学习HPC和代码优化.我试图在Goto的开创性矩阵乘法论文(http://www.cs.utexas.edu/users/pingali/CS378/2008sp/papers/gotoPaper.pdf)中复制结果.尽管我付出了最大努力,但我无法超过理论CPU最高性能的50%.

背景

请参阅此处的相关问题(优化的2x2矩阵乘法:慢速装配与快速SIMD),包括有关我的硬件的信息

我尝试过的

这篇相关论文(http://www.cs.utexas.edu/users/flame/pubs/blis3_ipdps14.pdf)很好地描述了Goto的算法结构.我在下面提供了我的源代码.

我的问题

我要求一般帮助.我一直在研究这个问题太久了,已经尝试了很多不同的算法,内联汇编,各种尺寸的内核(2x2,4x4,2x8,...,mxn m和n大),但我似乎无法打破50%CPU Gflops.这纯粹是出于教育目的,而不是作业.

源代码

希望是可以理解的.如果没有请问.我设置了宏结构(for循环),如上面第2篇文章中所述.我按照两篇论文中的讨论打包矩阵,并在图11中以图形方式显示(http://www.cs.utexas.edu/users/flame/pubs/BLISTOMSrev2.pdf).我的内核计算2x8块,因为这似乎是Nehalem架构的最佳计算(参见GotoBLAS源代码 - 内核).内核基于计算排名1更新的概念,如此处所述(http://code.google.com/p/blis/source/browse/config/template/kernels/3/bli_gemm_opt_mxn.c)

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <string.h>
#include <x86intrin.h>
#include <math.h>
#include <omp.h>
#include <stdint.h>


// define some prefetch functions
#define PREFETCHNTA(addr,nrOfBytesAhead) \
        _mm_prefetch(((char *)(addr))+nrOfBytesAhead,_MM_HINT_NTA)

#define PREFETCHT0(addr,nrOfBytesAhead) \
        _mm_prefetch(((char *)(addr))+nrOfBytesAhead,_MM_HINT_T0)

#define PREFETCHT1(addr,nrOfBytesAhead) \
        _mm_prefetch(((char *)(addr))+nrOfBytesAhead,_MM_HINT_T1)

#define PREFETCHT2(addr,nrOfBytesAhead) \
        _mm_prefetch(((char *)(addr))+nrOfBytesAhead,_MM_HINT_T2)

// define a min function
#ifndef min
    #define min( a, b ) ( …

我试图更多地了解 CPU 缓存如何影响性能。作为一个简单的测试，我将矩阵第一列的值与不同数量的总列数相加。

// compiled with: gcc -Wall -Wextra -Ofast -march=native cache.c
// tested with: for n in {1..100}; do ./a.out $n; done | tee out.csv
#include <assert.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

double sum_column(uint64_t ni, uint64_t nj, double const data[ni][nj])
{
    double sum = 0.0;
    for (uint64_t i = 0; i < ni; ++i) {
        sum += data[i][0];
    }
    return sum;
}

int compare(void const* _a, void const* _b)
{
    double const a = *((double*)_a);
    double …