C中实现矩阵乘法的方法

来源:爱站网时间:2020-06-09编辑:网友分享
相信大家都知道如何计算矩阵乘法,但是小编今天将为大家介绍更高效的矩阵乘法的实现方法,是不是很多用户们会好奇呢?那么下面我们就一起去看看C中实现矩阵乘法的方法。

相信大家都知道如何计算矩阵乘法,但是小编今天将为大家介绍更高效的矩阵乘法的实现方法,是不是很多用户们会好奇呢?那么下面我们就一起去看看C中实现矩阵乘法的方法。

如何计算矩阵乘法,这个大家都知道。通常情况下,我们都是用以下代码实现的

 

for(i=0;i     for(j=0;j         sum=0;
        for(k=0;k             sum+=A[i][k]*B[k][j];
        C[i][j]+=sum;
}


但是考虑了高速缓存的问题后,其实有一种更好的实现方式:

 

 

 

 


for(i=0;i     for(k=0;k         r=A[i][k];
        for(j=0;j             C[i][j]+=r*B[k][j];
}

 


细看一番就会发现这两种实现语义是等价的,但是后者的实际运行效率却比前者高。

 

那为什么会如此呢?

那是因为CPU读数据时,并不是直接访问内存,而是先查看缓存中是否有数据,有的话直接从缓存读取。而从缓存读取数据比从内存读数据快很多。

当数据不在缓存中时,CPU会将包含数据在内的一个数据块读到缓存,如果程序具有良好空间局部性,那么第一次cache miss后,之后的几次数据访问就可以直接在缓存中完成。除了空间局部性(程序倾向于引用与当前数据邻近的数据)之外,还有时间局部性(程序倾向于引用最近被引用过的数据)。

回到矩阵乘法。(我们只考虑内循环)

前者对矩阵A,有良好的空间局部性,假设一次能缓存四个元素,则每次迭代对于A只有0.25次miss,但是对于B,则不然,因此B是按列访问的,每次访问都会miss,因此每次迭代总的miss数是1.25。

后者对于矩阵C和矩阵B都有良好的局部性,每次迭代都只有0.25词miss,因此总的miss数是0.5。后者每次迭代多了一次存储(对C[i][j]写入),但是即便如此,后者的运行效率也比前者高。

总而言之,要想程序跑得快,就要在程序中多利用局部性,让缓存hold住你的数据,减少访存次数。要知道CPU可以在3个时钟周期内访问到L1 cache,10个时钟周期左右的时间访问到L2 cache。访问内存却要上百个时钟周期,孰快孰慢,很清楚了吧?

以上就是C中实现矩阵乘法的方法,大家学习的怎样呢?只有我们掌握好了专业知识,才能不畏惧任何人。

上一篇:使用红黑树的方法

下一篇:Java3D创建空间几何模型的方法

您可能感兴趣的文章

相关阅读

热门软件源码

最新软件源码下载