# Set Associative Cache

###### tags: `IT鐵人`

## Direct Mapped缺點

上次提到了Direct Mapped的做法，概念上就是取餘數決定要放在Cache的哪個block，以下圖來說


因為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的示意圖：


不過提高數字的情況下，一方面同樣的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))：


## 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)