??在計(jì)算機(jī)系統(tǒng)模型中，CPU執(zhí)行指令，而存儲(chǔ)器系統(tǒng)為CPU存放指令和數(shù)據(jù)。實(shí)際上，存儲(chǔ)器系統(tǒng)是一個(gè)具有不同容量、成本和訪問(wèn)時(shí)間的存儲(chǔ)設(shè)備的層次結(jié)構(gòu)。
??如果你的程序需要的數(shù)據(jù)是存儲(chǔ)在CPU寄存器中，那么在指令的執(zhí)行期間，在0個(gè)周期內(nèi)就能訪問(wèn)到它們。如果存儲(chǔ)在高速緩存中，需要4~75個(gè)周期。如果存儲(chǔ)在主存中，需要上百個(gè)周期。而如果存儲(chǔ)在磁盤上，需要大約幾千萬(wàn)個(gè)周期！
??計(jì)算機(jī)程序的一個(gè)基本屬性稱為局部性。具有良好局部性的程序傾向于一次又一次地訪問(wèn)相同的數(shù)據(jù)項(xiàng)集合，或是傾向于訪問(wèn)鄰近的數(shù)據(jù)項(xiàng)集合。具有良好局部性的程序比局部性差的程序更多地傾向于從存儲(chǔ)器層次結(jié)構(gòu)中較高層次處訪問(wèn)數(shù)據(jù)項(xiàng)，因此運(yùn)行得更快。

存儲(chǔ)技術(shù)

隨機(jī)訪問(wèn)存儲(chǔ)器

??隨機(jī)訪問(wèn)存儲(chǔ)器（ Random-Access Memory,RAM）分為兩類：靜態(tài)的和動(dòng)態(tài)的。靜態(tài)RAM（SRAM）比動(dòng)態(tài)RAM（DRAM）更快，但也貴得多。SRAM用來(lái)作為高速緩存存儲(chǔ)器。DRAM用來(lái)作為主存以及圖形系統(tǒng)的幀緩沖區(qū)。

靜態(tài)RAM

??SRAM將每個(gè)位存儲(chǔ)在一個(gè)雙穩(wěn)態(tài)的（ bistable）存儲(chǔ)器單元里。每個(gè)單元是用一個(gè)六晶體管電路來(lái)實(shí)現(xiàn)的。這個(gè)電路有這樣一個(gè)屬性，它可以無(wú)限期地保持在兩個(gè)不同的電壓配置（ configuration）或狀態(tài)（ state）之一。其他任何狀態(tài)都是不穩(wěn)定的，在不穩(wěn)定狀態(tài)時(shí)，電路會(huì)迅速轉(zhuǎn)移到兩個(gè)穩(wěn)定狀態(tài)的一個(gè)。

??由于SRAM存儲(chǔ)器單元的雙穩(wěn)態(tài)特性，只要有電，它就會(huì)永遠(yuǎn)地保持它的值。即使有干擾（例如電子噪音）來(lái)擾亂電壓，當(dāng)干擾消除時(shí)，電路就會(huì)恢復(fù)到穩(wěn)定值。

動(dòng)態(tài)RAM

??DRAM將每個(gè)位存儲(chǔ)為對(duì)一個(gè)電容的充電。DRAM存儲(chǔ)器可以制造得非常密集。每個(gè)單元由一個(gè)電容和一個(gè)訪問(wèn)晶體管組成。但是，與SRAM不同，DRAM存儲(chǔ)器單元對(duì)干擾非常敏感。當(dāng)電容的電壓被擾亂之后，它就永遠(yuǎn)不會(huì)恢復(fù)了。暴露在光線下會(huì)導(dǎo)致電容電壓改變。

??下表總結(jié)了SRAM和DRAM存儲(chǔ)器的特性。只要有供電，SRAM就會(huì)保持不變。與DRAM不同，它不需要刷新。SRAM的存取比DRAM快。SRAM對(duì)諸如光和電噪聲這樣的干擾不敏感。代價(jià)是SRAM單元比DRAM單元使用更多的晶體管，因而密集度低，而且更貴，功耗更大。

傳統(tǒng)的DRAM

??DRAM芯片中的單元（位）被分成d個(gè)超單元（ supercell），每個(gè)超單元都由w個(gè)DRAM單元組成。一個(gè)\(d \times w\)的DRAM總共存儲(chǔ)了\(dw\)位信息。超單元被組織成一個(gè)r行c列的長(zhǎng)方形陣列，這里rc=d。每個(gè)超單元有形如（i,j）的地址，這里i表示行，而j表示列。

??例如，如下圖所示是一個(gè)16×8的DRAM芯片的組織，有d=16個(gè)超單元，每個(gè)超單元有w=8位，r=4行，c=4列。帶陰影的方框表示地址（2,1）處的超單元。信息通過(guò)稱為引腳（pin）的外部連接器流入和流出芯片。每個(gè)引腳攜帶一個(gè)1位的信號(hào)。下圖給出了兩組引腳：8個(gè)data引腳，它們能傳送一個(gè)字節(jié)到芯片或從芯片傳出一個(gè)字節(jié)，以及2個(gè)addr引腳，它們攜帶2位的行和列超單元地址。其他攜帶控制信息的引腳沒(méi)有顯示出來(lái)。

??每個(gè)DRAM芯片被連接到某個(gè)稱為內(nèi)存控制器（ memory controller）的電路，這個(gè)電路可以一次傳送w位到每個(gè)DRAM芯片或一次從每個(gè)DRAM芯片傳出w位。為了讀出超單元（i，j）的內(nèi)容，內(nèi)存控制器將行地址i發(fā)送到DRAM，然后是列地址j。DRAM把超單元（i,j）的內(nèi)容發(fā)回給控制器作為響應(yīng)。行地址i稱為RAS（ Row Access strobe，行訪問(wèn)選通脈沖）請(qǐng)求。列地址j稱為CAS（ Column Access strobe，列訪問(wèn)選通脈沖）請(qǐng)求。注意，RAS和CAS請(qǐng)求共享相同的DRAM地址引腳。

??例如，要從圖6-3中16×8的DRAM中讀出超單元（2,1），內(nèi)存控制器發(fā)送行地址2，如下圖a所示。DRAM的響應(yīng)是將行2的整個(gè)內(nèi)容都復(fù)制到一個(gè)內(nèi)部行緩沖區(qū)。接下來(lái)，內(nèi)存控制器發(fā)送列地址1，如下圖b所示。DRAM的響應(yīng)是從行緩沖區(qū)復(fù)制出超單元（2,1）中的8位，并把它們發(fā)送到內(nèi)存控制器。

??電路設(shè)計(jì)者將DRAM組織成二維陣列而不是線性數(shù)組的一個(gè)原因是降低芯片上地址引腳的數(shù)量。例如，如果示例的128位DRAM被組織成一個(gè)16個(gè)超單元的線性數(shù)組，地址為0~15，那么芯片會(huì)需要4個(gè)地址引腳而不是2個(gè)。二維陣列組織的缺點(diǎn)是必須分兩步發(fā)送地址，這增加了訪問(wèn)時(shí)間。

增強(qiáng)的DRAM

??可以通過(guò)以下方式提高訪問(wèn)基本DRAM的速度。

??快頁(yè)模式DRAM（ Fast Page Mode dram, FPM DRAM）。傳統(tǒng)的DRAM將超單元的一整行復(fù)制到它的內(nèi)部行緩沖區(qū)中，使用一個(gè)，然后丟棄剩余的。FPM DRAM允許對(duì)同一行連續(xù)地訪問(wèn)可以直接從行緩沖區(qū)得到服務(wù)。

假如要讀取第4行的3個(gè)超單元，傳統(tǒng)DRAM需要發(fā)出3次RAS,CAS。而FPM DRAM只需要發(fā)出一次RAS，CAS，后面跟2個(gè)CAS即可。

? 擴(kuò)展數(shù)據(jù)輸出DRAM（ Extended Data Out Dram, EDO DRAM）。 FPM DRAM的個(gè)增強(qiáng)的形式，它允許各個(gè)CAS信號(hào)在時(shí)間上靠得更緊密一點(diǎn)。

??同步DRAM（ Synchronous DRaM, SDRAM）。 SDRAM用與驅(qū)動(dòng)內(nèi)存控制器相同的外部時(shí)鐘信號(hào)的上升沿來(lái)代替許多這樣的控制信號(hào)。最終效果就是 SDRAM能夠比那些異步的存儲(chǔ)器更快地輸出它的超單元的內(nèi)容。

??雙倍數(shù)據(jù)速率同步DRAM（ Double data- Rate SynchronouS DRAm, DDR SDRAM）。DDR SDRAM是對(duì) SDRAM的一種增強(qiáng)，它通過(guò)使用兩個(gè)時(shí)鐘沿作為控制信號(hào)，從而使DRAM的速度翻倍。不同類型的 DDR SDRAM是用提高有效帶寬的很小的預(yù)取緩沖區(qū)的大小來(lái)劃分的：DDR（2位）、DDR2（4位）和DDR（8位）。

??視頻RAM（ Video ram,VRAM）。它用在圖形系統(tǒng)的幀緩沖區(qū)中。VRAM的思想與 FPM DRAM類似。兩個(gè)主要區(qū)別是：1）VRAM的輸出是通過(guò)依次對(duì)內(nèi)部緩沖區(qū)的整個(gè)內(nèi)容進(jìn)行移位得到的；2）VRAM允許對(duì)內(nèi)存并行地讀和寫。因此，系統(tǒng)可以在寫下一次更新的新值（寫）的同時(shí)，用幀緩沖區(qū)中的像素刷屏幕（讀）。

非易失性存儲(chǔ)器

??如果斷電，DRAM和SRAM會(huì)丟失它們的信息，從這個(gè)意義上說(shuō)，它們是易失的（ volatile）。另一方面，非易失性存儲(chǔ)器（ nonvolatile memory）即使是在關(guān)電后，仍然保存著它們的信息。

??對(duì)EPROM編程是通過(guò)使用一種把1寫人 EPROM的特殊設(shè)備來(lái)完成的。 EPROM能夠被擦除和重編程的次數(shù)的數(shù)量級(jí)可以達(dá)到1000次。EEPROM能夠被編程的次數(shù)的數(shù)量級(jí)可以達(dá)到10次。

??閃存（ flash memory）是一類非易失性存儲(chǔ)器，基于 EEPROM，它已經(jīng)成為了一種重要的存儲(chǔ)技術(shù)。

訪問(wèn)主存

??數(shù)據(jù)流通過(guò)稱為總線（bus）的共享電子電路在處理器和DRAM主存之間來(lái)來(lái)回回。每次CPU和主存之間的數(shù)據(jù)傳送都是通過(guò)一系列步驟來(lái)完成的，這些步驟稱為總線事務(wù)（ bus transaction）。讀事務(wù)（ read transaction）從主存?zhèn)魉蛿?shù)據(jù)到CPU。寫事務(wù)（ write trans-action）從CPU傳送數(shù)據(jù)到主存。

??總線是一組并行的導(dǎo)線，能攜帶地址、數(shù)據(jù)和控制信號(hào)。取決于總線的設(shè)計(jì)，數(shù)據(jù)和地址信號(hào)可以共享同一組導(dǎo)線，也可以使用不同的。同時(shí)，兩個(gè)以上的設(shè)備也能共享同一總線?？刂凭€攜帶的信號(hào)會(huì)同步事務(wù)，并標(biāo)識(shí)出當(dāng)前正在被執(zhí)行的事務(wù)的類型。例如，當(dāng)前關(guān)注的這個(gè)事務(wù)是到主存的嗎？還是到諸如磁盤控制器這樣的其他I/O設(shè)備？這個(gè)事務(wù)是讀還是寫？總線上的信息是地址還是數(shù)據(jù)項(xiàng)？

??展示了一個(gè)示例計(jì)算機(jī)系統(tǒng)的配置。主要部件是CPU芯片、我們將稱為IO橋接器（I/ O bridge）的芯片組（其中包括內(nèi)存控制器），以及組成主存的DRAM內(nèi)存模塊這些部件由一對(duì)總線連接起來(lái)，其中一條總線是系統(tǒng)總線（ system bus），它連接CPU和I/O橋接器，另一條總線是內(nèi)存總線（ memory bus），它連接I/O橋接器和主存。I/O橋接器將系統(tǒng)總線的電子信號(hào)翻譯成內(nèi)存總線的電子信號(hào)。

局部性

??一個(gè)編寫良好的計(jì)算機(jī)程序常常具有良好的局部性（ locality）。也就是，它們傾向于引用鄰近于其他最近引用過(guò)的數(shù)據(jù)項(xiàng)的數(shù)據(jù)項(xiàng)，或者最近引用過(guò)的數(shù)據(jù)項(xiàng)本身。這種傾向性，被稱為局部性原理（ principle of locality），是一個(gè)持久的概念，對(duì)硬件和軟件系統(tǒng)的設(shè)計(jì)和性能都有著極大的影響。局部性通常有兩種不同的形式：時(shí)間局部性（ temporal locality）和空間局部性（ spatial locality）。在一個(gè)具有良好時(shí)間局部性的程序中，被引用過(guò)一次的內(nèi)存位置很可能在不遠(yuǎn)的將來(lái)再被多次引用。在一個(gè)具有良好空間局部性的程序中，如果一個(gè)內(nèi)存位置被引用了次，那么程序很可能在不遠(yuǎn)的將來(lái)引用附近的一個(gè)內(nèi)存位置。一般而言，有良好局部性的程序比局部性差的程序運(yùn)行得更快。

??如下所示的函數(shù)sumvec，它對(duì)一個(gè)向量的元素求和。在這個(gè)例子中，變量sum在每次循環(huán)迭代中被引用一次，因此，對(duì)于sum來(lái)說(shuō)，有好的時(shí)間局部性。另一方面，因?yàn)閟un是標(biāo)量，對(duì)于sum來(lái)說(shuō)，沒(méi)有空間局部性。

int sumvec(int v[N])
{
    int i,sum = 0;
    for (i = 0; i < N; i++)
        sum += v[i];
    return sum;
}

引用模式：
地址：			0		4		8		12		16
內(nèi)容：			v0		v1		v2		v3		v4
訪問(wèn)順序：		1		2		3		4		5

??如上所示，向量v的元素是被順序讀取的，一個(gè)接一個(gè)，按照它們存儲(chǔ)在內(nèi)存中的順序（為了方便，我們假設(shè)數(shù)組是從地址0開(kāi)始的）。因此，對(duì)于變量v，函數(shù)有很好的空間局部性，但是時(shí)間局部性很差，因?yàn)槊總€(gè)向量元素只被訪問(wèn)一次。

步長(zhǎng)為1的引用模式為順序引用模式（ sequential reference pattern）。一個(gè)連續(xù)向量中，每隔k個(gè)元素進(jìn)行訪問(wèn)，就稱為步長(zhǎng)為k的引用模式（ stride-k reference pattern）。步長(zhǎng)為1的引用模式是程序中空間局部性常見(jiàn)和重要的來(lái)源。一般而言，隨著步長(zhǎng)的增加，空間局部性下降。

??如下的函數(shù) sumarrayrows，它對(duì)一個(gè)二維數(shù)組的元素求和。雙重嵌套循環(huán)按照行優(yōu)先順序（row major order）讀數(shù)組的元素。也就是，內(nèi)層循環(huán)讀第一行的元素，然后讀第二行，依此類推。函數(shù) sumarrayrows具有良好的空間局部性，因?yàn)樗凑諗?shù)組被存儲(chǔ)的行優(yōu)先順序來(lái)訪問(wèn)這個(gè)數(shù)組。其結(jié)果是得到一個(gè)很好的步長(zhǎng)為1的引用模式，具有良好的空間局部性。

int sum_array_rows(int a[M][N])
{
    int i, j, sum = 0;

    for (i = 0; i < M; i++)
        for (j = 0; j < N; j++)
            sum += a[i][j];
    return sum;
}

引用模式：
地址：			0		4		8		12		16
內(nèi)容：			a00		a01		a02		a10		a11
訪問(wèn)順序：		1		2		3		4		5

存儲(chǔ)器層次結(jié)構(gòu)

??存儲(chǔ)技術(shù)和計(jì)算機(jī)軟件的一些基本的和持久的屬性：
??存儲(chǔ)技術(shù)：不同存儲(chǔ)技術(shù)的訪問(wèn)時(shí)間差異很大。速度較快的技術(shù)每字節(jié)的成本要比速度較慢的技術(shù)高，而且容量較小。CPU和主存之間的速度差距在增大。
??計(jì)算機(jī)軟件：一個(gè)編寫良好的程序傾向于展示出良好的局部性。

??硬件和軟件的這些基本屬性互相補(bǔ)充得很完美。它們這種相互補(bǔ)充的性質(zhì)使人想到一種組織存儲(chǔ)器系統(tǒng)的方法，稱為存儲(chǔ)器層次結(jié)構(gòu)（ memory hierarchy），下圖展示了一個(gè)典型的存儲(chǔ)器層次結(jié)構(gòu)。一般而言，從高層往底層走，存儲(chǔ)設(shè)備變得更慢、更便宜和更大。在最高層（L0），是少量快速的CPU寄存器，CPU可以在一個(gè)時(shí)鐘周期內(nèi)訪問(wèn)它們。接下來(lái)是一個(gè)或多個(gè)小型到中型的基于SRAM的高速緩存存儲(chǔ)器，可以在幾個(gè)CPU時(shí)鐘周期內(nèi)訪問(wèn)它們。然后是一個(gè)大的基于DRAM的主存，可以在幾十到幾百個(gè)時(shí)鐘周期內(nèi)訪問(wèn)它們。接下來(lái)是慢速但是容量很大的本地磁盤。最后，有些系統(tǒng)甚至包括了一層附加的遠(yuǎn)程服務(wù)器上的磁盤，要通過(guò)網(wǎng)絡(luò)來(lái)訪問(wèn)它們。

存儲(chǔ)器結(jié)構(gòu)中的緩存

??一般而言，高速緩存（ cache，讀作“cash”）是一個(gè)小而快速的存儲(chǔ)設(shè)備，它作為存儲(chǔ)在更大、也更慢的設(shè)備中的數(shù)據(jù)對(duì)象的緩沖區(qū)域。使用高速緩存的過(guò)程稱為緩存（ caching，讀作“ cashing"）。

??存儲(chǔ)器層次結(jié)構(gòu)的中心思想是，對(duì)于每個(gè)k，位于k層的更快更小的存儲(chǔ)設(shè)備作為位于k+1層的更大更慢的存儲(chǔ)設(shè)備的緩存。換句話說(shuō)，層次結(jié)構(gòu)中的每一層都緩存來(lái)自較低一層的數(shù)據(jù)對(duì)象。

??數(shù)據(jù)總是以塊大小為傳送單元（ transfer unit）在第k層和第k+1層之間來(lái)回復(fù)制的。雖然在層次結(jié)構(gòu)中任何一對(duì)相鄰的層次之間塊大小是固定的，但是其他的層次對(duì)之間可以有不同的塊大小。如上圖所示，L1和L0之間的傳送通常使用的是1個(gè)字大小的塊。L2和L1之間（以及L3和I2之間、I4和I3之間）的傳送通常使用的是幾十個(gè)字節(jié)的塊。而L5和L4之間的傳送用的是大小為幾百或幾千字節(jié)的塊。一般而言，層次結(jié)構(gòu)中較低層（離CPU較遠(yuǎn)）的設(shè)備的訪問(wèn)時(shí)間較長(zhǎng)，因此為了補(bǔ)償這些較長(zhǎng)的訪問(wèn)時(shí)間，傾向于使用較大的塊。

緩存命中

??當(dāng)程序需要第k+1層的某個(gè)數(shù)據(jù)對(duì)象d時(shí)，它首先在當(dāng)前存儲(chǔ)在第k層的一個(gè)塊中查找d。如果d剛好緩存在第k層中，那么就是我們所說(shuō)的緩存命中（ cache hit）。

緩存不命中

??另一方面，如果第k層中沒(méi)有緩存數(shù)據(jù)對(duì)象d，那么就是我們所說(shuō)的緩存不命中（ cache miss）。當(dāng)發(fā)生緩存不命中時(shí)，第k層的緩存從第k+1層緩存中取出包含d的那個(gè)塊，如果第k層的緩存已經(jīng)滿了，可能就會(huì)覆蓋現(xiàn)存的一個(gè)塊。（緩存的替換策略：隨機(jī)替換替換策略，最少被使用（LRU）替換策略）。

緩存不命中種類

??區(qū)分不同種類的緩存不命中有時(shí)候是很有幫助的。如果第k層的緩存是空的，那么對(duì)任何數(shù)據(jù)對(duì)象的訪問(wèn)都會(huì)不命中。一個(gè)空的緩存有時(shí)被稱為冷緩存（ cold cache），此類不命中稱為強(qiáng)制性不命中（ compulsory miss）或冷不命中（ cold miss）。冷不命中很重要，因?yàn)樗鼈兺ǔＪ嵌虝旱氖录?，不?huì)在反復(fù)訪問(wèn)存儲(chǔ)器使得緩存暖身（ warmed up）之后的穩(wěn)定狀態(tài)中出現(xiàn)。

緩存管理

??存儲(chǔ)器層次結(jié)構(gòu)的本質(zhì)是，每一層存儲(chǔ)設(shè)備都是較低一層的緩存。在每一層上，某種形式的邏輯必須管理緩存。這里，我們的意思是指某個(gè)東西要將緩存劃分成塊，在不同的層之間傳送塊，判定是命中還是不命中，并處理它們。管理緩存的邏輯可以是硬件、軟件，或是兩者的結(jié)合。

高速緩存存儲(chǔ)器

??高速緩存關(guān)于讀的操作非常簡(jiǎn)單。首先，在高速緩存中查找所需字\(w\)的副本。如果命中，立即返回字\(w\)給CPU。如果不命中，從存儲(chǔ)器層次結(jié)構(gòu)中較低層中取出包含字\(w\)的塊，將這個(gè)塊存儲(chǔ)到某個(gè)高速緩存行中（可能會(huì)驅(qū)逐一個(gè)有效的行），然后返回字\(w\)。

??寫的情況就要復(fù)雜一些了。假設(shè)我們要寫一個(gè)已經(jīng)緩存了的字\(w\)（寫命中， write hit）。在高速緩存更新了它的\(w\)的副本之后，怎么更新\(w\)在層次結(jié)構(gòu)中緊接著低一層中的副本呢？最簡(jiǎn)單的方法，稱為直寫（ write-through），就是立即將\(w\)的高速緩存塊寫回到緊接著的低一層中。雖然簡(jiǎn)單，但是直寫的缺點(diǎn)是每次寫都會(huì)引起總線流量。另一種方法，稱為寫回（ write-back），盡可能地推遲更新，只有當(dāng)替換算法要驅(qū)逐這個(gè)更新過(guò)的塊時(shí)，才把它寫到緊接著的低一層中。由于局部性，寫回能顯著地減少總線流量，但是它的缺點(diǎn)是增加了復(fù)雜性。高速緩存必須為每個(gè)高速緩存行維護(hù)一個(gè)額外的修改位（ dirty bit），表明這個(gè)高速緩存塊是否被修改過(guò)。

??另一個(gè)問(wèn)題是如何處理寫不命中。一種方法，稱為寫分配（ write-allocate），加載相應(yīng)的低一層中的塊到高速緩存中，然后更新這個(gè)高速緩存塊。寫分配試圖利用寫的空間局部性，但是缺點(diǎn)是每次不命中都會(huì)導(dǎo)致一個(gè)塊從低一層傳送到高速緩存。另一種方法，稱為非寫分配（not- write-allocate），避開(kāi)高速緩存，直接把這個(gè)字寫到低一層中。直寫高速緩存通常是非寫分配的。寫回高速緩存通常是寫分配的。

??高速緩存既保存數(shù)據(jù)，也保存指令。只保存指令的高速緩存稱為 i-cache。只保存程序數(shù)據(jù)的高速緩存稱為 d-cache。既保存指令又包括數(shù)據(jù)的高速緩存稱為統(tǒng)一的高速緩存（ unified cache）?，F(xiàn)代處理器包括獨(dú)立的 i-cache和d-cache。這樣做有很多原因。有兩個(gè)獨(dú)立的高速緩存，處理器能夠同時(shí)讀一個(gè)指令字和一個(gè)數(shù)據(jù)字。 i-cache通常是只讀的，因此比較簡(jiǎn)單。通常會(huì)針對(duì)不同的訪問(wèn)模式來(lái)優(yōu)化這兩個(gè)高速緩存，它們可以有不同的塊大小，相聯(lián)度和容量。使用不同的高速緩存也確保了數(shù)據(jù)訪問(wèn)不會(huì)與指令訪問(wèn)形成沖突不命中，反過(guò)來(lái)也是一樣，代價(jià)就是可能會(huì)引起容量不命中增加。

編寫高速緩存友好的代碼

??確保代碼高速緩存友好的基本方法。
??1）讓最常見(jiàn)的情況運(yùn)行得快。程序通常把大部分時(shí)間都花在少量的核心函數(shù)上，而這些函數(shù)通常把大部分時(shí)間都花在了少量循環(huán)上。所以要把注意力集中在核心函數(shù)里的循環(huán)上，而忽略其他部分。
??2）盡量減小每個(gè)循環(huán)內(nèi)部的緩存不命中數(shù)量。在其他條件（例如加載和存儲(chǔ)的總次數(shù)）相同的情況下，不命中率較低的循環(huán)運(yùn)行得更快。

??考慮如下的函數(shù)

int sumvec(int v[N])
{
	int i,sum = 0;
    
	for(i = 0;i<N;i++)
		sum +=v[i];
	return sum;
}

??首先，注意對(duì)于局部變量i和sum，循環(huán)體有良好的時(shí)間局部性?，F(xiàn)在考慮一下對(duì)向量v的步長(zhǎng)為1的引用。一般而言，如果一個(gè)高速緩存的塊大小為B字節(jié)，那么一個(gè)步長(zhǎng)為k的引用模式（這里k是以字為單位的）平均每次循環(huán)迭代會(huì)有\(\min (1,(wordsize \times k)/B)\)次緩存不命中。當(dāng)k=1時(shí)，它取最小值，所以對(duì)v的步長(zhǎng)為1的引用確實(shí)是高速緩存友好的。

??例如，假設(shè)v是塊對(duì)齊的，字為4個(gè)字節(jié)，高速緩存塊為4個(gè)字，而高速緩存初始為空（冷高速緩存）。在這個(gè)例子中，對(duì)v[0]的引用會(huì)不命中，而相應(yīng)的包含v[0] ~v[3]的塊會(huì)被從內(nèi)存加載到高速緩存中。因此，接下來(lái)三個(gè)引用都會(huì)命中。對(duì)v[4]的引用會(huì)導(dǎo)致不命中，而個(gè)新的塊被加載到高速緩存中，接下來(lái)的三個(gè)引用都命中，依此類推?？偟膩?lái)說(shuō)，四個(gè)引用中，三個(gè)會(huì)命中，在這種冷緩存的情況下，這是我們所能做到的最好的情況了。

??總之，簡(jiǎn)單的 sumvec示例說(shuō)明了兩個(gè)關(guān)于編寫高速緩存友好的代碼的重要問(wèn)題：第一，對(duì)局部變量的反復(fù)引用是好的，因?yàn)榫幾g器能夠?qū)⑺鼈兙彺嬖诩拇嫫魑募校〞r(shí)間局部性）。第二，步長(zhǎng)為1的引用模式是好的，因?yàn)榇鎯?chǔ)器層次結(jié)構(gòu)中所有層次上的緩存都是將數(shù)據(jù)存儲(chǔ)為連續(xù)的塊（空間局部性）。

總結(jié)

??本章主要介紹了各種各樣的存儲(chǔ)系統(tǒng)及其原理，一般來(lái)說(shuō)，較小、較快的設(shè)備在頂部，較大、較慢的設(shè)備在底部。因?yàn)榫帉懥己玫某绦蛴泻玫木植啃?，大多?shù)數(shù)據(jù)都可以從較高層得到服務(wù)，結(jié)果就是存儲(chǔ)系統(tǒng)能以較高層的速度運(yùn)行，但卻有較低層的成本和容量。我們可以通過(guò)編寫有良好空間和時(shí)間局部性的程序來(lái)顯著地改進(jìn)程序的運(yùn)行時(shí)間。例如，可以利用基于SRAM的高速緩存存儲(chǔ)器。主要原因是從高速緩存取數(shù)據(jù)的程序比主要從內(nèi)存取數(shù)據(jù)的程序運(yùn)行得快得多。

?