# Set Associative Cache
###### tags: `IT鐵人`
## Direct Mapped缺點
上次提到了Direct Mapped的做法,概念上就是取餘數決定要放在Cache的哪個block,以下圖來說
![](https://i.imgur.com/miGESxq.png)
因為1,5,9 mod 4的結果都是1,所以他們都會對應到Cache Block 1,要是今天發生了1,5,9大量被存取的狀況,那麼每次都會發生Cache miss,為了改正這件事發生,只要讓Cache Block不要一次只能存取一個Memory Block就好了,這就是Set Associative Cache的由來。
## Set Associative Cache
就如剛剛上面提到的,我們在每個Cache Block entry多增加幾個Block,通常都是以2的次方來做,形成2-way/4-way/8-way set associatve。
最後還有一個最極端的作法,稱為Fully associatve,就是不管甚麼餘數了,每個位置每個人都可以用,所以Cache的利用程度會最高。
下圖是各種Set associative cache的示意圖:
![](https://i.imgur.com/BsU5JqE.png)
不過提高數字的情況下,一方面同樣的Cache Block entry數量就會變少,當一個entry有太多Block時,找Block時就要在進入entry時一個一個檢查tag是否正確。
所以基本上miss rate會降低,不過hit time就會增加,所以如何選擇set associative cache的類型就是一大課題,要經過實驗測試,探討不同情境下的需求後才比較好做選擇。
## 白話說明Set Associative Cache
我們可以這樣子想,假設一間學校的學生是固定的,教室的數量可以自行增加,那如果一個班只有一個學生,那麼我們要找特定同學時只要到對的班級就好了,不過這樣子班級的數量就會非常大。
假設一個班級裝30位同學,總共有30個班級,那麼我們找到對的班級後,還要一個一個對座號,直到找出對的同學。
怎麼樣的分法比較好,取決於班級的管理難易度,如果班級能夠很快速地找到特定座號,那麼提高班級中的人數也不一定是壞事,反之則盡量不要增加班級中的人數。
雖然跟Cache的特性還是有些出入,比如說Cache miss後需要替換掉Block,班級通常不會淘汰同學補進新的。不過在找班級以及對照座號的概念其實是差不多的。
找人示意圖(圖片取自自由時報 [佔不到教室位子 中年男爆氣烙20人要他出來喬](https://news.ltn.com.tw/news/life/breakingnews/3342167)):
![](https://i.imgur.com/7GQgNRo.png)
## Replace
在Set Associative Cache中,因為一個entry中有多個位子,所以當滿位並且又有新的Block要進來時,我們就要挑一個Block淘汰掉,選擇也是一門學問,可以隨機挑選,也可以把最先進來的老屁股使用,不過最常使用的是LRU(Least Recently Used),也就是要淘汰距離上次使用到的時間最久的Block,以下示範一個例子。
> 假設這是一個2-way set associative cache,並且共有4個Block(也就是說只有兩個entry)。
> |index|Block0|Block1|
> |-|-|-|
> |0|||
> |1|||
>
> CPU要求的Block依序如下:3,4,8,5,6,3,9。
> 在前面四次request後Cache長這樣:
> |index|Block0|Block1|
> |-|-|-|
> |0|4|8|
> |1|3|5|
>
> 後面的6,3,9依序會發生下列的事情:
> 6會替換4,3原本就在Cache中(Hit),9會替換比較久沒有用到的5。
> 所以最後Cache內容為:
> |index|Block0|Block1|
> |-|-|-|
> |0|6|8|
> |1|3|9|
## What's Next?
這次說明了Set Associative Cache的用法以及優缺點說明,還有用白話的方式舉例說明,也示範了一下Replace。
下次會提出另一種減少miss rate的方式,由於Cache的做法都是用相同層級的記憶體,也就是說現在只有一層城牆,如果第一層抓不住就宣告失敗了。
如果我們有兩層以上的城牆,效果會變得怎樣呢?
|上一篇|下一篇|
|--|--|
|[近水樓台先得月](https://hackmd.io/@dZfCcN4hT8aUuDPv3B8CWQ/SyCUTiyet)|[Multilevel Cache](https://hackmd.io/@dZfCcN4hT8aUuDPv3B8CWQ/BkAc7ihxK)
![](https://i.imgur.com/RP06xcd.png)