如下是一道關于高速緩存的經典題目:
假定主存位址位數為 32 位,按位元組編址,主存和 cache 之間采用全相聯映射方式,主存塊大小為一個字,每字 32 位,采用回寫( Write Back )方式和随機替換政策,則能存放 32K 字資料的 cache 的總容量至少應有多少位?
如果不了解高速緩存的原理,看到這個題大機率會懵住。答案在最後,暫時先不看這道題,來複習一下CSAPP第6章。
一、存儲器技術
1. 随機通路存儲器(RAM)
易失性存儲器:可分為靜态RAM(SRAM)和動态RAM(DRAM)。
- SRAM是用六半導體電路實作,比較穩定,存取速度較快但價格貴,多用于高速緩存存儲器;
- DRAM以充電電容和通路半導體實作,并不十分穩定,其自然的維持時間很短,是以需要記憶體系統周期性的讀出并重寫來重新整理每一位。功耗大于SRAM,速度低于SRAM但價格低,多用于主存。
非易失性存儲器:隻讀存儲器(ROM),閃存,固态硬碟(SSD)。
2. 磁盤存儲
2.1 總線結構:
如圖,CPU、主存、I/O裝置通過I/O橋互相連接配接。CPU與I/O橋之間的總線叫系統總線,主存與I/O橋之間的總線叫記憶體總線,外部I/O裝置通過I/O總線連接配接到I/O橋。I/O橋的作用是信号翻譯和傳遞。
2.2 磁盤構造
如圖是旋轉磁盤的構造示意圖。主要有以下幾部分:
- 盤片:磁盤由盤片構成。
- 表面:每個盤片有兩個表面。
- 磁道:每個表面上分布着一組同心圓叫磁道。
- 扇區:每個磁道被劃分為若幹扇區,每個扇區包含相等的資料位(通常為512位元組)。磁盤以扇區大小的塊來讀寫資料。
- 磁道:每個表面上分布着一組同心圓叫磁道。
- 表面:每個盤片有兩個表面。
- 主軸:盤片中央可以旋轉的軸,使得盤片以固定速率旋轉,通常是5400~15000轉每分鐘(RPM)。
- 讀寫頭:用來讀寫儲在磁性表面的位。
磁盤通常會帶有一個控制電路,整個裝置叫磁盤驅動器,簡稱磁盤。
2.3 扇區的通路時間
對扇區的通路時間有三個主要部分:
- 尋道時間:傳動臂将讀寫頭定位到包含目标扇區的磁道上所需的時間。
- 旋轉時間:驅動器等待目标扇區旋轉到讀寫頭下所需的時間。平均旋轉時間是旋轉一周耗時的一半。
- 傳送時間:目标扇區在讀寫頭下經過的時間。
二、存儲器層次結構
存儲器層次結構的核心思想:對于每個k,位于k層的更快更小的儲存設備作為位于k+1層的更大更慢的儲存設備的緩存。
三、 高速緩存存儲器(關鍵)
高速緩存存儲器位于CPU和主存之間,其出現的原因是CPU和主存之間的性能差距越來越大。通用的高速緩存存儲器的組織結構如下:
假設計算機系統的記憶體位址長m位,其可表示的位址個數為
2^m
個。其位址可按上圖劃分為3部分:t位長的标志部分,s位長的索引部分和b位長的偏移部分。是以有恒定關系m = t + s + b。(該劃分并不考慮位址的意義,隻是單純地将它當做無符号整數,其劃分為這幾部分,隻是用來定位緩存存儲器内的資料)
如圖,高速緩存存儲器被組織為S個組,每個組有E個行,每個行有1個塊,每個塊有
2^b
個位元組。每行除了有一個塊以外,還有一些額外的資訊:
- 有效位(必須):用來标記該行的資料是否有效。長1位。
- 标記(必須):用來對行唯一定位,與對應位址中t位長的标記部分一緻。很明顯該标記長為t位。
- 髒位(可選):用來說明該行是否被修改,以便在緩存換出時決定是否要寫回磁盤。長1位。
在m位長的位址中,t位長的标志部分用來唯一确定存儲器的E個行中的一行,s位長的索引部分用于唯一确定S個組中的一個,b個位長的偏移部分用來定位塊中的位元組。
由位址查找緩存資料的步驟:給定一個位址,首先看位址中的索引部分,找到高速緩存對應的組,其有效位是1(如果是0說明緩存不命中,這時要去記憶體尋找資料,并替換某個緩存行),再看位址中的t位長的标記部分,對應組中逐個比對,直到找到行中标志部分與位址标志部分相同的行(找不到也說明緩存不命中),再看位址中的b位長的偏移部分,将對應的高速緩存行中的塊偏移一定值,傳回給CPU。這時是緩存命中。
1. 直接映射高速緩存
直接映射高速緩存:每組隻有一行(E = 1)的高速緩存。
2. 組相聯高速緩存
組相聯高速緩存:每個組有多于1個的行。
3. 全相聯高速緩存
全相聯高速緩存:隻有一個組,該組包含所有高速緩存行。适合做小的高速緩存,如翻譯後備緩沖器(TLB)。
再來看下開頭的題目:
32bit位址空間按位元組編址,主存中每個塊大小為1個字,每個字大小為32位=4Byte。
全相聯cache中隻有一個組,每組有若幹行,每行含一個塊,以及長1的有效位,長1的髒位(題上要求寫回方式),長為t的标記位(用來定行每行塊内位元組)。
由于每個塊長為1個字=32位=4Byte,4Byte的塊需要用到2個二進制位的偏移來定位(是以b = 2),也就是t = m - b = 32 - 2 = 30,這麼一來每一行的非資料位有30(标記位)+ 1(有效位) + 1(髒位)= 32位。
要緩存存32K字資料,而該cache中每行存一個塊=1字,是以最少需要有32K行,每行裡的非資料位有32位,資料位為1字=32位,相當于每行占64位,共有32K行,總存儲位數應該最少為32K*64=2048K。
2019/10/14 15:57