Apa yang menyebabkan variabilitas tinggi ini dalam siklus untuk loop ketat sederhana dengan -O0 tetapi tidak -O3, pada Cortex-A72?

9

Saya menjalankan beberapa eksperimen untuk mendapatkan runtimes yang sangat konsisten untuk sepotong kode. Kode yang saya pilih saat ini adalah beban kerja terikat-CPU yang cukup arbitrer:

int cpu_workload_external_O3(){
    int x = 0;
    for(int ind = 0; ind < 12349560; ind++){
        x = ((x ^ 0x123) + x * 3) % 123456;
    }
    return x;
}

Saya telah menulis modul kernel yang menonaktifkan interupsi dan kemudian menjalankan 10 percobaan fungsi di atas, menentukan waktu setiap percobaan dengan mengambil perbedaan pada penghitung siklus jam dari sebelum dan sesudah. Hal-hal lain yang perlu diperhatikan:

  • mesin ini adalah ARM Cortex-A72, dengan 4 soket dengan masing-masing 4 core (masing-masing dengan cache L1 sendiri)
  • skala frekuensi jam tidak aktif
  • Hyperhreading tidak didukung
  • mesin tidak menjalankan apa-apa kecuali untuk beberapa proses sistem tulang kosong

Dengan kata lain, saya percaya sebagian besar / semua sumber variabilitas sistem diperhitungkan, dan, terutama ketika dijalankan sebagai modul kernel dengan interupsi dinonaktifkan melalui spin_lock_irqsave(), kode harus mencapai kinerja yang identik hampir sama dijalankan-untuk-menjalankan (mungkin kinerja kecil yang sukses) pada jalankan pertama ketika beberapa instruksi pertama kali ditarik ke dalam cache, tapi hanya itu).

Memang, ketika kode benchmark dikompilasi dengan -O3, saya melihat kisaran paling banyak 200 siklus dari ~ 135.845.192 rata-rata, dengan sebagian besar uji coba mengambil jumlah waktu yang persis sama. Namun , ketika dikompilasi dengan -O0, kisaran melonjak hingga sebanyak 158.386 siklus dari ~ 262.710.916. Dengan rentang yang saya maksud adalah perbedaan antara waktu lari terpanjang dan terpendek. Selain itu, untuk -O0kode, tidak ada banyak konsistensi yang mana dari cobaan yang paling lambat / tercepat - berlawanan dengan intuisi, dalam satu kesempatan yang tercepat adalah yang pertama, dan yang paling lambat adalah yang tepat setelah itu!

Jadi : apa yang mungkin menyebabkan ini terikat tinggi pada variabilitas dalam -O0kode? Melihat majelis, tampaknya -O3kode menyimpan semuanya (?) Dalam register, sedangkan -O0kode memiliki banyak referensi spdan sepertinya mengakses memori. Tapi meskipun begitu, saya berharap semuanya masuk ke cache L1 dan duduk di sana dengan waktu akses yang cukup deterministik.


Kode

Kode yang dijadikan patokan ada di cuplikan di atas. Perakitan di bawah. Keduanya dikompilasi gcc 7.4.0tanpa bendera kecuali untuk -O0dan -O3.

-O0

0000000000000000 <cpu_workload_external_O0>:
   0:   d10043ff        sub     sp, sp, #0x10
   4:   b9000bff        str     wzr, [sp, #8]
   8:   b9000fff        str     wzr, [sp, #12]
   c:   14000018        b       6c <cpu_workload_external_O0+0x6c>
  10:   b9400be1        ldr     w1, [sp, #8]
  14:   52802460        mov     w0, #0x123                      // #291
  18:   4a000022        eor     w2, w1, w0
  1c:   b9400be1        ldr     w1, [sp, #8]
  20:   2a0103e0        mov     w0, w1
  24:   531f7800        lsl     w0, w0, #1
  28:   0b010000        add     w0, w0, w1
  2c:   0b000040        add     w0, w2, w0
  30:   528aea61        mov     w1, #0x5753                     // #22355
  34:   72a10fc1        movk    w1, #0x87e, lsl #16
  38:   9b217c01        smull   x1, w0, w1
  3c:   d360fc21        lsr     x1, x1, #32
  40:   130c7c22        asr     w2, w1, #12
  44:   131f7c01        asr     w1, w0, #31
  48:   4b010042        sub     w2, w2, w1
  4c:   529c4801        mov     w1, #0xe240                     // #57920
  50:   72a00021        movk    w1, #0x1, lsl #16
  54:   1b017c41        mul     w1, w2, w1
  58:   4b010000        sub     w0, w0, w1
  5c:   b9000be0        str     w0, [sp, #8]
  60:   b9400fe0        ldr     w0, [sp, #12]
  64:   11000400        add     w0, w0, #0x1
  68:   b9000fe0        str     w0, [sp, #12]
  6c:   b9400fe1        ldr     w1, [sp, #12]
  70:   528e0ee0        mov     w0, #0x7077                     // #28791
  74:   72a01780        movk    w0, #0xbc, lsl #16
  78:   6b00003f        cmp     w1, w0
  7c:   54fffcad        b.le    10 <cpu_workload_external_O0+0x10>
  80:   b9400be0        ldr     w0, [sp, #8]
  84:   910043ff        add     sp, sp, #0x10
  88:   d65f03c0        ret

-O3

0000000000000000 <cpu_workload_external_O3>:
   0:   528e0f02        mov     w2, #0x7078                     // #28792
   4:   5292baa4        mov     w4, #0x95d5                     // #38357
   8:   529c4803        mov     w3, #0xe240                     // #57920
   c:   72a01782        movk    w2, #0xbc, lsl #16
  10:   52800000        mov     w0, #0x0                        // #0
  14:   52802465        mov     w5, #0x123                      // #291
  18:   72a043e4        movk    w4, #0x21f, lsl #16
  1c:   72a00023        movk    w3, #0x1, lsl #16
  20:   4a050001        eor     w1, w0, w5
  24:   0b000400        add     w0, w0, w0, lsl #1
  28:   0b000021        add     w1, w1, w0
  2c:   71000442        subs    w2, w2, #0x1
  30:   53067c20        lsr     w0, w1, #6
  34:   9ba47c00        umull   x0, w0, w4
  38:   d364fc00        lsr     x0, x0, #36
  3c:   1b038400        msub    w0, w0, w3, w1
  40:   54ffff01        b.ne    20 <cpu_workload_external_O3+0x20>  // b.any
  44:   d65f03c0        ret

modul kernel

Kode yang menjalankan uji coba di bawah ini. Bunyinya PMCCNTR_EL0sebelum / setelah setiap iterasi, menyimpan perbedaan dalam sebuah array, dan mencetak waktu min / max pada akhirnya di semua percobaan. Fungsi cpu_workload_external_O0dan cpu_workload_external_O3berada di file objek eksternal yang dikompilasi secara terpisah, dan kemudian ditautkan.

#include <linux/init.h>
#include <linux/module.h>
#include <linux/kernel.h>

#include "cpu.h"

static DEFINE_SPINLOCK(lock);

void runBenchmark(int (*benchmarkFunc)(void)){
    // Enable perf counters.
    u32 pmcr;
    asm volatile("mrs %0, pmcr_el0" : "=r" (pmcr));
    asm volatile("msr pmcr_el0, %0" : : "r" (pmcr|(1)));

    // Run trials, storing the time of each in `clockDiffs`.
    u32 result = 0;
    #define numtrials 10
    u32 clockDiffs[numtrials] = {0};
    u32 clockStart, clockEnd;
    for(int trial = 0; trial < numtrials; trial++){
        asm volatile("isb; mrs %0, PMCCNTR_EL0" : "=r" (clockStart));
        result += benchmarkFunc();
        asm volatile("isb; mrs %0, PMCCNTR_EL0" : "=r" (clockEnd));

        // Reset PMCCNTR_EL0.
        asm volatile("mrs %0, pmcr_el0" : "=r" (pmcr));
        asm volatile("msr pmcr_el0, %0" : : "r" (pmcr|(((uint32_t)1) << 2)));

        clockDiffs[trial] = clockEnd - clockStart;
    }

    // Compute the min and max times across all trials.
    u32 minTime = clockDiffs[0];
    u32 maxTime = clockDiffs[0];
    for(int ind = 1; ind < numtrials; ind++){
        u32 time = clockDiffs[ind];
        if(time < minTime){
            minTime = time;
        } else if(time > maxTime){
            maxTime = time;
        }
    }

    // Print the result so the benchmark function doesn't get optimized out.
    printk("result: %d\n", result);

    printk("diff: max %d - min %d = %d cycles\n", maxTime, minTime, maxTime - minTime);
}

int init_module(void) {
    printk("enter\n");
    unsigned long flags;
    spin_lock_irqsave(&lock, flags);

    printk("-O0\n");
    runBenchmark(cpu_workload_external_O0);

    printk("-O3\n");
    runBenchmark(cpu_workload_external_O3);

    spin_unlock_irqrestore(&lock, flags);
    return 0;
}

void cleanup_module(void) {
    printk("exit\n");
}

Perangkat keras

$ lscpu
Architecture:        aarch64
Byte Order:          Little Endian
CPU(s):              16
On-line CPU(s) list: 0-15
Thread(s) per core:  1
Core(s) per socket:  4
Socket(s):           4
NUMA node(s):        1
Vendor ID:           ARM
Model:               3
Model name:          Cortex-A72
Stepping:            r0p3
BogoMIPS:            166.66
L1d cache:           32K
L1i cache:           48K
L2 cache:            2048K
NUMA node0 CPU(s):   0-15
Flags:               fp asimd evtstrm aes pmull sha1 sha2 crc32 cpuid
$ lscpu --extended
CPU NODE SOCKET CORE L1d:L1i:L2 ONLINE
0   0    0      0    0:0:0      yes
1   0    0      1    1:1:0      yes
2   0    0      2    2:2:0      yes
3   0    0      3    3:3:0      yes
4   0    1      4    4:4:1      yes
5   0    1      5    5:5:1      yes
6   0    1      6    6:6:1      yes
7   0    1      7    7:7:1      yes
8   0    2      8    8:8:2      yes
9   0    2      9    9:9:2      yes
10  0    2      10   10:10:2    yes
11  0    2      11   11:11:2    yes
12  0    3      12   12:12:3    yes
13  0    3      13   13:13:3    yes
14  0    3      14   14:14:3    yes
15  0    3      15   15:15:3    yes
$ numactl --hardware
available: 1 nodes (0)
node 0 cpus: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
node 0 size: 32159 MB
node 0 free: 30661 MB
node distances:
node   0
  0:  10

Pengukuran Sampel

Di bawah ini adalah beberapa output dari satu eksekusi modul kernel:

[902574.112692] kernel-module: running on cpu 15                                                                                                                                      
[902576.403537] kernel-module: trial 00: 309983568 74097394 98796602 <-- max
[902576.403539] kernel-module: trial 01: 309983562 74097397 98796597                                                                                                                  
[902576.403540] kernel-module: trial 02: 309983562 74097397 98796597                                                                                                                  
[902576.403541] kernel-module: trial 03: 309983562 74097397 98796597
[902576.403543] kernel-module: trial 04: 309983562 74097397 98796597
[902576.403544] kernel-module: trial 05: 309983562 74097397 98796597                                                                                                                  
[902576.403545] kernel-module: trial 06: 309983562 74097397 98796597
[902576.403547] kernel-module: trial 07: 309983562 74097397 98796597
[902576.403548] kernel-module: trial 08: 309983562 74097397 98796597
[902576.403550] kernel-module: trial 09: 309983562 74097397 98796597                                                                                                                  
[902576.403551] kernel-module: trial 10: 309983562 74097397 98796597
[902576.403552] kernel-module: trial 11: 309983562 74097397 98796597
[902576.403554] kernel-module: trial 12: 309983562 74097397 98796597                                                                                                                  
[902576.403555] kernel-module: trial 13: 309849076 74097403 98796630 <-- min
[902576.403557] kernel-module: trial 14: 309983562 74097397 98796597                                                                                                                  
[902576.403558] kernel-module: min time: 309849076
[902576.403559] kernel-module: max time: 309983568                                                                                                                                    
[902576.403560] kernel-module: diff: 134492

Untuk setiap percobaan, nilai yang dilaporkan adalah: # siklus (0x11), # akses L1D (0x04), # akses L1I (0x14). Saya menggunakan bagian 11.8 dari referensi PMU ARM ini ).

sevko
sumber
2
Apakah ada utas lain yang berjalan? Akses memori mereka menyebabkan persaingan untuk bandwidth bus dan ruang cache bisa berpengaruh.
PRL
Bisa jadi. Saya belum mengisolasi core apa pun, dan meskipun demikian sebuah thread kernel mungkin dijadwalkan pada salah satu core lain pada socket. Tetapi jika saya mengerti lscpu --extendeddengan benar, maka setiap core memiliki data L1 dan cache instruksi masing-masing, dan kemudian setiap socket memiliki cache L2 bersama untuk 4 core-nya, jadi selama semuanya dilakukan dalam cache L1 saya akan mengharapkan kode untuk cukup banyak "memiliki" bisnya (karena itu satu-satunya yang berjalan pada intinya, sampai selesai). Saya tidak tahu banyak tentang perangkat keras pada level ini.
sevko
1
Ya, ini jelas dilaporkan sebagai 4 soket, tapi itu mungkin hanya masalah bagaimana interkoneksi ini dipasang di dalam SoC 16-core. Tetapi Anda memiliki mesin fisik, bukan? Apakah Anda memiliki nomor merek dan model untuk itu? Jika tutupnya lepas, mungkin Anda juga bisa memastikan apakah benar-benar ada 4 soket yang terpisah. Saya tidak melihat mengapa semua ini penting, meskipun, kecuali mungkin nomor vendor / model mobo. Benchmark Anda murni inti tunggal dan harus tetap panas di cache, jadi yang penting adalah inti A72 itu sendiri dan penyangga toko + penerusan toko.
Peter Cordes
1
Saya mengubah modul kernel untuk melacak tiga penghitung dan menambahkan beberapa contoh keluaran. Apa yang menarik adalah bahwa sebagian besar berjalan konsisten, tetapi kemudian acak akan jauh lebih cepat. Dalam hal ini, sepertinya yang tercepat sebenarnya memiliki akses L1 yang sedikit lebih sedikit , yang mungkin menyiratkan prediksi cabang yang lebih agresif di suatu tempat. Juga, sayangnya saya tidak memiliki akses ke mesin. Ini adalah contoh awal AWS (yang memberi Anda kepemilikan penuh atas perangkat keras fisik, jadi seolah-olah tidak ada gangguan dari hypervisor, dll.).
sevko
1
Menariknya, jika saya membuat modul kernel menjalankan kode ini pada semua CPU secara bersamaan on_each_cpu(), masing-masing melaporkan hampir tidak ada variabilitas di 100 percobaan.
sevko

Jawaban:

4

Di kernel Linux baru-baru ini, mekanisme migrasi halaman NUMA otomatis secara berkala menembak jatuh entri TLB sehingga dapat memonitor lokalitas NUMA. Reload TLB akan memperlambat kode O0, bahkan jika data tetap di L1DCache.

Mekanisme migrasi halaman tidak boleh diaktifkan pada halaman kernel.

Anda memeriksa untuk melihat apakah migrasi halaman NUMA otomatis diaktifkan

$ cat /proc/sys/kernel/numa_balancing

dan Anda dapat menonaktifkannya dengan

$ echo 0 > /proc/sys/kernel/numa_balancing
John D McCalpin
sumber
Saya telah melakukan beberapa pengujian terkait belakangan ini. Saya menjalankan beban kerja yang membuat banyak akses acak ke buffer memori yang cocok dengan nyaman di cache L1. Saya menjalankan banyak percobaan kembali ke belakang, dan waktu berjalan sangat konsisten (bervariasi secara harfiah kurang dari 0,001%), kecuali secara berkala ada lonjakan kecil ke atas. Dalam lonjakan itu, benchmark hanya berjalan 0,014% lebih lama. Ini kecil, tetapi masing-masing paku ini memiliki besaran yang persis sama, dan lonjakan terjadi sekali hampir persis setiap 2 detik. Mesin ini telah numa_balancingdinonaktifkan. Mungkin Anda punya ide?
sevko
Menemukannya. Saya menatap counter perf sepanjang hari tetapi ternyata akar penyebabnya adalah sesuatu yang sama sekali tidak berhubungan .. Saya menjalankan tes ini dalam sesi tmux pada mesin yang tenang. Interval 2 detik bertepatan persis dengan interval refresh tmux statusline saya, yang membuat permintaan jaringan di antara beberapa hal lainnya .. Menonaktifkannya membuat paku menghilang. Tidak tahu bagaimana skrip dijalankan oleh baris status saya pada cluster inti yang berbeda berdampak pada proses yang berjalan pada cluster inti yang terisolasi, hanya menyentuh data L1 ..
sevko
2

Varians Anda berada di urutan 6 * 10 ^ -4. Walaupun mengejutkan lebih dari 1,3 * 10 ^ -6, begitu program Anda berbicara dengan cache, ia terlibat dalam banyak operasi yang disinkronkan. Disinkronkan selalu berarti waktu yang terbuang.

Suatu hal yang menarik adalah bagaimana perbandingan -O0, -O3 Anda meniru aturan umum bahwa L1-cache-hit adalah sekitar 2x referensi register. O3 rata-rata Anda berjalan di 51,70% dari waktu O0 Anda. Ketika Anda menerapkan varian lebih rendah / atas, kami memiliki (O3-200) / (O0 + 158386), kami melihat peningkatan menjadi 51,67%.

Singkatnya, ya, cache tidak akan pernah bersifat deterministik; dan varian rendah yang Anda lihat sesuai dengan apa yang diharapkan dari sinkronisasi dengan perangkat yang lebih lambat. Ini hanya varian besar jika dibandingkan dengan mesin register-only yang lebih deterministik.

mevets
sumber
Instruksi diambil dari cache L1i. Saya kira Anda mengatakan bahwa tidak dapat menderita dari pelambatan yang tidak dapat diprediksi karena tidak koheren dengan cache data pada inti yang sama atau lainnya? Tapi bagaimanapun, jika jawaban Dr. Bandwidth benar, variansnya bukan karena cache itu sendiri, melainkan karena pembatalan dTLB berkala oleh kernel. Penjelasan itu sepenuhnya menjelaskan semua pengamatan: peningkatan varians dari termasuk setiap beban / toko di ruang pengguna, dan fakta bahwa penurunan ini tidak terjadi ketika mengatur waktu loop di dalam modul kernel. (Memori kernel Linux tidak dapat ditukar.)
Peter Cordes
Tembolok biasanya bersifat deterministik saat Anda mengakses data panas. Mereka dapat multi-porting untuk memungkinkan lalu lintas yang koherensi tanpa mengganggu muatan / toko dari inti itu sendiri. Dugaan Anda bahwa gangguan yang disebabkan oleh inti lainnya masuk akal, tetapi saya para numa_balancingTLB sendiri mungkin menjelaskannya.
Peter Cordes
Cache pengintai harus memiliki urutan yang tidak terputus di mana permintaan apa pun harus dihentikan. Perlambatan 10 ^ -4 pada operasi siklus 1 vs 2 berarti cegukan satu jam setiap 10 ^ 5 operasi. Seluruh pertanyaan benar-benar sebuah no-op, variansnya kecil.
mevets