一次只能有一個CPU訪問RAM？

Question

我目前正在嘗試進入多核編程。我想用C++/Python/Java編寫/實現並行矩陣乘法（我猜Java是最簡單的）。

但是我自己無法回答的一個問題是RAM訪問如何與多個CPU一起工作。

我的想法

我們有兩個矩陣A和B，我們想計算C = A * B：

並行執行只會更快，當N，M或p很大。假設n，m和p> = 10,000。爲簡單起見，假設n = m = p = 10,000 = 10^4。

我們知道，我們可以計算每個$ {C_ I，J} $ withouth的看着C的其他條目因此，我們可以計算在每一個平行{C_ I，J}：

但是，所有的c_ {1，i}（i \ in 1，...，p）都需要A的第一行。由於A是一個10^8雙精度的數組，它需要800 MB。這絕對比CPU緩存大。但是一行（80kB）將適合CPU緩存。所以我想最好把C的每一行都分配給一個CPU（只要CPU是空閒的）。所以這個CPU至少有A在它的緩存中，並從中受益。

我的問題

如何RAM訪問了不同的內核管理（在正常英特爾在筆記本）？

我想必須有一個「控制器」，一次給一個CPU獨佔訪問權限。這個控制器有一個特殊的名字嗎？

偶然地，兩個或多個CPU可能需要相同的信息。他們能同時得到它嗎？內存訪問是矩陣乘法問題的瓶頸嗎？

請讓我也知道，當你知道一些好書向你介紹多核編程（在C++/Python/Java中）。

Answer 1

您應該以緩存友好的方式（有很多方法 - 搜索「平鋪」here's a nice explanation from Berkeley）分離並行化矩陣乘法的問題，從多核如何共享某些資源（如共享緩存和內存。第一個是指如何避免高速緩存顛簸，並且可以實現數據的有效重用（在給定的高速緩存層次結構上），後者是指內存帶寬利用率。確實，兩者是連接的，但它們大多是相互排斥的，因爲良好的緩存會降低您的出站帶寬（這對於性能和功耗來說當然是可取的）。但是，有時候，如果數據不可重複使用或算法無法修改以適應緩存，則無法完成。在這些情況下，內存帶寬可能會成爲你的瓶頸，不同的核心將盡可能地分享它。大多數現代CPU都有多個共享最後一級緩存的內核（我不確定這是在某些智能手機細分市場中的情況，但通常適用於筆記本電腦/臺式機/服務器）。該緩存反過來與內存控制器進行通信（該內存控制器曾經坐落在一個名爲北橋的不同芯片上，但是由於幾年前已集成到大多數CPU中以便更快訪問）。 通過內存控制器，整個CPU可以與DRAM進行通信並告訴它要獲取什麼。MC通常足夠聰明，可以組合訪問，從而只需要最少的時間和精力來獲取（請記住，從DRAM中獲取「頁面」是一項長期任務，通常需要首先驅逐緩存在讀出放大器中的當前頁面）。

請注意，這種結構意味着MC不必分別與多個內核通話，它只是將數據提取到最後一級緩存。內核也不需要直接與內存控制器通信，因爲訪問通過最後一級緩存進行過濾（有少數例外，例如不可緩存的訪問將通過它，IO訪問有另一個控制器）。除了它們自己的私有緩存之外，所有內核都將共享該緩存存儲。

現在有關共享的說明 - 如果2個（或更多）內核同時需要相同的數據，那麼您很幸運 - 無論它是否已經在緩存中（在這種情況下，兩個訪問都將通過發送數據發送到每個核心，並將它們標記爲「共享」），或者如果數據不存在，則兩者都將等到MC能夠將其帶入（一次），然後繼續與打擊情況一樣。然而，一旦有一個或多個內核需要將新數據寫入該行或其中的一部分，一旦出現異常。在這種情況下，修改器將發出讀取所有權請求（RFO），這會阻止共享線路並使其他核心中的所有副本無效，否則您將面臨失去緩存一致性或一致性的風險（因爲一個核心可能使用陳舊的數據或察覺不正確的記憶順序）。這被稱爲並行算法中的爭用條件，並且是複雜的鎖定/屏蔽機制的原因。再次注意，這與實際的RAM訪問是正交的，並且可能同樣適用於最後一級緩存訪問。