251      魔獸

內存訪問模型的重要性

在高性能的計算中，我們常說緩存失效（cache-miss）是一個算法中最大性能損失點。 近些年來，我們的處理器處理能力的增長速度已經大大超 過了訪問主內存的延遲的縮短。 通過更寬的，多通道的總線，到主內存的帶寬已經大大增加，但延遲並沒有相應顯著減少。 為了減少延遲，處理器采用愈加複雜 的多層的高速緩存子係統。
在1994年的一篇論文“Hitting the memory wall: implications of the obvious”中描述了這個問題，並且認為由於緩存失效（cache-miss）必定存在，緩存不能最終解決這個問題。我的目標是：向大家展示通過利用訪問模型，它是對緩存層次結構的思考，上麵的結論並不是必然的。
讓我們帶著問題，來看下麵的例子， 我們的硬件試圖通過一些技術來減少主內存的延遲。 內存訪問模型主要基於下麵三個規律：
1、時間局部性 ：最近訪問過的內存最可能立馬再次被訪問；
2、空間局部性：相鄰的內存最可能立馬再次被訪問；
3、 跨越式：內存訪問可能會遵循一種可預測的模式。

首先讓我們通過一些代碼和測試結果，來說明這三個規律的正確性：
1、線性訪問情形的內存訪問是完全可以預測的；
2、在一個限定的內存區域內做偽隨機訪問，然後跳到下一個限定內存區域，如此重複。這個“限定內存區域”就是大家所熟知的內存頁;。
3、在一個大麵積堆內存中偽隨機訪問。

下麵的代碼需要添加 -Xmx4g JVM選項運行：

 結果：

分析：

這段代碼我分別在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操作可能會引發一個回寫操作，將修改的值寫回主內存；

注 ：隨著更隨機的訪問，結合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緩存可以覆蓋更大的地址範圍。

注：當使用大頁時，僅僅在隨機訪問整個堆的場景下，TLB緩存失效才非常明顯；

 硬件預加載（Pre-Fetchers）：

硬件會去嚐試預測程序中的下一次訪問的內存，去選擇並加載到緩存區。最簡單的方式是根據空間局域性，預加載相鄰近的緩存行，或者通過識別基於有規律步幅訪問模式，通常步幅長度小於2KB。 在下麵的測試中，我們將測量命中通過預加載加載到緩衝區數據的次數

注 ：在線性訪問的時候我們預加載的命中率是非常明顯的。

 內存控製器和行緩衝區：

隻有最後一級緩存（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緩存做了更加詳盡的測試