Nop*_*ope 15 c performance caching cpu-architecture cpu-cache
在编写模拟时,我的伙伴说他喜欢尝试编写足够小的程序以适应缓存.这有什么实际意义吗？据我所知,缓存比RAM和主内存快.是否可以指定您希望程序从缓存运行或至少将变量加载到缓存中？我们正在编写模拟,因此任何性能/优化收益都是巨大的好处.
如果您知道任何解释CPU缓存的好链接,那么请指出我的方向.
Jer*_*fin 30
至少对于典型的桌面CPU,您无法直接指定很多缓存使用情况.您仍然可以尝试编写缓存友好的代码.在代码方面,这通常意味着展开循环(仅一个明显的例子)很少有用 - 它扩展了代码,而现代CPU通常可以最小化循环的开销.您通常可以在数据方面做更多事情,以改善引用的位置,防止错误共享(例如,两个经常使用的数据片段将尝试使用相同的缓存部分,而其他部分仍未使用).
编辑(使某些点更明确):
典型的CPU具有许多不同的缓存.现代桌面处理器通常具有至少2级且通常3级的高速缓存.通过(至少几乎)通用协议,"级别1"是与处理元件"最接近"的高速缓存,并且数字从那里上升(级别2是下一级,之后是级别3,等等)
在大多数情况下,(至少)1级缓存被分成两半:指令缓存和数据缓存(英特尔486几乎是我所知道的唯一例外,指令和数据都有一个缓存 - 但它已经彻底过时了,可能不值得考虑.
在大多数情况下,缓存被组织为一组"行".通常一次读取,写入和跟踪一行高速缓存的内容.换句话说,如果CPU将使用来自高速缓存行的任何部分的数据,则从下一个较低级别的存储读取整个高速缓存行.靠近CPU的高速缓存通常较小并且具有较小的高速缓存行.
这种基本体系结构导致了编写代码时缓存的大多数特性.您希望尽可能多地将某些内容读入缓存中,然后使用它执行所有操作,然后继续使用其他内容.
这意味着,当您处理数据时,通常最好读取相对少量的数据(足够小以适应缓存),尽可能多地处理该数据,然后继续下一个块数据.像Quicksort这样的算法可以快速地将大量输入分解为逐渐变小的部分,这或多或少会自动执行此操作,因此它们往往对缓存非常友好,几乎与缓存的精确细节无关.
这也会影响您编写代码的方式.如果你有一个像这样的循环:
for i = 0 to whatever
step1(data);
step2(data);
step3(data);
end for
你通常最好将多个步骤串在一起,因为你可以达到适合缓存的数量.溢出缓存的那一刻,性能会急剧下降.如果上面步骤3的代码足够大以至于它不适合缓存,那么通常最好将循环分成两部分(如果可能):
for i = 0 to whatever
step1(data);
step2(data);
end for
for i = 0 to whatever
step3(data);
end for
循环展开是一个相当激烈的争议主题.一方面,它可以导致代码更加CPU友好,减少了为循环本身执行的指令的开销.同时,它可以(并且通常会)增加代码大小,因此它相对缓存不友好.我自己的经验是,在合成基准测试中,往往会对大量数据进行少量处理,您可以从循环展开中获得很多收益.在更实际的代码中,您倾向于对单个数据进行更多处理,您可以获得更少的收益 - 并且溢出缓存导致严重的性能损失并不是特别罕见.
数据缓存的大小也有限.这意味着您通常希望尽可能密集地打包数据,以便尽可能多的数据适合缓存.仅举一个明显的例子,与指针链接在一起的数据结构需要在计算复杂性方面获得相当多的收益,以弥补这些指针使用的数据缓存空间量.如果您要使用链接数据结构,通常希望至少确保将相对较大的数据链接在一起.
然而,在很多情况下,我发现我最初学习的技巧是将数据装入微小处理器中的微小内存,这些处理器已经(大部分)已经过时了几十年,在现代处理器上运行良好.现在的意图是在缓存而不是主存储器中容纳更多数据,但效果几乎相同.在很多情况下,您可以认为CPU指令几乎是免费的,并且整体执行速度由缓存(或主存储器)的带宽决定,因此从密集格式解压缩数据的额外处理工作在你的好意 当您处理足够的数据以至于它们都不再适合缓存时,尤其如此,因此整体速度由主存储器的带宽决定.在这种情况下,您可以执行大量指令以节省一些内存读取,并且仍然可以提前完成.
并行处理会加剧这个问题.在许多情况下,重写代码以允许并行处理可能导致性能几乎没有增加,有时甚至导致性能损失.如果整体速度受从CPU到内存的带宽控制,那么有更多内核竞争该带宽不太可能有任何好处(并且可能造成实质性损害).在这种情况下,使用多个内核来提高速度往往归结为更加紧密地打包数据,并利用更多的处理能力来解压缩数据,因此真正的速度增益来自于减少消耗的带宽并且额外的内核不会浪费时间从更密集的格式解压缩数据.
并行编码中可能出现的另一个基于缓存的问题是变量的共享(和错误共享).如果两个(或更多)内核需要写入内存中的相同位置,则保存该数据的高速缓存行最终可以在内核之间来回切换,以便为每个内核提供对共享数据的访问.结果通常是并行运行的代码比串行运行的代码慢(即,在单个内核上).这有一种称为"错误共享"的变体,其中不同内核上的代码正在写入单独的数据,但不同内核的数据最终位于同一缓存行中.由于缓存完全根据整行数据控制数据,因此无论如何数据都会在核心之间来回移动,从而导致完全相同的问题.
一篇有用的论文将告诉你关于缓存的更多信息,这是Ulrich Drepper 每位程序员应该了解的内容.Hennessey非常透彻地介绍它.Christer和Mike Acton也写了很多关于这个的好东西.
我认为你应该更多地担心数据缓存而不是指令缓存 - 根据我的经验,dcache misses更频繁,更痛苦,更有用的修复.
更新：1/13/2014 据这位高级芯片设计人员介绍，高速缓存未命中现已成为代码性能的绝对主导因素，因此就相对性能而言，我们基本上可以追溯到80年代中期和286颗快速芯片加载，存储，整数算术和缓存未命中的瓶颈。
Cliff Click @ Azul撰写的“现代硬件速成班” 。。。。。
---现在我们将您带回您的定期计划-
有时候，一个例子比描述如何做更好。本着这种精神，这是一个特别成功的示例，说明了我如何更改一些代码以更好地在芯片缓存中使用。这是在486 CPU上完成的，后来又移植到了第一代Pentium CPU。对性能的影响是相似的。
示例：下标映射
这是我用来将数据放入具有通用用途的芯片缓存中的一种技术示例。
我有一个双浮点向量，长度为1,250个元素，这是一条流行病学曲线，尾巴很长。曲线的“有趣”部分仅具有大约200个唯一值，但我不希望使用两面if（）测试来弄乱CPU的流水线（因此，长尾巴可以用作下标，这是最极端的）值（蒙特卡罗代码会吐出的值）），我需要在代码“热点”内进行其他十二个条件测试的分支预测逻辑。
我决定采用一种方案，在该方案中，我将8位整数的向量用作双精度向量的下标，我将其缩短为256个元素。这些小整数在零之前的128之前和零之后的128都具有相同的值，因此，除了中间的256个值以外，它们都指向double向量中的第一个或最后一个值。
这将存储需求缩减为2k（双打）和1,250字节（8位下标）。这将10,000字节缩减为3,298。由于程序在此内循环中花费了90％或更多的时间，因此这两个向量从未被推出8k数据缓存。该程序的性能立即提高了一倍。在计算100万以上抵押贷款的OAS值的过程中，此代码被击中了1000亿次。
由于很少触及曲线的尾部，因此很有可能实际上只有微小的int向量的中间200-300个元素被保留在高速缓存中，而160-240个中间双精度代表了1/8的百分比。在我花了一年多时间优化的程序上，它的性能显着提高，并在一个下午完成。
我也同意Jerry的观点，就像我的经验一样，向指令缓存倾斜代码并没有像对数据缓存进行优化那样成功。这是我认为AMD的通用缓存不如Intel的独立数据和指令缓存有用的原因之一。IE：您不希望指令占用高速缓存，因为它不是很有帮助。在某种程度上，这是因为CISC指令集最初是为了弥补CPU和内存速度之间的巨大差异而创建的，除了80年代后期的异常之外，这几乎总是正确的。
我用来支持数据缓存并节省指令缓存的另一项最喜欢的技术是，在结构定义中使用很多位整数，并且通常使用最小的数据大小。要屏蔽4位int以保留一年中的月份，或9位以保留一年中的日期，依此类推，等等，这需要CPU使用掩码来屏蔽位所使用的主机整数，这会缩小数据，有效地增加了缓存和总线的大小，但需要更多指令。尽管此技术产生的代码在综合基准测试中表现不佳，但在用户和进程争夺资源的繁忙系统上却表现出色。