iT邦幫忙

2021 iThome 鐵人賽

DAY 10
0
自我挑戰組

杰哥的考研紀錄系列 第 10

Day-10 近水樓台先得月

近水樓台先得月

tags: IT鐵人

區域性原則

有在組裝電腦的人就會知道,電腦的儲存裝置包括記憶體跟硬碟,硬碟又有分成SSD跟HDD,記憶體的空間比較小,存取速度比較快;硬碟的空間通常比較大,存取速度較慢。另外還有很靠近CPU的快取記憶體,存取速度又更快了,我們的指令跟程式都是從這些地方拿來處理的。

在執行程式的時候,如果指令或是資料在需要的時候才抓進來,時間會拉很長,所以我們會期望當我們需要資料時,資料能正好在靠近的地方,就能更快的處理。

不過由於越快的裝置儲存的空間就越小,這個現象稱為區域性。

區域性(Locality):程式在任何一個時間點只會存取一小部份的位址空間。

時間區域性(temporal locality) 空間區域性(spatial locality)
如果一個項目被存許到,那麼它很快就會再次被存取。 如果一個項目被存取到,那麼它位址附近的項目也會很快被存取。

不同的記憶體技術

剛剛提到的三種記憶體(快取記憶體、記憶體、硬碟),他們的技術大概分為以下四種。

資料大概是2015~2018

類型 技術 存取時間 價位(per GB)
快取記憶體 SRAM 1~10ns $1000
主記憶體 DRAM 80ns $10
SSD Flash Memory 100,000ns $1
HDD Magnetic Disk 10,000,000 $0.1

可以看到速度差距很大,但速度快的又很貴,所以才需要我們這個章節討論的內容。

快取系統與虛擬記憶體

剛剛介紹的記憶體中,我們將快取記憶體(Cache)跟主記憶體(Memory)稱為快取系統;主記憶體(Memory)跟硬碟(Hard Disk)稱為虛擬記憶體。

簡單來說我們會偏向將最需要的部份放在快的那一層,對於快取系統來說放在快取記憶體,對於虛擬記憶體來說放在主記憶體。

每次我們需要東西時,如果它正好在比較快的那層,我們就稱為hit,反之稱為miss。所以我們要盡可能提昇hit rate,減少miss rate。

當東西不在快的那層時,我們就需要比較多的時間去下面一層尋找,這時要花比較多的時間,稱之為miss penalty,就是出錯得到的懲罰。

Direct Mapped

記憶體中我們將最小的單位稱為block或line,杰哥習慣用block稱呼。也就是說Cache從Memory抓資料都是以一個block為單位。不過因為Cache的容量比較小,所以要抓儲存資料的方式就很重要。

這邊介紹最簡單的方式,Direct Mapped。基本上就是用取餘數的方式決定要將Memory資料放在Cache的哪個位置,因為解釋有點麻煩,直接用例子來說明:

在這邊我們假設一個block是4bytes,並且這時CPU要求byte address為38的資料,這時候我們要先算出他在哪個block,透過floor function和除法可以得到是第九個block,那麼第九個block應該要放在Cache的哪個位置?

這邊就是direct mapped的重點了,我們只要直接的取9 mod 4的結果即可,結果的1就代表我們應該放在Cache的第一個block。

另一件要注意的事情是,不只有第九個block會對應到Cache的第一個block,還有1,5,13等等,所以我們還要另外標記這是哪個個Memory block,只要取9除以4的商即可,也就是放在tag欄位的2,如此一來我們就可以保證這格不會被誤會成是第五個Memory block之類的。

Cache Memory圖解

因為Cache不可能只有4個block,這邊用1024(1K)大小的Cache Memory簡略說明剛剛的對照關係:

我們假設byte address有32bits。以下慢慢說明每個分區代表的意思。

  • 對於一個block有4bytes來說,我們需要2bits指名要哪個byte。
  • 對於1024的Cache Index,我們取後面10bits指名,也就是餘數的部份。
  • Tag的話就是剩下的20bits。
  • 另外我們需要一個Valid bit表示這格的內容是不是有效的,有時候資料可能被人取走,我們沒辦法保證資料正確,或是在程式第一次載入時,其中的資料可能是上次殘留的,所以也要將Valid bit設定為0表示無效資料。
  • Cache中的Data就是我們要的資料,取出來的32bits會跟byte offset比對,確認要取哪段byte。

利用空間區域性

不過剛剛一個block只放4bytes的資料,也就是一個word的大小。這樣沒有用到空間區域性的特性,所以我們要試著增加一個block的大小,這樣子一次拿出來的空間就更大,就越有機會抓到等等可能用到的資料,通常對於陣列最有效果。

增加block大小就需要多幾個bit指名要哪個word,以下展示一個block有四個word的Cache Memory:

這時候除了原本有的東西以外,還要多一個Block offset,指名要block中的哪個word,其餘的部份都一樣,只有tag的部份被壓縮空間。

可以想成因為Block數目變少了,每個Index可能分配到的Memory Block變少了,所以tag的數量就便少了。

What's Next?

除了提昇Block數量以減少我們還有其他技巧可以減少miss rate,這部份留到下個單元再來解釋。

就醬~ㄅㄅ。

上一篇 下一篇
在Hazard尋求解法是否搞錯了什麼 Set Associative Cache

上一篇
Day-9 在Hazard尋求解法是否搞錯了什麼
下一篇
Day-11 Set Associative Cache
系列文
杰哥的考研紀錄30

尚未有邦友留言

立即登入留言