讀書筆記：CSAPP第6章-存儲器層次結構

如下是一道關于高速緩存的經典題目：

假定主存位址位數為 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