前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >利用矩阵分块优化算法

利用矩阵分块优化算法

作者头像
fem178
发布于 2023-08-25 06:03:02
发布于 2023-08-25 06:03:02
62600
代码可运行
举报
运行总次数:0
代码可运行

存储系统对于程序执行时间有显著影响。处理器由于访存导致的暂停时间受到失效率和失效代价的影响。众所周知,为了弥补CPU与内存两者之间的性能差异,就在CPU内部引入了CPU cache,也称高速缓存。CPU cache通常分为大小不等的三级缓存,分别是L1 cache、L2 cache和L3 cache。如图1所示。

▲ 图1 三级cache

许多软件优化技术通过重用cache中的数据来大幅度提高处理器性能,通过改善程序的时间局部性来提升访问效率。换言之,不要频繁替换cache中的数据。

处理数组时,如果能将数组元素按照访问顺序存放在存储器中,则能够获得性能上的好处。但是,假设同时处理多个数组,一些数组按行访问,一些数组按列访问。按行存储(称为行优先)或者按列存储(称为列优先)数组都不能解决问题,这是因为在程序的每个循环体中行访问和列访问同时会被使用到。因而,分块算法针对子矩阵(submatrice)或者数据块来进行操作,并不针对数组中完整的一行或一列进行操作。它的目标是,在替换之前对已在cache中的数据进行尽可能多的访问,这就是说,提高程序的时间局部性以减少cache失效。例如,在数值计算库Lapack的DGEMM中的内层循环中

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
for (int j = ; j < n; ++j) {
    double cij = C[i+j*n]; /* cij = C[i][j] */
    for( int k = ; k < n; k++ ) {
        cij += A[i+k*n] * B[k+j*n]; /* cij += A[i][k]*B[k][j] */
        C[i+j*n] = cij; /* C[i][j] = cij */
    }
}

▲ 图3  DGEMM的cache分块版本。假设数组C初始化为0。函数doblock 以普通的DGEMM为基础,增加了新参数来描述BLOCKSIZE大小的子矩阵的起始位置。

图4给出使用分块思想对三个数组进行访问的示例。仅对于容量失效来说,需要访问的内存数据字总数为

。(相比未分块前)这个数据得到了改善,原因在于参数

。由此可见,分块思想挖掘出程序的时间局部性和空间局部性,比如数组A的访问得益于空间局部性,而数组B的访问得益于时间局部性。

▲ 图4  数组C、A和B的访问(BLOCKSIZE =3)。注意,与图2 相比,访问的元素数量变少

图5中给出了采用cache分块对未优化DGEMM性能的影响。矩阵规模最大时,未优化程序的性能折半。采用cache分块的版本,即使矩阵规模达到960x960=3232阵规模性能也仅仅降低了不到10%。

▲ 图5  未优化DGEMM与 cache 分块 DGEMM的性能比较,矩阵维度从32x32增加至960x960

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2023-08-23,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 数值分析与有限元编程 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验