具有唯一矩陣轉置問題的2D阻塞-有解無憂

我有struct complex {double real = 0.0; double imag = 0.0;};以 3 階張量的形式組織的型別的復雜值資料。底層容器具有與記憶體頁面邊界對齊的連續記憶體布局。

張量的自然“切片”方向是沿方向 1。這意味著快取行以方向 3、2 和最后 1 的順序延伸。換句話說，索引函式看起來像這樣：(i, j, k) -> i * N2 * N3 j * N3 k. 具有唯一矩陣轉置問題的 2D 阻塞

我需要沿方向 2 轉置切片。在上面的第一張影像中，紅色矩形是我希望轉置的張量切片。

我的 C 代碼如下所示：

for (auto vslice_counter = std::size_t{}; vslice_counter < n2;   vslice_counter)
    {        
        // blocked loop
        for (auto bi1 = std::size_t{}; bi1 < n1; bi1  = block_size)
        {
            for (auto bi3 = std::size_t{}; bi3 < n3; bi3  = block_size)
            {
                for (auto i1 = std::size_t{}; i1 < block_size;   i1)
                {
                    for (auto i3 = std::size_t{}; i3 < block_size;   i3)
                    {
                        const auto i1_block = bi1   i1;
                        const auto i3_block = bi3   i3;
                        tens_tr(i3_block, vslice_counter, i1_block) = tens(i1_block, vslice_counter, i3_block);
                    }
                }
            }
        }
    }

用于測驗的機器：雙路 Intel(R) Xeon(R) Platinum 8168 with

24 核 @ 2.70 GHz 和
L1、L2 和 L3 快取大小分別為 32 kB、1 MB 和 33 MB。

我用塊大小繪制了這個函式的性能圖表，但我驚訝地發現沒有變化！事實上，樸素的實作和這個一樣好。

問題：在這種情況下，2D 阻塞是否有助于提高性能？

編輯：

附加資訊：

使用的編譯器是英特爾 C 編譯器。
block_size是輸入引數，而不是編譯時間常數。
在測驗期間，我將值block_size從 4 更改為 256。這分別轉換為 256 B 和 1 MB 的塊，因為這些塊是邊長的正方形block_size。我的目標是用塊填充 L1 和/或 L2 快取。
用于優化的編譯標志：-O3;-ffast-math;-march=native;-qopt-zmm-usage=high

uj5u.com熱心網友回復：

TL;DR：2D 阻塞代碼并不快，主要是因為快取垃圾（還有一點是由于預取）。簡單的實作和 2D-??blocking 都是低效的。這篇文章中描述了類似的效果。您可以使用小型臨時陣列緩解此問題，并使用暫存器平鋪優化來提高性能。額外的填充也可能會有所幫助。

CPU 快取

首先，現代 CPU 的快取都是set-associative cache。一個 m 路關聯快取可以看作是一個n x m矩陣，其n集合包含一個m快取行塊。記憶體塊首先映射到一個集合，然后放入任何一個m目標集的快取行（關于快取替換策略）。當演算法（如轉置）執行跨步記憶體訪問時，處理器通常訪問相同的集合，并且可以使用的目標快取行的數量要少得多。當步幅為 2 的大冪（或更準確地說，可被 2 的大冪整除）時尤其如此。可以訪問的可能高速快取行的數量可以使用模運算或基本模擬來計算。在最壞的情況下，所有訪問都在同一個快取行集上完成（包含m快取行）。在這種情況下，每次訪問都會導致處理器逐出集合中的一個快取行，以使用通常不完美的替換策略在其中加載一個新的快取行。您的 Intel(R) Xeon(R) Platinum 8168 處理器具有以下快取屬性：

  Level     Size (KiB/core)    Associativity    # Sets
-------------------------------------------------------
L1D Cache           32             8-way           64
 L2 Cache         1024            16-way         1024
 L3 Cache         1408            11-way         2048

* All cache have 64-byte cache lines

這意味著您執行的訪問步幅可被 4096 位元組（即 256 個復數）整除，然后所有訪問都將映射到 L1D 快取中的同一 L1D 快取集，從而導致沖突未命中，因為只能加載 8 個快取行同時地。這會導致一種稱為快取垃圾的影響，大大降低了性能。這篇文章提供了更完整的解釋：CPU 快取如何影響 C 程式的性能？.

快取對轉置的影響

您提到它block_size最多可以是 256n1并且n3可以被 256 整除，因為提供的代碼已經隱含假設n1并且n3可以被整除block_size，我希望n2也可以被 256 整除。這意味著沿維度 3 的線的大小p * 256 * (2 * 8) = 4096p bytes = 64p cache lines是p = n3 / block_size。這意味著所有行的第 i 個專案將映射到完全相同的 L1D 快取集。

由于您在維度 1 和 3 之間執行轉置，這意味著行之間的空間更大。兩個后續行的兩個第 i 項之間的間隙是G = 64 * p * n2快取行。假設n2能被 16 整除，G = 1024 * p * q那么q = n2 / 16.

有這樣的差距是一個巨大的問題。實際上，您的演算法讀取/寫入同一塊中許多行的許多 i 項。因此，此類訪問將映射到 L1D 和 L2 快取中的同一組，從而導致快取垃圾。如果block_size> 16，快取行將幾乎系統地重新加載到 L2（4 次）。我預計 L3 在這種情況下不會有太大幫助，因為它主要是為內核之間的共享資料而設計的，它的延遲非常大（50-70 個周期）并且p * q肯定可以被 2 的冪整除。由于缺乏并發性，處理器無法減輕延遲（即可以同時預取的可用快取行）。這導致帶寬被浪費，更不用說非連續訪問已經降低了吞吐量。block_size如上一篇相關文章（如上鏈接）所示，這種效果應該已經以較小的兩個值的冪可見。

預取的影響

在這種情況下，像您這樣的英特爾 Skylake SP 處理器每次訪問同時預取至少 2 個快取行（128 位元組）。這意味著 a block_size< 8 不足以完全使用tens. 結果，太小block_size會由于預取而浪費帶寬，而太大也會浪費帶寬，但由于快取垃圾。我希望最好block_size的接近8。

如何解決這個問題

一種解決方案是將每個塊存盤在一個小的臨時二維陣列中，然后轉置，然后寫入。乍一看，由于更多的記憶體訪問，它看起來會更慢，但它通常要快得多。實際上，如果塊大小相當小（例如 <=32），那么小的臨時陣列可以完全適合 L1 快取，因此在轉置期間不會受到任何快取垃圾的影響。該塊可以被有效地讀取，但可以更有效地存盤（即更連續的訪問）。

添加另一個阻塞級別應該有助于提高性能，因為 L2 快取被更有效地使用（例如，使用block_sizeset 128~256）。勒貝格曲線可用于實作快速快取遺忘演算法，盡管它使代碼更加復雜。

另一個優化包括添加另一個阻塞級別來執行稱為register-tiling的優化。這個想法是使用 2 個嵌套回圈操作一個具有較小編譯時間常數的塊，以便編譯器展開回圈并生成更好的指令。例如，對于大小為 4x4 的 tile，這使編譯器能夠生成以下代碼（參見Godbolt）：

..B3.7:
        vmovupd   xmm0, XMMWORD PTR [rdx r8]
        vmovupd   XMMWORD PTR [r15 rdi], xmm0 
        inc       r14 
        vmovupd   xmm1, XMMWORD PTR [16 rdx r8]
        vmovupd   XMMWORD PTR [r15 r10], xmm1 
        vmovupd   xmm2, XMMWORD PTR [32 rdx r8]
        vmovupd   XMMWORD PTR [r15 r12], xmm2 
        vmovupd   xmm3, XMMWORD PTR [48 rdx r8]
        vmovupd   XMMWORD PTR [r15 r13], xmm3 
        vmovupd   xmm4, XMMWORD PTR [rdx r9]
        vmovupd   XMMWORD PTR [16 r15 rdi], xmm4 
        vmovupd   xmm5, XMMWORD PTR [16 rdx r9]
        vmovupd   XMMWORD PTR [16 r15 r10], xmm5 
        vmovupd   xmm6, XMMWORD PTR [32 rdx r9]
        vmovupd   XMMWORD PTR [16 r15 r12], xmm6 
        vmovupd   xmm7, XMMWORD PTR [48 rdx r9]
        vmovupd   XMMWORD PTR [16 r15 r13], xmm7 
        vmovupd   xmm8, XMMWORD PTR [rdx r11]
        vmovupd   XMMWORD PTR [32 r15 rdi], xmm8 
        vmovupd   xmm9, XMMWORD PTR [16 rdx r11]
        vmovupd   XMMWORD PTR [32 r15 r10], xmm9 
        vmovupd   xmm10, XMMWORD PTR [32 rdx r11]
        vmovupd   XMMWORD PTR [32 r15 r12], xmm10 
        vmovupd   xmm11, XMMWORD PTR [48 rdx r11]
        vmovupd   XMMWORD PTR [32 r15 r13], xmm11 
        vmovupd   xmm12, XMMWORD PTR [rdx rbp]
        vmovupd   XMMWORD PTR [48 r15 rdi], xmm12 
        vmovupd   xmm13, XMMWORD PTR [16 rdx rbp]
        vmovupd   XMMWORD PTR [48 r15 r10], xmm13 
        vmovupd   xmm14, XMMWORD PTR [32 rdx rbp]
        vmovupd   XMMWORD PTR [48 r15 r12], xmm14 
        vmovupd   xmm15, XMMWORD PTR [48 rdx rbp]
        vmovupd   XMMWORD PTR [48 r15 r13], xmm15 
        add       r15, rsi 
        add       rdx, 64 
        cmp       r14, rbx 
        jb        ..B3.7

而不是這個（重復8次）：

..B2.12:
        vmovupd   xmm0, XMMWORD PTR [rsi r14]
        vmovupd   XMMWORD PTR [rbx r15], xmm0
        inc       rax
        vmovupd   xmm1, XMMWORD PTR [16 rsi r14]
        vmovupd   XMMWORD PTR [rbx r13], xmm1
        add       rbx, r9
        add       rsi, 32
        cmp       rax, rcx
        jb        ..B2.12

最后，可以使用 AVX/AVX-2/AVX-512 內在函式為僅 x86-64 的處理器實作更快的切片轉置。

請注意，在每行的末尾添加一些填充以使它們不能被的冪整除也應該顯著有助于減少快取垃圾。話雖如此，一旦應用了上述優化，這可能就沒有用了。

轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/480049.html

標籤：C 表现缓存性能测试转置

上一篇：有人可以解釋一下Dmitry是如何降低NMin數學的嗎？

下一篇：您如何推斷基準資料的波動？