內存訪問模式很重要

在高性能計算中，通常會說高速緩存未命中的代價是算法的最大性能損失。多年來，處理器速度的提高大大超過了延遲到主內存的速度。通過更寬的多通道總線，到主內存的帶寬已大大增加，但是延遲并未顯著減少。為了掩蓋這種延遲，我們的處理器采用了具有許多層的，越來越復雜的緩存子系統。

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_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_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_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_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_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_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。

對于線性遍歷情況，似乎不存在內存延遲。但是，當我們以越來越多的隨機模式在內存中四處走動時，等待時間開始變得非常明顯。

隨機堆遍歷產生了有趣的結果。這是我們最壞的情況，考慮到這些系統的硬件規格，我們可能會根據內存控制器和內存模塊的等待時間分別為上述測試選擇150ns，65ns和75ns。對于Nehalem（i7-860），我可以使用4GB陣列進一步破壞高速緩存子系統，從而使每次迭代平均約55ns。 i7-2760QM具有更大的負載緩沖區，TLB緩存，并且Linux運行著透明的大頁面，所有這些頁面都在進一步隱藏延遲。通過跨步使用不同的質數，結果會因處理器類型而異，例如對于Nehalem嘗試PRIME_INC = 39916801。我想用Sandy Bridge在更大的堆上進行測試。

主要優勢是對存儲器的訪問模式越可預測，那么緩存子系統隱藏主存儲器延遲的性能就越好。讓我們更詳細地看一下這些緩存子系統，以嘗試了解所觀察到的結果。

硬件組件

我們有很多層緩存以及預取器，以考慮如何隱藏延遲。在本節中，我將嘗試介紹用于隱藏我們的硬件和系統軟件朋友所采用的延遲的主要組件。我們將調查這些延遲隱藏的組件和使用Linux PERF和谷歌輕量級性能計數器的實用程序從我們的CPU，告訴我們執行我們的計劃，這些組件是如何有效的檢索性能計數器。性能計數器是特定于CPU的，我在這里使用的是Sandy Bridge的特定。

資料快取

處理器通常具有2或3層數據緩存。隨著遷移的增加，每一層都隨著延遲的增加而逐漸變大。最新的Intel處理器具有3層（L1D，L2和L3）。大小分別為32KB，256KB和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.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  |
+-----------------+-----------+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 |
+-----------------+----------+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 |
+-----------------+----------+

注意：隨著訪問模式變得更加隨機，組合的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.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庫的訪問。內存分為行和列。要訪問地址，首先必須選擇行地址（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提供了內存訪問模式很重要。