存儲器山

存儲器山是一種綜合研究存儲器層次結構的工具。它反映了存儲器層次結構中不同層次的帶寬。也反映了具有不同的時間局部性與空間局部性的程序的性能。通過分析存儲器山的數據，還可以看出存儲器系統的部分硬體參數。

T. Stricker於1997年在其論文中介紹了存儲器山的思想，利用它對存儲器系統進行全面描述，並在後來的工作中提出了術語「存儲器山」。卡耐基梅隆大學教授Randal Bryant的著作《深入理解計算機系統》（頁面存檔備份，存於網際網路檔案館）（Computer Systems: A programmer's Perspective, Randal Bryant, David O'Hallaron）一書第6.6.1節亦提出了存儲器山的概念，並進行了詳細分析。

理論上，每台計算機都有一個唯一的存儲器山。通過運行一段測試程序，可以得到它的存儲器山。了解存儲器山，對應用程式的優化能起到指導作用。下圖展示了一個基於Intel Core 2 Duo 處理器的存儲器山。

基於Intel Core 2 Duo 處理器的存儲器山

存儲器山測試原理

為了說明存儲器山的測試程序的原理，首先簡要介紹局部性和存儲器層次結構這兩個重要概念，然後介紹存儲器山的定義和測試程序的原理模型。

局部性

通常，一個編寫良好的（優化的）程序具有良好的局部性，主要表現在兩個方面。

時間局部性（Temporal locality）：如果被訪問過的存儲器地址在較短時間內被再次訪問，則程序具有良好的時間局部性。在一定的時間內，重複訪問同一個地址的次數越多，時間局部性越好。換句話說，對同一個地址的兩次訪問間隔時間越短，時間局部性越好。

空間局部性（Spatial locality）：如果程序訪問某個存儲器地址後，又在較短時間內訪問臨近的存儲器地址，則程序具有良好的空間局部性。兩次訪問的地址越接近，空間局部性越好。

局部性在程序中普遍存在。好的程序通常具有好的局部性，是一個普適的原理。

存儲器層次結構

不同類型的存儲設備，其訪問速率相差很大。其基本規律為：訪問速率越高的設備，單位容量的成本越高，於是越不容易做得很大。計算機系統的設計者需要在控制成本的同時，儘量提高存儲器系統的速率。

受益於局部性的概念，計算機的存儲器系統通常設計成一個層次結構，CPU內部的暫存器為該層次結構的最高層----它的容量最小，但速率最高。往下依次為各級cache，主存，磁碟等等。該層次結構的運行策略是：儘量讓當前被頻繁訪問的存儲區的內容駐留在較高層存儲器，作為代價，把不常訪問的存儲區的內容置換到較低層存儲器。同時，儘量讓當前被訪問的元素附近的元素也駐留在較高層存儲器。一個具有良好的局部性的程序，幾乎能總是訪問高層的存儲器，享受到最高的訪問速率。

從程式設計師的角度來看，要儘量編寫具有良好的局部性的程序，以適應層次結構，提高程序運行速率。

存儲器山測試程序

具有不同的時間局部性和空間局部性的程序，對存儲器層次結構的利用效率是不同的。局部性較好，則能得到較快的訪問速率。構造一個存儲器測試程序，以不同的時間局部性和空間局部性對存儲器進行訪問，就能得到存儲器系統在不同的局部性下的性能（即訪問速率）。以控制時間局部性的變量為x軸，控制空間局部性的變量為y軸，存儲器訪問速率為z軸，就能得到一個三維圖形，它看起來像一座有著山峰，山脊和山坡的小山，即存儲器山。

通過存儲器山，可以直觀地看到具有不同的時間局部性和空間局部性的程序對存儲器的訪問速率的巨大差別。可作為程式設計師優化程序的參考。

更加有趣的是，通過分析存儲器山的數據，還可以看出存儲器系統的部分硬體參數。包括L1數據cache（簡稱為L1-Dcache）、L2-cache和主存（物理介質通常為SDRAM）各自的最高平均速率，L1-Dcache和L2-cache的容量，甚至L1-Dcache的行尺寸。

不過，存儲器山並非萬能工具。從中無法看出cache的相聯度、訪問延遲等參數（這些參數可以用其他測試程序間接得出，但無法從存儲器山測試程序中得出）。由於連續密集訪問，cache預取（Prefetching）也會被阻塞從而無法體現其效果。

存儲器山測試程序的核心就是這樣一個循環：

Kernel_loop(elems, stride):
for (i = 0; i < elems; i += stride)
    result = data[i];

其中，data是一個整形數組（整形元素單位為4字節），result是一個暫存器變量 （頁面存檔備份，存於網際網路檔案館）。Kernel_loop所做的事情，就是將data數組的內容依次讀取到CPU的暫存器中。參數elems表示data數組的尺寸，即工作集（working set）尺寸。參數stride表示訪問時的步長，即相鄰兩次訪問的元素的地址間隔。 用Get_readrate()函數來獲取特定參數下Kernel_loop的讀速率：

Get_readrate(elems, stride):
Kernel_loop(elems, stride);           // 为cache预热，避免“冷缺失”
time_start = GetTimer();               // 记录测试开始时间
Kernel_loop(elems, stride);          // 执行真正的测试
time_end = GetTimer();                // 记录测试结束时间
time_cost = time_end – time_start;   // 得到时间开销
readrate = (elems*sizeof(int)/stride) / time_cost; // 换算为读速率

main()函數改變elems和stride參數的大小，記錄Kernel_loop在各個參數下的讀速率：

main():
for (elems = MINELEMS; elems <= MAXELEMS; elems <<= 1)
    for (stride = 1; stride <= MAXSTRIDE; stride++)
        Get_ readrate (elems, stride);

以elems為x軸，stride為y軸，readrate為z軸，即可得到一座存儲器山。這裡，elems控制時間局部性。因為當stride固定時，elems越小，對同一個地址的兩次訪問（cache預熱時一次，真正測試時一次）間隔的時間越短。而stride控制空間局部性。因為stride越小，相鄰兩次訪問的地址間隔越小。readrate即是不同時空局部性下對存儲器的讀速率。MINELEMS、MAXELEMS、MAXSTRIDE等常量的具體數值根據測試平台的參數來選擇。

另請參考

• 《深入理解計算機系統》官方網站給出的存儲器山測試程序原始碼 （頁面存檔備份，存於網際網路檔案館）。
• 《深入理解計算機系統》官方網站推薦的生成存儲器山的程序ECT memperf （頁面存檔備份，存於網際網路檔案館），該程序由存儲器山概念的最早提出者Tom Stricker編寫。
• 卡耐基梅隆大學給出的R.E.Bryant的簡歷，著作列表中第一位便是《深入理解計算機系統》。
• 卡耐基梅隆大學給出的《深入理解計算機系統》電子版目錄 （頁面存檔備份，存於網際網路檔案館），目錄封面為存儲器山，第6.6.1節（The Memory Mountain）為對存儲器山的分析。
• Introducing Computer Systems from a Programmer's Perspective （頁面存檔備份，存於網際網路檔案館），《深入理解計算機系統》的作者對該書的介紹。

• Memory part 2: CPU caches （頁面存檔備份，存於網際網路檔案館）來自lwn.net的文章，作者Ulrich Drepper，深入分析了cache的性能，其中包括對cache帶寬的詳細分析。
• Memory Hierarchy in Cache-Based Systems （頁面存檔備份，存於網際網路檔案館），作者Ruud van der Pas, 2002, Sun Microsystems，是關於CPU高速緩存系統很好的入門介紹。
• RightMark Memory Analyzer （頁面存檔備份，存於網際網路檔案館），功能豐富的存儲器測試分析軟體。
• Intel Core 2 Duo Test （頁面存檔備份，存於網際網路檔案館），對Core2處理器的評測。
• 文獻1的第6.2節，以及文獻2的第7.1節，有關於局部性的更多討論。
• 文獻1的第6章，以及文獻2的第7章，有關於存儲器層次結構的更多討論。
• 文獻1的6.6.1節，有關於存儲器山測試程序的更多討論。