caching(快取)
定義:用來暫時存放資料的一種記憶體空間,存取時可先到這一個記憶體空間尋找,而減少到下層記憶體的存取次數,而提昇平均存取效率
ex:cache memory(快取記憶體),file cache(檔案快取),proxy(代理伺服器)
ps:buffering(緩衝區)是指一個工作區,用來平衡兩設備間資料傳輸速度的差異,可避免整體系統運作受限於週邊設備速度,提昇系統效能
cache memory(快取記憶體)
用途:允許cpu直接到cache memory查看所需資料是否存在?若是,則直接存取不必再到主記憶單元
好處:減少到主記憶單元存取的次數,解決主記憶體單元存取不夠快的問題
對讀取而言:
hit(擊中)表示可直接由快取記憶體讀取所需要的指令或資料
miss(失誤)則有二種設計:
read through(貫穿式讀取):先到主記憶體單元讀取所需的指令或資料,同時進行資料區塊在主記憶體與快取記憶體間的搬動
non-read through(非貫穿式讀取):先進行資料區塊在主記憶體與快取記憶體間的搬動,再到快取記憶體讀取所需要的指令或資料
ps:read through效能較好
對寫入而言:
直接寫入快取記憶體有分:
write through(貫穿式寫入):對快取記憶體寫入時,也同時寫入主記憶體,適合多cpu
copy back(拷貝式寫入):只對快取記憶體寫入,適合單一cpu
若寫入的資料不在快取記憶體有分:
fetch on write(抓取式寫入):將資料區塊由主記憶體搬動到快取記憶體,再將資料寫入快取記憶體
write around(繞過式寫入):只將資料寫入主記憶體
ps:使用write through時常搭配write around,而用copy back常搭配fetch on write
快取記憶體average access time
hit ratio=擊中率,miss overhead=失誤代價
公式=擊中時間+(1-hit ratio)*miss overhead=擊中時間+失誤率*miss overhead
新的中央處理器時間
公式=(執行的計時週期個數+等待的計時週期個數)*ct=ic*(執行的cpi+等待的cpi)*ct
ps:等待的計時週期個數
公式=程式的記憶體存取次數*失誤率*miss overhead
ps:等待的cpi
公式=指令的平均記憶體存取次數*失誤率*miss overhead
block區塊
說明:快取記憶體與主記憶體單元之間的對映單位
ps:快取記憶體的區塊通常稱為block frame(區塊框)
block大小的取捨同時影響失誤率與失誤代價,並與快取記憶體的平均存取時間直接相關
block太小或太大會增加失誤率
……………………….
快取記憶體的動態位址轉換
採用硬體實作的技術來完成,透過mapping function(對映函數)來決定一個主記憶體單元block要對映到那一個快取記憶體的block frame
快取記憶體的mapping function有:
direct mapping(直接對映):直接將主記憶體內的每個區塊映射到唯一的快取線路
fully associative(完全關聯):可以把主記憶體的區塊載入到任何一條快取線路
set associative(集合關聯):集合direct mapping和fully associative的優點
sector mapping(區段對映):將每一個主記憶體單元的sector(區段)對映到所有的快取記憶體sector frame(區段框)
ps:不同的設計只在位址轉換的效能與取代策略的彈性之間進行取捨
direct mapping
對映主記憶體的格式為:[ 標籤 | 區塊框編號 | 相對位址 ]
相對位址欄位元依block大小,區塊框編號欄的位元依區塊數量
ex:
設block為32byte有512個,記憶體位址長度為32bit
則相對位址欄為5bit,區塊框編號欄為9bit,標籤欄為18bit(因為32-5-9)
ex:
相對位址欄為3bit,區塊框編號欄為5bit
則有8byte are in each line(block) of the cache,the cache will hold 32 lines(blocks),256bytes is the total size of the cache memory(32*8)
ex:
word為32bit,記憶體大小為512kb
則會有128k word,因此block欄為17bit ; 32bit=4byte,因此相對位置欄為2bit ; 32bit-17bit-2bit=13bit,因此tag為13bit
有最佳的位址轉換效能,但完全無取代策略的彈性,而且會有較高的失誤率
記憶體管理單元完成動態動態位址轉換時:
1先使用區塊框編號決定一個快取記憶體的block frame
2使用標籤與快取記憶體的block frame的標籤欄位進行比較,若內容相同表示hit
3最後使用相對位址對block內部的一個位址進行存取
ex:
設快取記憶體有2個block frame,主記憶體有8個block,則block對應如下
block frame0 對應到block 0,2,4,6
block frame1 對應到block 1,3,5,7
fully associative
對映主記憶體的格式為:[ 標籤 | 相對位址 ]
相對位址欄位元依block大小
ex:
設block為32byte有512個,記憶體位址長度為32bit
則相對位址欄為5bit,標籤欄為27bit(因為32-5)
有最差的位址轉換效能,最大取代策略的彈性,有較低的失誤率
ex:
設快取記憶體有2個block frame,主記憶體有8個block,則block對應如下
block frame0 對應到block 0,1,2,3,…6,7
block frame1 對應到block 0,1,2,3,…6,7
set associative
對映主記憶體的格式為:[ 標籤 | 集合編號 | 相對位址 ]
相對位址欄位元依block大小,集合編號欄的位元依集合數量
ex:
設block為64byte,快取記憶體有1024個集合,記憶體位址長度為32bit
則相對位址欄為6bit,集合編號欄為10bit,標籤欄為16bit(因為32-6-10)
ex:
cache is 8-way set associative,cache size is 512kbyte,block size is 64bytes
則cache有8k個block(因為512k/64),1024個集合(因為8k/8)
ex:
設cache有1024個block,集合編號欄為9bit
則有512個set,而每個set有2個block(因為1024/512)
較佳的位址轉換效能,較大的取代策略彈性,一般快取記憶體使用
記憶體管理單元完成動態位址轉換時:
1先使用集合編號決定一個快取記憶體的集合
2再使用標籤與集合內部所有block frame的標籤欄位進行比較,若內容相同表示hit
3最後使用相對位址對block frame內部的一個位址進行存取
ex:
設一集合有2個block frame,快取記憶體有4個block frame,主記憶體有8個block,則block對應如下
set0含block frame0 對應到block 0,2,4,6
set0含block frame1 對應到block 0,2,4,6
set1含block frame2 對應到block 1,3,5,7
set1含block frame3 對應到block 1,3,5,7
sector mapping
與完全關聯相同,差別在區塊變為區段,一般用在較大資料區塊的應用
……………………….
取代演算法
說明:演算法用的取代策略對快取記憶體的存取效率有重大的影響
LRU(least recently used,最近罕用):將集合中目前最不常用的的區塊加以取代
可減少失誤次數,實作困難且成本高,常用在虛擬記憶體中
ex:設block frame=4,進入的block順序為1,3,2,5,6,7,2,4,5,2,5,3,1,2,則2,2,5,2被hit
| 1 | 3 | 2 | 5 | 6 | 7 | 2 | 4 | 5 | 2 | 5 | 3 | 1 | 2 |
| 1 | 3 | 2 | 5 | 6 | 7 | 7 | 7 | 4 | 2 | 5 | |||
| 1 | 3 | 2 | 5 | 6 | 7 | 2 | 4 | 4 | 2 | 5 | 3 | ||
| 1 | 3 | 2 | 5 | 6 | 7 | 2 | 4 | 5 | 2 | 5 | 3 | 1 | |
| 1 | 3 | 2 | 5 | 6 | 7 | 2 | 4 | 5 | 2 | 5 | 3 | 1 | 2 |
FIFO(first in first out,先進先出):將集合中最早進入的區塊加以取代
實作較簡單,失誤較高
ex:設block frame=4,進入的block順序為1,3,2,5,6,7,2,4,5,2,5,3,1,2,則2,5,2被hit
| 1 | 3 | 2 | 5 | 6 | 7 | 2 | 4 | 5 | 2 | 5 | 3 | 1 | 2 |
| 1 | 3 | 2 | 2 | 5 | 5 | 6 | 7 | 4 | 2 | 2 | |||
| 1 | 3 | 2 | 5 | 5 | 6 | 6 | 7 | 4 | 2 | 5 | 5 | ||
| 1 | 3 | 2 | 5 | 6 | 6 | 7 | 7 | 4 | 2 | 5 | 3 | 3 | |
| 1 | 3 | 2 | 5 | 6 | 7 | 7 | 4 | 4 | 2 | 5 | 3 | 1 | 1 |
random(隨機選取):由集合中隨機選一個區塊加以取代
實作最簡單,常用在快取記憶體
optimal(最佳化原則)
快取記憶體失誤原因可分為:
compulsory miss(強迫性失誤):一開始存取空的快取記憶體時造成的失誤
增加區塊大小可改善,但過大會增加conflict miss
capacity miss(空間性失誤):快取記憶體的空間無法容納所有需要存取的區塊
增加快記憶體大小可改善
conflict miss(衝突性失誤):因取代策略造成區塊被取代,並再度對此區塊進行存取時所造成的失誤
增加快記憶體大小可改善,使用fully associative可避免所有conflict miss
ps:block太小會讓強迫性失誤增加,太大會讓衝突性失誤變高