iT邦幫忙

2021 iThome 鐵人賽

DAY 11
0
自我挑戰組

杰哥的考研紀錄系列 第 11

Day-11 Set Associative Cache

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人要他出來喬):

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的做法都是用相同層級的記憶體,也就是說現在只有一層城牆,如果第一層抓不住就宣告失敗了。

如果我們有兩層以上的城牆,效果會變得怎樣呢?

上一篇 下一篇
近水樓台先得月 Multilevel Cache


上一篇
Day-10 近水樓台先得月
下一篇
Day-12 Multilevel Cache
系列文
杰哥的考研紀錄30

尚未有邦友留言

立即登入留言