2020-09-18

CSAPP 和 CMU Introduction to computer system (CS 15-213 2015 fall) 的筆記。

相關資料

1. Textbook
2. 在vscode上使用C

6.The-Memory-Hierarchy

由于計算機通路不同層次的結構的存儲器時間不同，了解存儲器層次結構，對程式的性能有巨大影響。整章的關鍵思想是局部性（locality），指程式傾向于通路相同的資料集或者鄰近的資料集。

Storage technologies and trends

Random-­Access Memory （RAM）

随機通路存儲器，分為靜态的SRAM和動态的DRAM，SRAM更快更貴，通路速度快10倍。

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-SEiFjRvo-1600419118110)(https://s1.ax1x.com/2020/09/13/w0LjLq.png)]

NonvolaCle Memories

非易失性存儲器，即斷電後仍然可以儲存資訊，整體上稱為ROM（隻讀存儲器）。

Uses for NonvolaCle Memories

1. bios，網卡，磁盤控制器，gpu，
2. ssd（solid state disks）
3. 磁盤緩存

Traditional Bus Structure Connecting CPU and Memory

通過總線（bus）

disk

磁盤廣泛應用的大量資料儲存設備。

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-NKABPy9k-1600419118116)(https://s1.ax1x.com/2020/09/14/wBqPIO.png)]

由于現代磁盤構造複雜，有多個盤面，盤面上有不同的記錄區。于是就有了邏輯分區，存儲在磁盤控制器上的映射（surface， track， sector）

I/O Bus

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-4P2DEcak-1600419118118)(https://s1.ax1x.com/2020/09/14/wBOEDI.png)]

IO總線與底層cpu無關，盡管比系統總線，記憶體總線慢，但相容更多的第三方裝置。

SSD

SSD是基于閃存的存儲技術，是傳統旋轉磁盤的有力替代品。（快，貴）

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-0UyPBw2n-1600419118120)(https://s1.ax1x.com/2020/09/14/wBjCXd.png)]

1. 一個閃存有塊（block）和頁（plage）組成。
2. 資料以頁為機關讀寫，讀比寫快。(擦除時間較長)
3. 隻有在一頁完全擦除後才能寫入。
4. 一個塊大約可以進行100000詞重複寫。

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-XyBZDKQ2-1600419118122)(https://s1.ax1x.com/2020/09/14/wrROFs.png)]

Locality of reference

局部性通常分為兩種不同的形式。

1. 時間局部性（temporal locality）：被引用過一次的記憶體位置很可能在不遠的将來被再次引用。
2. 空間局部性（spatial locality）：被引用過的記憶體位置附近很可能被再次引用。

data reference

1. 數組按序通路（spatial）
2. 對一個變量重複引用（temporal）

instruction reference

1. 循環體内的指令（spatial）
2. 循環被執行多次（temporal）

Caching in the memory hierarchy

由于存儲技術硬體的差異和程式局部性的特性，計算機科學家設計了組織存儲器系統的方法——存儲器層次結構。

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-7LdoCWtu-1600419118123)(https://s1.ax1x.com/2020/09/14/wrhmZD.png)]

每一層的緩存都源自于上一層。越往上，越小，越快。

通過這樣的層次結構，用便宜的儲存器在底部構造了大的儲存池，但程式的資料處理速度接近頂部的緩存。（這樣做能成是因為局部性）

types of cache misses

1. cold miss：當cache空的時候
2. conflict miss：因為硬體緩存采用嚴格的放置政策（随機放置定位成本太高）k+1層的某個塊放置在k層的塊中，會導緻對象被映射到同意個塊中，一直不命中。
3. capacity miss：緩沖塊不夠大。

Cache memory organization and operation

緩沖器結構

怎麼看位址，tag是在行中定位（E）定位，set index 是在塊中定位（S），b是偏移量。

為什麼用中間的位做索引：因為可以避免連續的位址映射到同一個緩存區（conflict miss）

置換的原則通常是LRU（least recently used）

write

命中時的寫入分兩種

1. write-through：立刻寫入記憶體
2. write-back：寫入緩存，等被更換時再寫入記憶體。

不命中的寫入

1. write-allocate：讀進緩存，更新緩存
2. 直接寫入記憶體。

緩存的性能

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-LTUYZNfd-1600419118126)(https://s1.ax1x.com/2020/09/14/wrLau9.png)]

Performance impact of caches

全書的封面，memory mountain，程式以步長stride掃描數組頭elems個元素來産生讀序列。然後傳回測試出的吞吐量。

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-u1IhWx7k-1600419118128)(https://s1.ax1x.com/2020/09/14/wsPHnf.png)]

Rearranging loops to improve spacial locality

通過調整矩陣循環的順序提高空間局部性，其中典型的是矩陣乘法。

C語言數組的存儲是行存儲。對一個矩陣，行周遊的miss rate 是1/B當矩陣次元大于bolcksize的時候。但列周遊的話是1.

C i j = ∑ k a i k ∗ b k j C_{ij} = \sum_k a_{ik} * b_{kj} Cij​=k∑​aik​∗bkj​

這裡b會涉及到列周遊。通過把k放在循環最頂層，消除列周遊。

Using blocking to improve temporal locality

通過塊的方法，提高時間局部性。

将資料分成一塊塊的，使得整塊載入緩存計算，完成所有讀寫，然後下一個塊。但是代碼非常難寫。