Mengapa ada performa luar biasa di 2048x2048 versus 2047x2047 multiplikasi?

127

Saya membuat beberapa pembandingan multiplikasi matriks, seperti yang disebutkan sebelumnya dalam Mengapa MATLAB begitu cepat dalam penggandaan matriks?

Sekarang saya punya masalah lain, ketika mengalikan dua matriks 2048x2048, ada perbedaan besar antara C # dan lainnya. Ketika saya coba kalikan hanya 2047x2047 matriks, sepertinya normal. Menambahkan beberapa yang lain untuk perbandingan juga.

1024x1024 - 10 detik.

1027x1027 - 10 detik.

2047x2047 - 90 detik.

2048x2048 - 300 detik.

2049x2049 - 91 detik. (memperbarui)

2500x2500 - 166 detik

Itu adalah perbedaan tiga setengah menit untuk kasus 2k dengan 2k.

menggunakan array 2dim

//Array init like this
int rozmer = 2048;
float[,] matice = new float[rozmer, rozmer];

//Main multiply code
for(int j = 0; j < rozmer; j++)
{
   for (int k = 0; k < rozmer; k++)
   {
     float temp = 0;
     for (int m = 0; m < rozmer; m++)
     {
       temp = temp + matice1[j,m] * matice2[m,k];
     }
     matice3[j, k] = temp;
   }
 }
Serigala
sumber
23
Ini akan menjadi pertanyaan ujian yang bagus untuk pemrograman C tingkat lanjut atau kelas Desain OS ;-)
Dana the Sane
Sudahkah Anda mencoba menguji array multidimensi [,] dan bergerigi [] [] serta 32 dan 64 bit? Saya hanya menguji beberapa kali tetapi bergerigi tampak lebih sesuai dengan hasil Anda tetapi bergerigi 64bit tinggi, saya tidak tahu apakah ada heuristik di jit yang berlaku untuk situasi ini atau jika cache terkait seperti yang disarankan sebelumnya. Jika Anda menginginkan solusi GPGPU ada research.microsoft.com/en-us/projects/accelerator yang harus bersaing dengan waktu di pos lainnya.
Kris
Pertanyaan yang agak naif, tetapi berapa banyak ops (penambahan / penggandaan) yang terlibat dalam mengalikan dua matriks kuadrat?
Nick T

Jawaban:

61

Ini mungkin ada hubungannya dengan konflik di cache L2 Anda.

Cache missses pada matice1 bukan masalah karena diakses secara berurutan. Namun untuk matice2 jika kolom lengkap cocok dengan L2 (yaitu ketika Anda mengakses matice2 [0, 0], matice2 [1, 0], matice2 [2, 0] ... dll, tidak ada yang diusir) daripada tidak ada masalah dengan cache merindukan dengan matice2 baik.

Sekarang untuk lebih dalam bagaimana cache bekerja, jika alamat byte variabel Anda adalah X, daripada baris cache untuk itu adalah (X >> 6) & (L - 1). Di mana L adalah jumlah total garis cache di cache Anda. L selalu berkekuatan 2. Enam berasal dari fakta bahwa 2 ^ 6 == 64 byte adalah ukuran standar garis cache.

Sekarang apa artinya ini? Yah itu berarti bahwa jika saya memiliki alamat X dan alamat Y dan (X >> 6) - (Y >> 6) dapat dibagi oleh L (yaitu beberapa kekuatan besar 2), mereka akan disimpan dalam cacheline yang sama.

Sekarang untuk kembali ke masalah Anda apa perbedaan antara 2048 dan 2049,

ketika 2048 adalah ukuran Anda:

jika Anda mengambil & matice2 [x, k] dan & matice2 [y, k] perbedaannya (& matice2 [x, k] >> 6) - (& matice2 [y, k] >> 6) akan habis dibagi 2048 * 4 (ukuran dari float). Jadi kekuatan besar 2.

Jadi tergantung pada ukuran L2 Anda, Anda akan memiliki banyak konflik garis cache, dan hanya menggunakan sebagian kecil dari L2 Anda untuk menyimpan kolom, sehingga Anda tidak akan benar-benar dapat menyimpan kolom penuh dalam cache Anda, sehingga Anda akan mendapatkan kinerja yang buruk .

Ketika ukuran 2049, maka perbedaannya adalah 2049 * 4 yang bukan kekuatan 2 sehingga Anda akan memiliki lebih sedikit konflik dan kolom Anda akan masuk ke cache dengan aman.

Sekarang untuk menguji teori ini ada beberapa hal yang dapat Anda lakukan:

Alokasikan array matice2 array Anda seperti ini matice2 [razmor, 4096], dan jalankan dengan razmor = 1024, 1025 atau ukuran apa pun, dan Anda akan melihat kinerja yang sangat buruk dibandingkan dengan yang Anda miliki sebelumnya. Ini karena Anda secara paksa menyelaraskan semua kolom untuk saling bertentangan.

Kemudian coba matice2 [razmor, 4097] dan jalankan dengan ukuran berapa pun dan Anda akan melihat kinerja yang jauh lebih baik.

zviadm
sumber
Apakah Anda membuat kesalahan dalam 2 paragraf terakhir? Kedua percobaan sama persis. :)
Xeo
Cache associativity juga berperan.
Ben Jackson
20

Mungkin efek caching. Dengan dimensi matriks yang merupakan kekuatan besar dua, dan ukuran cache yang juga merupakan kekuatan dua, Anda hanya dapat menggunakan sebagian kecil dari cache L1 Anda, banyak memperlambat segalanya. Perkalian matriks naif biasanya dibatasi oleh kebutuhan untuk mengambil data ke dalam cache. Algoritma yang dioptimalkan menggunakan ubin (atau algoritma cache-oblivious) fokus pada membuat lebih baik menggunakan cache L1.

Jika Anda menghitung waktu pasangan lain (2 ^ n-1,2 ^ n) Saya berharap Anda akan melihat efek yang sama.

Untuk menjelaskan lebih lengkap, di loop dalam, di mana Anda mengakses matice2 [m, k], ada kemungkinan bahwa matice2 [m, k] dan matice2 [m + 1, k] diimbangi satu sama lain oleh 2048 * sizeof (float) dan dengan demikian memetakan ke indeks yang sama di cache L1. Dengan cache asosiatif N-way, Anda biasanya memiliki 1-8 lokasi cache untuk semua ini. Dengan demikian hampir semua akses tersebut akan memicu penggusuran cache L1, dan mengambil data dari cache yang lebih lambat atau memori utama.

Jonathan Moore
sumber
+1. Mungkin terdengar. Seseorang harus berhati-hati dengan cache cache.
Macke
16

Ini mungkin ada hubungannya dengan ukuran cache cpu Anda. Jika 2 baris matriks matriks tidak cocok, maka Anda akan kehilangan waktu menukar elemen dari RAM. Elemen 4095 tambahan mungkin cukup untuk mencegah agar baris tidak pas.

Dalam kasus Anda, 2 baris untuk 2047 matriks 2d berada dalam 16KB memori (dengan asumsi jenis 32 bit). Misalnya, jika Anda memiliki cache L1 (paling dekat dengan cpu di bus) dari 64KB, maka Anda dapat memasukkan setidaknya 4 baris (dari 2047 * 32) ke dalam cache sekaligus. Dengan baris yang lebih panjang jika ada padding yang diperlukan yang mendorong pasangan baris melebihi 16KB, maka segala sesuatunya mulai menjadi berantakan. Juga, setiap kali Anda 'ketinggalan' cache, bertukar data dari cache lain atau memori utama menunda banyak hal.

Dugaan saya adalah bahwa varians dalam menjalankan kali Anda melihat dengan matriks ukuran yang berbeda dipengaruhi oleh seberapa efektif sistem operasi dapat menggunakan cache yang tersedia (dan beberapa kombinasi hanya bermasalah). Tentu saja ini semua merupakan penyederhanaan besar di pihak saya.

Dana the Sane
sumber
2
tetapi sangat tidak mungkin ia memiliki cache CPU 16,7 MB
Marino Šimić
Saya memperbarui hasil dengan 2049x2049 - 91 detik. Jika itu "masalah cache", bukankah ini masih 300+?
Wolf
@ Marino jawabannya telah diperbarui untuk memperhitungkannya.
Dana the Sane
1
Saya merasa tidak ada satu pun dari penjelasan ini yang dapat secara memadai membahas rincian baru mengenai berbagai dan ukuran yang jarang menimbulkan masalah, dengan yang lain di antaranya tidak terpengaruh.
Ken Rockot
2
Saya kira penjelasan ini tidak benar. Masalahnya terletak pada tidak memanfaatkan kapasitas cache sepenuhnya karena konflik garis cache ketika ukuran kekuatan 2. Juga sistem operasi tidak ada hubungannya dengan cache, karena bukan OS yang memutuskan apa yang harus cache dan apa yang harus digusur, itu semua dalam perangkat keras. OS ada hubungannya dengan penyelarasan data, tetapi dalam hal ini semua tentang bagaimana C # memutuskan untuk mengalokasikan data dan bagaimana mewakili array 2D dalam memori, OS tidak ada hubungannya dengan itu.
zviadm
5

Mengingat bahwa waktu menurun pada ukuran yang lebih besar bukankah itu lebih cenderung menjadi konflik cache, terutama dengan kekuatan 2 untuk ukuran matriks yang bermasalah? Saya bukan ahli tentang masalah caching, tetapi info yang bagus tentang masalah kinerja yang berhubungan dengan cache di sini .


sumber
Bagian 5 dari tautan pada cache associativity tampaknya berlaku khususnya.
Dana the Sane
4

Ketika Anda mengakses matice2array secara vertikal, itu akan lebih banyak bertukar dan keluar dari cache. Jika Anda mirror array secara diagonal, sehingga Anda dapat mengaksesnya menggunakan [k,m]bukan[m,k] , kode akan berjalan jauh lebih cepat.

Saya menguji ini untuk matriks 1024x1024, dan ini sekitar dua kali lebih cepat. Untuk 2048x2048 matriks sekitar sepuluh kali lebih cepat.

Guffa
sumber
Ini tidak menjelaskan mengapa 2049 lebih cepat dari 2048.
Macke
@ Macke: Itu karena melewati batas dalam cache memori, sehingga ada lebih banyak cache yang terlewat.
Guffa
Mengapa downvote? Jika Anda tidak mengatakan apa yang Anda pikir salah, itu tidak dapat memperbaiki jawabannya.
Guffa
Downvote lain tanpa penjelasan ... Apakah jawaban saya memiliki terlalu sedikit "mungkin", "tebak" dan "harus" di dalamnya, seperti jawaban yang paling banyak mendapat dukungan ...?
Guffa
4

Cache Aliasing

Atau meronta-ronta cache , jika saya dapat koin istilah.

Tembolok bekerja dengan mengindeks dengan bit pesanan rendah dan penandaan dengan bit pesanan tinggi.

Gambar bahwa cache Anda memiliki 4 kata dan matriks Anda adalah 4 x 4. Ketika sebuah kolom diakses dan baris memiliki kekuatan dua panjangnya, maka setiap elemen kolom dalam memori akan dipetakan ke elemen cache yang sama.

Kekuatan dua-plus-satu sebenarnya sekitar optimal untuk masalah ini. Setiap elemen kolom baru akan dipetakan ke slot cache berikutnya persis seolah-olah mengakses dengan baris.

Dalam kehidupan nyata, tag mencakup beberapa alamat yang meningkat secara berurutan yang akan men-cache beberapa elemen yang berdekatan dalam satu baris. Dengan mengimbangi bucket yang dipetakan oleh setiap baris baru, melintasi kolom tidak menggantikan entri sebelumnya. Ketika kolom berikutnya dilalui, seluruh cache akan diisi dengan baris yang berbeda dan setiap bagian baris yang masuk ke cache akan menekan beberapa kolom.

Karena cache jauh lebih cepat daripada DRAM (kebanyakan karena on-chip) hit rate adalah segalanya.

DigitalRoss
sumber
2

Anda tampaknya telah mencapai batas ukuran cache, atau mungkin memiliki beberapa masalah pengulangan dalam timing Anda.

Apa pun masalahnya, Anda tidak perlu menulis sendiri perkalian matriks dalam C # dan alih-alih menggunakan versi BLAS yang dioptimalkan. Ukuran matriks itu harus dikalikan dalam waktu satu detik pada mesin modern mana pun.

David Heffernan
sumber
1
Saya mengetahui BLAS, tetapi tugasnya bukan untuk membuatnya secepat mungkin, tetapi menulis dan mengujinya dalam berbagai bahasa. Ini adalah masalah yang sangat aneh bagi saya dan saya benar-benar ingin tahu mengapa hasilnya seperti itu.
Wolf
3
@ Serigala Saya merasa sulit untuk merasa bersemangat tentang apakah sesuatu yang harus mengambil detik membutuhkan waktu 90 detik atau 300 detik.
David Heffernan
4
Cara terbaik untuk mempelajari cara kerja sesuatu adalah dengan menulisnya sendiri dan melihat bagaimana Anda dapat meningkatkan implementasi Anda; inilah (semoga) yang dilakukan Wolf.
Callum Rogers
@Callum Rogers, setuju. Itulah bagaimana saya belajar pentingnya ukuran penyangga dalam operasi penyalinan file.
Kelly S. French
1

Memanfaatkan hierarki cache secara efektif sangat penting. Anda perlu memastikan bahwa array multidimensi memiliki data dalam pengaturan yang bagus, yang dapat dilakukan dengan memasang ubin . Untuk melakukan ini, Anda harus menyimpan array 2D sebagai array 1D bersama dengan mekanisme pengindeksan. Masalah dengan metode tradisional adalah bahwa meskipun dua elemen array yang berdekatan yang berada di baris yang sama bersebelahan dalam memori, dua elemen yang berdekatan dalam kolom yang sama akan dipisahkan oleh elemen W dalam memori, di mana W adalah jumlah kolom . Ubin dapat membuat sebanyak faktor perbedaan kinerja.

Arlen
sumber
Hmm - namun sebuah array dinyatakan sebagai 2D (float [,] matice = new float [rozmer, rozmer];) hanya pernah dialokasikan dalam RAM sebagai array satu dimensi dan perhitungan baris / langkah dilakukan di bawah tenda. Jadi mengapa menyatakannya sebagai 1D dan melakukan perhitungan baris / langkah manual menjadi lebih cepat? Apakah maksud Anda sol'n mengalokasikan array besar sebagai array ubin lebih kecil yang masing-masing dapat masuk ke cache di mana array besar tidak akan?
Eric M
1
Jika pustaka Anda atau alat apa pun yang Anda gunakan tidak cocok, maka Anda tidak perlu melakukannya. Tetapi jika Anda menggunakan array 2D tradisional di, katakanlah, C / C ++, maka pemasangan ubin akan meningkatkan kinerja.
Arlen
0

Saya menduga itu adalah hasil dari sesuatu yang disebut " Sequential Flooding ". Apa ini adalah bahwa Anda mencoba untuk mengulang daftar objek yang sedikit lebih besar dari ukuran cache, sehingga setiap permintaan tunggal ke daftar (array) harus dilakukan dari ram, dan Anda tidak akan mendapatkan cache tunggal memukul.

Dalam kasus Anda, Anda mengulang-ulang array 2048 indeks 2048 kali, tetapi Anda hanya memiliki ruang untuk 2047 (mungkin karena beberapa overhead dari struktur array), jadi setiap kali Anda mengakses pos array, perlu mendapatkan pos array ini dari ram. Itu kemudian disimpan dalam cache, tetapi tepat sebelum digunakan lagi, itu dibuang. Jadi cache pada dasarnya tidak berguna, mengarah ke waktu eksekusi yang lebih lama.

Otomatis
sumber
1
Salah. 2049 lebih cepat dari 2048, yang membantah klaim Anda.
Macke
@ Macke: Itu sangat mungkin. Tetapi ada sedikit kemungkinan bahwa kebijakan cache yang digunakan dalam prosesornya mungkin masih membuat keputusan ini. Ini sangat tidak mungkin, tetapi itu tidak terpikirkan.
Otomatis