聯想緩存模擬 - 與出現故障的方案

Question

雖然在模擬全關聯緩存（以MIPS彙編）工作，一對夫婦的問題浮現在腦海根據網上看了一些資料處理;

據馬里蘭

尋找一個插槽大學的一些注意事項：最多隻有一個插槽應該匹配。如果 存在是 比賽，那麼你有一個錯誤的 全相聯高速緩存方案不止一個插槽。你 應該不會有高速緩存行的多個副本 在 全相聯高速緩存的任何插槽。 很難保持多個副本，並且不是 是有意義的。其他緩存行可以使用這些插槽 。

這是否意味着我應該檢查整個標籤列表以檢查第二個匹配的所有時間？畢竟，如果我不這樣做，我將永遠不會「意識到」緩存的錯誤，但是，檢查每一次看起來相當低效。

在這種情況下，我檢查，並以某種方式設法找到第二個匹配，意味着錯誤的緩存方案，那麼我該怎麼做？儘管最好的答案是修復我的實現，但是如果出現這種情況，我仍然對如何在執行過程中處理它感興趣。

Answer 1

如果超過一個有效插槽的地址匹配，那麼這意味着已執行了相同的地址上一個搜索的時候，無論是在不使用應該有相匹配的地址的有效插槽（也許是因爲它不是在檢查第一位）或多個無效插槽用於存儲根本不在緩存中的行。

毫無疑問，這應該被視爲一個錯誤。

但是，如果我們剛剛決定不修復bug（也許我們寧願不犯那麼多的硬件提升到一個更好的實現）最明顯的選擇是挑選插槽無效之一。它將可用於其他緩存行。

至於如何挑選無效哪一個，如果重複行的一個是乾淨的，無效的一個優先於髒緩存行。如果超過高速緩存行很髒，他們不同意你有一個更大的錯誤修復，但無論如何你的緩存不同步，它可能無所謂你選擇。

編輯：這裏是如何我有可能實現的硬件來做到這一點：

首先，它沒有一大堆的意義開始有重複的假設，而我們會解決這稍後在適當的時候。在緩存新行時必然發生的幾種可能性。

• 該行已經在緩存中，需要
• 線不在緩存中沒有動作，但也有無效的插槽：將新行插入可用插槽的一個
• 線不在緩存中，但沒有可用的無效插槽。另一條有效線路必須被驅逐，新線路才能取代它。
  
  • 選擇驅逐候選人會產生性能後果。清理緩存行可以免費被驅逐，但如果選擇不當，它可能會導致另一個緩存未命中。考慮是否所有的緩存行都是髒的。如果只有乾淨的高速緩存行被逐出，那麼在兩個地址之間交替的許多順序讀取將在每次讀取時導致高速緩存未命中。緩存失效是Comp Sci中的兩個問題之一（另一個是'命名事物'），並且超出了這個確切問題的範圍。

我可能會實施，檢查正確的插槽作用於每個它們的搜索。然後另一個塊將從該列表中選出第一個並對其執行操作。

現在，回到問題。重複項可能會進入緩存的條件是什麼？如果內存訪問是嚴格排序的，並且實現（如上）是正確的，我不認爲重複是可能的。因此沒有必要檢查它們。

現在讓我們考慮一個更令人難以置信的情況，其中單個緩存在兩個CPU內核之間共享。我們將只做最簡單的事情，除了每個內核的緩存本身之外，它可以工作並複製所有內容。因此，插槽搜索硬件是而不是共享。爲了支持這一點，每個插槽使用一個額外的位作爲互斥體。搜索硬件不能使用被另一個核心鎖定的插槽。具體而言，

• 如果地址在緩存中，請嘗試鎖定該插槽並返回該插槽。如果插槽已被鎖定，則失速，直到它空閒爲止。
• 如果地址不在高速緩存中，請查找未鎖定的插槽，該插槽無效或有效但可以回收。

在這種情況下，我們實際上可能最終處於兩個槽共享相同地址的位置。如果兩個內核嘗試寫入不在緩存中的地址，它們將最終獲得不同的插槽，並且會出現重複行。首先讓我們想想看會發生什麼：

• 這兩行都是從主內存讀取的。他們將是相同的價值，他們都將是乾淨的。驅逐也是正確的。
• 這兩行都是寫入。兩者都會很髒，但可能並不相同。這是應用程序通過發佈內存隔離或其他內存排序指令已解決的競爭條件。我們無法猜測應該使用哪一個，如果沒有緩存，競態條件會持續到RAM中。驅逐也是正確的。
• 一行是一個讀，一個是寫。寫入很髒，但讀取很乾淨。如果沒有干預緩存，這種競爭條件又會持續到內存中，但讀者可能看到不同的值。清除乾淨的行是正確的RAM，也有副作用，總是有利於閱讀，然後寫命令。

所以現在我們知道該怎麼做，但是這個邏輯屬於哪裏。首先讓我們想想如果我們什麼都不做，會發生什麼。隨後對任一內核上相同地址的高速緩存訪​​問可返回任一行。即使兩個核心都沒有發出寫入，讀取可能會不同，在兩個值之間交替。這打破了所有關於記憶排序的想法。

一種解決方案可能只是說髒線只屬於一個內核，線不髒，但髒和歸另一個內核所有。

• 在兩次同時讀取的情況下，兩行都是相同的，解鎖的和可互換的。無論核心在哪一行獲得後續操作都無關緊要。
• 在併發寫入的情況下，兩條線不同步，但相互不可見。雖然由此產生的競爭條件是不幸的，但它仍然導致合理的內存排序，就好像在被清除的行上發生的所有操作發生在清理行上的任何操作之前一樣。
• 如果讀取和寫入同時發生，髒線對讀取核心是不可見的。然而，兩個內核都可以看到乾淨的行，並且會導致內存排序對作者造成破壞。將來的寫入甚至可能會導致它同時鎖定（因爲兩者都會變髒）。

最後一個案例幾乎妨礙了那些髒線被清理乾淨。這迫使至少一些額外的硬件首先尋找髒線，並且只有當沒有找到髒線時清理線。所以，現在我們有一個新的併發緩存實現：

• 如果地址是在緩存和衛生條件很差，請求核擁有，使用插槽
• 如果地址是在緩存中，但乾淨
  • 進行讀取，只使用該插槽
  • 的寫操作，標記插槽髒，並使用該插槽
• 如果地址不在緩存中，有無效的插槽，使用了無效的插槽
• 如果沒有無效插槽，請逐出並使用該插槽。

我們正在接近，實施中還有一個漏洞。如果兩個內核訪問相同的地址，但不同時會怎麼樣？最簡單的事情可能只是說髒線對其他內核是不可見的。在高速緩存中，但骯髒與完全不在高速緩存中相同。

現在我們所要考慮的其實就是爲應用程序提供同步工具。我可能會做一個工具，只是明確地刷新一條線，如果它很髒。這隻會調用驅逐期間使用的相同硬件，但將該行標記爲乾淨而非無效。

要做出長篇幅短文，其思想是通過刪除它們來處理重複內容，但要確保它們不會導致進一步的內存排序問題，並將重複數據刪除工作留給應用程序或最終驅逐。