menu

hjk41的日志

Avatar

优化大矩阵运算速度

太大的矩阵(1000*1000以上)在使用一般的算法运算时会产生很多的cache miss,导致运算速度太低,所以有必要进行优化

1000*1000的整型矩阵需要占用大约4MB,这样大的数据一般是不可能完全放到cache里的,所以最好的方法就是把它切成几个小块,然后对每个小块进行运算。

对矩阵加减法来说,这样切的意义不大,因为它们完全就是顺序操作,每个数据只用到一次,所以切成小块的cache miss率并不会降低

对乘法运算来说就比较重要了,比如矩阵运算 c=a*b,如果a,b都是1000*1000的矩阵,那么a中每个元素都要参与1000次运算,这时将矩阵切成小块的意义就大了。
一般来说,我们算矩阵乘法时会将a中的第 i 行与b中的第 j 列顺序相乘,以得到 c[i][j],这样的话等到 a 中第 i 行最后一个数据与 b 中第 j 列最后一个数据相乘时, a[i][0]与b[0][j]已经很久没用了,很可能已经被淘汰出cache,再算 a[i][0]*b[0][j+1]时又得从内存中取,所以速度很慢。如果将a,b分块进行运算,就能在很大程度上避免这种情况,从而加速程序运行。

那怎么分块呢?

评论已关闭