亚洲av成人无遮挡网站在线观看,少妇性bbb搡bbb爽爽爽,亚洲av日韩精品久久久久久,兔费看少妇性l交大片免费,无码少妇一区二区三区

Chinaunix

標題: smp cache line并發(fā)訪問 [打印本頁]

作者: blake326 時間: 2014-06-27 09:59
標題: smp cache line并發(fā)訪問
smp比如8核，比如我現(xiàn)在有一個數(shù)組，a[8] = {0}; 地址是0xd000000;這樣a[0] ~ a[7]都是在同一個cache line中的, 并且每個cpu對應(yīng)的cacheline都是share狀態(tài)的。那么考慮下面并發(fā)場景：
cpu0 寫 a[0] = 0;
cpu1 寫 a[1] = 1;
cpu2 寫 a[2] = 2;
...
cpu7 寫 a[7] = 7;
結(jié)果是：
cpu0，把cache line寫成了0，。。。，然后發(fā)出一個inv 廣播到其他cpu
cpu1，把cache line寫成了。1.。。，然后發(fā)出一個inv 廣播到其他cpu
。。。

問題是：
1. 假設(shè)同時發(fā)生的，最終cache line的值是多少？
2. 某個cpu 寫完自己的cache line，發(fā)出去一個inv 廣播，然后又收到一個inv 事件，那么這個事件如何處理呢？
3. 這種代碼是不是無法保證cache line等于 0,1,2,3,4,5,6,7

作者: chishanmingshen 時間: 2014-06-27 10:41
本帖最后由 chishanmingshen 于 2014-06-27 11:16 編輯

回復(fù) 1# blake326

通過內(nèi)存中轉(zhuǎn)。比如：給a[1]賦值后，cpu0和cpu1的cache line已經(jīng)都一樣了。
而且，我覺得你這個case，8次操作，僅在第一次操作會發(fā)一次inv，并不是8次。

作者: blake326 時間: 2014-06-27 12:40
回復(fù) 2# chishanmingshen

cpu0 寫完 a[0] = 0, 會發(fā)一個inv事件到其他cpu，其他cpu會inv 相應(yīng)的cache line，這樣就會感知到cache變化，但是假設(shè)多個cpu同時寫的話，不能保證這個順序了。

參考：
http://www.72891.cn/thread-3593865-1-1.html

作者: chishanmingshen 時間: 2014-06-27 14:02
回復(fù) 3# blake326

我覺得你這個問題跟亂序不大涉及。
可能8次寫是亂序的，但是總有一個cpu先讓自己的cacheline 從S到M，這樣其他的只能讀內(nèi)存了。

所以最終結(jié)果是ok的，雖然損耗時間。

作者: arm-linux-gcc 時間: 2014-06-27 17:45
本帖最后由 arm-linux-gcc 于 2014-06-27 17:46 編輯

今天面試剛好被問到了這個問題

最終各個core的inner cache都會是invalid
outter cache最終會是0 1 2 3 ... 7

這種用法性能低下，最好用per-cpu，以達到避免競爭同一個line的目的

作者: wth0722 時間: 2014-06-27 19:14
回復(fù) 5# arm-linux-gcc

為什麼outter cache最終會是0 1 2 3 ... 7 ?

我個人認知如下，如有錯幫忙釘正

第一個搶到cache的人會去更新 & invalid

第二搶到cache的，會發(fā)現(xiàn)該cache line已經(jīng)invalid (也就是所謂的write miss)

所以他就寫到記憶體，並在去cache上找一個cache line存放 (他不一定上一個cache line位置)

第二個寫完時，他又去下invalid

第三個搶到cache的，就會跟第二個一樣

以後以此類推

作者: arm-linux-gcc 時間: 2014-06-27 20:28
本帖最后由 arm-linux-gcc 于 2014-06-27 20:38 編輯

以outter include inner這種情況來說：因為arm cortex-a15就是這種情況
core 0寫了inner line，會使得core 1的相應(yīng)inner line變?yōu)閕nvalid，同時core 0的這次寫會同步到outter上
core 1寫自己的inner line時會發(fā)現(xiàn)沒有命中，于是就會去outter找有沒有能夠命中的line，于是發(fā)現(xiàn)outter中有能夠命中的，于是會寫outter，同時也使得core 0的inner變?yōu)閕nvalid

cortex-a9則是可以配置成exclusive或inclusive的
exclusive時應(yīng)該就最終在outter和inner中都沒有能夠命中的

作者: blake326 時間: 2014-06-27 21:27
回復(fù) 7# arm-linux-gcc

core 0寫了inner line，會使得core 1的相應(yīng)inner line變?yōu)閕nvalid，同時core 0的這次寫會同步到outter上

這個順序是如何保證的呢？
core1 變成invalid是因為會收到core0的inv request。但是在core1收到inv request之前的話，core1就開始寫cache怎么辦？

從這個帖子里http://www.72891.cn/thread-3593865-1-1.html 來說，core0寫完cache之后，應(yīng)該會發(fā)出inval request到其他core，并且會接受其他core 的inval 成功的reply。整個邏輯還是搞不清楚現(xiàn)在。

作者: blake326 時間: 2014-06-27 21:33
我現(xiàn)在懷疑這種并發(fā)訪問可能會發(fā)生只有cpu2成功寫入的結(jié)果，例如： 0 0 2 0 0 0 0 0

www.72891.cn/forum.php?mod=viewthread&tid=1972593
這個里面講的 Figure 2. Data Destruction by Dirty Cache Lines 問題，感覺有點類似。

作者: blake326 時間: 2014-06-28 11:05
本帖最后由 blake326 于 2014-06-28 11:06 編輯

參考cache一致性的一個文檔：
http://www.72891.cn/thread-4070325-1-1.html

基本的mesi協(xié)議中，cache存在四種狀態(tài)e，s，m，i
i invalid，表示該數(shù)據(jù)沒有對應(yīng)cache line
e excluisve，表示該數(shù)據(jù)有效，并且只存在本cpu的cache line中。其他cpu沒有cache該數(shù)據(jù)。
m modify, 表示該數(shù)據(jù)有效，但是與存儲器中的不一致，并且只存在本cpu的cache line中。其他cpu沒有cache該數(shù)據(jù)。
s share, 表示該數(shù)據(jù)有效，并且多個cpu都有該數(shù)據(jù)的cache line并且他們的狀態(tài)都是share。

然后，當CPU對一段存儲器進行寫操作時，如果這些數(shù)據(jù)在本地Cache中命中時，其狀態(tài)可能為E、S、M或者O。
   狀態(tài)為E或者M時，數(shù)據(jù)將直接寫入到Cache中，并將狀態(tài)改為M。
   狀態(tài)為S時，數(shù)據(jù)將直接寫入到Cache中，并將狀態(tài)改為M，同時其他CPU保存該數(shù)據(jù)副本的Cache行狀態(tài)將從S或者O遷移到I(Probe Write Hit)。
   狀態(tài)為O時，數(shù)據(jù)將直接寫入到Cache中，并將狀態(tài)改為M，同時其他CPU保存該數(shù)據(jù)副本的Cache行狀態(tài)將從S遷移到I(Probe Write Hit)。

這里，我們不管狀態(tài)o（owner), 其實我現(xiàn)在的問題就是：
   狀態(tài)為S時，數(shù)據(jù)將直接寫入到Cache中，并將狀態(tài)改為M，同時其他CPU保存該數(shù)據(jù)副本的Cache行狀態(tài)將從S或者O遷移到I(Probe Write Hit)。這個操作是不是原子的？

假設(shè)某個時間點，所有cpu該數(shù)據(jù)都是cache share的。那么這時：
cpu0, 寫了 0 0 0 0 0 0 0
cpu1, 寫了 0 1 0 0 0 0 0
cpu2，寫了 0 0 2 0 0 0 0

如果，該操作時原子的話，那么這種并發(fā)疑問就沒有了，結(jié)果勢必會使cache line變成, 0 1 2 3 4 5 6 7。而且怎樣保證原子性的呢？

作者: blake326 時間: 2014-06-29 22:24
本帖最后由 blake326 于 2014-06-29 22:25 編輯

好吧沒人回，我自己理解下，關(guān)鍵的一點：
“ 狀態(tài)為S時，數(shù)據(jù)將直接寫入到Cache中，并將狀態(tài)改為M，同時其他CPU保存該數(shù)據(jù)副本的Cache行狀態(tài)將從S或者O遷移到I(Probe Write Hit)�！边@個是否原子？
這個操作看起來有很多小步組成的，寫數(shù)據(jù)到cache，修改m，同時發(fā)送inval request到其他cpu，可能還要處理其他cpu回來的inval replay。所以，當然不是原子的了，要不然肯定很影響性能的。
但是，更關(guān)鍵的一點，mesi會保證整個一套動作是安全的，之前的例子，cpu0，cpu1同時寫s的cache line，那么對于這同一個cache line，mesi應(yīng)該會有一個同步機制（類似 mutex）之類的保證同時只有一個cpu操作了addr響應(yīng)的cache line.比如，cpu0，cpu1同時開始寫，首先，mesi會仲裁選擇一個cpu進行對cache line進行操作，另外一個cpu只能等待，待的就是之前說的一些列操作：狀態(tài)為S時，數(shù)據(jù)將直接寫入到Cache中，并將狀態(tài)改為M，同時其他CPU保存該數(shù)據(jù)副本的Cache行狀態(tài)將從S或者O遷移到I)。因此，我這個帖子的結(jié)果就是，最終cache line的值是0, 1, 2, 3, 4, 5, 6, 7. arm-linux-gcc同志是正確的。

重新整理一下cache一致性的狀態(tài)切換：
假設(shè)有cpu0, cpu1。一個虛擬地址addr。
則cpu0, cpu1都有一個addr對應(yīng)的cache line, 狀態(tài)有四種：有效E，修改M，共享S，無效I。I實際上就是說該addr在cache中沒有緩存的意思。根據(jù)這四種狀態(tài)，組合分析一下。

cpu0,cpu1的cache狀態(tài)一樣：
都是I狀態(tài)：
cpu0讀的話，首先會像mesi申請cache line使用權(quán)，然后開始分配一個cache line并且從ddr把addr的值讀取過來，狀態(tài)變成E。
cpu0寫的話，首先會像mesi申請cache line使用權(quán)，然后開始分配一個cache line并且從寫addr，狀態(tài)變成E。
都是S狀態(tài):
cpu0讀的話，首先會像mesi申請cache line使用權(quán)，如果其他cpu已經(jīng)獲取了cache line的使用權(quán)的話，則這里要等待。獲得cache line使用權(quán)之后，直接把cache line的值讀出來就好了。
cpu0寫的話，首先會像mesi申請cache line使用權(quán)，cpu0寫addr，修改本地cache，狀態(tài)變成M，且發(fā)送一個inv消息給cpu1通知cpu1失效響應(yīng)的cache line，當然cpu1應(yīng)該會發(fā)送一個inval replay回來。
都是E,M的狀態(tài)是不存在的。因為，E/M狀態(tài)的核心一點就是表示cache line只在本地cpu中存在，不存在競爭關(guān)系。

cpu0,cpu1的cache狀態(tài)不一樣：
cpu0 I, cpu1 E:
cpu0 讀addr，首先會像mesi申請cache line使用權(quán)，發(fā)現(xiàn)cpu1有對應(yīng)的E cache，新建一個本地的cache line將cpu1的cache line拷貝過來，并且設(shè)置大家的狀態(tài)為S。
cpu0 寫addr，首先會像mesi申請cache line使用權(quán)，發(fā)現(xiàn)cpu1有對應(yīng)的E cache，發(fā)送一個inv消息告訴cpu1，并且等待其inval replay返回，然后本地新建一個cache line將ddr 讀進來，之后修改本地cache line，并且設(shè)置狀態(tài)M。
cpu1 讀addr，因為E狀態(tài)，無需向mes申請cache line使用權(quán)，直接讀cache。
cpu1 寫addr，因為E狀態(tài)，無需向mes申請cache line使用權(quán)，直接寫cache，設(shè)置狀態(tài)為M。

cpu0 I, cpu1 M:
cpu0 讀addr，首先會像mesi申請cache line使用權(quán)，發(fā)現(xiàn)cpu1有對應(yīng)的M cache，發(fā)送一個flush消息告訴cpu1并且等待cpu1刷新cache到ddr，然后新建一個本地cache line將ddr 從內(nèi)存讀進來，并且設(shè)置狀態(tài)為E。
cpu0 寫addr，首先會像mesi申請cache line使用權(quán)，發(fā)現(xiàn)cpu1有對應(yīng)的M cache，發(fā)送一個flush消息告訴cpu1并且等待cpu1刷新cache到ddr，然后新建一個本地cache line將ddr 從內(nèi)存讀進來并且寫，并且設(shè)置狀態(tài)為M。
cpu1 讀addr，因為M狀態(tài)，無需向mes申請cache line使用權(quán)，直接讀。
cpu1 寫addr，因為M狀態(tài)，無需向mes申請cache line使用權(quán)，直接寫。

cpu亂序模型：
http://www.72891.cn/thread-3593865-1-1.html

cpu亂序，cache一致性，和內(nèi)存屏障。
內(nèi)存屏障mb() 是和cpu亂序，chache一致性相關(guān)的。下面的老例子：
cpu0
a = 1;
wmb();
b = 2;

cpu1
讀 b;
rmb();
讀 a;

cpu亂序模型會讓a=1,a=2執(zhí)行順序顛倒。讀b，讀a順序顛倒。
wmb() 會使 a=1先執(zhí)行，然后再執(zhí)行 b=1, 說的再細一點同cache一致性就有關(guān)系了，因為a=1，之前說了是一個很多小步驟組成的過程，獲取cache使用權(quán)，寫cache，發(fā)送inval a ，修改m狀態(tài)。wmb實際上就是保證，在wmb之前所有的inval request已經(jīng)發(fā)了出去。就是說保證先發(fā)inval a, 然后再發(fā)inval b.

rmb() 會先執(zhí)行讀b，然后再執(zhí)行讀a，仔細一點，實際上就是說在rmb之前所有的inval request完成了。那么，我們剛才已經(jīng)知道了cpu1先收到的inval a然后是inval b，假設(shè)在 rmb()時，inval b已經(jīng)執(zhí)行了，那么這個時候會處理掉所有的inval request，確保inval a也應(yīng)執(zhí)行了。就是說cpu1假設(shè)讀到了b=2，那么rmb()之后，a肯定是1.

cache alias：
http://www.72891.cn/forum.php?mod=viewthread&tid=1972593

cache一般有幾種類型：
pipt
vivt
vipt noalias
vipt alias

實際上armv7 的dcache是vipt noalias的。icache是vipt alias的。
為什么會有cache alias問題呢，為什么amv7 dcache又沒有呢。

一個cache由 cache line size * num set * way 組成。
一般是 32 * 256 * 4 = 32KB.
如果line size * num set = 8KB大于page size的話那么就有可能有alias問題。
假設(shè)0xf000 0000和0xf000 1000兩段地址都是映射同一個page的話，那么訪問0xf000 0000和0xf000 1000時，他們在cache中的num是不同的，就是有各自的cache line，但是映射的物理地址是一樣的。如果硬件不能自動處理的話，軟件一定要處理好。
現(xiàn)在假設(shè)dcache是vipt alias的話，文件系統(tǒng)寫一個page cache時，會調(diào)用flush_dcache_page()來解決這個alias問題。
最終會調(diào)用到flush_pfn_alias()，好久不看相關(guān)的東西，看不懂這個鳥玩意了，請高手幫忙分析下。

作者: asuka2001 時間: 2014-06-30 13:47
回復(fù) 7# arm-linux-gcc

請教下：MESI是否有隊列做串行化？假設(shè)core 0和 core 1都寫了自己的 L1，然后同時發(fā)起 inval，誰成功？失敗者是否會得到通知并且重新 RFO再次寫入?

作者: asuka2001 時間: 2014-06-30 13:49
回復(fù) 11# blake326

mesi會保證整個一套動作是安全的

MESI作為 cache coherency protocol 硬件上應(yīng)該需要保證其串行，但是這個細節(jié)的確沒 google到，請賜教！

作者: blake326 時間: 2014-06-30 13:55
回復(fù) 13# asuka2001

這個帖子本來我就是這個疑問的。
所以想了想，為什么cache有這么幾種狀態(tài)，要把i,s, 和 m，e區(qū)分開來。m和e cache可以直接操作，而i，s 的cache所以會有一個保護同步機制。
所以，都是猜的。

作者: asuka2001 時間: 2014-06-30 14:01
回復(fù) 14# blake326

可能要找找硬件實現(xiàn)了，以前沒仔細考慮過這個問題，你的這個問題很有價值：）

大家可以更加深入的討論下 MESI的狀態(tài)轉(zhuǎn)化和底層硬件上的實現(xiàn)問題，比如 M -> S我記得是由硬件 snoop完成的。。。但是 inval怎么實現(xiàn)的，如何保證順序性，這些就不清楚了！

作者: arm-linux-gcc 時間: 2014-06-30 14:27
回復(fù) 12# asuka2001

應(yīng)該是有串行化處理的，SCU應(yīng)該會仲裁的

其中一些細節(jié)和過程我也不清楚，得找時間看看這方面的資料先

作者: asuka2001 時間: 2014-07-01 08:12
回復(fù) 16# arm-linux-gcc

我搜索了一下 arm的 architecture spec，沒有比較詳細準確的定義，估計得翻具體的芯片手冊看有沒有。

歡迎光臨 Chinaunix (http://www.72891.cn/)