[筆記] 平行計算 Ch2 part 7 Directory-based Protocol

本系列是 Parallel Programming in C with MPI and OpenMP 這本書的讀書心得!

上篇前情提要:

Multiprocessor 兩種:Centralized Multiprocessor 與 Distributed Multiprocessor

Centralized Multiprocessor :
直接把Uniprocessor做擴充!
直接把CPU掛到bus上!
不管哪一個CPU處理去連記憶體都一樣快!(有相同的Memory access time)
這種的稱為:
UMA : Uniform memory access multiprocessor
SMP : Symmetrical multiprocessor 對稱型的多處理機

這個架構在處理Cache coherence(快取一致性)的機制為 Write Invalidate Protocol,其運作的內容於上一篇詳細介紹過

Distributed Multiprocessor:

這種架構下,每一個CPU都會分到(Distributed)一塊自己主要在用的Memory (primary memory)
增加Memory頻寬,降低存取Memory的時間
如此的好處是擴充性高!增加CPU不會像UMA架構那樣,直接占用到Bus的頻寬,
而是自己就會分配到一塊主要用的記憶體空間,不會常常需要跟別人共用
這種架構稱為 :
NUMA : non-uniform memory access multiprocessor

本篇要繼續介紹這個架構下的Cache coherence問題所處理的機制:Directory-based Protocol

Directory-based Protocol



首先要來了解一下這個 protocol 用三種狀態來描述Data的狀況

分別用U,S,E 這三個代號來簡稱

Uncached :data 的狀態目前是閒置的(沒有正在被share)所以可以放心拿去用

Shared:data 的狀態目前是被shared,也就是有其他的CPU把data copy去他的cache裡面使用,此時還是可以把data拿去用!只是要登記一下你也有在用就是了

Exclusive:這是mutual exclusive的意思,表示現在data的狀態正在被修改中,其他人不可以使用!有再用的人請把手邊那份的先丟掉,因為data要被更新了!

制定這三種狀態有什麼用途呢?

讓我們看下去~~

架構圖:



這個架構下

每個CPU都有離自己比較近的Local Memory,也有自己的cache以及一個Directory。



然後有一個變數 X 他目前的值是 7 ,directory裡面放他的狀態是 U 0 0 0 

U 表示現在沒人使用,0 0 0 分別記錄了 CPU 0, CPU 1, CPU 2 這三位使用變數X的狀況都是還沒有在用的 0 



當 CPU 0 要讀取 X 時,看到狀態是 0 0 0 當中的第一個bit是 0 表示 CPU 0 還沒有在用,所以會Read Miss 



於是先把狀態改成 S 1 0 0 ,記錄了目前狀態是 " Shared " ,1 0 0 記錄了目前是 CPU 0 在用它!



然後 CPU 0 才能順利把data 讀出來複製到他自己的cache當中



當 CPU 2 也想要讀取 X 時,看到 1 0 0 的第三個bit是 0 也會Read Miss !



先把第三個bit改成1 -> 從剛剛的 1 0 0 變成 1 0 1 ,然後可以順利讀取到 X



此時,當 CPU 0 想要寫入新的值 6 的時候,看到狀態是 1 0 1 表示除了他自己以外,還有另一個人也在用!

發生 Write Miss !!



這時會先把正在使用 X 的人cache當中的 X 資料清掉!



再把X 的狀態改成 E 1 0 0 ,注意:此時Memory當中的資料還沒更改成新的!



這時如果還有人(CPU 1)要讀取 X 時,首先看到狀態 E 1 0 0 會先Read Miss 



因為狀態是 E 1 0 0所以要用之前要先問 CPU 0 來把它改回 S 的狀態



改之前的這個時候,才會把剛剛想要更新的Data 寫回去 Memory當中



再把狀態改成 S 1 1 0 讓 CPU 1 順利拿到 X 的 data 並且確保拿到的是正確的新的資料!

故事說到這邊,可以發現這種機制是採取所謂"被動"的方式來更改(寫回Memory)!

如上例先把 CPU 0 保護措施做好,等有其他人要用的時候,才把要更新資料寫回Memory !

留言

這個網誌中的熱門文章

[筆記] CRLF跟LF之區別 --- 隱形的 bug

[ML筆記] Batch Normalization

[筆記] 統計實習(1) SAS 基礎用法 (匯入資料並另存SAS新檔,SUBSTR,計算總和與平均,BMI)

[ML筆記] Ensemble - Bagging, Boosting & Stacking