网站架构设计师就业指导,软件开发与网站开发的区别,精品课程网站怎么做,wordpress防采集源码在高性能计算中#xff0c;通常会说高速缓存未命中的代价是算法的最大性能损失。 多年来#xff0c;处理器速度的提高大大超过了延迟到主内存的速度。 通过更宽的多通道总线#xff0c;到主内存的带宽已大大增加#xff0c;但是延迟并未显着减少。 为了掩盖这种延迟#x… 在高性能计算中通常会说高速缓存未命中的代价是算法的最大性能损失。 多年来处理器速度的提高大大超过了延迟到主内存的速度。 通过更宽的多通道总线到主内存的带宽已大大增加但是延迟并未显着减少。 为了掩盖这种延迟我们的处理器采用了具有许多层的越来越复杂的缓存子系统。 1994年的论文“触及内存壁显而易见的含义”描述了这个问题并继续指出由于强制性丢失缓存缓存最终并没有帮助。 我的目的是表明通过使用显示缓存层次结构注意事项的访问模式这个结论是不可避免的。 让我们从一些示例开始将问题放在上下文中。 我们的硬件尝试通过多种技术来隐藏主内存延迟。 基本上对内存访问模式有三大押注 时间的最近可能需要再次访问最近访问的内存。 空间可能很快就会需要相邻的内存。 大步走内存访问可能遵循可预测的模式。 为了说明这三个赌注让我们编写一些代码并衡量结果。 以线性方式遍历内存是完全可预测的。 伪随机在限制区域内四处走走然后继续前进。 这个限制区域就是通常所说的内存的操作系统页面 。 伪随机地在大堆区域中走动。 码 以下代码应与-Xmx4g JVM选项一起运行。 public class TestMemoryAccessPatterns
{private static final int LONG_SIZE 8;private static final int PAGE_SIZE 2 * 1024 * 1024;private static final int ONE_GIG 1024 * 1024 * 1024;private static final long TWO_GIG 2L * ONE_GIG;private static final int ARRAY_SIZE (int)(TWO_GIG / LONG_SIZE);private static final int WORDS_PER_PAGE PAGE_SIZE / LONG_SIZE;private static final int ARRAY_MASK ARRAY_SIZE - 1;private static final int PAGE_MASK WORDS_PER_PAGE - 1;private static final int PRIME_INC 514229;private static final long[] memory new long[ARRAY_SIZE];static{for (int i 0; i ARRAY_SIZE; i){memory[i] 777;}}public enum StrideType{LINEAR_WALK{public int next(final int pageOffset, final int wordOffset, final int pos){return (pos 1) ARRAY_MASK;}},RANDOM_PAGE_WALK{public int next(final int pageOffset, final int wordOffset, final int pos){return pageOffset ((pos PRIME_INC) PAGE_MASK);}},RANDOM_HEAP_WALK{public int next(final int pageOffset, final int wordOffset, final int pos){return (pos PRIME_INC) ARRAY_MASK;}};public abstract int next(int pageOffset, int wordOffset, int pos);}public static void main(final String[] args){final StrideType strideType;switch (Integer.parseInt(args[0])){case 1:strideType StrideType.LINEAR_WALK;break;case 2:strideType StrideType.RANDOM_PAGE_WALK;break;case 3:strideType StrideType.RANDOM_HEAP_WALK;break;default:throw new IllegalArgumentException(Unknown StrideType);}for (int i 0; i 5; i){perfTest(i, strideType);}}private static void perfTest(final int runNumber, final StrideType strideType){final long start System.nanoTime();int pos -1;long result 0;for (int pageOffset 0; pageOffset ARRAY_SIZE; pageOffset WORDS_PER_PAGE){for (int wordOffset pageOffset, limit pageOffset WORDS_PER_PAGE;wordOffset limit;wordOffset){pos strideType.next(pageOffset, wordOffset, pos);result memory[pos];}}final long duration System.nanoTime() - start;final double nsOp duration / (double)ARRAY_SIZE;if (208574349312L ! result){throw new IllegalStateException();}System.out.format(%d - %.2fns %s\n,Integer.valueOf(runNumber),Double.valueOf(nsOp),strideType);}
} 结果 Intel U4100 1.3GHz, 4GB RAM DDR2 800MHz,
Windows 7 64-bit, Java 1.7.0_050 - 2.38ns LINEAR_WALK
1 - 2.41ns LINEAR_WALK
2 - 2.35ns LINEAR_WALK
3 - 2.36ns LINEAR_WALK
4 - 2.39ns LINEAR_WALK0 - 12.45ns RANDOM_PAGE_WALK
1 - 12.27ns RANDOM_PAGE_WALK
2 - 12.17ns RANDOM_PAGE_WALK
3 - 12.22ns RANDOM_PAGE_WALK
4 - 12.18ns RANDOM_PAGE_WALK0 - 152.86ns RANDOM_HEAP_WALK
1 - 151.80ns RANDOM_HEAP_WALK
2 - 151.72ns RANDOM_HEAP_WALK
3 - 151.91ns RANDOM_HEAP_WALK
4 - 151.36ns RANDOM_HEAP_WALKIntel i7-860 2.8GHz, 8GB RAM DDR3 1333MHz,
Windows 7 64-bit, Java 1.7.0_050 - 1.06ns LINEAR_WALK
1 - 1.05ns LINEAR_WALK
2 - 0.98ns LINEAR_WALK
3 - 1.00ns LINEAR_WALK
4 - 1.00ns LINEAR_WALK0 - 3.80ns RANDOM_PAGE_WALK
1 - 3.85ns RANDOM_PAGE_WALK
2 - 3.79ns RANDOM_PAGE_WALK
3 - 3.65ns RANDOM_PAGE_WALK
4 - 3.64ns RANDOM_PAGE_WALK0 - 30.04ns RANDOM_HEAP_WALK
1 - 29.05ns RANDOM_HEAP_WALK
2 - 29.14ns RANDOM_HEAP_WALK
3 - 28.88ns RANDOM_HEAP_WALK
4 - 29.57ns RANDOM_HEAP_WALKIntel i7-2760QM 2.40GHz, 8GB RAM DDR3 1600MHz,
Linux 3.4.6 kernel 64-bit, Java 1.7.0_050 - 0.91ns LINEAR_WALK
1 - 0.92ns LINEAR_WALK
2 - 0.88ns LINEAR_WALK
3 - 0.89ns LINEAR_WALK
4 - 0.89ns LINEAR_WALK0 - 3.29ns RANDOM_PAGE_WALK
1 - 3.35ns RANDOM_PAGE_WALK
2 - 3.33ns RANDOM_PAGE_WALK
3 - 3.31ns RANDOM_PAGE_WALK
4 - 3.30ns RANDOM_PAGE_WALK0 - 9.58ns RANDOM_HEAP_WALK
1 - 9.20ns RANDOM_HEAP_WALK
2 - 9.44ns RANDOM_HEAP_WALK
3 - 9.46ns RANDOM_HEAP_WALK
4 - 9.47ns RANDOM_HEAP_WALK 分析 我在3种不同的CPU架构上运行了该代码这些代码说明了英特尔在代代化方面的进步。 从结果可以明显看出基于上述针对相对较小堆的3个下注每一代在隐藏到主内存的延迟方面都变得越来越好。 这是因为各种缓存的大小和复杂性一直在提高。 但是随着内存大小的增加它们的作用减弱。 例如如果将阵列大小增加一倍以达到4GB则i7-860进行随机堆遍历的平均延迟从约30ns增加到约55ns。 对于线性遍历情况似乎不存在内存延迟。 但是当我们以越来越多的随机模式在内存中四处走动时等待时间开始变得非常明显。 随机堆遍历产生了有趣的结果。 这是我们最坏的情况考虑到这些系统的硬件规格我们可能会根据内存控制器和内存模块的等待时间分别为上述测试选择150ns65ns和75ns。 对于Nehalemi7-860我可以使用4GB阵列进一步破坏高速缓存子系统从而使每次迭代平均约55ns。 i7-2760QM具有更大的负载缓冲区TLB缓存并且Linux运行着透明的大页面所有这些页面都在进一步隐藏延迟。 通过跨步使用不同的质数结果会因处理器类型而异例如对于Nehalem尝试PRIME_INC 39916801。 我想用Sandy Bridge在更大的堆上进行测试。 主要优势是对存储器的访问模式越可预测那么缓存子系统隐藏主存储器延迟的性能就越好。 让我们更详细地看一下这些缓存子系统以尝试了解所观察到的结果。 硬件组件 我们有很多层缓存以及预取器以考虑如何隐藏延迟。 在本节中我将尝试介绍用于隐藏我们的硬件和系统软件朋友所采用的延迟的主要组件。 我们将调查这些延迟隐藏的组件和使用Linux PERF和谷歌轻量级性能计数器的实用程序从我们的CPU告诉我们执行我们的计划这些组件是如何有效的检索性能计数器。 性能计数器是特定于CPU的我在这里使用的是Sandy Bridge的特定。 资料快取 处理器通常具有2或3层数据缓存。 随着迁移的增加每一层都随着延迟的增加而逐渐变大。 最新的Intel处理器具有3层L1DL2和L3。 大小分别为32KB256KB和4-30MB 对于3.0GHz CPU延迟分别为〜1ns〜4ns和〜15ns。 数据缓存实际上是硬件哈希表每个哈希值具有固定数量的插槽。 这些插槽称为“方式”。 8路关联高速缓存将具有8个插槽以保存散列到相同高速缓存位置的地址的值。 在这些插槽中数据缓存不存储字而是存储多个字的缓存行。 对于Intel处理器这些高速缓存行通常为64字节即在64位计算机上为8个字。 这在空间上押注了可能很快需要相邻存储器的情况如果我们想到一个对象的数组或字段通常就是这种情况。 数据缓存通常以LRU方式逐出。 高速缓存通过使用回写算法来工作而存储仅在驱逐修改后的高速缓存行时才需要传播到主内存中。 这引起了有趣的现象即负载可能导致对外部高速缓存层以及最终对主存储器的写回。 perf stat -e L1-dcache-loads,L1-dcache-load-misses java -Xmx4g TestMemoryAccessPatterns $Performance counter stats for java -Xmx4g TestMemoryAccessPatterns 1:1,496,626,053 L1-dcache-loads 274,255,164 L1-dcache-misses# 18.32% of all L1-dcache hitsPerformance counter stats for java -Xmx4g TestMemoryAccessPatterns 2:1,537,057,965 L1-dcache-loads 1,570,105,933 L1-dcache-misses# 102.15% of all L1-dcache hits Performance counter stats for java -Xmx4g TestMemoryAccessPatterns 3:4,321,888,497 L1-dcache-loads 1,780,223,433 L1-dcache-misses# 41.19% of all L1-dcache hits likwid-perfctr -C 2 -g L2CACHE java -Xmx4g TestMemoryAccessPatterns $java -Xmx4g TestMemoryAccessPatterns 1
------------------------------------
| Event | core 2 |
------------------------------------
| INSTR_RETIRED_ANY | 5.94918e09 |
| CPU_CLK_UNHALTED_CORE | 5.15969e09 |
| L2_TRANS_ALL_REQUESTS | 1.07252e09 |
| L2_RQSTS_MISS | 3.25413e08 |
------------------------------------
----------------------------
| Metric | core 2 |
----------------------------
| Runtime [s] | 2.15481 |
| CPI | 0.867293 |
| L2 request rate | 0.18028 |
| L2 miss rate | 0.0546988 |
| L2 miss ratio | 0.303409 |
----------------------------java -Xmx4g TestMemoryAccessPatterns 2
------------------------------------
| Event | core 2 |
------------------------------------
| INSTR_RETIRED_ANY | 1.48772e10 |
| CPU_CLK_UNHALTED_CORE | 1.64712e10 |
| L2_TRANS_ALL_REQUESTS | 3.41061e09 |
| L2_RQSTS_MISS | 1.5547e09 |
------------------------------------
---------------------------
| Metric | core 2 |
---------------------------
| Runtime [s] | 6.87876 |
| CPI | 1.10714 |
| L2 request rate | 0.22925 |
| L2 miss rate | 0.104502 |
| L2 miss ratio | 0.455843 |
---------------------------java -Xmx4g TestMemoryAccessPatterns 3
------------------------------------
| Event | core 2 |
------------------------------------
| INSTR_RETIRED_ANY | 6.49533e09 |
| CPU_CLK_UNHALTED_CORE | 4.18416e10 |
| L2_TRANS_ALL_REQUESTS | 4.67488e09 |
| L2_RQSTS_MISS | 1.43442e09 |
------------------------------------
---------------------------
| Metric | core 2 |
---------------------------
| Runtime [s] | 17.474 |
| CPI | 6.4418 |
| L2 request rate | 0.71973 |
| L2 miss rate | 0.220838 |
| L2 miss ratio | 0.306835 |
--------------------------- 注意随着访问模式变得更加随机组合的L1D和L2的缓存丢失率显着增加。 翻译后备缓冲区TLB 我们的程序处理需要转换为物理内存地址的虚拟内存地址。 虚拟内存系统通过映射页面来做到这一点。 我们需要知道给定页面的偏移量以及任何内存操作的大小。 通常页面大小为4KB然后逐渐增加到2MB或更大。 Linux在2.6.38内核中引入了Transparent Huge Pages 为我们提供了2MB的页面。 虚拟内存页到物理页的转换由页表维护。 这种转换可能导致对页表的多次访问这是巨大的性能损失。 为了加快查找速度处理器在每个缓存级别都有一个称为TLB缓存的小型硬件缓存。 由于页表可能不在附近的数据高速缓存中因此未命中TLB高速缓存可能会造成巨大的代价。 通过移至更大的页面TLB高速缓存可以为相同数量的条目覆盖更大的地址范围。 perf stat -e dTLB-loads,dTLB-load-misses java -Xmx4g TestMemoryAccessPatterns $Performance counter stats for java -Xmx4g TestMemoryAccessPatterns 1:1,496,128,634 dTLB-loads310,901 dTLB-misses# 0.02% of all dTLB cache hits Performance counter stats for java -Xmx4g TestMemoryAccessPatterns 2:1,551,585,263 dTLB-loads340,230 dTLB-misses# 0.02% of all dTLB cache hitsPerformance counter stats for java -Xmx4g TestMemoryAccessPatterns 3:4,031,344,537 dTLB-loads1,345,807,418 dTLB-misses# 33.38% of all dTLB cache hits 注意当使用大页面时当随机遍历整个堆时我们只会招致重大的TLB丢失。 硬件预取器 硬件将尝试预测我们程序将进行的下一次内存访问并推测性地将该内存加载到填充缓冲区中。 通过为空间投注预先加载相邻的缓存行或通过识别基于规则的跨步访问模式通常跨步长度通常小于2KB可以在最简单的级别上完成此操作。 下面的测试正在测量从硬件预取中命中填充缓冲区的负载数量。 likwid-perfctr -C 2 -t intel -g LOAD_HIT_PRE_HW_PF:PMC0 java -Xmx4g TestMemoryAccessPatterns $java -Xmx4g TestMemoryAccessPatterns 1
---------------------------------
| Event | core 2 |
---------------------------------
| LOAD_HIT_PRE_HW_PF | 1.31613e09 |
---------------------------------java -Xmx4g TestMemoryAccessPatterns 2
----------------------------
| Event | core 2 |
----------------------------
| LOAD_HIT_PRE_HW_PF | 368930 |
----------------------------java -Xmx4g TestMemoryAccessPatterns 3
----------------------------
| Event | core 2 |
----------------------------
| LOAD_HIT_PRE_HW_PF | 324373 |
---------------------------- 注意在线性行走中通过预取器成功实现成功的负载命中率。 内存控制器和行缓冲区 除了上一级缓存LLC之外还有存储控制器用于管理对SDRAM库的访问。 内存分为行和列。 要访问地址首先必须选择行地址RAS然后在该行中选择列地址CAS以获取单词。 该行通常为页面大小并加载到行缓冲区中。 即使在此阶段硬件仍在帮助隐藏延迟。 内存访问请求队列被维护和重新排序以便在可能的情况下可以从同一行中提取多个字。 非统一内存访问NUMA 系统现在在CPU插槽上具有内存控制器。 与现有的前端总线FSB和外部北桥存储控制器相比这种向插座式存储控制器的转移使等待时间减少了约50ns。 具有多个插槽的系统使用内存互连即Intel的QPI 当一个CPU想要访问由另一个CPU插槽管理的内存时使用。 这些互连的存在引起服务器内存访问的不统一性质。 在2插槽系统中内存可能是本地内存也可能是1跳。 在8插槽系统上内存最多可以跳3个跳每个跳在每个方向上都会增加20ns的延迟。 这对算法意味着什么 L1D缓存命中与导致主内存访问的完全未命中之间的差为2个数量级 即1ns与65-100ns。 如果算法随机地绕过我们不断增加的地址空间那么我们不太可能受益于隐藏这种延迟的硬件支持。 在设计算法和数据结构时我们能做些什么 是的我们可以做很多事情。 如果我们对位于同一位置的数据执行大量工作并且以可预测的方式跨越内存那么我们的算法可能会快很多倍。 例如与其像JDK中那样使用存储桶和链式哈希表不如使用带有线性探测的开放地址的哈希表。 与其在每个节点中使用链表或带有单个项目的树不如在每个节点中存储许多项目的数组。 正在研究与高速缓存子系统协调工作的算法方法。 我发现令人着迷的一个方面是Cache Oblivious Algorithms 。 这个名称有点误导但是这里有一些很棒的概念可以用来提高软件性能和更好地并行执行。 本文很好地说明了可以获得的性能优势。 结论 为了获得出色的性能同情缓存子系统非常重要。 我们已经在本文中看到了通过以与这些缓存而不是针对这些缓存一起工作的模式访问内存可以实现的目标。 现在在设计算法和数据结构时考虑缓存丢失更为重要可能比计算算法中的步骤还要重要。 在学习计算机科学时这不是我们在算法理论中所学的。 在过去的十年中技术发生了一些根本性的变化。 对我来说最重要的两个是多核以及具有64位地址空间的大内存系统的兴起。 可以肯定的是如果我们希望软件能够更快地执行并更好地扩展我们需要更好地利用CPU中的许多内核并注意内存访问模式。 参考 “ 机械访问”博客上的JCG合作伙伴 Martin Thompson提供了内存访问模式很重要 。 翻译自: https://www.javacodegeeks.com/2012/08/memory-access-patterns-are-important.html
