為什麼 513x513 矩陣轉置比 512x512 矩陣轉置更快？

了解512x512 和513x513 矩陣大小的矩陣轉置的性能差異

不同大小的方形矩陣在涉及到時表現出獨特的時間差異轉置它們。有趣的是，與維度為 2^n 1 的矩陣相比，維度為 2^n 的矩陣往往有較慢的轉置時間。雖然這些差異對於較小的n 值可能似乎微不足道，但在較大維度上它們變得顯著，如MATSIZE 512 所證明的那樣.

為了理解這種性能差異的根本原因，我們深入研究了以下概念：快取。

快取組織和集合映射

快取被組織成集合和行。每組包含多條可以儲存資料的線。為了找到特定記憶體位址所屬的集合，我們使用以下公式：

因此，記憶體位址以某種統一的方式對應到集合。

快取未命中和行驅逐

存取記憶體位置時，快取會檢查資料是否已存在。如果沒有，則發生高速緩存未命中，並從記憶體中讀取相應的行並將其放入高速緩存中。但是，當快取已滿時，它會逐出最近最少使用（LRU）行以容納新資料。

關鍵步幅

關鍵步幅表示間距競爭相同快取線的變數之間。其計算方式如下：

由關鍵步幅或其倍數間隔開的變數更有可能導致快取驅逐。

矩陣轉置與關鍵步幅

想像一個有 8kB 快取和四行的 64x64 矩陣每套。每行可容納八個 64 位元整數。此場景中的關鍵步長是 2048 字節，相當於矩陣的四行。

轉置矩陣時，我們交換行和列。當我們處理每一行並將其與其對應的列交換時，由關鍵步幅（四行）分隔的元素會遇到快取驅逐。這會導致大量快取重新加載，從而導致轉置速度變慢。

結論

512x512 和 513x513 矩陣之間的轉置時間差異源自於下列關係：矩陣維度與快取的關鍵步長。維度不是關鍵步幅倍數的矩陣會減少快取驅逐，從而加快換位時間。

以上是為什麼 513x513 矩陣轉置比 512x512 矩陣轉置更快？的詳細內容。更多資訊請關注PHP中文網其他相關文章！