设为首页 加入收藏

TOP

C语言丨为什么转置512x512矩阵,会比513x513矩阵慢很多?(一)
2019-03-28 16:10:34 】 浏览:174
Tags:语言 为什么 512x512 矩阵 会比 513x513

事情的起因是这样的,先看下面这段代码:

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和513的时候,出现了非常有意思的结果:

512 平均 2.19ms

513 平均 0.57ms

很让人惊讶吧,513竟然比512快。更进一步的研究发现,size=512的时候,运算速度会比同数量级的其它数字慢很多很多。这是怎么一回事呢?

stackoverflow上大牛给的解答非常正确,但是这次,我不想做翻译了。我从Professor Sibert那里,从Professor Goel那里,学到的知识,足够帮我解决这个问题了,我不是一个人。下面是我的解答:

很容易就联想到,造成这个问题的原因是CPU cache,我们有很多种方式来存储cache,具体可以参考这里

原作者没有给出他的CPU型号,但是如今的pc几乎都是采用的set associative的cache结构,下面我用2-way set associate来做例子,讲解一下cache的工作原理。


(图片取自Professor Sibert的讲义,这可是纯ascii画的哦= =)

一个内存地址,可以划分为block,tag,word,byte 4个部分。10bits的block,对应了1024个cache set,内存地址的block固定了,就必须存储在相应的set里面,这样可以把查询cache的事件从O(n)缩短为O(1)。

举个例子,block是1023(1111111111),你的数据就放在第1023个set里面。可能有人会觉得奇怪,为什么block不是取的最前面的10bits,这当然是有道理的,通常在内存里数据都是连续存放的,就是说,同一段程序用的数据,他们前10位几乎都是一样的,如果用前10位来定位block,那么collision的发生率非常高,cache效率非常低下,所以才选了后面的10位来定位block。

当然,每个set里面有多条记录,2-way是2条,你得遍历这两条记录,比较前面50位的tag,如果tag一样,并且Valid bit(V)=1,那么恭喜你,你的数据在cache里面,接着就可以通过word和byte来取数据了。

如果遍历完这两条记录,还是没有找到tag的话,那么很遗憾,你的数据不在cache里,得从内存里读。从内存里获取相应的数据,然后把它存到对应的cache set里,如果set里有空位的话最好,如果没有的话,用LRU来替换。因为一个set里只有2条数据,所以实现LRU仅仅需要一个额外bit就可以了,非常高效。

好了,背景知识介绍的差不多了,让我们回到这个问题上来。为什么512大小的矩阵,会比其它数字慢那么多?

让我们来计算一下,512×512的int矩阵,在内存里是连续存放的。每个cache line是16bytes,对应4个int,所以一个n阶矩阵的row可以填充n/4个cache set。假设第一个数据a[0][0]正好对应cache set 0,那么其中每一个数据a[i][j]对应的cache set是(512i+j)/4%1024=(128i+j/4)%1024。可以看到,前面的系数正好可以整除。很不巧的是,在进行矩阵转置的运算时,在第2个for循环中,我们需要依次访问每一个row中对应i的值。这样会造成下面的结果:假设i=0,set(a[0][0])=0, set(a[1][0])=128, set(a[2][0])=256…set(a[7][0])=896,set(a[0][0])=0,后面开始重复了,到a[15][0]的时候刚好填完整个cache的所有128整数倍的set,当读取a[16][0]的时候,将会发生replace,把a[0][0]从cache里移除。这样,当源程序的i=1时,将完全重复i=0的计算过程,每次取数据都需要先从memory读到cache中来,cache的作用完全没有体现。

而当size=513的时候,事情就不一样了,mat[i][j]对应的cache set是(513i+j)/4%1024,前面的系数除不尽了,每递增4次结果会比size=512时偏差1。例如:set(a[0][0])=0, set(a[1][0])=128, set(a[2][0])=256,set(a[3][0])=384,set(a[4][0])=513…这样就很微妙的把cache set给错开了。a[16][0]不在第0行而是第4行,不会覆盖之前的数据。即使将全部的a[0-15][i]都读入cache,也不会发生碰撞。之后,由于一个cache有4个word,a[0-15][i+1],a[0-15][i+2],a[0-15][i+3]也同时被读进cache里了,所以计算i+1,i+2,i+3时,仅仅需要读对应行的数据就可以了,同一行的数据都是连续的,所以碰撞率很低。这个计算过程很好的利用了cache,如果不考虑其他因素(实际上,这个已经是影响运行时间的最大因素了),理论上我们可以节省75%的运行时间,可以看到,这个理论预测是和提问者给的数据相符合的。

总之,当你的data size是128的整数倍的时候,得特别小心,搞不好cache collision就把你的程序给拖慢了呢

Update 1: 原代码有逻辑错误,这点大家都不要吐槽了,代码不是我写的= =

Update 2:帅哥问我,为什么可以加速这么多。这个循环包括4次读cache的操作,2次写cache的操作,以及0-2次replace操作。每次replace操作会有一次memory read,有可能会有memory write(假设它是write back)。前面的读写cache时间和读写内存相比,几乎可以忽略,对效率产生显著影响的是后面的内存读写。如果cache的hi
编程开发网

首页 上一页 1 2 下一页 尾页 1/2/2
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇C语言编程丨C语言指针和数组基础 下一篇C语言字符数组回顾