數(shù)據(jù)庫(kù)系統(tǒng)工程師知識(shí)點(diǎn)精講之高速緩沖存儲(chǔ)器

1、數(shù)據(jù)庫(kù)系統(tǒng)工程師知識(shí)點(diǎn)精講之高速緩沖存儲(chǔ)器高速緩沖存儲(chǔ)器Cache的功能是提高 CPU數(shù)據(jù)輸入輸出的速率，突破所謂的“馮•諾依曼瓶頸”，即CPU與存儲(chǔ)系統(tǒng)間數(shù)據(jù)傳送帶寬限制。高速存儲(chǔ)器能以極高的速率進(jìn)行數(shù)據(jù)的訪(fǎng) 問(wèn)，但因其價(jià)格高昂，如果計(jì)算機(jī)的內(nèi)存完全由這種高速存儲(chǔ)器組成則會(huì)大大增加計(jì)算機(jī)的 成本。通常在 CPU和內(nèi)存之間設(shè)置小容量的高速存儲(chǔ)器Cache。Cache容量小但速度快，內(nèi)存速度較低但容量大，通過(guò)優(yōu)化調(diào)度算法，系統(tǒng)的性能會(huì)大大改善，仿佛其存儲(chǔ)系統(tǒng)容量與內(nèi)存相當(dāng)而訪(fǎng)問(wèn)速度近似Cache。1 . Cache基本原理使用Cache改善系統(tǒng)性能的依據(jù)是程序的局部性原理。依

2、據(jù)局部性原理，把內(nèi)存中訪(fǎng)問(wèn)概率高的內(nèi)容存放在 Cache中，當(dāng)CPU需要讀取數(shù)據(jù)時(shí)首先在Cache中查找是否有所需內(nèi)容，如果有，則直接從Cache中讀??；若沒(méi)有，再?gòu)膬?nèi)存中讀取該數(shù)據(jù)，然后同時(shí)送往CPU和Cache。如果CPU需要訪(fǎng)問(wèn)的內(nèi)容大多都能在Cache中找到（稱(chēng)為訪(fǎng)問(wèn)命中），則可以大大提高系統(tǒng)性能。如果以h代表對(duì)Cache的訪(fǎng)問(wèn)命中率（“ 1-h ”稱(chēng)為失效率，或者稱(chēng)為未命中率 ）,t1 表示Cache的周期時(shí)間，t2表示內(nèi)存的周期時(shí)間，以讀操作為例，使用“ Cache+主存儲(chǔ) 器”的系統(tǒng)的平均周期為 t3，則：3 二彳 x 右 + 爲(wèi) x （1 A）計(jì)算機(jī)硬件基礎(chǔ)系統(tǒng)的平均存儲(chǔ)周期與

3、命中率有很密切的關(guān)系，命中率的提高即使很小也能導(dǎo)致性能上的較大改善。例如：設(shè)某計(jì)算機(jī)主存的讀 /寫(xiě)時(shí)間為100ns，有一個(gè)指令和數(shù)據(jù)合一的Cache，已知該Cache的讀/寫(xiě)時(shí)間為10ns ,取指令的命中率為 98% ,取數(shù)的命中率為 95%。在執(zhí)行 某類(lèi)程序時(shí)，約有1/5指令需要存/取一個(gè)操作數(shù)。假設(shè)指令流水線(xiàn)在任何時(shí)候都不阻塞， 則設(shè)置Cache后，每條指令的平均訪(fǎng)存時(shí)間約為：（2% X100ns+98% X10ns）+1/5 X（5% X100ns+95% X10ns）=14.7ns2 映射機(jī)制當(dāng)CPU發(fā)出訪(fǎng)存請(qǐng)求后，存儲(chǔ)器地址先被送到Cache控制器以確定所需數(shù)據(jù)是否已在Cache中，

4、若命中則直接對(duì) Cache進(jìn)行訪(fǎng)問(wèn)。這個(gè)過(guò)程稱(chēng)為 Cache的地址映射（映像）。 在Cache的地址映射中，主存和Cache將均分成容量相同的塊（頁(yè)）。常見(jiàn)的映射方法有直接映射、全相聯(lián)映射和組相聯(lián)映射。（1 ）直接映射。直接映射方式以隨機(jī)存取存儲(chǔ)器作為Cache存儲(chǔ)器，硬件電路較簡(jiǎn)單。直接映射是一種多對(duì)一的映射關(guān)系，但一個(gè)主存塊只能夠復(fù)制到Cache的一個(gè)特定位置上去。Cache的塊號(hào)i和主存的塊號(hào)j有函數(shù)關(guān)系：i=j%m （其中m為Cache總塊數(shù)）例如，某Cache容量為16KB （即可用14位表示），每塊的大小為16B （即可用4位表示），則說(shuō)明其可分為1024塊（可用10位表示）。則主

5、存地址的最低 4位為Cache的塊內(nèi)地址，然后接下來(lái)的中間10位為Cache塊號(hào)。如果內(nèi)存地址為1234E8F8H 的話(huà)（一 共32位），那么最后4位就是1000 （對(duì)應(yīng)十六進(jìn)制數(shù)的最后一位“8”），而中間10位,則應(yīng)從 E8F （）中獲取，得到1010001111。因此，內(nèi)存地址為1234E8F8H的單元裝入的 Cache地址為。直接映射方式的優(yōu)點(diǎn)是比較容易實(shí)現(xiàn)，缺點(diǎn)是不夠靈活，有可能使Cache的存儲(chǔ)空間Cache 。得不到充分利用。例如，假設(shè)Cache有8塊，則主存的第1塊與第17塊同時(shí)復(fù)制到 Cache的第1頁(yè)，即使Cache其他頁(yè)面空閑，也有一個(gè)主存頁(yè)不能寫(xiě)入（2） 全相聯(lián)映射。全相

6、聯(lián)映射使用相聯(lián)存儲(chǔ)器組成的Cache存儲(chǔ)器。在全相聯(lián)映射 方式中，主存的每一頁(yè)可以映射到 Cache的任一頁(yè)。如果淘汰 Cache中某一頁(yè)的內(nèi)容，則 可調(diào)入任一主存頁(yè)的內(nèi)容，因而較直接映射方式靈活。在全相聯(lián)映射方式中，主存地址不能直接提取 Cache頁(yè)號(hào)，而是需要將主存頁(yè)標(biāo)記與 Cache各頁(yè)的標(biāo)記逐個(gè)比較，直到找到標(biāo)記符合的頁(yè)（訪(fǎng)問(wèn) Cache命中），或者全部比較 完后仍無(wú)符合的標(biāo)記（訪(fǎng)問(wèn) Cache失?。?。因此這種映射方式速度很慢，失掉了高速緩存 的作用，這是全相聯(lián)映射方式的最大缺點(diǎn)。如果讓主存頁(yè)標(biāo)記與各Cache標(biāo)記同時(shí)比較，則成本又太高。全相聯(lián)映射方式因比較器電路難于設(shè)計(jì)和實(shí)現(xiàn)，只適用

7、于小容量Cache。（3） 組相聯(lián)映射。組相聯(lián)映射是直接映射和全相聯(lián)映射的折中方案。它將Cache中的塊再分成組，通過(guò)直接映射方式?jīng)Q定組號(hào)，通過(guò)全相聯(lián)映射的方式?jīng)Q定 Cache中的塊號(hào)。 在組相聯(lián)映射方式中，主存中一個(gè)組內(nèi)的塊數(shù)與Cache的分組數(shù)相同。例如，容量為64塊的Cache采用組相聯(lián)方式映像，每塊大小為128個(gè)字，每4塊為一組。若主存容量為4096塊，且以字編址，那么主存地址應(yīng)該為多少位？主存區(qū)號(hào)（組號(hào)）為多少位？這樣的題目，首先根據(jù)主存與Cache塊的容量需一致，既每個(gè)內(nèi)存塊的大小也是128個(gè)字，因此共有 1284096個(gè)字（219個(gè)字），即主存地址需要19

8、位。因?yàn)镃ache的容量為64塊，所以?xún)?nèi)存需要分為 4096/64個(gè)組，即26，因此主存組號(hào)需 6 位。在組相聯(lián)映射中，由于Cache中每組有若干可供選擇的頁(yè)， 因而它在映射定位方面較 直接映射方式靈活；每組頁(yè)數(shù)有限，因此付出的代價(jià)不是很大， 可以根據(jù)設(shè)計(jì)目標(biāo)選擇組內(nèi) 頁(yè)數(shù)。3 淘汰算法CPU和Cache。但是當(dāng)Cache產(chǎn)生了一次訪(fǎng)問(wèn)未命中之后，相應(yīng)的數(shù)據(jù)應(yīng)同時(shí)讀入 當(dāng)Cache已存滿(mǎn)數(shù)據(jù)后，新數(shù)據(jù)必須淘汰 Cache中的某些舊數(shù)據(jù)。 最常用的淘汰算法有隨 機(jī)淘汰法、先進(jìn)先出法(FIFO )和近期最少使用淘汰法(LRU)。其中平均命中率最高的 是LRU算法。4 .寫(xiě)操作因?yàn)樾枰ＷC緩存在Cache中的數(shù)據(jù)與內(nèi)存中的內(nèi)容一致，相對(duì)讀操作而言，Cache的寫(xiě)操作比較復(fù)雜，常用的有以下幾種方法。(1) 寫(xiě)直達(dá)(writethrough )。當(dāng)要寫(xiě)Cache時(shí)，數(shù)據(jù)同時(shí)寫(xiě)回內(nèi)存，有時(shí)也稱(chēng)為 寫(xiě)通。(2) 寫(xiě)回(writeback )。CPU修改Cache的某一行后，相應(yīng)的數(shù)據(jù)并不立即寫(xiě)入內(nèi)存單元，而是當(dāng)該行從Cache中被淘汰時(shí)，才把數(shù)據(jù)寫(xiě)回到內(nèi)存中。(3) 標(biāo)記法。對(duì) Cache中的每一