Mechanical Sympathy 系列翻译 内存访问模型

重要的内存访问模型

在高性能的计算中，我们常说缓存失效（cache-miss）是一个算法中最大性能损失点。 近些年来，我们的处理器处理能力的增长速度已经大大超过了访问主内存的延迟的增长。 通过更宽的，多通道的总线，到主内存的带宽已经大大增加，但延迟并没有相应显著减少。 为了减少延迟，处理器采用愈加复杂的多层的高速缓存子系统。 

在1994年的一篇论文“Hitting the memory wall: implications of the obvious”中描述了这个问题，并且认为由于缓存失效（cache-miss）必定存在，缓存不能最终解决这个问题。我的目标是：向大家展示通过利用访问模型，它是对缓存层次结构的思考，上面的结论并不是必然的。

让我们带着问题，来看下面的例子， 我们的硬件试图通过一些技术来减少主内存的延迟。 内存访问模型主要基于下面三个规律：

1、时间局部性 ：最近访问过的内存最可能立马再次被访问；

2、空间局部性：相邻的内存最可能立马再次被访问；

3、 跨越式：内存访问可能会遵循一种可预测的模式。

首先让我们通过一些代码和测试结果，来说明这三个规律的正确性：

1、线性访问情形的内存访问是完全可以预测的；

2、在一个限定内存区内伪随机的访问然后跨越到另一个。 这个限定区最广为人知的就是操作系统内存页。

3、在一个大面积堆内存中伪随机访问。

下面的代码需要添加 -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 {

            @Override
            public int next(final int pageOffset, final int wordOffset, final int pos) {
                return (pos + 1) & ARRAY_MASK;
            }
        },

        RANDOM_PAGE_WALK {

            @Override
            public int next(final int pageOffset, final int wordOffset, final int pos) {
                return pageOffset + ((pos + PRIME_INC) & PAGE_MASK);
            }
        },

        RANDOM_HEAP_WALK {

            @Override
            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_05
===========================================
0 - 2.38ns LINEAR_WALK
1 - 2.41ns LINEAR_WALK
2 - 2.35ns LINEAR_WALK
3 - 2.36ns LINEAR_WALK
4 - 2.39ns LINEAR_WALK

0 - 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_WALK

0 - 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_WALK

Intel i7-860 @ 2.8GHz, 8GB RAM DDR3 1333MHz, 
Windows 7 64-bit, Java 1.7.0_05
=============================================
0 - 1.06ns LINEAR_WALK
1 - 1.05ns LINEAR_WALK
2 - 0.98ns LINEAR_WALK
3 - 1.00ns LINEAR_WALK
4 - 1.00ns LINEAR_WALK

0 - 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_WALK

0 - 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_WALK

Intel i7-2760QM @ 2.40GHz, 8GB RAM DDR3 1600MHz, 
Linux 3.4.6 kernel 64-bit, Java 1.7.0_05
=================================================
0 - 0.91ns LINEAR_WALK
1 - 0.92ns LINEAR_WALK
2 - 0.88ns LINEAR_WALK
3 - 0.89ns LINEAR_WALK
4 - 0.89ns LINEAR_WALK

0 - 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_WALK

0 - 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架构中运行，如上面所显示的是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操作可能会引发一个回写操作，将修改的值写回主内存；

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 hits

 Performance 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.94918e+09 |
| CPU_CLK_UNHALTED_CORE | 5.15969e+09 |
| L2_TRANS_ALL_REQUESTS | 1.07252e+09 |
|     L2_RQSTS_MISS     | 3.25413e+08 |
+-----------------------+-------------+
+-----------------+-----------+
|     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  |
+-----------------+-----------+
+------------------------+-------------+
|         Event          |   core 2    |
+------------------------+-------------+
| L3_LAT_CACHE_REFERENCE | 1.26545e+08 |
|   L3_LAT_CACHE_MISS    | 2.59059e+07 |
+------------------------+-------------+

java -Xmx4g TestMemoryAccessPatterns 2
+-----------------------+-------------+
|         Event         |   core 2    |
+-----------------------+-------------+
|   INSTR_RETIRED_ANY   | 1.48772e+10 |
| CPU_CLK_UNHALTED_CORE | 1.64712e+10 |
| L2_TRANS_ALL_REQUESTS | 3.41061e+09 |
|     L2_RQSTS_MISS     | 1.5547e+09  |
+-----------------------+-------------+
+-----------------+----------+
|     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 |
+-----------------+----------+
+------------------------+-------------+
|         Event          |   core 2    |
+------------------------+-------------+
| L3_LAT_CACHE_REFERENCE | 1.52088e+09 |
|   L3_LAT_CACHE_MISS    | 1.72918e+08 |
+------------------------+-------------+

java -Xmx4g TestMemoryAccessPatterns 3
+-----------------------+-------------+
|         Event         |   core 2    |
+-----------------------+-------------+
|   INSTR_RETIRED_ANY   | 6.49533e+09 |
| CPU_CLK_UNHALTED_CORE | 4.18416e+10 |
| L2_TRANS_ALL_REQUESTS | 4.67488e+09 |
|     L2_RQSTS_MISS     | 1.43442e+09 |
+-----------------------+-------------+
+-----------------+----------+
|     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 |
+-----------------+----------+
+------------------------+-------------+
|         Event          |   core 2    |
+------------------------+-------------+
| L3_LAT_CACHE_REFERENCE | 1.40079e+09 |
|   L3_LAT_CACHE_MISS    | 1.34832e+09 |
+------------------------+-------------+

   注 ：随着更随机的访问，结合L1D，L2和L3的缓存失效率也显著增加。

 转换后援存储器(TLB)（译者注：TLB）

 我们的程序通常使用需要被翻译成物理内存地址的虚拟内存地址。 虚拟内存系统通过映射页（mapping pages）实现这个功能。 对内存的操作我们需要知道给定页面的偏移量和页大小。页大小通常情况从4KB到2MB，以至更大。 Linux的介绍Transparent Huge Pages表明在2.6.38内核中使用2 MB的页大小。虚拟内存页到物理页的转换关系维护在页表（page table）中 。 这种转换可能需要多次访问的页表，这是一个巨大的性能损失。 为了加快查找，处理器有为​每一级缓存都配备一个更小的硬件缓存，称为TLB缓存。 TLB缓存失效的代价是非常巨大的，因为页表（page table）可能不在附近的数据缓存中。 通过使用更大的页，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-loads
           310,901 dTLB-misses
              #    0.02% of all dTLB cache hits 

 Performance counter stats for 'java -Xmx4g TestMemoryAccessPatterns 2':
     1,551,585,263 dTLB-loads
           340,230 dTLB-misses
              #    0.02% of all dTLB cache hits

 Performance counter stats for 'java -Xmx4g TestMemoryAccessPatterns 3':
     4,031,344,537 dTLB-loads
     1,345,807,418 dTLB-misses
              #   33.38% of all dTLB cache hits  

 注：当使用大页时，仅仅在随机访问整个堆的场景下，TLB缓存失效才非常明显；

 硬件预加载（Pre-Fetchers）：

 硬件会去尝试预测程序中的下一次访问的内存，去选择并加载到缓存区。最简单的方式是根据空间局域性，预加载相邻近的缓存行，或者通过识别基于有规律步幅访问模式，通常步幅长度小于2KB。 在下面的测试中，我们将测量命中通过预加载加载到缓冲区数据的次数

 

likwid-perfctr -C 2 -g LOAD_HIT_PRE_HW_PF:PMC0 java -Xmx4g TestMemoryAccessPatterns $

java -Xmx4g TestMemoryAccessPatterns 1
+--------------------+-------------+
|       Event        |   core 2    |
+--------------------+-------------+
| LOAD_HIT_PRE_HW_PF | 1.31613e+09 |
+--------------------+-------------+

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 BANKS。 内存由行和列组成。 访问的一个地址的时候，首先行地址被选中（RAS），然后该行的列地址被选中（CAS），最后获取这个字（word）。行通常就是一个页的大小，并加载到一个行缓冲区（row buffer）。 即使在这个阶段，通过硬件仍能减少延迟。 访问内存的请求维护在一个队列中，并进行重排，尽可能一次从相同行中取出多个字（words）

 非统一内存访问（NUMA） ：

 现在系统在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的多核，和注重内存访问模型。

更新：2012年8月06日 

试图设计一个对所有处理器和内存的大小都随机访问算法是棘手的。 比如我下面的使用算法，在我的Sandy Bridge处理器速度较慢，但​​Nehalem的速度更快。 最关键的问题是当你以随机方式访问内存，性能将是非常难以预测的。 在所有的测试中，我也对包含L3缓存做了更加详尽的测试

  

private static final long LARGE_PRIME_INC = 70368760954879L;
    RANDOM_HEAP_WALK
    {
        public int next(final int pageOffset, final int wordOffset, final int pos)
        {
            return (int)(pos + LARGE_PRIME_INC) & ARRAY_MASK;
        }
    };

 

Intel i7-2760QM @ 2.40GHz, 8GB RAM DDR3 1600MHz, 
Linux 3.4.6 kernel 64-bit, Java 1.7.0_05
=================================================
0 - 29.06ns RANDOM_HEAP_WALK
1 - 29.47ns RANDOM_HEAP_WALK
2 - 29.48ns RANDOM_HEAP_WALK
3 - 29.43ns RANDOM_HEAP_WALK
4 - 29.42ns RANDOM_HEAP_WALK

 Performance counter stats for 'java -Xmx4g TestMemoryAccessPatterns 3':
     9,444,928,682 dTLB-loads
     4,371,982,327 dTLB-misses
         #   46.29% of all dTLB cache hits 

     9,390,675,639 L1-dcache-loads
     1,471,647,016 L1-dcache-misses
         #   15.67% of all L1-dcache hits  

+-----------------------+-------------+
|         Event         |   core 2    |
+-----------------------+-------------+
|   INSTR_RETIRED_ANY   | 7.71171e+09 |
| CPU_CLK_UNHALTED_CORE | 1.31717e+11 |
| L2_TRANS_ALL_REQUESTS | 8.4912e+09  |
|     L2_RQSTS_MISS     | 2.79635e+09 |
+-----------------------+-------------+
+-----------------+----------+
|     Metric      |  core 2  |
+-----------------+----------+
|   Runtime [s]   | 55.0094  |
|       CPI       | 17.0801  |
| L2 request rate | 1.10108  |
|  L2 miss rate   | 0.362611 |
|  L2 miss ratio  | 0.329324 |
+-----------------+----------+
+--------------------+-------------+
|       Event        |   core 2    |
+--------------------+-------------+
| LOAD_HIT_PRE_HW_PF | 3.59509e+06 |
+--------------------+-------------+
+------------------------+-------------+
|        Event           |   core 2    |
+------------------------+-------------+
| L3_LAT_CACHE_REFERENCE | 1.30318e+09 |
| L3_LAT_CACHE_MISS      | 2.62346e+07 |
+------------------------+-------------+

 全文完。。

原文地址：http://mechanical-sympathy.blogspot.com/2012/08/memory-access-patterns-are-important.html

墙内地址：http://ifeve.com/memory-access-patterns-are-important/