C中实现矩阵乘法的一种高效的方法
方法 实现 高效 一种 矩阵 乘法
2023-06-13 09:14:52 时间
如何计算矩阵乘法,这个大家都知道。通常情况下,我们都是用以下代码实现的:
for(i=0;i<n;++i)
for(j=0;j<n;++j){
sum=0;
for(k=0;k<n;++k)
sum+=A[i][k]*B[k][j];
C[i][j]+=sum;
}
但是考虑了高速缓存的问题后,其实有一种更好的实现方式:
for(i=0;i<n;++i)
for(k=0;k<n;++k){
r=A[i][k];
for(j=0;j<n;++j)
C[i][j]+=r*B[k][j];
}
细看一番就会发现这两种实现语义是等价的,但是后者的实际运行效率却比前者高。
那为什么会如此呢?
那是因为CPU读数据时,并不是直接访问内存,而是先查看缓存中是否有数据,有的话直接从缓存读取。而从缓存读取数据比从内存读数据快很多。
当数据不在缓存中时,CPU会将包含数据在内的一个数据块读到缓存,如果程序具有良好空间局部性,那么第一次cachemiss后,之后的几次数据访问就可以直接在缓存中完成。除了空间局部性(程序倾向于引用与当前数据邻近的数据)之外,还有时间局部性(程序倾向于引用最近被引用过的数据)。
回到矩阵乘法。(我们只考虑内循环)
前者对矩阵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个时钟周期内访问到L1cache,10个时钟周期左右的时间访问到L2cache。访问内存却要上百个时钟周期,孰快孰慢,很清楚了吧?
相关文章
- 移动端实现拖拽的两种方法
- 关联MySQL实现一对多表关联的高效方法(mysql一对多表)
- Oracle实现多行拼接的方法 Oracle实现多行拼接的简单技巧(oracle拼接多行)
- MySQL中存储头像的实现方法(mysql存储头像)
- Linux搭建 VPN:实现安全连接的简单方法(linux如何架设vpn)
- 实现Linux用户统一管理的有效方法(linux用户统一管理)
- 深入了解Linux的radix——探索高效数据结构的实现方法(linuxradix)
- 详解MySQL数据库迁移步骤:安全高效的实现方法(mysql如何迁移数据库)
- 快速高效的方法,一步步教你实现 Linux 服务器扩容(linux服务器扩容)
- Oracle字符类型转换技巧大全,如何实现快速高效的字符类型转换方法?详解实用的转换语句及技巧,一文搞定Oracle字符类型转换!(oracle字符类型转换)
- Oracle实现列转多列:快速高效的数据处理方法(oracle把列转多列)
- Redis:高效实用的消息队列实现方法(redis如何做消息队列)
- Linux 下实现CRC16 编码的简易方法(crc16linux)
- 利用MySQL实现两行取差,简单高效的数据处理方法(mysql 两行取差)
- 让Redis更加整洁的清理方法(清理redis怎么清理)
- MySQL实现上下级关联的方法简介(MySQL上下关联)
- 值Oracle中排除空值的实现方法(oracle中排除空)
- 在VBScript中实现-函数/方法名作为参数传入另一个函数
- php优化及高效提速问题的实现方法
- DB2自动递增字段实现方法
- java多线程应用实现方法
- PHP之生成GIF动画的实现方法
- js控制表单奇偶行样式的简单方法
- Android按钮按下的时候改变颜色实现方法
- JavaScript中实现最高效的数组乱序方法
- asp.net页面触发事件panel滚动条高度不变的实现方法
- js实现鼠标悬浮给图片加边框的方法