没有合适的资源?快使用搜索试试~ 我知道了~
局部性与数据复用1
需积分: 0 0 下载量 30 浏览量
2022-08-03
21:41:43
上传
评论
收藏 2.33MB PDF 举报
温馨提示
试读
11页
通常这种局部性来于应的性质,就像第四章看到的PDEs的情况。在其他情况下,如分动学(第7章),没有这种内在的局部性,因为所有的粒都与其他粒相互作,为了获得性能,
资源详情
资源评论
资源推荐
局部性和数据复⽤
翻⾃:《Introduction to High Performance Scientific Computing》-Victor Eijkhout
李岳昆( realyurk@gmail.com )、蒋志政( gezelligheid@aliyun.com )译
知乎专栏: ⾼性能计算翻译计划
Github专栏: https://github.com/realYurkOfGitHub/translation-Introduction-to-HPC
# 局部性和数据复⽤
算法的执⾏不仅包含计算操作,也包含数据传输部分,事实上,数据传输可能是影响算法效
率的主要因素。由于缓存和寄存器的存在,数据传输量可以通过编程的⽅式最⼩化,使数据
尽可能地留在处理器附近。这部分是⼀个巧妙编程的问题,但我们也可以看看理论上的问
题:算法是否⼀开始就允许这样做。
事实证明,在科学计算中,数据往往主要与在某种意义上靠近的数据互动,这将导致数据的
局部性;1.6.2节。通常这种局部性来⾃于应⽤的性质,就像第四章看到的PDEs的情况。在其
他情况下,如分⼦动⼒学(第7章),没有这种内在的局部性,因为所有的粒⼦都与其他粒⼦
相互作⽤,为了获得⾼性能,需要相当的编程技巧。
数据复⽤和计算密度
在前⾯的章节中,我们了解到处理器的设计有些不平衡:加载数据⽐执⾏实际操作要慢。这
种不平衡对于主存储器来说是很⼤的,⽽对于各种⾼速缓存级别来说则较⼩。因此,我们有
动⼒将数据保存在⾼速缓存中,并尽可能地保持数据的复⽤量。
当然,我们⾸先需要确定计算是否允许数据被重复使⽤。为此,我们定义了⼀个算法的计算
密度如下。
如果 是⼀个算法所操作的数据项的数量,⽽ 是它所需要的操作的数量,那么算术
强度就是 。
(我们可以⽤浮点数或字节来衡量数据项。后者使我们更容易强度与处理器的硬件规格相关
联)
计算密度也与延迟隐藏有关:即你可以减轻计算活动背后的数据加载对性能的负⾯影响的概
念。要做到这⼀点,你需要⽐数据加载更多的计算来使这种隐藏有效。⽽这正是计算强度的
定义:每⼀个字节/字/数字加载的⾼⽐率操作。
⽰例:向量操作
考虑到向量加法
这涉及到三次内存访问(两次加载和⼀次存储)和每次迭代的⼀次操作,给出的算术强度为
1/3。axpy(表⽰ " 乘以 加 ")操作
有两个操作,但内存访问的数量相同,因为 的⼀次性负载被摊销了。因此,它⽐简单的加
法更有效率,重⽤率为2/3。因此,它⽐简单的加法更有效,重⽤率为2/3。
内积计算
在结构上类似于axpy操作,每次迭代涉及⼀个乘法和加法,涉及两个向量和⼀个标量。然
⽽,现在只有两个加载操作,因为 可以保存在寄存器中,只在循环结束时写回内存。这⾥
的重⽤是1。
⽰例:矩阵操作
考虑矩阵乘法
这涉及 个数据项和 个运算,属于⾼阶运算。算术强度为 ,每个数据项将被使⽤
𝑂(𝑛)次。这意味着,通过适当的编程,这种操作有可能通过将数据保存在快速缓存中来克服
带宽/时钟速度的差距。
练习 1.14 根据上述定义,矩阵-矩阵乘积作为⼀种操作,显然具有数据重⽤性。矩阵-矩阵乘
积显然具有数据复⽤。请你论证⼀下,这种复⽤并不是⾃然形成的,是什么决定了初始算法
中国呢缓存是否对数据进⾏复⽤?
[在这次讨论中,我们只关⼼某个特定实现的操作数,⽽不是数学操作。例如,有⼀些⽅法可
以在少于 的操作中执⾏矩阵-矩阵乘法和⾼斯消除算法[189, 167]。然⽽,这需要不同的
实现⽅式,在内存访问和重⽤⽅⾯有⾃⼰的分析]。
矩阵与矩阵乘积是LINPACK基准[51]的核⼼;见2.11.4节。如果将其作为评价计算机从能的标
准则结果可能较为乐观:矩阵与矩阵的乘积是⼀个具有⼤量数据复⽤的操作,因此这对内存
带宽并不敏感,对于并⾏计算及⽽⾔,这对⽹络通信也并不敏感。通常情况下,计算机在
Linpack基准测试中会达到其峰值性能的60-90%,⽽其他测试标准得到的数值则可能较低。
Roofline模型
有⼀种平价计算及性能的理想模型,就是所谓的「屋脊线」(roofline model)模型[202],该
模型指出:性能受两个因素的制约,如图1.16的第⼀个图所⽰。
1. 图中顶部的横线所表⽰的峰值性能是对性能的绝对约束3,只有在CPU的各个⽅⾯(流⽔
线、多个浮点单元)都完美使⽤的情况下才能达到。这个数字的计算纯粹是基于CPU的特
性和时钟周期;假定内存带宽不是⼀个限制因素。
2. 每秒的操作数受限于带宽、绝对数和计算密度的乘积。
这是由图中的线性增长线所描述的。
剩余10页未读,继续阅读
兰若芊薇
- 粉丝: 24
- 资源: 301
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0