[Computer Architecture Cheat sheat] —Hierarchy Memory

1. Principle of locality
2. Different type of memory
3. Memory’s Hierarchy
4. Directed Mapping Cache
5. Set Associative Cache
6. Cache Miss issue
7. Multi-level cache
8. Virtual Memory

Locality of reference

我們所追求的記憶體應該是容量大且速度快的，但是容量大與速度快是相互牴觸的，因為記憶體越大花在找尋存取位置的時間就越長，所以記憶體大就不會快，所幸記憶體的存取有Locality(區域性)的特性，意即 :

程式在任何一個時間點，只會存取一小部分的位址空間

分為

• Temporal locality (時間區域性) — 當一個資料被存取(reference)時，它很可能在短時間內再被存取一 次 。 e.g : for loop、function …
• Spatial locality (空間區域性) ：：當一個資料被存取(reference)時，它周圍的資料也很可能在短時間內再被存取(reference)。e.g : array

我們便可使用多個不同大小及速度的記憶體組成階層式的記憶體系統來達到容量大且速度快的要求。

Different type of Memory

1. SRAM — Cache
2. DRAM — Main Memory

Hierarchy of Memory

記憶體階層的目的在於合理成本的建立快速存取記憶體：離CPU愈近，使用速度愈快、單價較高的小容量記憶體；離CPU愈遠，使用速度愈慢、單價較低的大容量記憶體。

Special Term used in Memory

1. Block / Line — 在記憶體階層中，如Cache與Memory之間傳遞資料的最小單位即是Block
2. Hit Rate/Hit Ratio — 在記憶體存取時，可在較高層級(Cache)中找到Data，稱之為Hit，而整體Hit data的比例即稱為Hit Rate
3. Miss Rate — Hit Rate的相反，意即當在較高層級(Cache)中找不到Data，辯稱為Miss，而整體Miss data的比例=1-Hit Rate=Miss Rate
4. Hit Time — 找尋data所花的時間，包括用來判斷是Hit/Miss的時間
5. Miss Penalty Time — 在記憶體存取時，遭遇Miss，所以必須從較低階層的記憶體(Main Memory)搬取Data至較高層(Cache)所需的時間。

因為High Level的記憶體容量較小且是用較快速的記憶體元件製成，所以Hit Time將會遠小於去存取下一層所花的時間，而存取下一層所花的時間則是Miss Penalty Time的主要部分。

如果Hit Rate夠高的話，那麼Memory Hierarchy 存取資料的速度將會接近最高(最快)記憶體階層的存取速度，而儲存容量將會等於最低(最大)階層的記憶體容量。

Cache issue

我們將談論Cache常見的幾個issue :

1. Cache Basic idea
2. Cache miss handling
3. Write hit handling
4. Write miss handling
5. Split/Combined cache
6. Non-blocking cache
7. 3-type of Cache for data mapping
8. Multi-Level Cache
9. 3C
10. Virtual/Physical addressed Cache
11. Cache Optimization Techniques
12. Cache Performance

Cache basic idea

1.Cache 與 Main Memory 的組成元件:

SRAM — Cache
DRAM — Main Memory

2.降低幾個cache的重要criteria方法

a.降低 cache miss rate
— (1.) 增加cache size
— (2.) 增加block size
— (3.) 增加associativity (關聯度)

a.降低 cache miss penalty
— (1.) 使用early restart 技術
— (2.) 使用critical word first 技術
— (3.) 使用mult-level cache 技術
— (4.) 使用critical word first 技術

a.降低 hit time(access cache data time)
— (1.) 使用virtually addressed cache
— (2.) 使用directed mapped cache

Cache miss handling

當資料無法從Cache中取得，稱為Cache Miss，其處理步驟為 :

l. Stall CPU,凍結暫存器的內容值

2.使用一個『分離的控制器』,將記憶體的資料載至Cache

3.從造成Cache Miss的cycle重新開始執行

其中Step-2 會將 Memory中的Data寫入Cache，這邊就有可能造成 Cache與Memory 資料 不一致(inconsistence)的問題。

Write hit handling

考慮每次執行”Store”指令，會將資料寫入Main Memory，但我們使用Cache技術，如果該address有在cache中(hit)，便會寫入Cache中。而此時Cache與Memory 資料會有不一致( inconsistence)的狀況發生。

我們有兩種解決方法 :

1. Write through
   寫入快取的同時也寫入記憶體中。
   優點：實作簡單
   缺點：效能差、不適用於virtual memory
2. Write back
   只寫入快取，等到被置換時才寫回記憶體
   優點：效能佳
   缺點：設計複雜

Write miss handling

考慮每次執行”Store”指令，會將資料寫入Main Memory，但我們使用Cache技術，如果該address不在cache中(miss)，此時該把資料寫到Cache或是Memory中 ?

兩種方法 :

1. Write Allocate
   在Cache中配置一區塊，並由記憶體取得所需區塊資 料後，將其寫入配置的區塊中。
2. No Write Allocate、Write around
   直接寫入記憶體，而不在快取中配置此區塊。

通常，write-back 會與 write allocate 搭配使用。
write-through 會與 write around 搭配使用。

Example

3-type of Cache for data mapping

因為Compiler(CPU)會分配記憶體的位置給程式和變數，而產生的位置是Byte address(Main Memory的位置)，所以我們必須將Cache Memory的位置與Main Memory的位置做對應(Mapping)。

其實就是Byte address [M.M] 與 Block address [Cahce]的不同 Mapping方式

Mapping的方式分為 :

1. Directed Mapping Cache
2. Set associative Mapping Cache
3. Fully associative Mapping Cache

Directed Mapping Cache

每個M.M(Main Memory)的位置恰好對應到Cache的一個位置

Block Address = [Byte Address % (number of Blocks)]

而每個Block Address的內容可能對應到許多的Byte Address，因此我們必須加入一個欄位 — Tag，用來辨別該Block Address中的內容是否是我們要的。

我們將Block Address拆分成兩部分，依照Cache有多少個Blocks將前面的bits做為(Cache)Index而剩餘的bits用來表示Tag。

Note : Block的個數如果為2的次方，我們在拆分成兩部分時，就可以直接切
" log2(numboer of Blocks) "個 bits後方為Index，其餘為Tag

e.g

Cache有8個Blocks，Block address=01101，則Index=011、Tag=01

最後我們加上一個Valid欄位(1 bit)，用來標註該address是空的還是已經開始用了。

Directed Mapping Cache Structure

Directed Mapping Cache’s size caculate

給予

1. Byte address length

(Address Space size=2^Byte addr. length=M.M的Block數)

2. Directed Cache data size

3. Block size

去計算Directed Mapping Cache總共需要多少個bits

Example

若

Improve Directed Mapping Cache Using Spitial Locality

上述的Directed Mapping Cache並沒有使用的空間區域性的優勢…

Set Associated Cache

相對於一對一的Directed Mapping Cache，Set Associated Cache是先將Cache分成數個集合(Set)， 每個集合數量固定，並且在對映時，只要集合中還有空出的快取，記憶體區塊 就能使用

一個快取包含 n 個區塊，就稱為n-way或 n關聯度(associative) 。

常見分類如下：

1. Directed mapped (One-way set associative)
2. Two-way set associative
3. Four-way set associative
4. Full set associative

當對映的過程，集合已經滿了，則需要置換。需要找出被置換的區塊。

方法又分4種 :

1. Random
2. FIFO
3. LRU
4. OPT

Directed Mapped 上文已經說明了，接下來是關聯度≥ 1的Cache Structure :

3C models

我們為cache miss 分為3種種類，並加以討論 :

1. Compulsory misses : (強迫性失誤)
   若一區塊從未被使用過，則第一次讀取 時，此區塊必定不會在快取中，即發生強迫性失誤。也稱為冷開機失誤(Cold-start Misses)
2. Capacity misses : (容量性失誤)
   當快取的容量不足以包含一程式執行所需之區塊時，就會發生快取的容量性失誤。因為區塊會不斷被取代、替換，而需要重新載入。
3. Confilict misses : (衝突性失誤)、Collision misses (碰撞失誤)
   只發生在set associative、與directed mapped 的cache；
   當許多區塊映射到同一區塊或集合時，所發生的快取失誤。
   此種失誤在相同容量的『完全關聯式快取』中不會發生。

並且根據cache的類型整理表，如下 :

Cache Miss Steps

Miss Penalty Discussion

Split Cache

Add Memory bandwidth to Cache

Multi-level Cache

多層快取可以有效減少Cache Miss Penalty。

設計主要快取(L1)與次要快取(L2)的考量不同：

• 主要快取注重在減少Hit time來縮短時脈週期。
• 次要快取注重在減少Miss Rate，以降低存取記憶體花太長時間的影響。

Virtual Memory

執行程式與取得資料的過程:

1.開起執行檔(滑鼠點擊:等方式)
2.OS把程式複製到硬碟SWAP Space之中,複製後,程式本身稱為Virtual Space
(又稱為User Program Space)
3.當程式使用到的空間較記憶體還要大時,OS會先把部分資料複製到Physical Memory,
並建立Page Table, 以 Physical Page Number 來記錄已經載入(數值)
、與還在硬碟內未載入(硬碟位置)的資料內容。
Page Table會與程式本身資料量相當
(圖示皆為8個,並會另外增加 Memory Management bits
( Valid bit、Reference bit、Dirty bit)
4.當CPU要存取某一資料時,會發出Virtual Address的要求指令
(直接指定硬碟内位置),Virtual Address是由兩部分組成:
Virtual Page Number 與 Page offset,
前者是對應到硬碟中程式本身的區塊、後者為區塊內的位置
5.因為CPU計算的資料來源為記憶體,故 Virtual Page Number會需要轉換為
Memory中的資料,因此會先透過加上Page'Table Register的數值,以找到
Page Table,再從 Page Table 取得對應的 Physical Page Number(圖中即是先將第4個 Virtual Page Number 加上PTR 數值·到Page Table第4號,確認Valid bit 為1,再找到對應 Physical Page Number 為1)
6.有了Physical Page Number,再結合先前的Page Offset,便組合成了Physical
Address
7.在Memory中,以對應的Physical Address 取得資料
(在Memory第1區塊内第100的位置)
8.回傳給CPU進行運算,完成資料取得

Memory Management Bits

1. Valid bit(有效位元) —
表示所需要存取的資料是否在記憶體中，
若為0則代表 “ Page fault ” 的發生(Cache 中的Miss)

2. Reference bit (參考位元) —
完整實作LRU的成本過高,因此大多是以『近似LRU』的方式完成,
而Reference bit即紀錄了使用次數，
可用來選出要被置換出去的Victim Page犧牲分頁

3. Dirty bit(修改位元:modified bit) —
當有資料改寫入Memory中時,因為硬碟速度過慢,不會即時被更新,
因此Dirtybit就會設定成1,以提示之後Write Back時要更新硬碟內資料 。

Valid bit 是由 HW 讀取、由 OS 修改

Reference bit 是由OS 讀取、OS 修改

Dirty Bit 是由 OS 讀取、OS修改