開篇

 上一篇博文

局部性原理淺析——良好代碼的基本素質

中對程序局部性有了一個簡單的介紹。基本上已經知道了如何編寫有良好局部性的代碼。但是為什么有良好局部性的代碼就能有良好的運行效率，這個問題將在這篇博文中給出解答。至于存儲器內部的組織實現，將在下篇文章中敘述。

存儲器層次結構

我們知道，計算機里的存儲器有:硬盤、主存、高速緩存（其中又有一級高速緩存、二級高速緩存等等）、在往上就是寄存器。

存儲器在計算機內部的組織方式如下圖所示：

相信上圖大家并不陌生。wiki對The memory hierarchy 的介紹的時候也有此圖。

我們發現，越往上，存儲器的容量越小、成本越高、速度越快。

為什么會出現這樣的結構呢？早起的存儲器層次結構只有三層：cpu寄存器、DRAM主存以及磁盤存儲。

由于CPU和主存之間巨大的速度差異，系統設計者被迫在CPU寄存器和主存之間插入了一個小的SRAM高速緩存存儲器稱為L1緩存，大約可以在2--4個時鐘周期內訪問。再后來發現L1高速緩存和主存之間還是有較大差距，又在L1高速緩存和主存之間插入了速度更快的L2緩存，大約可以在10個時鐘周期內訪問。于是，在這樣的模式下，在不斷的演變中形成了現在的存儲體系。

現在可以知道整個存儲器體系被分為了很多層，那么他們之間是如何協調工作以提高運行效率的呢?

何為緩存

暫時你可以這樣理解:速度快的存儲器緩存了速度慢存儲器的數據。準確的描述：對于每個k ，位于k層的更快更小的存儲器設備作為第k+1層的更大更慢存儲設備的緩存。就是說，k層存儲了k+1層中經常被訪問的數據。在緩存之間，數據是以塊為單位傳輸的。當然不同層次的緩存，塊的大小會不同。一般來說是越往上，塊越小。

請看下圖示例

k是k+1的緩存，他們之間的數據傳輸是以塊大小為單位的。如上圖中，k中緩存了k+1中塊編號為 4、9、14、3的數據。

當程序需要這些塊中的數據時，可直接沖緩存k中得到。這比從k+1層讀數據要快

緩存命中

當程序需要第k+1層中的某個數據時d，會首先在它的緩存k層中尋找。如果數據剛好在k層中，就稱為緩存命中（cache hit）。

緩存不命中

當需要的數據對象d不再緩存k中時，稱為緩存不命中。當發生緩存不命中時，第k層的緩存會從k+1層取出包含數據對象d的那個塊，如果k層的緩存已經放滿的話，就會覆蓋其中的一個塊。至于要覆蓋哪一個塊，這是有緩存中的替換策略決定的，比如說可以覆蓋使用頻率最小的塊，或者最先進入緩存的塊。。這里不再討論。在k層從k+1層中取出數據對象d后，程序就能在緩存中讀取數據對象d了。

緩存命中和局部性

這里先簡單的說說為什么局部性好的程序能有更好的性能

利用時間局部性:由于時間局部性，同一個數據對象會多次被使用。一旦一個數據對象從k+1層進入到k層的緩存中，就希望它多次被引用。這樣能節省很多訪問造成的時間開支。

利用空間局部性:假設緩存k能存n個數據塊。在對數組訪問的時候，由于數組是連續存放的，對第一個元素訪問的時候，會把第一個元素后面的一共n個元素（緩存k有n個數據塊）拷貝到緩存k中，這樣在對第二個元素到第n個元素的訪問時就可以直接從緩存里獲取，從而提高性能。

同理，訪問第n個元素的時候 ，n不在緩存中，緩存管理器會把從n到2n的元素拷貝到緩存中，對它們的訪問就可以直接在緩存中進行。

通過空間局部性，我們希望對后面對緩存中其他對象的訪問能補償不命中后拷貝這些塊的時間花費。

現代系統中處處有緩存，為了使大家能更好的理解，下表對于計算機中不同層次的存儲器和性能等參數做了以總結（僅供參考）

小結

 這篇文章主要介紹了計算機存儲器內部的組織結構以及他們之間的關系，并簡單說了下緩存實現機制，以及緩存和局部性之間的關系。

至于緩存內部如何實現，程序如何從緩存內存取數據，將在下一篇中給出

本人認知有限，如上述文章有不足之處歡迎指正交流。

參看資料：computer systems

如有轉載請注明出處：http://www.rzrgm.cn/yanlingyin/

一條魚、yanlingyin@ 博客園 2012-2-12

 E-mail：yanlingyin@yeah.net