为您推荐:
精华内容
最热下载
问答
  • 5星
    3.13MB qq_52745968 2021-06-17 11:18:37
  • 5星
    2.85MB leidownndsc 2018-07-01 12:34:50
  • 788KB u013566527 2021-05-11 14:54:27
  • CPU Cache Line伪共享问题的总结和分析》 以下文章来源于小林coding,作者小林coding Table of Contents CPU Cache 有多快? CPU Cache 的数据结构和读取过程是什么样的? 如何写出让 CPU 跑得更快的代码?...

    CPU Cache Line伪共享问题的总结和分析

    以下文章来源于小林coding ,作者小林coding

    Table of Contents

    CPU Cache 有多快?

    CPU Cache 的数据结构和读取过程是什么样的?

    如何写出让 CPU 跑得更快的代码?

    总结


    前言

    代码都是由 CPU 跑起来的,我们代码写得好与坏就决定了 CPU 的执行效率,特别是在编写计算密集型的程序,更要注重 CPU 的执行效率,否则将会大大影响系统性能。

    CPU 内部嵌入了 CPU Cache(高速缓存),它的存储容量很小,但是离 CPU 核心很近,所以缓存的读写速度是极快的,那么如果 CPU 运算时,直接从 CPU Cache 读取数据,而不是从内存的话,运算速度就会很快。

    但是,大多数人不知道 CPU Cache 的运行机制,以至于不知道如何才能够写出能配合 CPU Cache 工作机制的代码,一旦你掌握了它,你写代码的时候,就有新的优化思路了。

    那么,接下来我们就来看看,CPU Cache 到底是什么样的,是如何工作的呢,又该如何写出让 CPU 执行更快的代码呢?

    CPU Cache 有多快?

    你可能会好奇为什么有了内存,还需要 CPU Cache?根据摩尔定律,CPU 的访问速度每 18 个月就会翻倍,相当于每年增长 60% 左右,内存的速度当然也会不断增长,但是增长的速度远小于 CPU,平均每年只增长 7% 左右。于是,CPU 与内存的访问性能的差距不断拉大。

    到现在,一次内存访问所需时间是 200~300 多个时钟周期,这意味着 CPU 和内存的访问速度已经相差 200~300 多倍了。

    为了弥补 CPU 与内存两者之间的性能差异,就在 CPU 内部引入了  CPU Cache,也称高速缓存。

    CPU Cache 通常分为大小不等的三级缓存,分别是 L1 Cache、L2 Cache 和 L3 Cache

    由于 CPU Cache 所使用的材料是 SRAM,价格比内存使用的 DRAM 高出很多,在当今每生产 1 MB 大小的 CPU Cache 需要 7 美金的成本,而内存只需要 0.015 美金的成本,成本方面相差了 466 倍,所以 CPU Cache 不像内存那样动辄以 GB 计算,它的大小是以 KB 或 MB 来计算的。

    在 Linux 系统中,我们可以使用下图的方式来查看各级 CPU Cache 的大小,比如我这手上这台服务器,离 CPU 核心最近的 L1 Cache 是 32KB,其次是 L2 Cache 是 256KB,最大的 L3 Cache 则是 3MB。

    其中,L1 Cache 通常会分为「数据缓存」和「指令缓存」,这意味着数据和指令在 L1 Cache 这一层是分开缓存的,上图中的 index0 也就是数据缓存,而 index1 则是指令缓存,它俩的大小通常是一样的。

    另外,你也会注意到,L3 Cache 比 L1 Cache 和 L2 Cache 大很多,这是因为 L1 Cache 和 L2 Cache 都是每个 CPU 核心独有的,而 L3 Cache 是多个 CPU 核心共享的。

    程序执行时,会先将内存中的数据加载到共享的 L3 Cache 中,再加载到每个核心独有的 L2 Cache,最后进入到最快的 L1 Cache,之后才会被 CPU 读取。它们之间的层级关系,如下图:

    越靠近 CPU 核心的缓存其访问速度越快,CPU 访问 L1 Cache 只需要 2~4 个时钟周期,访问 L2 Cache 大约 10~20 个时钟周期,访问 L3 Cache 大约 20~60 个时钟周期,而访问内存速度大概在 200~300 个时钟周期之间。如下表格:

    所以,CPU 从 L1 Cache 读取数据的速度,相比从内存读取的速度,会快 100 多倍。


    CPU Cache 的数据结构和读取过程是什么样的?

    CPU Cache 的数据是从内存中读取过来的,它是以一小块一小块读取数据的,而不是按照单个数组元素来读取数据的,在 CPU Cache 中的,这样一小块一小块的数据,称为 Cache Line(缓存块)

    你可以在你的 Linux 系统,用下面这种方式来查看 CPU 的 Cache Line,你可以看我服务器的 L1 Cache Line 大小是 64 字节,也就意味着 L1 Cache 一次载入数据的大小是 64 字节

    比如,有一个 int array[100] 的数组,当载入 array[0] 时,由于这个数组元素的大小在内存只占 4 字节,不足 64 字节,CPU 就会顺序加载数组元素到 array[15],意味着 array[0]~array[15] 数组元素都会被缓存在 CPU Cache 中了,因此当下次访问这些数组元素时,会直接从 CPU Cache 读取,而不用再从内存中读取,大大提高了 CPU 读取数据的性能。

    事实上,CPU 读取数据的时候,无论数据是否存放到 Cache 中,CPU 都是先访问 Cache,只有当 Cache 中找不到数据时,才会去访问内存,并把内存中的数据读入到 Cache 中,CPU 再从 CPU Cache 读取数据。

    这样的访问机制,跟我们使用「内存作为硬盘的缓存」的逻辑是一样的,如果内存有缓存的数据,则直接返回,否则要访问龟速一般的硬盘。

    那 CPU 怎么知道要访问的内存数据,是否在 Cache 里?如果在的话,如何找到 Cache 对应的数据呢?我们从最简单、基础的直接映射 Cache(Direct Mapped Cache 说起,来看看整个 CPU Cache 的数据结构和访问逻辑。

    前面,我们提到 CPU 访问内存数据时,是一小块一小块数据读取的,具体这一小块数据的大小,取决于 coherency_line_size 的值,一般 64 字节。在内存中,这一块的数据我们称为内存块(Bock,读取的时候我们要拿到数据所在内存块的地址。

    对于直接映射 Cache 采用的策略,就是把内存块的地址始终「映射」在一个 CPU Line(缓存块) 的地址,至于映射关系实现方式,则是使用「取模运算」,取模运算的结果就是内存块地址对应的 CPU Line(缓存块) 的地址。

    举个例子,内存共被划分为 32 个内存块,CPU Cache 共有 8 个 CPU Line,假设 CPU 想要访问第 15 号内存块,如果 15 号内存块中的数据已经缓存在 CPU Line 中的话,则是一定映射在 7 号 CPU Line 中,因为 15 % 8 的值是 7。

    机智的你肯定发现了,使用取模方式映射的话,就会出现多个内存块对应同一个 CPU Line,比如上面的例子,除了 15 号内存块是映射在 7 号 CPU Line 中,还有 7 号、23 号、31 号内存块都是映射到 7 号 CPU Line 中。

    因此,为了区别不同的内存块,在对应的 CPU Line 中我们还会存储一个组标记(Tag)。这个组标记会记录当前 CPU Line 中存储的数据对应的内存块,我们可以用这个组标记来区分不同的内存块。

    除了组标记信息外,CPU Line 还有两个信息:

    • 一个是,从内存加载过来的实际存放数据(Data

    • 另一个是,有效位(Valid bit,它是用来标记对应的 CPU Line 中的数据是否是有效的,如果有效位是 0,无论 CPU Line 中是否有数据,CPU 都会直接访问内存,重新加载数据。

    CPU 在从 CPU Cache 读取数据的时候,并不是读取 CPU Line 中的整个数据块,而是读取 CPU 所需要的一个数据片段,这样的数据统称为一个字(Word。那怎么在对应的 CPU Line 中数据块中找到所需的字呢?答案是,需要一个偏移量(Offset)

    因此,一个内存的访问地址,包括组标记、CPU Line 索引、偏移量这三种信息,于是 CPU 就能通过这些信息,在 CPU Cache 中找到缓存的数据。而对于 CPU Cache 里的数据结构,则是由索引 + 有效位 + 组标记 + 数据块组成。

    如果内存中的数据已经在 CPU Cahe 中了,那 CPU 访问一个内存地址的时候,会经历这 4 个步骤:

    1. 根据内存地址中索引信息,计算在 CPU Cahe 中的索引,也就是找出对应的 CPU Line 的地址;

    2. 找到对应 CPU Line 后,判断 CPU Line 中的有效位,确认 CPU Line 中数据是否是有效的,如果是无效的,CPU 就会直接访问内存,并重新加载数据,如果数据有效,则往下执行;

    3. 对比内存地址中组标记和 CPU Line 中的组标记,确认 CPU Line 中的数据是不是我们要访问的内存数据,如果不是的话,CPU 就会直接访问内存,并重新加载数据,如果是的话,则往下执行;

    4. 根据内存地址中偏移量信息,从 CPU Line 的数据块中,读取对应的字。

    到这里,相信你对直接映射 Cache 有了一定认识,但其实除了直接映射 Cache 之外,还有其他通过内存地址找到 CPU Cache 中的数据的策略,比如全相连 Cache (Fully Associative Cache)、组相连 Cache (Set Associative Cache)等,这几种策略的数据结构都比较相似,我们理解流直接映射 Cache 的工作方式,其他的策略如果你有兴趣去看,相信很快就能理解的了。


    如何写出让 CPU 跑得更快的代码?

    我们知道 CPU 访问内存的速度,比访问 CPU Cache 的速度慢了 100 多倍,所以如果 CPU 所要操作的数据在 CPU Cache 中的话,这样将会带来很大的性能提升。访问的数据在 CPU Cache 中的话,意味着缓存命中,缓存命中率越高的话,代码的性能就会越好,CPU 也就跑得越快。

    于是,「如何写出让 CPU 跑得更快的代码」这个问题,可以改成「如何写出 CPU 缓存命中率高的代码」。

    在前面我也提到, L1 Cache 通常分为「数据缓存」和「指令缓存」,这是因为 CPU 会分别处理数据和指令,比如 1+1=2 这个运算,+ 就是指令,会被放在「指令缓存」中,而输入数字 1 则会被放在「数据缓存」里。

    因此,我们要分开来看「数据缓存」和「指令缓存」的缓存命中率

    如何提升数据缓存的命中率?

    假设要遍历二维数组,有以下两种形式,虽然代码执行结果是一样,但你觉得哪种形式效率最高呢?为什么高呢?

    经过测试,形式一 array[i][j]  执行时间比形式二 array[j][i] 快好几倍。

    之所以有这么大的差距,是因为二维数组 array 所占用的内存是连续的,比如长度 N 的值是 2 的话,那么内存中的数组元素的布局顺序是这样的:

    形式一用 array[i][j]  访问数组元素的顺序,正是和内存中数组元素存放的顺序一致。当 CPU 访问 array[0][0] 时,由于该数据不在 Cache 中,于是会「顺序」把跟随其后的 3 个元素从内存中加载到 CPU Cache,这样当 CPU 访问后面的 3 个数组元素时,就能在 CPU Cache 中成功地找到数据,这意味着缓存命中率很高,缓存命中的数据不需要访问内存,这便大大提高了代码的性能。

    而如果用形式二的 array[j][i] 来访问,则访问的顺序就是:

    你可以看到,访问的方式是跳跃式的,而不是顺序的,那么如果 N 的数值很大,那么操作 array[j][i] 时,是没办法把 array[j+1][i] 也读入到 CPU Cache 中的,既然 array[j+1][i] 没有读取到 CPU Cache,那么就需要从内存读取该数据元素了。很明显,这种不连续性、跳跃式访问数据元素的方式,可能不能充分利用到 CPU Cache 的特性,从而代码的性能不高。

    那访问 array[0][0] 元素时,CPU 具体会一次从内存中加载多少元素到 CPU Cache 呢?这个问题,在前面我们也提到过,这跟 CPU Cache Line 有关,它表示 CPU Cache 一次性能加载数据的大小,可以在 Linux 里通过 coherency_line_size 配置查看它的大小,通常是 64 个字节。

    也就是说,当 CPU 访问内存数据时,如果数据不在 CPU Cache 中,则会一次性连续加载 64 字节大小的数据到 CPU Cache,那么当访问 array[0][0] 时,由于该元素不足 64 字节,于是就会往后顺序读取 array[0][0]~array[0][15] 到 CPU Cache 中。顺序访问的 array[i][j] 因为利用了这一特点,所以就会比跳跃式访问的 array[j][i] 要快。

    因此,遇到这种遍历数组的情况时,按照内存布局顺序访问,将可以有效地利用 CPU Cache 带来的好处,这样我们代码的性能就会得到很大的提升。

    如何提升指令缓存的命中率?

    提升数据的缓存命中率的方式,是按照内存布局顺序访问,那针对指令的缓存该如何提升呢?

    我们以一个例子来看看,有一个元素为 0 到 100 之间随机数字组成的一维数组:

    接下来,对这个数组做两个操作:

    • 第一个操作,循环遍历数组,把小于 50 的数组元素置为 0;

    • 第二个操作,将数组排序;

    那么问题来了,你觉得先遍历再排序速度快,还是先排序再遍历速度快呢?

    在回答这个问题之前,我们先了解 CPU 的分支预测器。对于 if 条件语句,意味着此时至少可以选择跳转到两段不同的指令执行,也就是 if 还是 else 中的指令。那么,如果分支预测可以预测到接下来要执行 if 里的指令,还是 else 指令的话,就可以「提前」把这些指令放在指令缓存中,这样 CPU 可以直接从 Cache 读取到指令,于是执行速度就会很快

    当数组中的元素是随机的,分支预测就无法有效工作,而当数组元素都是顺序的,分支预测器会动态地根据历史命中数据对未来进行预测,这样命中率就会很高。

    因此,先排序再遍历速度会更快,这是因为排序之后,数字是从小到大的,那么前几次循环命中 if < 50 的次数会比较多,于是分支预测就会缓存 if 里的 array[i] = 0 指令到 Cache 中,后续 CPU 执行该指令就只需要从 Cache 读取就好了。

    如果你肯定代码中的 if 中的表达式判断为 true 的概率比较高,我们可以使用显示分支预测工具,比如在 C/C++ 语言中编译器提供了 likely 和 unlikely 这两种宏,如果 if 条件为 ture 的概率大,则可以用 likely 宏把 if 里的表达式包裹起来,反之用 unlikely 宏。

    实际上,CPU 自身的动态分支预测已经是比较准的了,所以只有当非常确信 CPU 预测得不准,且能够知道实际的概率情况时,才建议使用这两种宏。

    如果提升多核 CPU 的缓存命中率?

    在单核 CPU,虽然只能执行一个进程,但是操作系统给每个进程分配了一个时间片,时间片用完了,就调度下一个进程,于是各个进程就按时间片交替地占用 CPU,从宏观上看起来各个进程同时在执行。

    而现代 CPU 都是多核心的,进程可能在不同 CPU 核心来回切换执行,这对 CPU Cache 不是有利的,虽然 L3 Cache 是多核心之间共享的,但是 L1 和 L2 Cache 都是每个核心独有的,如果一个进程在不同核心来回切换,各个核心的缓存命中率就会受到影响,相反如果进程都在同一个核心上执行,那么其数据的 L1 和 L2 Cache 的缓存命中率可以得到有效提高,缓存命中率高就意味着 CPU 可以减少访问内存的频率。

    当有多个同时执行「计算密集型」的线程,为了防止因为切换到不同的核心,而导致缓存命中率下降的问题,我们可以把线程绑定在某一个 CPU 核心上,这样性能可以得到非常可观的提升。

    在 Linux 上提供了 sched_setaffinity 方法,来实现将线程绑定到某个 CPU 核心这一功能。

    总结

    由于随着计算机技术的发展,CPU 与 内存的访问速度相差越来越多,如今差距已经高达好几百倍了,所以 CPU 内部嵌入了 CPU Cache 组件,作为内存与 CPU 之间的缓存层,CPU Cache 由于离 CPU 核心很近,所以访问速度也是非常快的,但由于所需材料成本比较高,它不像内存动辄几个 GB 大小,而是仅有几十 KB 到 MB 大小。

    当 CPU 访问数据的时候,先是访问 CPU Cache,如果缓存命中的话,则直接返回数据,就不用每次都从内存读取数据了。因此,缓存命中率越高,代码的性能越好。

    但需要注意的是,当 CPU 访问数据时,如果 CPU Cache 没有缓存该数据,则会从内存读取数据,但是并不是只读一个数据,而是一次性读取一块一块的数据存放到 CPU Cache 中,之后才会被 CPU 读取。

    内存地址映射到 CPU Cache 地址里的策略有很多种,其中比较简单是直接映射 Cache,它巧妙地把内存地址拆分成「索引 + 组标记 + 偏移量」的方式,使得我们可以将很大的内存地址,映射到很小的 CPU Cache 地址里。

    要想写出让 CPU 跑得更快的代码,就需要写出缓存命中率高的代码,CPU L1 Cache 分为数据缓存和指令缓存,因而需要分别提高它们的缓存命中率:

    • 对于数据缓存,我们在遍历数据的时候,应该按照内存布局的顺序操作,这是因为 CPU Cache 是根据 CPU Cache Line 批量操作数据的,所以顺序地操作连续内存数据时,性能能得到有效的提升;

    • 对于指令缓存,有规律的条件分支语句能够让 CPU 的分支预测器发挥作用,进一步提高执行的效率;

    另外,对于多核 CPU 系统,线程可能在不同 CPU 核心来回切换,这样各个核心的缓存命中率就会受到影响,于是要想提高进程的缓存命中率,可以考虑把线程绑定 CPU 到某一个 CPU 核心。

     

    展开全文
    Rong_Toa 2020-10-25 15:55:49
  • 2.12MB sup945 2018-03-17 14:26:10
  • 转载:https://coolshell.cn/articles/10249.htmlCPU cache一直是理解计算机体系...正好网上有人推荐了微软大牛Igor Ostrovsky一篇博文《漫游处理器缓存效应》,文章不仅仅用7个最简单的源码示例就将CPU cache的原理...

    转载:https://coolshell.cn/articles/10249.html

    CPU cache一直是理解计算机体系架构的重要知识点,也是并发编程设计中的技术难点,而且相关参考资料如同过江之鲫,浩瀚繁星,阅之如临深渊,味同嚼蜡,三言两语难以入门。正好网上有人推荐了微软大牛Igor Ostrovsky一篇博文《漫游处理器缓存效应》,文章不仅仅用7个最简单的源码示例就将CPU cache的原理娓娓道来,还附加图表量化分析做数学上的佐证,个人感觉这种案例教学的切入方式绝对是俺的菜,故而忍不住贸然译之,以飨列位看官。

    原文地址:Gallery of Processor Cache Effects

    大多数读者都知道cache是一种快速小型的内存,用以存储最近访问内存位置。这种描述合理而准确,但是更多地了解一些处理器缓存工作中的“烦人”细节对于理解程序运行性能有很大帮助。

    在这篇博客中,我将运用代码示例来详解cache工作的方方面面,以及对现实世界中程序运行产生的影响。

    下面的例子都是用C#写的,但语言的选择同程序运行状况以及得出的结论几乎没什么影响。

    示例1:内存访问和运行

    你认为相较于循环1,循环2会运行多快?

    1
    2
    3
    4
    5
    6
    7
    int [] arr = new int [64 * 1024 * 1024];
     
    // Loop 1
    for ( int i = 0; i < arr.Length; i++) arr[i] *= 3;
     
    // Loop 2
    for ( int i = 0; i < arr.Length; i += 16) arr[i] *= 3;

    第一个循环将数组的每个值乘3,第二个循环将每16个值乘3,第二个循环只做了第一个约6%的工作,但在现代机器上,两者几乎运行相同时间:在我机器上分别是80毫秒和78毫秒。

    两个循环花费相同时间的原因跟内存有关。循环执行时间长短由数组的内存访问次数决定的,而非整型数的乘法运算次数。经过下面对第二个示例的解释,你会发现硬件对这两个循环的主存访问次数是相同的。

    示例2:缓存行的影响

    让我们进一步探索这个例子。我们将尝试不同的循环步长,而不仅仅是1和16。

    1
    for ( int i = 0; i < arr.Length; i += K) arr[i] *= 3;

    下图为该循环在不同步长(K)下的运行时间:

    running times of this loop for different step values (K)

    注意当步长在1到16范围内,循环运行时间几乎不变。但从16开始,每次步长加倍,运行时间减半。

    背后的原因是今天的CPU不再是按字节访问内存,而是以64字节为单位的块(chunk)拿取,称为一个缓存行(cache line)。当你读一个特定的内存地址,整个缓存行将从主存换入缓存,并且访问同一个缓存行内的其它值的开销是很小的。

    由于16个整型数占用64字节(一个缓存行),for循环步长在1到16之间必定接触到相同数目的缓存行:即数组中所有的缓存行。当步长为32,我们只有大约每两个缓存行接触一次,当步长为64,只有每四个接触一次。

    理解缓存行对某些类型的程序优化而言可能很重要。比如,数据字节对齐可能决定一次操作接触1个还是2个缓存行。那上面的例子来说,很显然操作不对齐的数据将损失一半性能。

    示例3:L1和L2缓存大小

    今天的计算机具有两级或三级缓存,通常叫做L1、L2以及可能的L3(译者注:如果你不明白什么叫二级缓存,可以参考这篇精悍的博文lol)。如果你想知道不同缓存的大小,你可以使用系统内部工具CoreInfo,或者Windows API调用GetLogicalProcessorInfo。两者都将告诉你缓存行以及缓存本身的大小。

    在我的机器上,CoreInfo现实我有一个32KB的L1数据缓存,一个32KB的L1指令缓存,还有一个4MB大小L2数据缓存。L1缓存是处理器独享的,L2缓存是成对处理器共享的。

    Logical Processor to Cache Map:
    *— Data Cache 0, Level 1, 32 KB, Assoc 8, LineSize 64
    *— Instruction Cache 0, Level 1, 32 KB, Assoc 8, LineSize 64
    -*– Data Cache 1, Level 1, 32 KB, Assoc 8, LineSize 64
    -*– Instruction Cache 1, Level 1, 32 KB, Assoc 8, LineSize 64
    **– Unified Cache 0, Level 2, 4 MB, Assoc 16, LineSize 64
    –*- Data Cache 2, Level 1, 32 KB, Assoc 8, LineSize 64
    –*- Instruction Cache 2, Level 1, 32 KB, Assoc 8, LineSize 64
    —* Data Cache 3, Level 1, 32 KB, Assoc 8, LineSize 64
    —* Instruction Cache 3, Level 1, 32 KB, Assoc 8, LineSize 64
    –** Unified Cache 1, Level 2, 4 MB, Assoc 16, LineSize 64

    (译者注:作者平台是四核机,所以L1编号为0~3,数据/指令各一个,L2只有数据缓存,两个处理器共享一个,编号0~1。关联性字段在后面例子说明。)

    让我们通过一个实验来验证这些数字。遍历一个整型数组,每16个值自增1——一种节约地方式改变每个缓存行。当遍历到最后一个值,就重头开始。我们将使用不同的数组大小,可以看到当数组溢出一级缓存大小,程序运行的性能将急剧滑落。

    1
    2
    3
    4
    5
    6
    7
    int steps = 64 * 1024 * 1024;
    // Arbitrary number of steps
    int lengthMod = arr.Length - 1;
    for ( int i = 0; i < steps; i++)
    {
         arr[(i * 16) & lengthMod]++; // (x & lengthMod) is equal to (x % arr.Length)
    }

    下图是运行时间图表:
    cache size

    你可以看到在32KB和4MB之后性能明显滑落——正好是我机器上L1和L2缓存大小。

    示例4:指令级别并发

    现在让我们看一看不同的东西。下面两个循环中你以为哪个较快?

    1
    2
    3
    4
    5
    6
    7
    8
    int steps = 256 * 1024 * 1024;
    int [] a = new int [2];
     
    // Loop 1
    for ( int i=0; i<steps; i++) { a[0]++; a[0]++; }
     
    // Loop 2
    for ( int i=0; i<steps; i++) { a[0]++; a[1]++; }

    结果是第二个循环约比第一个快一倍,至少在我测试的机器上。为什么呢?这跟两个循环体内的操作指令依赖性有关。

    第一个循环体内,操作做是相互依赖的(译者注:下一次依赖于前一次):
    same value dependency
    但第二个例子中,依赖性就不同了:
    different values dependency

    现代处理器中对不同部分指令拥有一点并发性(译者注:跟流水线有关,比如Pentium处理器就有U/V两条流水线,后面说明)。这使得CPU在同一时刻访问L1两处内存位置,或者执行两次简单算术操作。在第一个循环中,处理器无法发掘这种指令级别的并发性,但第二个循环中就可以。

    [原文更新]:许多人在reddit上询问有关编译器优化的问题,像{ a[0]++; a[0]++; }能否优化为{ a[0]+=2; }。实际上,C#编译器和CLR JIT没有做优化——在数组访问方面。我用release模式编译了所有测试(使用优化选项),但我查询了JIT汇编语言证实优化并未影响结果。

    示例5:缓存关联性

    缓存设计的一个关键决定是确保每个主存块(chunk)能够存储在任何一个缓存槽里,或者只是其中一些(译者注:此处一个槽位就是一个缓存行)。

    有三种方式将缓存槽映射到主存块中:

    1. 直接映射(Direct mapped cache)
      每个内存块只能映射到一个特定的缓存槽。一个简单的方案是通过块索引chunk_index映射到对应的槽位(chunk_index % cache_slots)。被映射到同一内存槽上的两个内存块是不能同时换入缓存的。(译者注:chunk_index可以通过物理地址/缓存行字节计算得到)
    2. N路组关联(N-way set associative cache)
      每个内存块能够被映射到N路特定缓存槽中的任意一路。比如一个16路缓存,每个内存块能够被映射到16路不同的缓存槽。一般地,具有一定相同低bit位地址的内存块将共享16路缓存槽。(译者注:相同低位地址表明相距一定单元大小的连续内存)
    3. 完全关联(Fully associative cache)
      每个内存块能够被映射到任意一个缓存槽。操作效果上相当于一个散列表。

    直接映射缓存会引发冲突——当多个值竞争同一个缓存槽,它们将相互驱逐对方,导致命中率暴跌。另一方面,完全关联缓存过于复杂,并且硬件实现上昂贵。N路组关联是处理器缓存的典型方案,它在电路实现简化和高命中率之间取得了良好的折中。

    完全关联与多路关联的cache映射
    (此图由译者给出,直接映射和完全关联可以看做N路组关联的两个极端,从图中可知当N=1时,即直接映射;当N取最大值时,即完全关联。读者可以自行想象直接映射图例,具体表述见参考资料。)

    举个例子,4MB大小的L2缓存在我机器上是16路关联。所有64字节内存块将分割为不同组,映射到同一组的内存块将竞争L2缓存里的16路槽位。

    L2缓存有65,536个缓存行(译者注:4MB/64),每个组需要16路缓存行,我们将获得4096个集。这样一来,块属于哪个组取决于块索引的低12位bit(2^12=4096)。因此缓存行对应的物理地址凡是以262,144字节(4096*64)的倍数区分的,将竞争同一个缓存槽。我机器上最多维持16个这样的缓存槽。(译者注:请结合上图中的2路关联延伸理解,一个块索引对应64字节,chunk0对应组0中的任意一路槽位,chunk1对应组1中的任意一路槽位,以此类推chunk4095对应组4095中的任意一路槽位,chunk0和chunk4096地址的低12bit是相同的,所以chunk4096、chunk8192将同chunk0竞争组0中的槽位,它们之间的地址相差262,144字节的倍数,而最多可以进行16次竞争,否则就要驱逐一个chunk)。

    这是我记录的随笔:

    /home/me/Desktop/1527490301421.jpg

    为了使得缓存关联效果更加明了,我需要重复地访问同一组中的16个以上的元素,通过如下方法证明:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    public static long UpdateEveryKthByte(byte[] arr, int K)
    {
         Stopwatch sw = Stopwatch.StartNew();
         const int rep = 1024*1024; // Number of iterations – arbitrary
         int p = 0;
         for ( int i = 0; i < rep; i++)
         {
             arr[p]++;
             p += K;
             if (p >= arr.Length) p = 0;
         }
         sw.Stop();
         return sw.ElapsedMilliseconds;
    }

    该方法每次在数组中迭代K个值,当到达末尾时从头开始。循环在运行足够长(2^20次)之后停止。

    我使用不同的数组大小(每次增加1MB)和不同的步长传入UpdateEveryKthByte()。以下是绘制的图表,蓝色代表运行较长时间,白色代表较短时间:
    timing
    蓝色区域(较长时间)表明当我们重复数组迭代时,更新的值无法同时放在缓存中。浅蓝色区域对应80毫秒,白色区域对应10毫秒。

    让我们来解释一下图表中蓝色部分:

    1.为何有垂直线?垂直线表明步长值过多接触到同一组中内存位置(大于16次)。在这些次数里,我的机器无法同时将接触过的值放到16路关联缓存中。

    一些糟糕的步长值为2的幂:256和512。举个例子,考虑512步长遍历8MB数组,存在32个元素以相距262,144字节空间分布,所有32个元素都会在循环遍历中更新到,因为512能够整除262,144(译者注:此处一个步长代表一个字节)。

    由于32大于16,这32个元素将一直竞争缓存里的16路槽位。

    (译者注:为何512步长的垂直线比256步长颜色更深?在同样足够多的步数下,512比256访问到存在竞争的块索引次数多一倍。比如跨越262,144字节边界512需要512步,而256需要1024步。那么当步数为2^20时,512访问了2048次存在竞争的块而256只有1024次。最差情况下步长为262,144的倍数,因为每次循环都会引发一个缓存行驱逐。)

    有些不是2的幂的步长运行时间长仅仅是运气不好,最终访问到的是同一组中不成比例的许多元素,这些步长值同样显示为蓝线。

    2.为何垂直线在4MB数组长度的地方停止?因为对于小于等于4MB的数组,16路关联缓存相当于完全关联缓存。

    一个16路关联缓存最多能够维护16个以262,144字节分隔的缓存行,4MB内组17或更多的缓存行都没有对齐在262,144字节边界上,因为16*262,144=4,194,304。

    3.为何左上角出现蓝色三角?在三角区域内,我们无法在缓存中同时存放所有必要的数据,不是出于关联性,而仅仅是因为L2缓存大小所限。

    举个例子,考虑步长128遍历16MB数组,数组中每128字节更新一次,这意味着我们一次接触两个64字节内存块。为了存储16MB数组中每两个缓存行,我们需要8MB大小缓存。但我的机器中只有4MB缓存(译者注:这意味着必然存在冲突从而延时)。

    即使我机器中4MB缓存是全关联,仍无法同时存放8MB数据。

    4.为何三角最左边部分是褪色的?注意左边0~64字节部分——正好一个缓存行!就像上面示例1和2所说,额外访问相同缓存行的数据几乎没有开销。比如说,步长为16字节,它需要4步到达下一个缓存行,也就是说4次内存访问只有1次开销。

    在相同循环次数下的所有测试用例中,采取省力步长的运行时间来得短。

    将图表延伸后的模型:
    timing2

    缓存关联性理解起来有趣而且确能被证实,但对于本文探讨的其它问题比起来,它肯定不会是你编程时所首先需要考虑的问题。

    示例6:缓存行的伪共享(false-sharing)

    在多核机器上,缓存遇到了另一个问题——一致性。不同的处理器拥有完全或部分分离的缓存。在我的机器上,L1缓存是分离的(这很普遍),而我有两对处理器,每一对共享一个L2缓存。这随着具体情况而不同,如果一个现代多核机器上拥有多级缓存,那么快速小型的缓存将被处理器独占。

    当一个处理器改变了属于它自己缓存中的一个值,其它处理器就再也无法使用它自己原来的值,因为其对应的内存位置将被刷新(invalidate)到所有缓存。而且由于缓存操作是以缓存行而不是字节为粒度,所有缓存中整个缓存行将被刷新!

    为证明这个问题,考虑如下例子:

    1
    2
    3
    4
    5
    6
    7
    8
    private static int [] s_counter = new int [1024];
    private void UpdateCounter( int position)
    {
         for ( int j = 0; j < 100000000; j++)
         {
             s_counter[position] = s_counter[position] + 3;
         }
    }

    在我的四核机上,如果我通过四个线程传入参数0,1,2,3并调用UpdateCounter,所有线程将花费4.3秒。

    另一方面,如果我传入16,32,48,64,整个操作进花费0.28秒!

    为何会这样?第一个例子中的四个值很可能在同一个缓存行里,每次一个处理器增加计数,这四个计数所在的缓存行将被刷新,而其它处理器在下一次访问它们各自的计数(译者注:注意数组是private属性,每个线程独占)将失去命中(miss)一个缓存。这种多线程行为有效地禁止了缓存功能,削弱了程序性能。

    示例7:硬件复杂性

    即使你懂得了缓存的工作基础,有时候硬件行为仍会使你惊讶。不用处理器在工作时有不同的优化、探试和微妙的细节。

    有些处理器上,L1缓存能够并发处理两路访问,如果访问是来自不同的存储体,而对同一存储体的访问只能串行处理。而且处理器聪明的优化策略也会使你感到惊讶,比如在伪共享的例子中,以前在一些没有微调的机器上运行表现并不良好,但我家里的机器能够对最简单的例子进行优化来减少缓存刷新。

    下面是一个“硬件怪事”的奇怪例子:

    1
    2
    3
    4
    5
    6
    7
    8
    private static int A, B, C, D, E, F, G;
    private static void Weirdness()
    {
         for ( int i = 0; i < 200000000; i++)
         {
             // do something...
         }
    }

    当我在循环体内进行三种不同操作,我得到如下运行时间:

               操作                    时间
    A++; B++; C++; D++;     719 ms
    A++; C++; E++; G++;     448 ms
    A++; C++;                      518 ms

    增加A,B,C,D字段比增加A,C,E,G字段花费更长时间,更奇怪的是,增加A,C两个字段比增加A,C,E,G执行更久!

    我无法肯定这些数字背后的原因,但我怀疑这跟存储体有关,如果有人能够解释这些数字,我将洗耳恭听。

    这个例子的教训是,你很难完全预测硬件的行为。你可以预测很多事情,但最终,衡量及验证你的假设非常重要。

    关于第7个例子的一个回帖

    Goz:我询问Intel的工程师最后的例子,得到以下答复:

    “很显然这涉及到执行单元里指令是怎样终止的,机器处理存储-命中-加载的速度,以及如何快速且优雅地处理试探性执行的循环展开(比如是否由于内部冲突而多次循环)。但这意味着你需要非常细致的流水线跟踪器和模拟器才能弄明白。在纸上预测流水线里的乱序指令是无比困难的工作,就算是设计芯片的人也一样。对于门外汉来说,没门,抱歉!”

    P.S.个人感悟——局部性原理和流水线并发

    程序的运行存在时间和空间上的局部性,前者是指只要内存中的值被换入缓存,今后一段时间内会被多次引用,后者是指该内存附近的值也被换入缓存。如果在编程中特别注意运用局部性原理,就会获得性能上的回报。

    比如C语言中应该尽量减少静态变量的引用,这是因为静态变量存储在全局数据段,在一个被反复调用的函数体内,引用该变量需要对缓存多次换入换出,而如果是分配在堆栈上的局部变量,函数每次调用CPU只要从缓存中就能找到它了,因为堆栈的重复利用率高。

    再比如循环体内的代码要尽量精简,因为代码是放在指令缓存里的,而指令缓存都是一级缓存,只有几K字节大小,如果对某段代码需要多次读取,而这段代码又跨越一个L1缓存大小,那么缓存优势将荡然无存。

    关于CPU的流水线(pipeline)并发性简单说说,Intel Pentium处理器有两条流水线U和V,每条流水线可各自独立地读写缓存,所以可以在一个时钟周期内同时执行两条指令。但这两条流水线不是对等的,U流水线可以处理所有指令集,V流水线只能处理简单指令。

    CPU指令通常被分为四类,第一类是常用的简单指令,像mov, nop, push, pop, add, sub, and, or, xor, inc, dec, cmp, lea,可以在任意一条流水线执行,只要相互之间不存在依赖性,完全可以做到指令并发。

    第二类指令需要同别的流水线配合,像一些进位和移位操作,这类指令如果在U流水线中,那么别的指令可以在V流水线并发运行,如果在V流水线中,那么U流水线是暂停的。

    第三类指令是一些跳转指令,如cmp,call以及条件分支,它们同第二类相反,当工作在V流水线时才能通U流水线协作,否则只能独占CPU。

    第四类指令是其它复杂的指令,一般不常用,因为它们都只能独占CPU。

    如果是汇编级别编程,要达到指令级别并发,必须要注重指令之间的配对。尽量使用第一类指令,避免第四类,还要在顺序上减少上下文依赖。

    参考资料

    wiki上的CPU cache解析(中文版)(英文版)。

    上海交通大学师生制作的一个关于cache映射功能、命中率计算的教学演示程序,模拟了不同关联模式下cache的映射和命中几率,形象直观。

    网易数据库大牛@何_登成自制PPT《CPU Cache and Memory Ordering》,信息量超大!

    南京大学计算机教学公开PPT,温馨提示,地址域名里面改变字段”lecture”后面的数字编号可切换课程;-).


    下文转载自:https://blog.csdn.net/leoufung/article/details/48804627

    最近组内有个同事在做cacheline相关的特性,向其学习了一下,对原来的cacheline的理解更近了一步。这里总结一下。请彭超大侠有空的话帮忙在斧正一下

    Cache就是对内存的内容进行缓存的一个硬件。cache和内存的逻辑关系结构如下图所示。从左往右,从上到下逐个说明,下图就是上面介绍的直接映射.







    首先物理内存又是通过物理地址PA(physical address)标识的,内存块用PA+SIZE表示,在读取内存的时候,CPU会将内存块load到cache中,但是并不是按照SIZE的大小load内存块,而是按照cacheline的大小load一个内存块,指定的物理内存块将被包含在这段被load的内存中(如上图黄色+蓝色部分所示,黄色代表了内存块在cacheline大小的内存块中的位置)。所以在编程的时候,尽量将结构设计为cacheline对其的,一次可以加载完成,访问下个结构体的时候,就可以直接访问另一个cacheline,而不发生冲突了。

    物理地址又被分为三个部分,tag+index+offset。index就是物理地址在cache这个大数组中的位置,相当于数组索引,索引到了后,offset说明了PA所在的内存在cacheline中的偏移量。
    这样看来,就会发现很可能两个物理地址中见的index很有可能发生重复,这就是cacheline冲突。这样的情况下,就要先废除cacheline上前一个的内容后重新加载新的内存才会有效。这样的冲突会大大降低内存的访问效率,所以intel有提出了一种更新的架构,如下图N路映射所示




    在每个cacheline的下一级又多了way的概念,每个cacheline的下一级又被分为4WAY或8WAY,每个way都相当于一个cacheline。这样即使index冲突,也可以将内存内容放到不同的way中减少冲突。tag就是用来表示是那个way上的。上面的结构就是所谓的4路组相连或8路组相连的概念。

    展开全文
    liguangxianbin 2018-05-28 14:50:43
  • 一、CPU,内存和cache之间的关系   如今的CPU和二十几年前的相比,其精密程度和运作速度可谓天壤之别。在以前,CPU的工作频率和内存总线的频率是处于一个等级的,CPU对内存的访问速度也只是比对寄存器的访问速度要...

    一、CPU,内存和cache之间的关系           

           如今的CPU和二十几年前的相比,其精密程度和运作速度可谓天壤之别。在以前,CPU的工作频率和内存总线的频率是处于一个等级的,CPU对内存的访问速度也只是比对寄存器的访问速度要慢那么一点儿,所以CPU直接访问内存是再合理不过了。但是近十几年来,CPU发展迅猛,其工作频率大大增加,而内存的发展却无法跟上大哥的步伐。当然,并不是做不出访问频率高的内存,而是SRAM那样的高速度内存相对于作为普通内存的DRAM而言,成本过高。因此,一个折中的选择就是在CPU和内存之间引入高速缓存(cache),作为CPU和内存之间的渠道。CPU将接下来最有可能用到的数据存放在cache中,那么CPU是如何预测到接下来将要用到的数据的呢?这种预测是基于程序代码和数据在时间和空间上的局部性原理(locality)。所谓局部性原理,就是指由于循环结构的存在,在最近这段时间,同样的代码和数据很有可能再被使用。下图给出了CPU,cache和内存之间的基本关系

     

               

          

           虽然计算机采用的是冯诺依曼架构,但是经验表明,将代码用的cache和数据用的cache分离开来效率更高。Intel正是从1993年开始,针对代码和数据使用相互独立的cache。随着cache的引入,cache和内存之间的工作频率差别又开始慢慢拉大,这样,又引入了下一级的cache,其容量比第一级大,速度比第一级慢。这同样是速度和经济的折中考虑,如今甚至有系统引入三级高速缓存,如下图所示

     

    其中L1d是第一级数据缓存,L1i是第一级指令缓存,要注意的一点事该图只是一个概略的描述,实际上数据从任何一个CPU Core流向主存是不用经过高级缓存(L2,L3)的。

     

    二、cache的操作   

               当CPU需要数据时,首先到cache内部去寻找,如果找到了,则称为命中了(cache hit),如果没有找到,则称为丢失(cache miss),这时CPU必须到内存去读取数据,并且将其保存在cache中以备后用。

           cache中需要保存数据字在主存中的地址,cache的每个入口都被相应数据的地址所标记,当CPU要完成一次读或写操作时,会在cache中寻找匹配的标记。cache中存储的地址可以是虚拟地址,也可以是物理地址,根据cache的实现而不同。由于标记在cache中本身要占用空间,所以如果以字为粒度在cache中标记主存的地址单元那就显得有些低效。解决的办法很简单,还记得cache是基于空间的局部性原理的,由于被标记的内存字的邻近单元也有可能被使用,所以会把它们也一起加载到cache中去。因此一个cache的入口处存储的并不是单一的字,而是几个连续的字,它们被称为缓存行(cache line).

           对应每个cache line,都有这样一个结构

              

     

           data bolck存放的是缓存行中所保存的就是从主存取过来的数据,tag表示的是数据块在主存中的地址(并不是完整的地址),flag bits是一些在操作过程中涉及到的标志位。

           而对于主存中的每个地址单元,我们都可以按下图的结构进行解析

          

            我们已经知道,一个cache line对应的是主存中连续的几个字,那么这些字的低位对于映射一个cache line是没用的,比如说在一个32位系统中,一个cache line的大小是16个字,也就是64个字节,那么其低6位在映射一个cache时是没有用的,其作用是用来指定该内存单元在对应cache line中的偏移。Cache Set则指明了该内存单元位于哪一个cache set(一个cache set 可以包含一个或多个cache line,这与cache和内存之间的映射关系有关,在后面会进行讲解),S的长度为以2为底的log(cache sets),由于一个cache set可以包含多个cache line,所以还需要高T位的tag域来指明该内存单元是位于哪个cache line中。

           下面来说说flag bits域。对于指令cache来说,flag bits位只有一位,即valid位。顾名思义,valid位指明了相应的cache line中是否装载了有效的数据。系统刚上电时,所有的cache line中的valid位都被设置为invalid.对于数据cache来说,flag bits除了有valid位外,还有一个dirty位。对于cache line来说,如果读进来的数据还未被修改,则称为clean;相反,如果数据被修改了但是还没被写回内存,这时将dirty置位表示内存和cache里的数据不同步。在SMP系统中,所有的处理器都必须协调工作保证它们所看到的内存里的内容必须是一样的,这种问题被称为缓存一致性(cache coherency).假设一个处理器的cache内对某一内存有一份clean cache copy,而这时该处理器监测到另一个处理器对相应的该内存单元发出一个写请求,那么前一个处理器将会把相应的cache line给设置为dirty,等待后者的写操作完成并进行重装载,以保证数据的同步性。显然,读操作是不会影响cache的一致性的。对于cache的实现的一些细节将在下一篇中给出。

     

    原文:http://blog.csdn.net/vanbreaker/article/details/7470830


    三、cache和内存的关联方式(associativity)

               根据cache和内存之间的映射关系的不同,cache可以分为三类:一类是全关联cache(full associative cache),一种是直接关联cache(direct mapped cache),还有一种是N路关联cache(N-ways associative cache).

     

    1.全相联型cache

                顾名思义,全相联型cache的特点就是cache内的任何一个cache line都可以映射到内存的任何一处地方,这使得全关联cache的命中率是最高的,但是CPU要想访问和内存相互映射的cache不得不把内存地址与大量的cache标志(tag)

    进行比较匹配,这使得效率下降,而且对于cache,其内部电路十分复杂,因此只有容量很小的cache才会设计成全关联型的(如一些INTEL处理器中的TLB Cache).对于全关联方式,内存地址的解析方式如下图所示:

         

    可以看到内存地址只解析成tag和offset两个域,其中tag是和cache line对应的整个物理地址,而offset即是该内存单元在cache line中的偏移。

     

    2.直接相联型cache

             设一个cache中总共存在N个cache line,那么内存被分成N等分,其中每一等分对应一个cache line,需要注意的是这里所说的1等分只是大小上的一等分,在内存上并不是完全连续的。具体的来说,假设cache的大小事4M,而一个cache line的大小是64B,那么就一共有4M/64B=65536个cache line,那么对应我们的内存,0x00000000~0x00000000+64B, 0x00000000+4M~0x00000000+4M+64B,  ……,就这样被分为很多个区段,对于一个确定的cache line,如第0个,那么在这么多区段中只有一个区段能被映射进去,没有被映射进去的区段不能占用其他的cache line,这样就势必导致cache的命中率下降,所以直接关联是一种很''死''的映射方法,它的命中率是最低的,但是其实现方式最为简单,匹配速度也最快。对于直接关联方式,内存地址的解析如下图所示

    该图在前篇文章中出现过,在前文中提到过cache set可以包含一个或多个cache line,那么对于直接关联cache,cache set就是一个cache line,在刚才说到的4M/64B的cache例子中,offset的长度为6位(bit 0~bit 5),cache set的长度为16位(bit 6~bit 21),用cache set域即可直接定位对应的cache line的位置。

     

     

    3.N路相联型cache

          N路相连cache是前两种cache的折中形式,在这种方式下,内存同样被分为很多区域,一个区域的大小为N个cache line的大小,一个区域映射到对应的N个连续的cache line,并且该区域内的单元可以映射到N个cache line中的任意一个。假设一个4-路相联cache,其大小为64M,一个cache line的大小为16K,那么总共有64M/16K=16384个cache line,但是在4-路相联的情况下,我们并不是简简单单拥有16384个cache line,而是拥有了16384/4=4096个区域(sets),每个区域有4个cache line.一个内存单元可以缓存到它所对应的set中的任意一个cache line中去。对于内存地址的解析,N路相联型和直接相联型在结构上是一样的,但是因为N路相联型的cache中的cache set有N个cache line,所以在通过内存地址单元的cache set域确定相应的set外,还要通过tag域来确定对应的cache line.

     

          细心的朋友应该已经发现了,实际上直接相联型cache和全相联型cache只是N路相联型cache的特殊情况,当N为1时,1-路相联型cache即为直接相联型cache.而当N值和cache line的总数相等时,整个cache即为一个set,成为全相联型cache。下面再给出直接相联型cache和全相联型cache与内存的映射关系图。

    注:图中的Index即为cache set

     

    原文:http://blog.csdn.net/vanbreaker/article/details/7475093


    四、cache的写策略

            内存的数据被加载到了cache后,在某个时刻其要被写回内存,对于这个时刻的选取,有如下几个不同的策略。

            write-through:所谓write-through,就是指在CPU改写一个cache line后,cache line也被CPU写回内存。这种策略保证了在任何时刻,内存的数据和cache中的数据都是同步的,因此write-through最容易实现cache的一致性。显然,由于CPU要频繁地将cache里的被修改的数据写回内存,这种方法最大的缺点就是速度慢,效率低。假设一段程序在频繁地修改一个局部变量,那么尽管这个局部变量的生命周期很短,而且其他程序也用不到它,CPU依然会频繁地在cache和内存之间交换数据,这样会大大增加FSB总线(见《从硬件的体系结构开始》)上的数据流量。

            write-back:write-back相对于write-through而言是一种更精炼的方法,采用write-back策略,CPU在改写了cache line后,并不是马上把其写回内存,而是将该cache line标志为dirty。只有当cache中发生一次cache miss,其他的数据要占用该cache line时,CPU才会把其写回内存。在实现write-back策略时,有一个重要的问题是需要被考虑到的,当多个处理器访问同一内存时,必须保证所有处理器所看到的内存内容是相同的,也就是一致性的问题。当一个cache line被一个处理器设置为dirty后,另一个处理器要访问同一内存,那么显然,该处理器真正需要的数据是前者的cache里的数据,而不是内存中还未更新的数据,后面会讲解这个问题是如何解决的。

           在此之前我们再来看两种写策略,分别是write-combining和uncacheable. 这两种策略都是针对特殊的地址空间来使用的。

            write-combining是针对于具体设备内存(如显卡的RAM)的一种优化处理策略。对于这些设备来说,数据从cache到内存转移的开销比直接访问相应的RAM的开销还要高得多,所以应该尽量避免过多的数据转移。试想,如果一个cache line里的字被改写了,CPU将其写回内存,紧接着又一个字被改写了,CPU又将该cache line写回内存,这样就显得低效,符合这种情况的一个例子就是显示屏上水平相连的像素点数据。write-combining策略的引入就是为了解决这种问题,顾名思义,这种策略就是当一个cache line里的数据一个字一个字地都被改写完了之后,才将该cache line写回到内存中。

           uncacheable内存是一部分特殊的内存,该内存里的数据时硬编码的,可以不需要CPU的控制就能实现一些功能,比如用来访问一些链接在外部总线(如PCIe,etc)的设备而被映射的地址空间。PCI card中的内存可以不依赖CPU的控制就能发生改变,所以它是不需要被缓存的。

     

    五、多处理器支持

            在一个典型的系统中,几个cache通过共享总线来连接到内存,而这些cache又分别附属给几个不同的CPU。这些cache的共同目标就是尽可能减少对主存的使用。为了解决cache的一致性问题,cache的设计者们引入了很多不同的协议,其中MESI协议被广泛用于支持write-back cache. 还记得在前面说过,数据cache中用两位来表示一个cache line的状态,MESI协议中利用这两位组成4种状态,分别是Modified,Exclusive,Shared和Invalid,下面说明这四种状态的含义

       Modified:本地处理器修改了cache line中的数据,并且数据只存在于这一个cache中,在其他cache中没有备份。

       Exclusive:cache line中的数据没有被修改,并且数据只存在于这一个cache中,在其他cache中没有备份。

       Shared:cache line中的数据没有本修改,该数据有可能在其他cache中有备份。

       Invalid:cache line中的数据是无效的。

     

      下面给出各个状态之间的转换图:

            

     

         每两个状态之间的转换说明,网上有一位朋友描述得很详细,我将他总结的贴在下面

      

    当前状态

    事件

    行为

    下一个状态

    I(Invalid)

    Local Read

    如果其它Cache没有这份数据,本Cache从内存中取数据,Cache line状态变成E;

    如果其它Cache有这份数据,且状态为M,则将数据更新到内存,本Cache再从内存中取数据,2个Cache 的Cache line状态都变成S;

    如果其它Cache有这份数据,且状态为S或者E,本Cache从内存中取数据,这些Cache 的Cache line状态都变成S

    E/S

    Local Write

    从内存中取数据,在Cache中修改,状态变成M;

    如果其它Cache有这份数据,且状态为M,则要先将数据更新到内存;

    如果其它Cache有这份数据,则其它Cache的Cache line状态变成I

    M

    Remote Read

    既然是Invalid,别的核的操作与它无关

    I

    Remote Write

    既然是Invalid,别的核的操作与它无关

    I

    E(Exclusive)

    Local Read

    从Cache中取数据,状态不变

    E

    Local Write

    修改Cache中的数据,状态变成M

    M

    Remote Read

    数据和其它核共用,状态变成了S

    S

    Remote Write

    数据被修改,本Cache line不能再使用,状态变成I

    I

    S(Shared)

    Local Read

    从Cache中取数据,状态不变

    S

    Local Write

    修改Cache中的数据,状态变成M,

    其它核共享的Cache line状态变成I

    M

    Remote Read

    状态不变

    S

    Remote Write

    数据被修改,本Cache line不能再使用,状态变成I

    I

    M(Modified)

    Local Read

    从Cache中取数据,状态不变

    M

    Local Write

    修改Cache中的数据,状态不变

    M

    Remote Read

    这行数据被写到内存中,使其它核能使用到最新的数据,状态变成S

    S

    Remote Write

    这行数据被写到内存中,使其它核能使用到最新的数据,由于其它核会修改这行数据,状态变成I

    I

                                       MESI状态迁移

     

       (注:该表引自http://blog.csdn.net/muxiqingyang/article/details/6615199

     

    原文:

    http://blog.csdn.net/vanbreaker/article/details/7477853




    展开全文
    wolf96 2015-11-29 11:25:06
  • CPU Cache 出现原因 CPU速度比主存快很多倍,CPU瓶颈在存取数据 SRAM比DRAM速度快,但太贵, 少量SRAM做Cache就能大幅提升性能 CPU Cache 三级缓存 一级缓存与二级缓存属于他们自己的CPU内核, 三级缓存也叫共享...

    什么是缓存

    一台电脑有两种内存
    一种是在RAM模块中使用的DRAM(Dynamic RAM),使用电容器来存储数据的内存需要动态地被电流刷新才能存储数据
    另一种是CPU中使用叫做SRAM(Static RAM)
    在这里插入图片描述

    CPU Cache 出现原因

    • CPU速度比主存快很多倍,CPU瓶颈在存取数据
    • SRAM比DRAM速度快,但太贵,
    • 少量SRAM做Cache就能大幅提升性能

    CPU Cache 三级缓存

    一级缓存与二级缓存属于他们自己的CPU内核,
    三级缓存也叫共享缓存,因为它的内存在所有CPU核心间共享
    在这里插入图片描述

    展开全文
    wanniwa 2020-06-01 23:45:58
  • Zhu_Zhu_2009 2019-04-11 18:57:32
  • xcw_1987 2019-06-11 11:09:16
  • KIDGIN7439 2019-11-18 17:57:22
  • u010983881 2018-09-14 16:13:06
  • lixiaogang_theanswer 2020-12-31 01:10:33
  • 898KB weixin_42681774 2021-10-04 03:39:33
  • juS3Ve 2019-08-29 08:18:00
  • farmwang 2018-10-25 10:07:29
  • Rong_Toa 2020-11-04 21:24:50
  • weixin_43895356 2021-05-10 19:28:05
  • midion9 2015-10-29 10:20:10
  • 3星
    19KB vt8365a 2011-11-10 09:50:43
  • tercel_zhang 2016-08-18 21:27:53
  • majianting 2019-01-15 16:39:30
  • daaikuaichuan 2017-11-21 09:54:05
  • 23KB jiebing2020 2021-09-24 22:45:04
  • u011414616 2018-03-29 20:35:16
  • wagsyang 2018-01-21 01:53:46
  • wmq880204 2016-11-11 18:29:18
  • notbaron 2015-08-31 23:45:09
  • 5星
    361KB weixin_38363081 2018-06-29 21:26:33

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 289,680
精华内容 115,872
关键字:

CPUcache