在高性能的计算中,我们常说缓存失效(cache-miss)是一个算法中最大性能损失点。 近些年来,我们的处理器处理能力的增长速度已经大大超 过了访问主内存的延迟的缩短。 通过更宽的,多通道的总线,到主内存的带宽已经大大增加,但延迟并没有相应显著减少。 为了减少延迟,处理器采用愈加复杂 的多层的高速缓存子系统。 在1994年的一篇论文“Hitting the memory wall: implications of the obvious”中描述了这个问题,并且认为由于缓存失效(cache-miss)必定存在,缓存不能最终解决这个问题。我的目标是:向大家展示通过利用访问模型,它是对缓存层次结构的思考,上面的结论并不是必然的。 让我们带着问题,来看下面的例子, 我们的硬件试图通过一些技术来减少主内存的延迟。 内存访问模型主要基于下面三个规律: 1、时间局部性 :最近访问过的内存最可能立马再次被访问; 2、空间局部性:相邻的内存最可能立马再次被访问; 3、 跨越式:内存访问可能会遵循一种可预测的模式。 首先让我们通过一些代码和测试结果,来说明这三个规律的正确性: 1、线性访问情形的内存访问是完全可以预测的; 2、在一个限定的内存区域内做伪随机访问,然后跳到下一个限定内存区域,如此重复。这个“限定内存区域”就是大家所熟知的内存页;。 3、在一个大面积堆内存中伪随机访问。
下面的代码需要添加 -Xmx4g JVM选项运行:
01 public class TestMemoryAccessPatterns { 02 03 private static final int LONG_SIZE = 8; 04 private static final int PAGE_SIZE = 2 * 1024 * 1024; 05 private static final int ONE_GIG = 1024 * 1024 * 1024; 06 private static final long TWO_GIG = 2L * ONE_GIG; 07 private static final int ARRAY_SIZE = (int) (TWO_GIG / LONG_SIZE); 08 private static final int WORDS_PER_PAGE = PAGE_SIZE / LONG_SIZE; 09 private static final int ARRAY_MASK = ARRAY_SIZE - 1; 10 private static final int PAGE_MASK = WORDS_PER_PAGE - 1; 11 private static final int PRIME_INC = 514229; 12 private static final long[] memory = new long[ARRAY_SIZE]; 13 14 static { 15 for (int i = 0; i < ARRAY_SIZE; i++) { 16 memory[i] = 777; 17 } 18 } 19 20 public enum StrideType { 21 LINEAR_WALK { 22 23 @Override 24 public int next(final int pageOffset, final int wordOffset, final int pos) { 25 return (pos + 1) & ARRAY_MASK; 26 } 27 }, 28 29 RANDOM_PAGE_WALK { 30 31 @Override 32 public int next(final int pageOffset, final int wordOffset, final int pos) { 33 return pageOffset + ((pos + PRIME_INC) & PAGE_MASK); 34 } 35 }, 36 37 RANDOM_HEAP_WALK { 38 39 @Override 40 public int next(final int pageOffset, final int wordOffset, final int pos) { 41 return (pos + PRIME_INC) & ARRAY_MASK; 42 } 43 }; 44 45 public abstract int next(int pageOffset, int wordOffset, int pos); 46 47 } 48 49 public static void main(final String[] args) { 50 final StrideType strideType; 51 52 switch (Integer.parseInt(args[0])) { 53 case 1: 54 strideType = StrideType.LINEAR_WALK; 55 break; 56 case 2: 57 strideType = StrideType.RANDOM_PAGE_WALK; 58 break; 59 case 3: 60 strideType = StrideType.RANDOM_HEAP_WALK; 61 break; 62 default: 63 throw new IllegalArgumentException("Unknown StrideType"); 64 } 65 66 for (int i = 0; i < 5; i++) { 67 perfTest(i, strideType); 68 } 69 } 70 71 private static void perfTest(final int runNumber, final StrideType strideType) { 72 final long start = System.nanoTime(); 73 int pos = -1; 74 long result = 0; 75 for (int pageOffset = 0; pageOffset < ARRAY_SIZE; pageOffset += WORDS_PER_PAGE) { 76 for (int wordOffset = pageOffset, limit = pageOffset + WORDS_PER_PAGE; wordOffset < limit; wordOffset++) { 77 pos = strideType.next(pageOffset, wordOffset, pos); 78 result += memory[pos]; 79 } 80 } 81 final long duration = System.nanoTime() - start; 82 final double nsOp = duration / (double) ARRAY_SIZE; 83 if (208574349312L != result) { 84 throw new IllegalStateException(); 85 } 86 System.out.format("%d - %.2fns %s\n", Integer.valueOf(runNumber), Double.valueOf(nsOp), strideType); 87 } 88}这段代码我分别在3种不同的CPU架构中运行,如上面所显示的是intel的各个发展阶段的CPU。 很显然,每一代CPU都拥有更好的降低主内存 的延迟的能力。除了相对较小的堆,这个实验是基于上面3个规律。 虽然各个缓存的规模和复杂程度不断提高。 然而由于内存大小的增加,他们变得不那么 有效了。 例如,在i7-860堆内随机访问时,如果数组容量扩大一倍,达到4GB的大小,平均延迟由大约30ns增加到大约55ns。似乎在线性访问的 情形下,不存在内存延迟。 然而当我们以更加随机模式访问内存,延迟时间就更加明显。
在堆内存的随机访问得到一个非常有趣的结果。 这是我们实验中最坏的场景,在这些给定的系统硬件规格情况下,我们分别得到150ns,65ns,75ns的内存控制器(memory controller)和内存模块的延迟。 对Nehalem处理器(i7-860),我们可以用4GB的array去进一步测试缓存子系统,平均每次的结果大约55ns;
i7-2760QM具有更大的负载缓存(load buffer),TLB缓存(TLB caches),并且Linux运行在一个透明的大内存页环境下,大内存分页本身可以进一步降低延迟。通过改变代表访问步幅的素数值(译者注:程序中的 PRIME_INC),发现不同的处理器类型得到的结果差异更大。例如:Nehalem CPU 并且PRIME_INC = 39916801 。 我们在这样一个拥有更大的堆的Sandy Bridge(译者注:Sandy Bridge为Intel推出处理器,该处理器采用32nm制程。Sandy Bridge(之前称作Gesher)是Nehalem的继任者)场景下来测试;
最主要是更大程度上消除了内存访问的可预测性的影响;和在降低主内存延迟上更好的缓存子系统。 让我们来看看在这些缓存子系统中的一些小细节,来理解所观察到的结果。
在考虑降低延迟的时候,我们使用多层的缓存加上预加载(pre-fetchers); 在本节中,我会尽量覆盖为了降低延迟,我们已经在使用的主要组件,包括硬件和系统软件;我们将使用perf(译者注:Perf Event 是一款随Linux 内核代码一同发布和维护的性能诊断工具)和Lightweight Performance Counters工具来研究这些延迟降低组件,这些工具可以在我们执行代码的时候,获取CPU的性能计数器(Performance counters ),来告诉我们这些组件有效性。我这里使用的是特定于Sandy Bridge性能计数器(Performance counters)
处理器通常有2层或3层的数据缓存。 每一层容量逐渐变大,延迟也逐渐增加。 最新的intel 3.0GHz的CPU处理器是3层结构(L1D,L2,L3),大小分别是32KB,256KB和4-30MB,延迟分别约为1ns,4ns,15ns。
数据缓存是高效的具有固定数量插槽(sorts)硬件哈希表。每个插槽(sort)对应一个哈希值。 这些插槽通常称为“通道、路(ways)”。一个8路组相联(译者注:CPU缓存) 的缓存有8个插槽,来保存哈希值在同一个缓存位置的地址。 数据缓存中的这些插槽(sort)里并不存储的字(word),它们存储多个字( multiple words)的缓存行(cache-lines )。 在intel处理器中缓存行(cache-lines )通常是64字节(64-bytes),对应到64位的机器上8个字(word)。 这极好的满足相邻的内存空间最可能立马需要访问的空间规律,最典型的场景是数组或者对象的字段;
数据缓存通常是LRU的方式失效。 缓存通过一个回写算法工作,只有当被修改的缓存行失效的时候,修改的值才会回写到主内存中。 这样会产生一个有趣的现象,一个load操作可能会引发一个回写操作,将修改的值写回主内存;
01perf stat -e L1-dcache-loads,L1-dcache-load-misses java -Xmx4g TestMemoryAccessPatterns $ 02 03 Performance counter stats for 'java -Xmx4g TestMemoryAccessPatterns 1': 04 1,496,626,053 L1-dcache-loads 05 274,255,164 L1-dcache-misses 06 # 18.32% of all L1-dcache hits 07 08 Performance counter stats for 'java -Xmx4g TestMemoryAccessPatterns 2': 09 1,537,057,965 L1-dcache-loads 10 1,570,105,933 L1-dcache-misses 11 # 102.15% of all L1-dcache hits 12 13 Performance counter stats for 'java -Xmx4g TestMemoryAccessPatterns 3': 14 4,321,888,497 L1-dcache-loads 15 1,780,223,433 L1-dcache-misses 16 # 41.19% of all L1-dcache hits 17 18 likwid-perfctr -C 2 -g L2CACHE java -Xmx4g TestMemoryAccessPatterns $ 19 20 java -Xmx4g TestMemoryAccessPatterns 1 21+-----------------------+-------------+ 22 | Event | core 2 | 23+-----------------------+-------------+ 24 | INSTR_RETIRED_ANY | 5.94918e+09 | 25 | CPU_CLK_UNHALTED_CORE | 5.15969e+09 | 26 | L2_TRANS_ALL_REQUESTS | 1.07252e+09 | 27 | L2_RQSTS_MISS | 3.25413e+08 | 28+-----------------------+-------------+ 29+-----------------+-----------+ 30 | Metric | core 2 | 31+-----------------+-----------+ 32 | Runtime [s] | 2.15481 | 33 | CPI | 0.867293 | 34 | L2 request rate | 0.18028 | 35 | L2 miss rate | 0.0546988 | 36 | L2 miss ratio | 0.303409 | 37+-----------------+-----------+ 38+------------------------+-------------+ 39 | Event | core 2 | 40+------------------------+-------------+ 41 | L3_LAT_CACHE_REFERENCE | 1.26545e+08 | 42 | L3_LAT_CACHE_MISS | 2.59059e+07 | 43+------------------------+-------------+ 44 45 java -Xmx4g TestMemoryAccessPatterns 2 46+-----------------------+-------------+ 47 | Event | core 2 | 48+-----------------------+-------------+ 49 | INSTR_RETIRED_ANY | 1.48772e+10 | 50 | CPU_CLK_UNHALTED_CORE | 1.64712e+10 | 51 | L2_TRANS_ALL_REQUESTS | 3.41061e+09 | 52 | L2_RQSTS_MISS | 1.5547e+09 | 53+-----------------------+-------------+ 54+-----------------+----------+ 55 | Metric | core 2 | 56+-----------------+----------+ 57 | Runtime [s] | 6.87876 | 58 | CPI | 1.10714 | 59 | L2 request rate | 0.22925 | 60 | L2 miss rate | 0.104502 | 61 | L2 miss ratio | 0.455843 | 62+-----------------+----------+ 63+------------------------+-------------+ 64 | Event | core 2 | 65+------------------------+-------------+ 66 | L3_LAT_CACHE_REFERENCE | 1.52088e+09 | 67 | L3_LAT_CACHE_MISS | 1.72918e+08 | 68+------------------------+-------------+ 69 70 java -Xmx4g TestMemoryAccessPatterns 3 71+-----------------------+-------------+ 72 | Event | core 2 | 73+-----------------------+-------------+ 74 | INSTR_RETIRED_ANY | 6.49533e+09 | 75 | CPU_CLK_UNHALTED_CORE | 4.18416e+10 | 76 | L2_TRANS_ALL_REQUESTS | 4.67488e+09 | 77 | L2_RQSTS_MISS | 1.43442e+09 | 78+-----------------------+-------------+ 79+-----------------+----------+ 80 | Metric | core 2 | 81+-----------------+----------+ 82 | Runtime [s] | 17.474 | 83 | CPI | 6.4418 | 84 | L2 request rate | 0.71973 | 85 | L2 miss rate | 0.220838 | 86 | L2 miss ratio | 0.306835 | 87+-----------------+----------+ 88+------------------------+-------------+ 89 | Event | core 2 | 90+------------------------+-------------+ 91 | L3_LAT_CACHE_REFERENCE | 1.40079e+09 | 92 | L3_LAT_CACHE_MISS | 1.34832e+09 | 93+------------------------+-------------+注 :随着更随机的访问,结合L1D,L2和L3的缓存失效率也显著增加。
我们的程序通常使用需要被翻译成物理内存地址的虚拟内存地址。 虚拟内存系统通过映射页(mapping pages)实现这个功能。 对内存的操作我们需要知道给定页面的偏移量和页大小。页大小通常情况从4KB到2MB,以至更大。 Linux的介绍Transparent Huge Pages表明在2.6.38内核中使用2 MB的页大小。虚拟内存页到物理页的转换关系维护在页表(page table) 中 。 这种转换可能需要多次访问的页表,这是一个巨大的性能损失。 为了加快查找,处理器有为每一级缓存都配备一个更小的硬件缓存,称为TLB缓存。 TLB缓存失效的代价是非常巨大的,因为页表(page table)可能不在附近的数据缓存中。 通过使用更大的页,TLB缓存可以覆盖更大的地址范围。
01perf stat -e dTLB-loads,dTLB-load-misses java -Xmx4g TestMemoryAccessPatterns $ 02 Performance counter stats for 'java -Xmx4g TestMemoryAccessPatterns 1': 03 1,496,128,634 dTLB-loads 04 310,901 dTLB-misses 05 # 0.02% of all dTLB cache hits 06 Performance counter stats for 'java -Xmx4g TestMemoryAccessPatterns 2': 07 1,551,585,263 dTLB-loads 08 340,230 dTLB-misses 09 # 0.02% of all dTLB cache hits 10 Performance counter stats for 'java -Xmx4g TestMemoryAccessPatterns 3': 11 4,031,344,537 dTLB-loads 12 1,345,807,418 dTLB-misses 13 # 33.38% of all dTLB cache hits注:当使用大页时,仅仅在随机访问整个堆的场景下,TLB缓存失效才非常明显;
硬件会去尝试预测程序中的下一次访问的内存,去选择并加载到缓存区。最简单的方式是根据空间局域性,预加载相邻近的缓存行,或者通过识别基于有规律步幅访问模式,通常步幅长度小于2KB。 在下面的测试中,我们将测量命中通过预加载加载到缓冲区数据的次数
01 likwid-perfctr -C 2 -g LOAD_HIT_PRE_HW_PF:PMC0 java -Xmx4g TestMemoryAccessPatterns $ 02 java -Xmx4g TestMemoryAccessPatterns 1 03+--------------------+-------------+ 04 | Event | core 2 | 05+--------------------+------------- 06 | LOAD_HIT_PRE_HW_PF | 1.31613e+09 | 07+--------------------+-------------+ 08 java -Xmx4g TestMemoryAccessPatterns 2 09+--------------------+--------+ 10 | Event | core 2 | 11+--------------------+--------+ 12 | LOAD_HIT_PRE_HW_PF | 368930 | 13+--------------------+--------+ 14 java -Xmx4g TestMemoryAccessPatterns 3 15+--------------------+--------+ 16 | Event | core 2 | 17+--------------------+--------+ 18 | LOAD_HIT_PRE_HW_PF | 324373 | 19+--------------------+--------+注 :在线性访问的时候我们预加载的命中率是非常明显的。
只有最后一级缓存(LLC)位于内存控制器内,内存控制器管理访问SDRAM BANKS。 内存由行和列组成。 访问的一个地址的时候,首先行地址被选中(RAS),然后该行的列地址被选中(CAS),最后获取这个字(word)。行通常就是一个页的大小,并加载到 一个行缓冲区(row buffer)。 即使在这个阶段,通过硬件仍能减少延迟。 访问内存的请求维护在一个队列中,并进行重排,尽可能一次从相同行中取出多个字(words)
现在系统在CPU插槽上有内存控制器。 插槽上的内存控制器大约有50ns的延迟,对现有的前端总线(FSB)和外部北桥(Northbridge)的内存控制器延迟已经减少了。多插槽的系统需要使用内存互连接口,intel使用QPI ,当一个CPU要访问另一个CPU插槽管理的内存时候讲使用到它。 这些互连的存在引起了非统一内存访问服务。 在2插槽系统中内存访问可能是在本地或1跳之遥(1hop away)。 在8插槽系统中内存访问可高达三跳,每一跳单向就会增加20ns的延迟。
L1D缓存命中和完全失效从主内存中访问结果之间的差异是2个数量级,即<1ns和65-100ns。 如果我们的算法在不断增加的地址空间中随机访问,那么我们就不能从硬件支持的降低延迟中受益。 在设计算法和数据结构的我们能做什么呢?事实上有很多事情我们可以做的。 如果我们执行单元的数据块是相邻的,紧密的。并且我们以可预见的方式访问内存。我们的算法会快很多倍。 例如,相比使用桶(bucket)和chain 模式的哈希表(译者注:hash tables) ,比如在JDK中默认,我们可以使用使用linear-probing策略的open-addressing模式的哈希表。 在使用 linked-lists 和 trees时相比每个node只包含单个项,更应该每个node包含一个数组或者多个项; 研究算法以达到与缓存子系统的协调。我发现一个迷人的领域是Cache Oblivious Algorithms虽然名字有点误导,但有这里有一些很棒的概念,关于如何提高软件的性能和并行执行能力。 这篇文章,很好的说明了可以获得的性能好处。
为了实现高性能,与缓存子系统达到一种协调是很重要的。 在这篇文章中我们看到,可以通过和内存访问模型协调的方式,而不是破坏的方式来实现,在设计算法和数据结构,考虑缓存失效是非常重要的,可能甚至比算法的 执行指令数更重要。 这些不是我们在学生时代学习计算机科学的算法理论中能学到的。 在过去十年里,技术发生了一些根本性的变化。 对我来说,最重要的是多核心的崛起,和64位地址空间的大内存系统的发展。 有一件事是肯定的,如果我们想软件执行的更快,伸缩性更好,我们必须更好地利用CPU的多核,和注重内存访问模型。
试图设计一个对所有处理器和内存的大小都随机访问算法是棘手的。 比如我下面的使用算法,在我的Sandy Bridge处理器速度较慢,但Nehalem的速度更快。 最关键的问题是当你以随机方式访问内存,性能将是非常难以预测的。 在所有的测试中,我也对包含L3缓存做了更加详尽的测试
1 private static final long LARGE_PRIME_INC = 70368760954879L; 2 RANDOM_HEAP_WALK 3 { 4 public int next(final int pageOffset, final int wordOffset, final int pos) 5 { 6 return (int)(pos + LARGE_PRIME_INC) & ARRAY_MASK; 7 } 8 };01 Intel i7-2760QM @ 2.40GHz, 8GB RAM DDR3 1600MHz, 02 Linux 3.4.6 kernel 64-bit, Java 1.7.0_05 03================================================= 04 0 - 29.06ns RANDOM_HEAP_WALK 05 1 - 29.47ns RANDOM_HEAP_WALK 06 2 - 29.48ns RANDOM_HEAP_WALK 07 3 - 29.43ns RANDOM_HEAP_WALK 08 4 - 29.42ns RANDOM_HEAP_WALK 09 10 Performance counter stats for 'java -Xmx4g TestMemoryAccessPatterns 3': 11 9,444,928,682 dTLB-loads 12 4,371,982,327 dTLB-misses 13 # 46.29% of all dTLB cache hits 14 15 9,390,675,639 L1-dcache-loads 16 1,471,647,016 L1-dcache-misses 17 # 15.67% of all L1-dcache hits 18 19+-----------------------+-------------+ 20 | Event | core 2 | 21+-----------------------+-------------+ 22 | INSTR_RETIRED_ANY | 7.71171e+09 | 23 | CPU_CLK_UNHALTED_CORE | 1.31717e+11 | 24 | L2_TRANS_ALL_REQUESTS | 8.4912e+09 | 25 | L2_RQSTS_MISS | 2.79635e+09 | 26+-----------------------+-------------+ 27+-----------------+----------+ 28 | Metric | core 2 | 29+-----------------+----------+ 30 | Runtime [s] | 55.0094 | 31 | CPI | 17.0801 | 32 | L2 request rate | 1.10108 | 33 | L2 miss rate | 0.362611 | 34 | L2 miss ratio | 0.329324 | 35+-----------------+----------+ 36+--------------------+-------------+ 37 | Event | core 2 | 38+--------------------+-------------+ 39 | LOAD_HIT_PRE_HW_PF | 3.59509e+06 | 40+--------------------+-------------+ 41+------------------------+-------------+ 42 | Event | core 2 | 43+------------------------+-------------+ 44 | L3_LAT_CACHE_REFERENCE | 1.30318e+09 | 45 | L3_LAT_CACHE_MISS | 2.62346e+07 | 46+------------------------+-------------+
原文地址 墙内地址
文章转自 并发编程网-ifeve.com
相关资源:敏捷开发V1.0.pptx