# 〈What Every Programmer Should Know About Memory〉閱讀筆記
## Ch3 CPU Caches
### Ch 3.2 Cache Operation at High Level
#### Memory address map to cache line
- O: as the offset into the cache line
- S: select the cache set
- T: distinguish all the cache lines in the same cache set
#### inclusive cache v.s. exclusive cache
- inclusive cache：
- L1 快取中的所有資料也會出現在 L2 快取中。同樣地，L2 快取中的所有資料也會出現在 L3 快取中。
- 管理簡單，但是浪費空間，因為每一級快取都要存儲同樣的資料
- 從 L1d 驅逐 (eviction) 資料的速度比 exclusive 快
- exclusive cache：
- 各級快取中的資料是不重複的。也就是說，L1 快取中的資料不會出現在 L2 快取中，L2 快取中的資料不會出現在 L3 快取中。
- 最大化了每一級快取的存儲容量，減少了資料的冗餘
- 從記憶體載入新資料的速度會比 inclusive cache 快 (直接 load 到 L1 不需要經過 L2)

#### symmetric multi-processor (SMP) systems 的 cache coherency
- 目的: SMP 中的每個處理器需要在任何時間點都能看到相同的記憶體內容，但是每個處理器都各自對應一個獨立的快取，因此需要使用快取一致性 (Cache coherence) 的機制讓快取之間取得的資料內容同步。
- 方法
- 處理器可以偵測是否有其他處理器想要去讀取或寫入某個快取行
- 偵測到寫入操作: 把此處理器的該快取行標示為 invalid (如果此快取行副本存在此處理器的快取當中的話)，以後要存取時必須重新載入資料
- 偵測到讀取操作: 不需要做任何改變
- 更複雜的實作方式
- 假設處理器 A 的某個快取行是 dirty 的，處理器 B 想要去讀取或寫入該快取行
- 此時記憶體中的資料還是舊的
- 利用 snooping — 處理器 A 可以主動地將資料直接傳給處理器 B，不經過主記憶體 (然而有些實作會讓主記憶體控制器 (memory controller) 可以偵測到發生這件事，將新資料更新到主記憶體)
- 假如是為了寫入而進行存取，處理器 A 的快取行副本將會被標示為 invalid。

### Ch 3.3 CPU Cache Implementation Details
#### Associativity
- fully associative cache


- direct-mapped cache


- set-associative cache


#### Effects of Associativity

- Association 可以降低 cache miss 發生的次數

#### Access Times for Random Write

- L1d 的大小為 $2^{13}$ bytes，L2 的大小為 $2^{20}$ bytes
- 假如整個工作集能塞進 L1d 中，對單一元素操作的 CPU 週期數會低於 10。一旦超過 L1d 的容量，處理器就必須從 L2 載入資料，而平均時間則迅速成長到 28 個 CPU 週期左右。一旦 L2 也不夠大，便飆升到 480 個 CPU 週期以上。
- 這張圖給了我們撰寫更有效率的程式以協助提升快取使用的動機

#### Measurements of Cache Effects (Single Threaded Sequential Access)
##### 實驗設計
- 環境
Pentium 4 machine in 64-bit mode
- 資料
建立一個連續記憶體位址的陣列，陣列中的元素型別為 `struct l`，其中 `NPAD` 可以設定元素的大小，陣列中的元素利用指標串聯成環狀串列，存取下一個元素的方式都需要透過指標。

struct l {
struct l *n;
long int pad[NPAD];
};

##### Sequential Read Access, NPAD=0

- 論文中針對結果的解釋
- 從趨勢中可以看到有三個階段: < $2^{14}$ bytes, $2^{15}$ ~ $2^{20}$ bytes, > $2^{21}$ bytes
- 原因：L1d 的大小是 16kB，L2 的大小是 1MB
- 在第一階段中平均處理一個元素需要的 cycle 數符合 L1d 存取所需的 cycle 數 (4 cycles)；但是第二階段處理元素需要的 cycle 數不符合 L2 存取所需的 cycle 數 (14 cycles)，實際只需要 9 cycles
- 原因：處理器預取 (prefetch) 了下一個快取行 $\rightarrow$ 當下一個快取行需要被使用時，其可能已經被載入到一半了，不需要延遲太久就可以使用
##### Sequential Read for Several Sizes

- 論文中針對結果的解釋
- 一樣可以根據使用的 cycle 數分成三個階段
- 在第一階段 (工作集大小小於 L1d 容量大小) 中，所有的元素大小都需要差不多的 cycle 數，因為不需要預取
- 在第二階段 (工作集大小介於 L1d 和 L2 容量大小之間) 中，除了元素大小最小的情況外，其他三者一樣需要差不多的 cycle 數，但是特別的是其數量稍高，和 L2 存取所需的 cycle 數差不多
- 原因：從 L2 預取到 L1 失效，因為元素的大小皆大於等於一個快取行的容量，每一輪都需要取新的快取行，因為沒辦法每個 cycle 都預取一個新的快取行，來不及預取完就要取新的快取行了
- 在第三階段 (工作集大小大於 L2 容量大小) 中，不同大小的元素所需的 cycle 數差異甚大
- 總結來說，當 NPAD=7 或更大時，存取所需的時間較大的原因：
- 預取來不及完成就要取新的快取行，導致預取起不了甚麼作用。
- 預取無法跨頁的邊界 (cross page boundaries)
- TLB cache 的 miss
- TLB 中存的會是 page 的虛擬位址轉換到實體位址的結果，因此在總資料量相同的情況下，元素大小越大，代表元素數量越少，TLB 查找的成本平均分攤到單一元素存取上越多。
- 計算實體記憶體位址的時間成本很大，這是造成 NPAD=31 存取元素所需的時間大於理論上存取主記憶體的原因之一

##### TLB Influence for Sequential Read

- 圖片解釋
- On Cache Line: cache line 中有一個元素
- On Page: page 中有一個元素
- 論文中針對結果的解釋
- 一個 page 中有一個元素的情況下
- 當工作集大小達 $2^{13}$ bytes 時，所需的 cycle 數會突然暴漲 $\rightarrow$ 此時為 TLB cache overflow
- 計算 page 的實體記憶體位址並將它存進 TLB cache 所需的 cycle 數很大，在這個情況下每次存取一個元素都需要計算一次，所以存取單一一個元素所需的 cycle 數很大

##### Sequential Read and Write, NPAD=1

- 圖片解釋
- Follow: 與前面實驗的數據結果相同
- Inc: 會在前往下一個元素前，增加目前元素的 pad[0] 成員的值
- Addnext0: 會取下一個元素的 pad[0] 的值，並加到目前串列元素的 pad[0] 成員中
- 論文中針對結果的解釋
- 一開始會假設 Addnext0 所需的 cycle 數會最多，因為要做的事情比較多
- 實際上在某些工作集大小的情況下，Addnext0 的執行速度會比 Inc 快
- 原因
- Addnext0 每次前往下一個元素前都必須先載入這個元素的值 $\rightarrow$ 強迫預取
- 當前往下一個元素時，它已經存在 L1d 了
- 因此當工作集大小符合 L2 的大小時，Addnext0 存取的速度會和 Follow 差不多
- Addnext0 會比 Inc 早耗盡 L2 的容量，因為需要從主記憶體中載入更多資料
- Addnext0 在工作集大小為 $2^{21}$ bytes 時所需的 cycle 數為 Follow 的兩倍
- 原因: 此時 L2 容量已滿，需要在 L2 中找新空間給從主記憶體中載入的新資料，由於 Inc 和 Addnext0 都有改變記憶體內容，需要將改變的內容寫回主記憶體，而 Follow 沒有修改，因此不用寫回去，所以 Inc 和 Addnext0 的 FSB 頻寬會是 Follow 的一半，使其需要花費兩倍的存取時間。

##### Advantage of Larger L2/L3 Caches

- 圖片解釋
- P4/32k/1M: P4 processor with 32k L1d and an 1M L2
- P4/16k/512k/2M: P4 processor with 16k L1d, 512k L2, and 2M L3
- Core2/32k/4M: Core2 processor with 32k L1d and 4M L2
- 論文中針對結果的解釋
- 最後一階段快取的容量越大時，存取元素所需的時間可以維持在較低水平越久 (也就是 L2 的存取時間)
- 若工作集大小可以被裁剪成最後一階快取的容量，程式效能能夠大幅提升。

#### Measurements of Cache Effects (Single Threaded Random Access)
##### Sequential vs Random Read, NPAD=0

- 論文中針對結果的解釋
- random access 增長 working set size 需要大量的 cycle 數
- 一般存取主記憶體需要 200-300 cycles，但是這邊卻需要 450 cycles 以上
- prefetch 起了反作用
- random access 的曲線並不像 sequential access 例子中那樣，在多個平緩階段變得平坦，曲線是持續上升的
- 當 working set size 大於 L2 的大小時，cache miss ratio 會開始增長
- cache miss ratio 增長的趨勢和這邊差不多

- 每次 working set size 加倍的時候，每個元素的存取時間都超過二倍 $\rightarrow$ 每個串列元素的平均存取時間增加了
- 原因：TLB miss 增長

##### Page-Wise Randomization, NPAD=7

- 圖片解釋
- 一般的情況下，是將整個串列作為一個區塊（block）隨機化
- 其它的 11 條曲線則表示在比較小的區塊內進行隨機化。
- 標記為「60」的曲線，代表每組由 60 個分頁（245,760 位元組）組成的集合會分別進行隨機化。
- 這使得在任何一個時間點使用的 TLB 項目的數量會受到限制

- 論文中針對結果的解釋
- 設定 NPAD=7 的原因是其大小 64 bytes 正好為 cache line 的大小，且因為隨機的特性，使得 prefetch 沒作用，同一個區塊中的元素存取 L2 cache 的 miss rate 也不會差異太大。
- 當區塊大小越小時，曲線越接近將整個串列作為一個區塊的隨機化方法
- 後者的效能大大受到 TLB misses 的影響

#### Write Behavior
##### write-through & write-back
- 目的: coherency (user space 中)
- write-through
- 當 cache line 被寫入時，處理器也會立即將 cache line 寫到 main memory 中
- 簡單但是不快
- write-back
- 處理器不會立即將被修改的 cache line 寫回到 main memory 裡，cache line 只會被標記為 dirty。當 cache line 在未來的某個時間點從 cache 被丟棄時，dirty bit 將會通知處理器去把資料寫回去，而不是直接丟棄內容。
- 複雜但是比較快 (大部分系統的 cache 都是用這個策略)
- 處理器甚至可以在 cache line 必須被清除之前，就先利用 FSB 的閒置容量來儲存 cache line 的內容
- 比較需要的注意的是，當有多於一個處理器（或是處理器核或 HT），必須確保每個處理器看到的一直都是相同的記憶體內容 (下章會說明)
##### write-combining & uncatcheable
- 都是用在定址空間中未被真正的 RAM 所支援的特殊區域
- write-combining
- 常用於裝置上的 RAM (如：顯示卡)
- 傳輸到裝置的成本比區域 RAM 存取的成本還高很多，因此避免過多的傳輸是很重要的
- 如果只因為修改 cache line 中的一個 word 而將整個 cache line 進行傳輸會太浪費
- 會先合併多個寫入存取再將 cache line 寫到裝置
- uncatcheable
- 此記憶體位置不被 RAM 所支援
- 它是一個被寫死的特殊位址，擁有某個在 CPU 外部實作的功能
- 例如：記憶體對映的（memory-mapped）位址範圍，轉譯為對附屬於匯流排上的擴充卡以及裝置（PCIe 等等）的存取、嵌入式單板（embedded board）上能夠用來開關 LED 的記憶體位址

#### Multi-Processor Support
##### MESI cache coherency protocol
每個 cache line 分別擁有以下四種狀態：
- **Modfied**: The local processor has **modified** the cache line. This also implies it is the **only copy** in any cache.
- **Exclusive**: The cache line is **not modified** but known to **not be loaded** into any other processor’s cache.
- **Shared**: The cache line is **not modified** and might **exist** in another processor’s cache.
- **Invalid**: The cache line is **invalid**, i.e., unused.


###### 狀態轉移
- 狀態轉移可以透過處理器監聽或窺探其它處理器的運作的方式來進行，不需耗費過多能源
- 處理器執行的某些操作會被發佈在 external pins 上，讓處理器的快取處理能被外界看到
- 處理中的 cache line 的 address 能在 address bus 上看到

###### 狀態轉移時機
- 一開始所有 cache line 是空的，每個狀態皆為 **Invalid**
- 當 Invalid 的 cache line 被載入 cache 進行**寫入**操作時
- Invalid $\rightarrow$ Modified
- 當 Invalid 的 cache line 被載入 cache 進行**讀取**操作時
- 若**有**其他處理器的 cache 有載入該 cache line
- Invalid $\rightarrow$ Shared
- 若**沒有**其他處理器的 cache 有載入該 cache line
- Invalid $\rightarrow$ Exclusive
- 假設一個 cache line 的狀態是 **Modified**
- 單純在本地處理器被**讀寫**不會改變狀態
- 有第二個處理器想要去**讀取**相同的 cache line
- 原先處理器需要將它的快取內容寄送給第二個處理器，寄送給第二個處理器的資料也會被記憶體控制器接收並處理，將其內容儲存在記憶體中。如果沒有這麼做，cache line 就不能被標為 Shared。
- 原先處理器的 cache line : Modified $\rightarrow$ Shared
- 第二個處理器的 cache line : 轉成 Shared
- 有第二個處理器想要去**寫入**相同的 cache line
- 發起 Request For Ownership (RFO) operation (成本很昂貴)
- 原先處理器的 cache line : Modified $\rightarrow$ Invalid
- 第二個處理器的 cache line : 轉成 Modified
- 假設一個 cache line 的狀態是 **Shared**
- 單純在**本地**處理器被**讀取**不會改變狀態
- **本地**處理器想要**寫入**該 cache line
- 發起 Request For Ownership (RFO) operation
- 原先處理器的 cache line : Shared $\rightarrow$ Modified
- 其他處理器的相同 cache line: 轉成 Invalid
- 有**第二個**處理器想要去**讀取**相同的 cache line
- 不需要改狀態
- 因為 memory 中已經有存它的資料且狀態已是 Shared
- 有**第二個**處理器想要去**寫入**相同的 cache line
- 發起 Request For Ownership (RFO) operation
- 原先處理器的 cache line : Shared $\rightarrow$ Invalid
- 第二個處理器的相同 cache line: 轉成 Modified
- 假設一個 cache line 的狀態是 **Exclusive**
- 狀態轉換和 Shared 差不多，唯一的重大差別是本地處理器寫入操作不需要發佈到 bus
- 因為此 cache 是唯一持有該 cache line 副本的 cache
- 處理器會盡量讓 cache line 的狀態保持為 Exclusive 而不是 Shared，因為效能較佳
- E $\rightarrow$ M 比 S $\rightarrow$ M 轉換較快

##### Multi Threaded Access



##### Special Case: Hyper-Threads
此圖的趴數為令執行緒的執行不減慢超過 50% 以上所需的最小快取命中率
- x 軸：single-thread code 的 cache hit rate
- y 軸：multi-thread code 的 cache hit rate

觀察
- single-thread code 的 cache hit rate 為 60% 的情況下，multi-thread code 需要至少 10% 的 cache hit rate 才能使執行緒的執行不減慢超過 50% 以上，比較簡單達成
- single-thread code 的 cache hit rate 為 95% 的情況下，multi-thread code 需要至少 80% 的 cache hit rate 才能使執行緒的執行不減慢超過 50% 以上，比較難達成

總結
- 因為 hyper-threads 會共用 cache 來載入他們的資料，所以如果兩個 hyper-threads 的 working set 沒有重疊的話，原先使用 single-thread 的 cache hit rate 會被減半。
- 所以 hyper-threads 比較適用於原先使用 single-thread 時 cache hit rate 較低的情況下
- 除此之外，processor 可以安排 thread 的執行時機，如果他可以妥善地讓其中一個 thread 等待的時候去執行另外一個 thread 的話，會讓整體的執行時間加快。不過平行執行的成本也需要算進整體的執行時間當中
- 通常會建議透過 BIOS 把電腦中的 hyper-threads 機制關掉 (除非機器有經過特別設計)

##### Other Details
- address tagging
- first level cache：使用 virtual address (latency 較小)
- larget caches (L2, L3, ...)：使用 physical address (latency 較大)
- 別在同個 process 裡將同個 physical memory location 映射到二個以上的 virtual addresses。
- 程式開發者可以做的事
- 完全使用 logical memory pages
- 使用盡可能大的 page size，以盡可能地多樣化 physical addresses