并行计算的基本概念与方法(1)-缓存与存储层次
1.1.工厂-中转站-仓库模型
可以将计算机的运行形象化成以下的情景:
有一座工厂(代表CPU), 一座仓库(代表Memory或内存), 之间有道路(代表总线)沟通, 仓库中的材料通过道路被运到工厂中(读取Memory)进行加工(例如修改数据值), 加工完成后又被返运到仓库中(等待之后再被运出来加工)
这个模型存在一个问题:
就是路上的运输时间开销
工厂和仓库的距离很远, 每当工厂的机器要对特定的材料进行加工的时候, 不得不赶到遥远的仓库中才能寻找到材料, 然后再运回来, 这样必然会降低效率, 这时候工程师很自然地想到: 在工厂和仓库之间建立一个靠近工厂的小型中转站，即Cache(Cache来自拉丁词coactare, 取压缩、堆放之意)
中转站的意义在于:
把仓库中常用的一部分材料运到里面, 这样工厂在想要加工特定的材料时, 就可以直接从临近的中转站取用, 材料加工完了首先放回中转站, 然后在未来的某个时刻再运到仓库中
1.2.对Cache的初步认识
Cache的存在可以使得计算机的运行效率大为提高, 因为节约了访问Memory的时间开销，使得工厂中的机器不容易被闲置, 这里叙述对Cache最初步的认识
1.2.1.缓存行的概念
Memory向Cache的最小数据传递单位是Cache Line(缓存行), 注意是最小传递单位,可设为B（即Block,块）, 现在一般是64字节, 也就是说从Memory向Cache运数据的时候, 总是以64字节为一整块运过去, 不能单个单个字节地去运
一方面, 俗话说“一个羊也是赶两个羊也是放”，Cache从Memory读取数据的时间开销是比较昂贵的, 来都来了, 为什么不顺便打包走邻近的数据呢?
另一方面, Memory中有密切关系的数据在“地址”上通常是连续的(严格地说其实是虚拟地址，因为数据的真实物理存放地址并不是连续的，一个程序所用的数据实际上往往被分割为多个物理碎片, 分散在Memory的不同部位, 但是计算机的内存管理技术架构出了一个虚拟Memory,在真实物理地址和虚拟地址之间建立了映射, 使得运行的程序误以为自己所用的数据都连续地存放在一起, 具体可以去查询虚拟Memory的概念)
Cache的容量要远小于Memory, 可设为M, 一是因为从一个小空间寻找常用数据显然比在一个更大更普适的空间(Memory)中寻找更快, 二是因为更小规模的存储器更容易集成到处理器附近
这就带来一系列非常重要的问题:
1.2.2.Memory与Cache的地址映射问题
如何将Memory(严格地说是虚拟Memory)的地址映射到Cache的地址上, 即如何将仓库与中转站的货架标号建立关联, 因为Memory的容量远大于Cache, 因此实际上必然会出现多个Memory地址共享一个Cache地址的情形
概括地说, 有三种映射策略:
直接映射(Direct-Mapped),全相联映射(Fully-Associative), 集合相联映射(Set-Associative), 后面再详述
1.2.3.Cache未命中问题(Cache Miss)
因为Cache容量有限, 必然会发生这种情形: CPU要访问一个数据, 但这个数据并不在Cache这个中转站中, 这时就不得不赶到更远的Memory中去读取数据, 记为一次Cache Miss(如果Cache里面正好有这个数据, 那么即称Cache命中)
通常将程序可能出现的Cache Miss次数定义为程序的通信复杂度,记为Q, 作为衡量程序性能的重要指标(因为cache和Memory的数据传递犹如两个站点进行通信)
Cache Miss的类型一般有:
Cold Miss, Capacity Miss, Conflict Miss
在多核环境下还有Sharing Miss(True-Sharing Miss and False-Sharing Miss), 这里面每个概念都很重要,后面再详述
1.2.4.Cache的替换策略
Cache容量是有限的, 当发生数据未命中(Cache Miss), 计算机会到Memory里把需要的数据所在的块按相应的Memory-Cache映射策略运到Cache里面, 如果此时对应的集合的容量已满(具体见地址映射策略), 就要将某个旧数据块踢出去, 代之以新数据, 最自然的替换策略是LRU策略(Least-Recently-Used, 可以去查)
1.2.5.Cache与Memory的一致性问题
Cache内的数据需要和Memory保持一致,一般有两种策略, 一是write-through(直写入法), 即Cache的数据被写入或修改时, 同时也向Memory写入, 用这种方式时时保持两者的数据一致, 劣势是时时需要访问Memory, 速度较慢,二是write-back(写回法), 即当Cache的数据被修改, 并不立即更新Memory, 只是将更新的Cache区域作标记, 等到这块区域要被新数据取代, 才更新Memory
1.3.存储层次金字塔
既然可以在仓库和工厂建立中转站,那么在中转站和工厂之间又可以建立更低级但更小更快的中转站, 以此类推, 事实上计算机按寄存器-缓存-内存-磁盘-网络构成一个存储层次的金字塔, 金字塔越往上存储器的容量越小,但访问速度越快, 越往下存储器的容量越大, 访问速度越慢, 当寄存器里没有所需的数据时就要求之于缓存, 缓存没有时就要求之于内存, 依次下去.在多处理器情形下，缓存层次中还可以细分为L1/L2/L3 Cache, 从L1到L2到L3,容量依次增大, L1,L2 Cache为单处理器所私有, L3 Cache则由多个处理器所共有
但任意两个相邻的存储层次都可以简化为Processor-Cache-Memory(加工厂-中转站-仓库这一两层模型), 中转站的规模远小于仓库, 性能优化的精髓就在于利用这个小小的中转站或高速缓存Cache, 尽可能地减少通信复杂度, 提高所谓的空间局部性, 低通信复杂度算法又被称为缓存高效算法(Cache-Efficient Algorithm)
一个极好的思路在于通过递归方法缩减问题规模, 将问题规模缩减到Cache可以完全容纳的程度, 这样就不再需要向更大但访问速度更慢的存储器寻找数据