最後使用的高速緩存行與不同的高速緩存行

Question

假設高速緩存行的寬度爲64字節，並且我有兩個數組a和b，它們填充高速緩存行並且也與高速緩存行對齊。我們還假設這兩個數組都在L1緩存中，所以當我從他們那裏讀取時，我沒有發現緩存未命中。

float a[16]; //64 byte aligned e.g. with __attribute__((aligned (64))) 
float b[16]; //64 byte aligned 

我讀a[0]。我的問題是現在閱讀a[1]比閱讀b[0]更快？ 換句話說，從上次使用的緩存行讀取速度更快嗎？

設置是否重要？現在假設我有一個32位的L1數據緩存，它是4路的。因此，如果a和b相距8192個字節，它們最終會在同一組中。這會改變我的問題的答案嗎？

另一種問我問題的方法是（我真正關心的）是閱讀一個矩陣。

換句話說，假設矩陣M適合L1高速緩存並且64字節對齊並且已經在L1高速緩存中，這兩個代碼選項中的哪一個將更有效。

float M[16][16]; //64 byte aligned 

版本1：

for(int i=0; i<16; i++) { 
    for(int j=0; j<16; j++) { 
     x += M[i][j]; 
    } 
} 

版本2：

for(int i=0; i<16; i++) { 
    for(int j=0; j<16; j++) { 
     x += M[j][i]; 
    } 
} 

編輯：爲了更清楚些，由於SSE/AVX讓我們假設我從a讀前八個值與AVX一起（例如與_mm256_load_ps()）。從a讀取下8個值會比從b讀取前8個值快（回想a和b已經在緩存中，所以不會有cahce miss）？

編輯：：自Intel Core 2和Nehalem以來，我主要對所有處理器感興趣，但我目前正在使用Ivy Bridge處理器並計劃儘快使用Haswell。

Answer 1

對於當前的英特爾處理器，加載兩個不同高速緩存行之間沒有性能差異，這兩個高速緩存行都在L1高速緩存中，其他所有條件都相同。鑑於float a[16], b[16];在同一高速緩存行a[0]最近被載入，a[1]爲a[0]和b[1]最近未加載但仍處於L1緩存，那麼就會出現在沒有其他一些因素的裝載a[1]和b[0]之間不存在性能差異。

有一點可以導致不同之處在於，如果最近存在某個地址與某個正在加載的值共享某些位的地址，但整個地址不同。英特爾處理器會比較一些地址位數，以確定它們是否可以與當前正在進行的商店相匹配。如果這些位匹配，則某些Intel處理器會延遲加載指令，以使處理器有時間解析完整的虛擬地址並將其與存儲的地址進行比較。但是，這是一個偶然的影響，並不是a[1]或b[0]所特有的。

從理論上來說，看到代碼的編譯器在短期內連續加載a[0]和a[1]可能會進行一些優化，例如使用一條指令加載它們。我上面的評論適用於硬件行爲，而不是C實施行爲。

隨着二維陣列的情況下，仍然應該是沒有區別，只要整個陣列M是在L1高速緩存。但是，當數組超過L1緩存時，數組的列遍歷對性能問題而言是臭名昭着的。出現問題的原因是地址映射到地址中固定位的緩存中，每個緩存集只能容納有限數量的緩存行，例如4個。這裏有一個問題情形：

• 數組M具有行長度是在地址導致的距離的倍數被映射到相同的高速緩存組，如4096個字節。例如，在陣列float M[1024][1024];,M[0][0]和M[1][0]相距4096字節並映射到相同的緩存集。
• 當您遍歷數組的一列時，您可以訪問M[0][0]，M[1][0],M[2][0],M[3][0]等等。每個這些元素的緩存行都被加載到緩存中。
• 當你沿着柱繼續，您可以訪問M[8][0]，M[9][0]，等等。由於每個緩存集都使用與前一個緩存集相同的緩存集，並且緩存集只能保存四行，因此包含M[0][0]等的較早行會從緩存中逐出。
• 當你完成列和讀M[0][1]開始下一列，該數據不再L1高速緩存，並且所有的負載必須取從L2緩存中的數據（或更糟，如果你也同樣慘敗L2緩存辦法）。

Answer 2

空間局部性是國王，因此版本＃1更快。一個好的編譯器甚至可以使用SSE/AVX矢量化讀取。

CPU重新排列讀取，因此無論哪一個是第一個都無關緊要。在無序的CPU中，如果兩個高速緩存行都是相同的，那麼它應該很小。

對於大型矩陣，保持局部性以使L1緩存保持熱點（緩存未命中少）更爲重要。

Answer 3

雖然我不直接知道你的問題的答案（其他人可能有更多關於處理器架構的知識），你試過嗎？是否有可能通過某種形式的benchmarking找出答案？

你可以得到一些功能的高分辨率計時器如QueryPerformanceCounter（假設你使用的是Windows）或操作系統等價的，然後遍歷你想x量的時間來測試讀取，然後再次獲得高分辨率定時器以獲得讀取平均時間。

爲不同的讀取再次執行此過程，您應該能夠比較不同類型讀取的平均讀取時間，這應該可以回答您的問題。這並不是說在不同的處理器上答案會保持不變。

Answer 4

獲取a[0]然後a[1]或b[0]在任一情況下應該達到2次訪問L1的緩存訪問。你沒有說你使用的是哪一個，但我不熟悉任何機制，它可以進一步「緩存」L1之上的全部緩存行（存儲單元中的任何位置），我不認爲這樣的機制可能是可行的（至少不是以合理的價格）。

假定你讀a[0]然後a[1]，並想保存再次訪問L1該行的努力 - 你的硬件必須既保持了整個緩存線某處在存儲單元中它會情況（不知道有多少這是常見的情況，所以這個功能可能不是努力），但也保持snoopable作爲您的緩存的邏輯擴展，以防其他內核試圖修改這兩個讀取之間的a[1]（其中x86允許wb內存）。事實上，它甚至可能是同一線程上下文中的商店，並且您必須警惕這一點（因爲當今大多數常見的x86 CPU都在無序執行加載）。如果你不保留這些（也可能是其他保護措施） - 如果你這樣做，你會破壞一致性 - 你已經創建了一個和你的L1一樣的怪物邏輯，只是爲了節省1-2個週期的訪問。然而，即使兩個選項都需要相同數量的高速緩存訪​​問，也可能存在影響其效率的其他因素，例如L1銀行業務，相同集訪問限制，懶惰LRU更新等等。所有這些都取決於在你的確切的機器實施。

如果您不只關注內存/緩存訪問效率，您的編譯器應該能夠矢量化訪問連續的內存位置，這仍然會導致相同的訪問，但在執行BW時會更輕。我認爲任何體面的編譯器都應該能夠以這種大小展開循環，並將連續的訪問合併到一個單獨的向量中，但是您可以通過使用選項1來幫助它（特別是如果還有寫入或其他有問題的指令在將compilcate工作編譯器中間）

編輯

既然你還問在L2矩陣擬合 - 簡化了問題 - 使用同一條線路在這種情況下（ s）的方式更好，因爲它可以讓你擊中L1，而另一種方法是不斷從L2中取出，這樣可以降低延遲和帶寬。這是背後的基本原理loop tiling/blocking