2018-12-02 CSAPP 第六章存儲(chǔ)器層次結(jié)構(gòu)

在簡(jiǎn)單模型中悠瞬，存儲(chǔ)器系統(tǒng)是一個(gè)線性的字節(jié)數(shù)組，CPU能夠在一個(gè)常數(shù)訪問(wèn)每個(gè)存儲(chǔ)器位置宵睦。

雖然是一個(gè)行之有效的模型记罚，但沒(méi)有反應(yīng)現(xiàn)代系統(tǒng)實(shí)際工作方式。

實(shí)際上壳嚎，存儲(chǔ)器系統(tǒng)(memory system)是一個(gè)具有不同容量桐智，成本和訪問(wèn)時(shí)間的存儲(chǔ)設(shè)備的層次結(jié)構(gòu)。

CPU寄存器保存著最常用的數(shù)據(jù)烟馅。(0周期)

靠近CPU的小的说庭，快速的高速緩存存儲(chǔ)器(cache memory)作為一部分存儲(chǔ)在相對(duì)慢速的主儲(chǔ)存器(main memory,簡(jiǎn)稱(chēng)主存)中的數(shù)據(jù)和指令的緩沖區(qū)。(1~30周期)

主存暫時(shí)存放儲(chǔ)存在容量較大的郑趁，慢速磁盤(pán)上的數(shù)據(jù)刊驴。(50~200周期)

磁盤(pán)又作為存儲(chǔ)在通過(guò)網(wǎng)絡(luò)連接的其他機(jī)器的磁盤(pán)或磁帶上數(shù)據(jù)的緩沖區(qū)。(幾千萬(wàn)個(gè)周期)

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

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

隨機(jī)訪問(wèn)存儲(chǔ)器(Random-Access Memory,RAM)分為兩類(lèi)穿撮，靜態(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ū)(顯存)。(一般有幾G)

具體分析

SRAM

SRAM將每個(gè)位存儲(chǔ)在一個(gè)雙穩(wěn)態(tài)(bistable)存儲(chǔ)器單元里栗柒。

每個(gè)存儲(chǔ)單元用一個(gè)六晶體管電路來(lái)實(shí)現(xiàn)礁扮。

有這樣屬性，可以無(wú)限期保持在兩個(gè)不同的電壓配置(configuration)或狀態(tài)之一瞬沦。

其他任何狀態(tài)都是不穩(wěn)定的太伊。如圖所示

由于這種雙穩(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è)電容充電名扛，這個(gè)電容非常小，通常只有30*10^-15法拉茧痒。

因此肮韧，DRAM存儲(chǔ)器可以造的十分密集。

每個(gè)單元由一個(gè)電容和一個(gè)訪問(wèn)晶體管組成。

但是弄企，DRAM存儲(chǔ)器對(duì)干擾非常敏感超燃。當(dāng)電容電壓被擾亂后，就永遠(yuǎn)不會(huì)恢復(fù)桩蓉。

很多原因會(huì)漏電淋纲，使得DRAM單元在10~100毫秒時(shí)間內(nèi)失去電荷劳闹。

幸運(yùn)的是院究，計(jì)算機(jī)的時(shí)鐘周期以納秒衡量，這個(gè)保持時(shí)間也相當(dāng)長(zhǎng)本涕。

存儲(chǔ)器系統(tǒng)必須周期性地讀出业汰，然后重寫(xiě)來(lái)刷新存儲(chǔ)器的每一位。

有些系統(tǒng)也使用糾錯(cuò)碼菩颖。

只要有供電样漆，SRAM就會(huì)保持不變。

SRAM不需要刷新

SRAM讀取比DRAM快

SRAM對(duì)干擾不敏感晦闰。

代價(jià)是SRAM單元比DRAM單元使用更多的晶體管放祟，因而密集度低，更貴呻右，功耗更大跪妥。

傳統(tǒng)的DRAM

DRAM芯片的單元被分為d個(gè)超單元(supell cell)

每一個(gè)個(gè)超單元由w個(gè)DRAM單元組成。一個(gè)d*w的DRAM總共存儲(chǔ)了dw位信息声滥。

超單元被組織成一個(gè)r行c列的長(zhǎng)方形陣列眉撵。

這里rc=d,每個(gè)超單元有形如(i,j)的地址，這里i表示行落塑，而j表示列纽疟。

注釋: 計(jì)算機(jī)構(gòu)架師稱(chēng)為單元(cell),電路設(shè)計(jì)者稱(chēng)為字(word)，避免混淆憾赁，取為超單元污朽。

-每個(gè)DRAM芯片被鏈接到某個(gè)稱(chēng)為存儲(chǔ)控制器的電路，這個(gè)電路可以一次傳送w位到每個(gè)DRAM芯片或一次從每個(gè)DRAM芯片傳出w位龙考。

為何有16個(gè)單元蟆肆，卻只要2位addr?

首先發(fā)送一個(gè)行地址i給DRAM。這叫RAS(Row Acess Strobe洲愤，行訪問(wèn)選通脈沖)颓芭。

DRAM的響應(yīng)是把第i行全部拷貝到一個(gè)內(nèi)部行緩沖區(qū)。

然后發(fā)送列地址j給DRAM柬赐。這叫CAS(Column Access Strobe,列訪問(wèn)選通脈沖)請(qǐng)求亡问。

DRAM的響應(yīng)將內(nèi)部行緩沖區(qū)的超單元(i,j)發(fā)送給存儲(chǔ)控制單元。

為何設(shè)計(jì)成二維陣列，而不是線性?

一個(gè)原因是降低芯片上地址引腳的數(shù)量州藕。原本需要2N 的引腳束世，只要N個(gè)就好了。

缺點(diǎn)是需要傳輸兩次床玻。增加訪問(wèn)時(shí)間毁涉。

存儲(chǔ)器模塊

DRAM芯片包裝在存儲(chǔ)器模塊(memory module)中，它是插到主板的擴(kuò)展槽上锈死。

常見(jiàn)的包裝包括168個(gè)引腳的雙列直插存儲(chǔ)器模塊(Dual Inline Memory Module),它以64位為塊傳送數(shù)據(jù)到存儲(chǔ)控制器和從存儲(chǔ)控制器傳出數(shù)據(jù)贫堰。

還包括72個(gè)引腳的單列直插存儲(chǔ)器模塊(Single Inline Memory Module),它以32位為塊傳送數(shù)據(jù)。

如圖展示一個(gè)存儲(chǔ)器模塊的基本思想待牵。

用對(duì)應(yīng)超單元地址(i其屏，j)的8個(gè)超單元來(lái)表示主存字節(jié)地址A處的64位雙字(此處:字=4字節(jié))。

通過(guò)將多個(gè)存儲(chǔ)器模塊連接到存儲(chǔ)控制器缨该，能夠聚合主存偎行。在這種情況下，當(dāng)控制器收到一個(gè)地址A時(shí)贰拿，控制器選擇包含A的模塊k,將A轉(zhuǎn)換成它的(i蛤袒，j)形式，并發(fā)送(i,j)到模塊k(不太懂這句話什么意思?)

增強(qiáng)的DRAM

基于傳統(tǒng)DRAM,進(jìn)行優(yōu)化膨更，改進(jìn)訪問(wèn)速度妙真。

快頁(yè)模式DRAM(Fast Page Mode DRAM,FPM DRAM)。

傳統(tǒng)的DRAM將超單元的一整行拷貝到它的內(nèi)部緩沖區(qū)询一，使用一個(gè)隐孽，然后丟棄剩余的。

FPM DRAM允許對(duì)同一行連續(xù)地訪問(wèn)可以直接從行緩沖區(qū)獲得服務(wù)健蕊。

擴(kuò)展輸出DRAM(Extended Data Out DRAM,EDO DRAM)不懂

FPM DRAM的一個(gè)增強(qiáng)形式菱阵，它允許單獨(dú)的CAS信號(hào)在時(shí)間上靠的緊密一些。

同步DRAM(Synchronous DRAM,SDRAM)不懂

就它們與存儲(chǔ)控制器通信使用一組顯示的控制信號(hào)來(lái)說(shuō)缩功，常規(guī)的晴及，F(xiàn)PM,EDO都是異步的。

最終效果就是SDRAM能夠比那些異步的存儲(chǔ)器更快輸出超單元內(nèi)容嫡锌。

雙倍數(shù)據(jù)速率同步DRAM(Double Date-rate Synchronous DRAM,DDR SDRAM)不懂

DDR SDRAM是對(duì)SDRAM的一種增強(qiáng)虑稼。

通過(guò)使用兩個(gè)時(shí)鐘沿作為控制信號(hào)，從而使DRAM速度翻倍势木。

不同類(lèi)型的DDR SDRAM是用提高有效帶寬的很小的預(yù)取緩沖區(qū)的大小來(lái)劃分的:

DDR(2位)

DDR2(4位)

DDR3(8位)

Rambus DRAM(RDRAM).不懂

這是一種私有技術(shù)蛛倦，它的最大帶寬比DDR SDRAMD的更高。

視頻 RAM(Video RAM,VRAM).不懂

它用在圖形系統(tǒng)的幀緩沖區(qū)中啦桌，VRAM的思想與FPM類(lèi)似溯壶，兩個(gè)主要區(qū)別是

VRAM的輸出通過(guò)依次對(duì)內(nèi)部緩沖區(qū)的整個(gè)內(nèi)容進(jìn)行移位得到及皂。

VRAM允許對(duì)存儲(chǔ)器并行地讀或?qū)憽?/p>

非易失性存儲(chǔ)器(ROM)。

非易失性存儲(chǔ)器(nonvolatie memory)即使在關(guān)電后且改，也仍然保存他們的信息验烧。

DRAM和SRAM是易失的(volatile).

由于歷史原因，雖然ROM有的類(lèi)型既可以讀也可以寫(xiě)又跛，但是它們整體被稱(chēng)為只讀存儲(chǔ)器(Read-Only Memory,ROM)碍拆。

ROM通過(guò)以它們能夠被寫(xiě)的次數(shù)和對(duì)他們進(jìn)行重編程的方式所用的機(jī)制區(qū)分。

PROM (Programmable ROM,可編程ROM)只能夠被編程一次慨蓝。PROM的每個(gè)存儲(chǔ)器有一個(gè)熔絲感混，它只能用高電流熔斷一次。

可擦寫(xiě)可編程ROM(Erasable Programmable ROM,EPROM)有一個(gè)透明的石英窗口菌仁，允許光到達(dá)存儲(chǔ)單元浩习。

紫外線光照射過(guò)窗口，EPROM單元就被清除為0.

對(duì)EPROM編程通過(guò)使用一種把1寫(xiě)入EPROM的特殊設(shè)備完成济丘。

EPROM可擦寫(xiě)次數(shù)達(dá)到1000次

電子可擦除PROM(EEPROM)類(lèi)似于EPROM,

但是它不需要一個(gè)物理上獨(dú)立的編程設(shè)備，直接在印刷電路卡上編程洽蛀。EEPROM能夠被編程次數(shù)的數(shù)量級(jí)可以達(dá)到10^5次摹迷。

閃存(flash memory)也是一類(lèi)非易失性存儲(chǔ)器，基于EEPROM,已經(jīng)成為一種重要的存儲(chǔ)設(shè)備郊供。

在6.1.3節(jié)峡碉，我們會(huì)仔細(xì)研究一種新型的基于閃存的磁盤(pán)驅(qū)動(dòng)器，稱(chēng)為固態(tài)硬盤(pán)(Solid State Disk,SSD).

它能夠提供相對(duì)于傳統(tǒng)旋轉(zhuǎn)磁盤(pán)更快速驮审，更強(qiáng)健和更低耗能的選擇鲫寄。

存儲(chǔ)在ROM設(shè)備中的程序通常稱(chēng)為固件(firmware)。

一些系統(tǒng)在固件中提供了少量基本的輸入和輸出函數(shù)疯淫。

例如地来，PC的BIOS(基本輸入/輸出系統(tǒng))的例程。

訪問(wèn)主存

數(shù)據(jù)流通過(guò)稱(chēng)為總線(bus)的共享電子電路在處理器和DRAM主存之間來(lái)來(lái)回回熙掺。

總線事務(wù)(bus transaction):每次CPU和主存之間的數(shù)據(jù)傳送都是通過(guò)一系列步驟來(lái)完成的未斑，這些步驟稱(chēng)為總線事務(wù)(bus transaction).

讀事務(wù)(read transaction): 主存把數(shù)據(jù)給CPU。

寫(xiě)事務(wù)(write transaction): CPU把數(shù)據(jù)寫(xiě)入主存币绩。

總線是一組并行的導(dǎo)線蜡秽，能攜帶地址，數(shù)據(jù)和控制信號(hào)缆镣。

取決于總線的設(shè)計(jì)芽突，數(shù)據(jù)和地址信號(hào)可以使用一條，也可以使用不同的董瞻。

同時(shí)寞蚌，兩個(gè)以上的設(shè)備也能共享一根總線。

控制線攜帶的信號(hào)為同步事務(wù)，標(biāo)示當(dāng)前執(zhí)行的事務(wù)類(lèi)型睬澡。

示例計(jì)算機(jī)系統(tǒng)的配置固额，CPU芯片，I/O橋的芯片組煞聪，組成DRAM的存儲(chǔ)器模塊斗躏。

有一對(duì)總線

系統(tǒng)總線: 鏈接CPU和I/O橋。

存儲(chǔ)器總線:鏈接I/O橋和主存昔脯。

I/O橋

將系統(tǒng)總線的電子信號(hào)翻譯成存儲(chǔ)器總線的電子信號(hào)啄糙。

I/O橋也將系統(tǒng)總線，存儲(chǔ)器總線連接到I/O總線云稚。

磁盤(pán)和圖形卡這樣I/O設(shè)備共享I/O總線隧饼。

關(guān)于總線設(shè)計(jì)的注釋

總線設(shè)計(jì)是計(jì)算機(jī)系統(tǒng)中的一個(gè)復(fù)雜而且變化迅速的方面。不同的廠商提出了不同的總線體系結(jié)構(gòu)静陈，作為產(chǎn)品差異化的一種方式燕雁。

Intel 系統(tǒng)使用北橋(northbridge)和南橋(southbridge)的芯片組分別將CPU連接到存儲(chǔ)器和I/O設(shè)備。

在比較老的系統(tǒng)鲸拥，Pentium和Core 2 系統(tǒng)中拐格，前端總線(Front Side Bus,FSB)將CPU連接到北橋。

AMD 將FSB替換為超傳輸(HyperTransprot)互聯(lián).

Core i7 使用的是快速通道(QuickPath)互聯(lián)刑赶。

接下來(lái)我們會(huì)集中于存儲(chǔ)器總線上捏浊。

movl A,%eax

這里地址A的內(nèi)容被加載到寄存器%eax中，有以下步驟撞叨。

CPU芯片上稱(chēng)為總線接口的電路發(fā)起總線上的讀事務(wù)金踪。

CPU將地址A放到系統(tǒng)總線上。

I/O橋?qū)⑿盘?hào)傳遞到存儲(chǔ)器總線牵敷。

主存感覺(jué)到存儲(chǔ)器總線上的地址信號(hào)胡岔，從存儲(chǔ)器總線讀地址，從DRAM取出數(shù)據(jù)字劣领，并將數(shù)據(jù)寫(xiě)到存儲(chǔ)器總線姐军。

I/O橋?qū)⑿盘?hào)翻譯稱(chēng)系統(tǒng)總線信號(hào)，然后沿著系統(tǒng)總線傳遞尖淘。

最后,CPU感受到系統(tǒng)總線上的數(shù)據(jù)奕锌，從總線上讀數(shù)據(jù)，拷貝到寄存器中村生。

如果是寫(xiě)事務(wù)

movl %eax惊暴，A

這里寄存器%eax的內(nèi)容寫(xiě)入地址中中，有以下步驟趁桃。

CPU將地址放到系統(tǒng)總線辽话。存儲(chǔ)器從存儲(chǔ)器總線讀出地址肄鸽，并等待數(shù)據(jù)到達(dá)。

CPU將數(shù)據(jù)放到系統(tǒng)總線油啤。主存從存儲(chǔ)器總線讀出數(shù)據(jù)典徘，并拷貝到DRAM中。

以上兩個(gè)步驟是并行的益咬。(如果數(shù)據(jù)總線和地址總線分開(kāi)的話)

6.1.2 磁盤(pán)存儲(chǔ)

磁盤(pán)是廣為應(yīng)用的保存大量數(shù)據(jù)的存儲(chǔ)設(shè)備逮诲，存儲(chǔ)數(shù)據(jù)的數(shù)量級(jí)可以達(dá)到1TB,1PB等等，而基于RAM的從幾百到幾千M字節(jié)幽告。不過(guò)梅鹦，從DRAM中讀比磁盤(pán)快10萬(wàn)倍，從SRAM讀比磁盤(pán)快100萬(wàn)倍冗锁。

6.1.2.1 磁盤(pán)構(gòu)造

磁盤(pán)是由盤(pán)片(platter)構(gòu)成的.

每個(gè)盤(pán)片有兩面或者稱(chēng)為表面(surface)齐唆。

盤(pán)片中央有一個(gè)可以旋轉(zhuǎn)的主軸(spindle)，它使得盤(pán)片以固定的旋轉(zhuǎn)速率(rotational rate)旋轉(zhuǎn)冻河，通常是5400~15 000轉(zhuǎn)每分鐘(Revolution Per Minute,RPM)

磁盤(pán)通常含一個(gè)或多個(gè)這樣的盤(pán)片箍邮，并封裝到一個(gè)密封的容器里。

如圖芋绸，展示了一個(gè)典型的磁盤(pán)表面的結(jié)構(gòu)媒殉。

每個(gè)表面是由一組稱(chēng)為磁道(track)的同心圓組成的。

每個(gè)磁道被劃分為一組扇區(qū)(sector)摔敛。

每個(gè)扇區(qū)包含相等數(shù)量的數(shù)據(jù)位(通常是512字節(jié))，這些數(shù)據(jù)編碼在扇區(qū)的磁性材料中全封。

扇區(qū)之間由一些間隙(gap)分隔

不存儲(chǔ)數(shù)據(jù)

間隙存儲(chǔ)用來(lái)標(biāo)識(shí)扇區(qū)的格式化位马昙。

磁盤(pán)是由一個(gè)或多個(gè)疊放在一起的盤(pán)片組成，被封裝在密封包裝刹悴。

整個(gè)裝置稱(chēng)為磁盤(pán)驅(qū)動(dòng)器(disk drive),我們通常簡(jiǎn)稱(chēng)為磁盤(pán)(disk).

有時(shí)又叫旋轉(zhuǎn)磁盤(pán)(rotating disk),使之區(qū)別基于閃存的固態(tài)硬盤(pán)(SSD)行楞。

SSD沒(méi)有可移動(dòng)的地方

磁盤(pán)商通常用術(shù)語(yǔ)柱面(cylinder)描述多個(gè)盤(pán)片。的構(gòu)造土匀。

柱面是所有盤(pán)片表面上到主軸中心的距離相等的磁道集合子房。

例如，一個(gè)驅(qū)動(dòng)器有三個(gè)盤(pán)片就轧，六個(gè)面证杭。那么柱面k是六個(gè)磁道k的集合。

6.1.2.2 磁盤(pán)容量

遠(yuǎn)古時(shí)期妒御，磁道上的扇區(qū)是固定的解愤，所以扇區(qū)的數(shù)目由靠?jī)?nèi)磁道能記錄的扇區(qū)數(shù)決定。

現(xiàn)在通過(guò)多區(qū)記錄技術(shù)乎莉。

在這種技術(shù)中送讲，柱面的集合被分割為不可相交的子集合奸笤，稱(chēng)為記錄區(qū)。

每個(gè)區(qū)包含一組連續(xù)的柱面哼鬓。

一個(gè)區(qū)的每個(gè)柱面都有相同的扇區(qū)數(shù)监右。

扇區(qū)數(shù)也是由一個(gè)區(qū)最里面磁道的扇區(qū)數(shù)決定。

下面給出一個(gè)容量計(jì)算公式异希。

G健盒，M,K大小依賴(lài)于上下文，磁盤(pán)和RAM中所對(duì)應(yīng)的大小一般不同宠互。

6.1.2.3 磁盤(pán)操作

6.1.3 固態(tài)硬盤(pán)?

固態(tài)硬盤(pán)（Solid State Disk味榛，SSD）是一種基于閃存的存儲(chǔ)技術(shù)，在某些情況下是傳統(tǒng)旋轉(zhuǎn)磁盤(pán)的極有吸引力的替代品予跌。

6.1.4 存儲(chǔ)技術(shù)趨勢(shì)?

不同的存儲(chǔ)技術(shù)有不同的價(jià)格和性能折中搏色。SRAM比DRAM快一點(diǎn)，而DRAM比磁盤(pán)要快很多券册。另一方面频轿，快速存儲(chǔ)總是比慢速存儲(chǔ)要貴的。SRAM每字節(jié)的造價(jià)比DRAM高烁焙，DRAM的造價(jià)又比磁盤(pán)高很多航邢。SSD位于DRAM和旋轉(zhuǎn)磁盤(pán)之間。

6.2 局部性

局部性(locality):傾向于引用臨近于其他最近引用過(guò)的數(shù)據(jù)項(xiàng)的數(shù)據(jù)項(xiàng)骄蝇∩乓螅或者最近引用過(guò)的數(shù)據(jù)項(xiàng)本身。

這種傾向被稱(chēng)為局部性原理九火，是一個(gè)持久的概念赚窃，對(duì)硬件，軟件設(shè)計(jì)都有極大影響岔激。

局部性通常有兩種不同的形式:

時(shí)間局部性(temporal locality).

被引用過(guò)一次的存儲(chǔ)器很可能在不遠(yuǎn)的將來(lái)再被多次引用勒极。

空間局部性(spatial locality).

一個(gè)存儲(chǔ)位置被引用了一次，在不遠(yuǎn)的將來(lái)虑鼎，很可能引用附近的位置辱匿。

現(xiàn)代計(jì)算機(jī)系統(tǒng)各個(gè)層次都利用了局部性。

硬件層炫彩，局部性原理允許計(jì)算機(jī)設(shè)計(jì)者引入高速緩存存儲(chǔ)器匾七。

保存最近被引用的指令和數(shù)據(jù)項(xiàng)，從而提高對(duì)主存的訪問(wèn)速度媒楼。

操作系統(tǒng)級(jí)

局部性原理允許使用主存作為虛擬地址空間最近被引用塊的高速緩存乐尊。

利用主存緩存磁盤(pán)文件系統(tǒng)最近使用的磁盤(pán)塊。

應(yīng)用程序設(shè)計(jì)

Web瀏覽器將最近被引用的文檔放到本地磁盤(pán)上划址，利用的就是時(shí)間局部性扔嵌。

6.2.1 對(duì)程序數(shù)據(jù)引用的局部性

考慮這個(gè)簡(jiǎn)單函數(shù)的局部性限府。

sum具有良好的時(shí)間局部性

在一段時(shí)間內(nèi)被多次訪問(wèn)。

v數(shù)組具有良好的空間局部性痢缎。

一段時(shí)間內(nèi)臨近的元素被多次訪問(wèn)

所以該程序具有良好的局部性胁勺。

像sumvec這樣順序訪問(wèn)一個(gè)向量中每個(gè)元素的函數(shù)，稱(chēng)為具有步長(zhǎng)為1的引用模式(stride-1 reference pattern)独旷。

有時(shí)稱(chēng)步長(zhǎng)為1的引用模式叫做順序引用模式署穗。

每隔k個(gè)訪問(wèn)，叫做步長(zhǎng)為k的引用模式嵌洼。

步長(zhǎng)為1的引用模式是空間局部性常見(jiàn)和最重要的來(lái)源案疲。

步長(zhǎng)越大，空間局部性越低麻养。

對(duì)于二維數(shù)組褐啡，兩種不同的循環(huán)方式，空間局部性的差異十分大鳖昌。

行優(yōu)先順序备畦，是最好的。

6.2.2 取指令的局部性

因?yàn)槌绦蛑噶畋环旁诖鎯?chǔ)器中许昨，CPU需要讀出這些指令懂盐，所以也能取指令的局部性。

順序執(zhí)行:良好的空間局部性糕档。

for: 良好的時(shí)間局部性莉恼。

代碼區(qū)別于數(shù)據(jù)的地方，執(zhí)行后速那，不會(huì)被修改溪食。

6.2.3 小結(jié)

在我們學(xué)習(xí)了高速緩存存儲(chǔ)器以及它們是如何工作的之后始鱼，我們會(huì)介紹如何用高速緩存命中率和不命中率來(lái)量化局部性的概念。

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

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

一般而言亭螟，高速緩存是一個(gè)小而快速的存儲(chǔ)設(shè)備残家，它作為存儲(chǔ)在更大榆俺，也更慢的設(shè)備中的數(shù)據(jù)對(duì)象的緩沖區(qū)域。使用高速緩存的過(guò)程稱(chēng)為緩存坞淮。

存儲(chǔ)器層次結(jié)構(gòu)的中心思想是:層次結(jié)構(gòu)中的每一層都是來(lái)自較低一層的緩存茴晋。

第k+1層被分為連續(xù)的數(shù)據(jù)對(duì)象片(chunk),稱(chēng)為塊(block)。

數(shù)據(jù)總是以塊作為傳送單元回窘，在存儲(chǔ)層間诺擅。

傳輸一個(gè)字節(jié)，和傳輸一個(gè)塊的時(shí)間上差不多

塊使空間局部性得到發(fā)揮

緩存命中

緩存不命中

替換/驅(qū)逐塊

犧牲塊

替換策略

隨機(jī)替換策略

最近最少被使用替換策略(LRU)

緩存不命中的種類(lèi)

一個(gè)空的緩存稱(chēng)為冷緩存

此時(shí)的不命中叫做冷不命中啡直，強(qiáng)制性不命中烁涌。

短暫的事件苍碟。

在緩存熱身后的穩(wěn)定狀態(tài)不會(huì)出現(xiàn)。

沖突不命中

限制性的放置策略中可能出現(xiàn)

容量不命中

工作集超過(guò)緩存大小撮执。

緩存管理

管理緩存可以是硬件微峰，也可以是軟件，可以是兩者的結(jié)合抒钱。

寄存器文件:編譯器管理.

L1蜓肆，L2，L3:內(nèi)置在緩存中的硬件邏輯管理谋币。

DRAM仗扬，內(nèi)存由地址翻譯硬件和操作系統(tǒng)共同管理。

本地磁盤(pán): 由軟件管理蕾额。

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

基于緩存的結(jié)構(gòu)行之有效早芭。

較慢的存儲(chǔ)器比塊的存儲(chǔ)器便宜。

能很好利用局部性凡简。

利用時(shí)間局部性:由于時(shí)間局部性逼友，同一數(shù)據(jù)對(duì)象可能被多次使用，一旦一個(gè)數(shù)據(jù)對(duì)象在第一次不命中時(shí)被拷貝到緩存中秤涩，我們就會(huì)期望后面對(duì)該目標(biāo)有一些的緩存命中帜乞。

利用空間局部性:塊通常包含多個(gè)數(shù)據(jù)對(duì)象，由于空間局部性筐眷，我們希望對(duì)該塊中其他對(duì)象節(jié)約的訪問(wèn)時(shí)間補(bǔ)償不命中時(shí)的拷貝時(shí)間黎烈。

6.4 高速緩存存儲(chǔ)器

6.4.1 通用的高速緩存存儲(chǔ)器結(jié)構(gòu)。

S個(gè)高速緩存組匀谣。

每個(gè)組有E個(gè)高速緩存行

每行是由一個(gè)B=2^b字節(jié)的數(shù)據(jù)塊組成的照棋，一個(gè)有效位，還有t=m-(b+s)個(gè)標(biāo)記位武翎。

m:地址長(zhǎng)度

高速緩存的結(jié)構(gòu)可以用元組(S,E,B,m)描述烈炭。

高速緩存的大小C指所有塊大小的和。標(biāo)記位和有效位不包括在內(nèi)宝恶。

C=S*E*B;

高速緩存如何尋址(以地址A)?

S->標(biāo)記位->塊偏移

對(duì)應(yīng)組選擇符隙，行匹配，字抽取

6.4.2 直接映射高速緩存

根據(jù)E高速緩存分為不同的類(lèi)

E=1時(shí)叫直接映射高速緩存

E>1時(shí)叫組相連高速緩存

S=1時(shí)叫全相連高速緩存

抽取請(qǐng)求字的過(guò)程垫毙，分為三步:

組選擇

行匹配

字抽取

不命中時(shí)

行替換

過(guò)于簡(jiǎn)單就不詳細(xì)描述了霹疫。

直接映射高速緩存中的沖突不命中

如果x[i]與y[i]恰好在同一個(gè)高速緩存組。

會(huì)不停的沖突不命中综芥。

在x和y塊之間不停的抖動(dòng)丽蝎。

抖動(dòng)描述的就是，高速緩存反復(fù)加載和驅(qū)逐相同的高速緩存塊膀藐。

避免方法

改變x數(shù)組大小屠阻。

組相連高速緩存

為什么用中間的位來(lái)做索引红省。

如果用高位作索引，那么組內(nèi)的數(shù)據(jù)在物理地址也是相鄰的栏笆。不能充分利用空間的局部性类腮。

6.4.3 組相連高速緩存

一個(gè)1<E<C/B的高速緩存通常稱(chēng)為E路組相連高速緩存。

組相連高速緩存中的組選擇

與之前的一樣蛉加，通過(guò)組索引位蚜枢。

組相連高速緩存中的行匹配和字選`。

有效位和標(biāo)記位

組相連高速緩存中不命中時(shí)的行替換

隨機(jī)

最不常用(Least-Frequently-Used,LFU)

頻數(shù)最低

最近最少使用(Least-Recently-Used,LRU)

時(shí)間最久遠(yuǎn)

6.4.4 全相連高速緩存

一個(gè)全相聯(lián)高速換粗(full associative cache)是由一個(gè)包含所有高速緩存行的組(即E=C/B)組成的针饥。

全相連的組選擇

只有一個(gè)組沒(méi)啥好說(shuō)的

全相連的行匹配和子選擇

和組相連一樣厂抽，但是規(guī)模更大。

所以只適用于做小的高速緩存

如TLB丁眼，緩存頁(yè)表項(xiàng)

6.4.5 有關(guān)寫(xiě)的問(wèn)題

處理寫(xiě)命中:

直寫(xiě):立即將w的高速緩存塊寫(xiě)會(huì)到緊接著的下一層筷凤。

優(yōu)點(diǎn):簡(jiǎn)單

缺點(diǎn):引起總線流量，速度慢

寫(xiě)回:盡可能地推遲操作苞七，只有當(dāng)替換算法要驅(qū)逐時(shí)更新藐守。

優(yōu)點(diǎn):減少總線流量。

缺電:復(fù)雜蹂风，額外維護(hù)一個(gè)修改位卢厂。

處理寫(xiě)不命中

寫(xiě)分配:加載相應(yīng)的低一層塊到高速緩存中，然后更新這個(gè)高速緩存塊惠啄。

跟寫(xiě)回搭配慎恒。

寫(xiě)不分配:直接寫(xiě)到低層。

跟直寫(xiě)搭配撵渡。

6.4.6 一個(gè)真實(shí)的高速緩存層次結(jié)構(gòu)的解剖

高速緩存融柬，指令，數(shù)據(jù)

只保存指令的高速緩存叫做i-cache

只保存程序數(shù)據(jù)的高速緩存叫做d-cache

兩者都保存的高速緩存叫做unified cache

6.4.7 高速緩存參數(shù)的性能影響

不命中率(miss rate):不命中數(shù)量/引用數(shù)量趋距。

命中率(hit rate): 1-不命中率粒氧。

命中時(shí)間(hit time): 從高速緩存?zhèn)魉鸵粋€(gè)字到CPU的時(shí)間。

不命中處罰(miss penalty):由于不命中的額外時(shí)間节腐。

L1:10

L2:40

L3:100

優(yōu)化高速緩存的成本和性能的折中是一項(xiàng)很精細(xì)的工作靠欢，這里只能簡(jiǎn)單討論。

高速緩存大小的影響

提高命中率

增加命中時(shí)間

塊大小的影響

更好利用空間局部性铜跑，提高命中率

影響時(shí)間局部性

不命中處罰越長(zhǎng)

現(xiàn)代系統(tǒng)一般在32~64字節(jié)中。

相連度影響

降低了高速緩存中的抖動(dòng)的可能性

好的替換策略能大大增強(qiáng)效率(提高命中率)骡澈。

價(jià)格更昂貴锅纺，命中時(shí)間更長(zhǎng)，不命中處罰更多肋殴。

所以是處罰時(shí)間((1-命中率)*不命中處罰)和命中時(shí)間的折中囤锉。

不命中處罰越高用這個(gè)坦弟。讓處罰時(shí)間更少

命中率提高

不命中處罰增長(zhǎng)忽略不計(jì)。

寫(xiě)策略影響

層次越往下官地，越用寫(xiě)回酿傍。

6.5 編寫(xiě)高速緩存友好代碼

與之前6.2.1 類(lèi)似的介紹

對(duì)局部變量反復(fù)利用

步長(zhǎng)為1的循環(huán)

二維數(shù)組，先行遍歷

6.6 綜合:高速緩存對(duì)程序性能的影響

6.6.1 存儲(chǔ)器山

一個(gè)程序從存儲(chǔ)系統(tǒng)中讀數(shù)據(jù)的速率稱(chēng)為讀吞吐量(read throughput),或者有時(shí)稱(chēng)為讀帶寬(rand bandwidth)驱入。

通過(guò)讀吞吐量來(lái)分析存儲(chǔ)器性能赤炒。

存儲(chǔ)器山是一種綜合研究存儲(chǔ)器層次結(jié)構(gòu)的工具。它反映了存儲(chǔ)器層次結(jié)構(gòu)中不同層次的帶寬亏较。也反映了具有不同的時(shí)間局部性與空間局部性的程序的性能莺褒。通過(guò)分析存儲(chǔ)器山的數(shù)據(jù)，還可以看出存儲(chǔ)器系統(tǒng)的部分硬件參數(shù)雪情。

6.6.2 重新排列循環(huán)以提高空間局部性

考慮n*n的矩陣乘法問(wèn)題遵岩。

C[i][j]+=A[i][k]*B[k][j]

i,j,k三層循環(huán)的順序無(wú)所謂，都能得到正確的結(jié)果巡通。

但是時(shí)間差異卻十分大尘执。

顯然能看出kij版本和ikj版本都十分優(yōu)秀

tisp:r=A[i][k]在i,k循環(huán)或k,i循環(huán)下，其實(shí)差不了多少宴凉，因?yàn)閚次循環(huán)才調(diào)用一次誊锭。

也因此上圖左右相鄰的兩個(gè)版本的復(fù)雜度都會(huì)差不多。

網(wǎng)絡(luò)旁注;使用分塊來(lái)提高空間局部性

就是類(lèi)似將數(shù)據(jù)結(jié)構(gòu)盡量設(shè)計(jì)成塊跪解。能提高效率炉旷，但會(huì)使得代碼更難懂。它更適合優(yōu)化編譯器或者頻繁執(zhí)行的庫(kù)函數(shù)叉讥。

6.6.3 在程序中利用局部性

精力注重內(nèi)循環(huán)

步長(zhǎng)為1,

一旦讀入一個(gè)對(duì)象窘行，就盡可能多使用它。

6.7 小結(jié)

基本存儲(chǔ)技術(shù)包括RAM,ROM和磁盤(pán)图仓。

RAM有兩個(gè)類(lèi)型