實驗3 多cache一致性算法

一、實驗目的

熟悉cache一致性模擬器（監聽法和目錄法）的使用，并且理解監聽法和目錄法的基本思想，加深對多cache一致性的理解。

做到給出指定的讀寫序列，可以模擬出讀寫過程中發生的替換、換出等操作，同時模擬出cache塊的無效、共享和獨占態的相互切換。

二、實驗說明

學習cache一致性監聽法和目錄法，并且進行一致性算法的模擬實驗，同時熟悉相關知識。

三 實驗內容

1、cache一致性算法-監聽法模擬

1） 利用監聽法模擬器進行下述操作，并填寫下表

以下 I 表示無效, S表示共享, E表示獨占。模擬器采用不優化設置.

所進行的訪問	是否發生了替換？	是否發生了寫回？	監聽協議進行的操作與塊狀態改變
CPU A 讀第5塊	替換 Cache A的塊1	否	CPU A讀不命中, Cache A發出BusRd信號, 存儲器第5塊經Bus傳送到Cache A第1塊, Cache A第1塊狀態從I變成S
CPU B 讀第5塊	替換Cache B的塊1	否	CPU B讀不命中, Cache B發出BusRd信號, 存儲器第5塊經Bus傳送到Cache B第1塊, Cache B第1塊狀態從I變成S
CPU C 讀第5塊	替換Cache C的塊1	否	CPU C讀不命中, Cache C發出BusRd信號, 存儲器第5塊經Bus傳送到Cache C第1塊, Cache C第1塊狀態從I變成S
CPU B 寫第5塊	否	否	CPU B寫命中, Cache B向Bus發出寫作廢信號, Cache A第1塊和Cache C第1塊狀態都從S變成I, Cache B第1塊狀態從S變成E
CPU D 讀第5塊	替換 Cache D的塊1	Cache B的塊1寫回	CPU D讀不命中, Cache D發出BusRd信號, Cache B監聽到后把它的第1塊寫回到存儲器第5塊, 然后狀態從E變成I。之后該塊又從存儲器傳送到Cache D第1塊, 狀態設為E
CPU B 寫第21塊	替換CacheB 的塊1	否	CPU B寫不命中, Cache B發出BusRdx信號, 存儲器第21塊經Bus傳送到Cache B第1塊, 將原本的第1塊替換出去, 狀態設為E
CPU A 寫第23塊	替換CacheA的塊3	否	CPU A讀不命中, Cache A發出BusRdx信號, 存儲器第23塊經Bus傳送到Cache A第3塊, 狀態設為E
CPU C 寫第23塊	替換CacheC的塊3	CacheA的塊3寫回	CPU C寫不命中, Cache C發出BusRdx信號, Cache A監聽到該信號, 將其第3塊寫回到存儲器第23塊, 同時Cache A中該塊狀態改為I。之后存儲器第23塊傳送到Cache C第3塊, 狀態設為E
CPU B 讀第29塊	替換CacheB的塊1	CacheB的塊1寫回	CPU B讀不命中, Cache B發出BusRd信號, 存儲器第29塊經Bus傳送到Cache B第1塊, 將原來的塊替換出去, 將狀態設為S
CPU B 寫第5塊	替換CacheB的塊1	否	CPU B寫不命中, Cache B發出BusRdx信號, Cache D監聽到該信號后將其第1塊作廢, 存儲器第5塊傳送到Cache B第1塊, 替換原來的塊, 狀態設為E

2） 請截圖，展示執行完以上操作后整個cache系統的狀態

監聽法的基本原理是，每個處理器核心的緩存都可以監視（監聽）其他核心對共享數據的讀寫操作。當一個處理器核心對共享數據進行寫入時，它會發送一個寫入操作的通知（invalidate、update等）給其他核心的緩存，告知它們更新或無效化相應的緩存行。其他核心的緩存會在收到通知后，根據通知的類型進行相應的操作。

以下是監聽法模擬的基本步驟：

1. 每個處理器核心的緩存行都包含一個有效位（valid bit）用于表示緩存行是否有效，以及一個標簽（tag）用于唯一標識該緩存行所存儲的內存地址。
2. 當一個處理器核心對共享數據進行寫入操作時，它首先檢查自己的緩存中是否存在該數據的緩存行。如果存在，它將更新緩存行中的數據，并將該緩存行標記為“已修改（modified）”。
3. 同時，該核心會發送一個寫入操作的通知給其他核心的緩存，通知它們該緩存行已經被修改。這個通知可以是無效化（invalidate）操作或更新（update）操作，具體的實現方式取決于具體的監聽法協議。
4. 其他核心的緩存在接收到通知后，根據通知的類型進行相應的操作：
   1. 如果接收到無效化操作，則將自己的緩存行標記為無效（invalid），以后再訪問該數據時需要從主內存或其他核心的緩存中重新獲取。
   2. 如果接收到更新操作，則將自己的緩存行中的數據更新為最新的數據。
5. 當一個處理器核心需要讀取共享數據時，它首先檢查自己的緩存中是否存在有效的緩存行。如果存在有效的緩存行，則直接讀取緩存中的數據。如果緩存行無效，則需要從主內存或其他核心的緩存中獲取最新的數據。

通過監聽法模擬，每個核心都能感知到其他核心對共享數據的操作，并及時進行相應的緩存行更新或無效化，從而保持多核系統中緩存中的數據一致性。這種方式能夠有效解決多核處理器中共享數據的一致性問題，提高系統的可靠性和性能。

2、cache一致性算法-目錄法模擬

1）利用目錄法模擬器進行下述操作，并填寫下表

所進行的訪問	監聽協議進行的操作與塊狀態改變
CPU A 讀第6塊	Cache A讀不命中 從本地存儲器中傳送第6塊到Cache A第2塊, Cache A該塊狀態設為S, 存儲器中第6塊狀態也設為S, 將對應A的presence bit置1
CPU B 讀第6塊	Cache B讀不命中, 通過互聯網絡從宿主存儲器中傳送第6塊到Cache B第2塊, Cache B該塊狀態設為S, 存儲器中將對應B的presence bit置1
CPU D 讀第6塊	Cache D讀不命中, 通過互聯網絡從宿主存儲器中傳送第6塊到Cache D第2塊, Cache D該塊狀態設為S, 存儲器中將對應D的presence bit置1
CPU B 寫第6塊	Cache B寫命中, 向宿主存儲器發送寫命中信號, 宿主存儲器向A, D發送作廢信號, 將第6塊的A, D對應的presence bit復位, 將塊狀態設為E。 Cache B寫第2塊, 將塊狀態設為E
CPU C 讀第6塊	Cache C讀不命中, 向宿主存儲器發送讀缺失信號, 宿主存儲器向Cache B發送Fetch信號, Cache B將其第2塊狀態設為S, 向宿主存儲器寫回該塊。宿主存儲器收到該塊后將狀態設為S, 將C對應的presence bit置1, 將該塊傳送給Cache C, Cache C將該塊狀態設為S
CPU D 寫第20塊	Cache D寫不命中, Memory C通過互聯網絡從宿主存儲器中傳送第20塊到Cache D第0塊, Cache D該塊狀態設為E, 存儲器中將對應D的presence bit置1, 塊狀態設為E
CPU A 寫第20塊	Cache A寫不命中, 向宿主存儲器中發送Write miss, 宿主存儲器向Cache D發送Fectch信號, Cache D將其第0塊寫回宿主存儲器, 將塊狀態設為I。 存儲器中將對應D的presence bit復位, 將A對應的presence bit置1, 塊狀態設為E, 將該塊傳送給Cache A。 Cache A中該塊狀態設為E
CPU D 寫第6塊	Cache D寫不命中, 向宿主存儲器發送Write miss, 宿主存儲器向Cache D傳送該塊, 將對應B, C的presence bit復位, 將D對應的presence bit置1, 塊狀態設為E, 向Cache B, C發出作廢信號。Cache D中該塊狀態設為E。 Cache B, C均將該塊狀態設為I
CPU A 讀第12塊	Cache A讀不命中, 第12塊要替換出Cache A中的第0塊, 先將原本的第0塊寫回到宿主存儲器第20塊, 存儲器中第20塊狀態變成未緩沖。宿主存儲器將第12塊的狀態設為S, 將A對應的presence bit置1, 將該塊傳送給Cache A。 然后換入, 塊狀態設為S

2）請截圖，展示執行完以上操作后整個cache系統的狀態

目錄法的基本原理是，每個緩存塊都有一個對應的目錄項。目錄項中記錄了該緩存塊在哪些核心的緩存中被緩存，以及該緩存塊的共享狀態。

以下是目錄法模擬的基本步驟：

1. 每個處理器核心的緩存塊都包含一個有效位（valid bit）用于表示緩存塊是否有效，以及一個標簽（tag）用于唯一標識該緩存塊所存儲的內存地址。
2. 每個緩存塊的目錄項記錄了哪些核心的緩存中包含該緩存塊的副本，并記錄了每個核心對該緩存塊的共享狀態，例如“獨占（exclusive）”、“共享（shared）”、“無效（invalid）”等。
3. 當一個處理器核心需要讀取共享數據時，它首先檢查自己的緩存中是否存在該數據的緩存塊。如果存在有效的緩存塊，它會從該緩存塊中讀取數據。如果緩存塊無效，則需要從主內存或其他核心的緩存中獲取最新的數據。
4. 當一個處理器核心對共享數據進行寫入操作時，它首先檢查自己的緩存中是否存在該數據的緩存塊。如果存在有效的緩存塊，并且該緩存塊的共享狀態為“獨占”，表示該核心是唯一一個擁有該數據副本的核心，那么該核心可以直接在緩存塊中更新數據。
5. 如果存在有效的緩存塊，但其共享狀態為“共享”，表示其他核心也擁有該數據的副本，那么該核心需要向目錄發送一個請求，請求將該緩存塊的共享狀態變為“獨占”。同時，目錄會向其他包含該數據副本的核心發送無效化操作，讓它們將緩存塊標記為無效。
6. 當其他核心的緩存接收到無效化操作時，它們將對應的緩存塊標記為無效。如果其他核心的緩存塊在之后的訪問中需要讀取或寫入該數據，它們需要從主內存或其他核心的緩存中重新獲取最新的數據。

通過目錄法的模擬，每個核心都可以通過目錄來獲取共享數據的最新狀態，同時協調共享數據的訪問。目錄維護了所有共享數據的副本信息和共享狀態，通過協調緩存之間的通信和狀態轉換，確保多核處理器系統中緩存的一致性。

四、思考題

目錄法和監聽法分別是集中式和基于總線，兩者優劣是什么？

答：

監聽法

• 優點：核數較少時，總線壓力較小，成本低，效果好.

• 缺點：需要通過總線廣播一致性相關信息. 總線上能夠連接的處理器數目有限。當核數增多時，總線沖突增加, 監聽帶寬成為瓶頸

目錄法

• 優點：使用集中目錄來記錄每個cache塊的狀態，不需要總線廣播一致性信息, 總線壓力小。

• 缺點：需要維護目錄數據結構, 隨著核數增加時目錄的開銷變大。

五、實驗總結

在我進行對cache一致性模擬器的實驗過程中，我深入研究了監聽法和目錄法這兩種常見的cache一致性協議。通過實際的模擬器操作，我對這兩種協議的原理和工作機制有了更深入的理解。

首先，我發現監聽法是一種基于總線的cache一致性協議。在這個協議中，所有的緩存控制器都通過總線來監聽其他緩存控制器的操作。當一個緩存控制器修改了共享數據時，它會通過總線發送一個信號，讓其他緩存控制器將對應的緩存行置為無效。這樣，其他緩存控制器在需要訪問這個緩存行時，就會重新從內存中讀取最新的數據，保證了數據的一致性。通過實驗，我清晰地觀察到了監聽法的特點：簡單、易于實現，但是總線的帶寬成為性能瓶頸，并且在大規模系統中會導致嚴重的總線競爭問題。

其次，我研究了目錄法，這是一種基于目錄的cache一致性協議。在這個協議中，每個緩存控制器都維護了一個目錄表，用于記錄共享數據的狀態和位置。當一個緩存控制器修改了共享數據時，它會向目錄表發送一個更新請求，將對應的緩存行置為無效或者共享狀態。其他緩存控制器在需要訪問這個緩存行時，需要先向目錄表發出請求，獲取該數據的狀態和位置信息，然后根據相應的狀態進行操作。通過實驗，我發現目錄法相對于監聽法來說，減輕了總線的壓力，提高了并發度和擴展性。然而，目錄的維護和更新會帶來一定的開銷，特別是在多處理器系統中。

其他緩存控制器在需要訪問這個緩存行時，需要先向目錄表發出請求，獲取該數據的狀態和位置信息，然后根據相應的狀態進行操作。通過實驗，我發現目錄法相對于監聽法來說，減輕了總線的壓力，提高了并發度和擴展性。然而，目錄的維護和更新會帶來一定的開銷，特別是在多處理器系統中。

通過這次實驗，我不僅對cache一致性的概念和原理有了更深入的理解，還通過實際模擬操作加深了對監聽法和目錄法的理解。我認識到在設計和選擇cache一致性協議時，需要綜合考慮系統規模、性能需求、開銷以及硬件限制等方面的因素。不同的協議適用于不同的場景，了解它們的特點和優缺點有助于我們做出合適的選擇。同時，我也意識到cache一致性對于多處理器系統的正確性和性能具有重要影響，因此在實際應用中需要仔細權衡