Saya membuat beberapa tolok ukur dengan CUDA, C ++, C #, Java, dan menggunakan MATLAB untuk verifikasi dan pembuatan matriks. Ketika saya melakukan perkalian matriks dengan MATLAB, 2048x2048
dan bahkan matriks yang lebih besar hampir langsung dikalikan.
1024x1024 2048x2048 4096x4096
--------- --------- ---------
CUDA C (ms) 43.11 391.05 3407.99
C++ (ms) 6137.10 64369.29 551390.93
C# (ms) 10509.00 300684.00 2527250.00
Java (ms) 9149.90 92562.28 838357.94
MATLAB (ms) 75.01 423.10 3133.90
Hanya CUDA yang kompetitif, tapi saya pikir setidaknya C ++ akan menjadi agak dekat dan tidak 60 kali lebih lambat. Saya juga tidak tahu harus berpikir apa tentang hasil C #. Algoritma ini adalah sama saja dengan C ++ dan Java, tapi ada lompatan raksasa 2048
dari 1024
.
Bagaimana MATLAB melakukan perkalian matriks begitu cepat?
Kode C ++:
float temp = 0;
timer.start();
for(int j = 0; j < rozmer; j++)
{
for (int k = 0; k < rozmer; k++)
{
temp = 0;
for (int m = 0; m < rozmer; m++)
{
temp = temp + matice1[j][m] * matice2[m][k];
}
matice3[j][k] = temp;
}
}
timer.stop();
performance
matlab
matrix
matrix-multiplication
Serigala
sumber
sumber
Jawaban:
Inilah hasil saya menggunakan MATLAB R2011a + Parallel Computing Toolbox pada mesin dengan Tesla C2070:
MATLAB menggunakan pustaka yang sangat dioptimalkan untuk perkalian matriks yang karenanya perkalian matriks MATLAB sangat cepat. The
gpuArray
Versi menggunakan magma .Pembaruan menggunakan R2014a pada mesin dengan Tesla K20c, dan yang baru
timeit
dangputimeit
berfungsi:Pembaruan menggunakan R2018b pada mesin WIN64 dengan 16 core fisik dan Tesla V100:
(NB: di beberapa titik (saya lupa kapan tepatnya)
gpuArray
beralih dari MAGMA ke cuBLAS - MAGMA masih digunakan untuk beberapagpuArray
operasi sekalipun)sumber
Pertanyaan semacam ini berulang dan harus dijawab lebih jelas daripada "MATLAB menggunakan perpustakaan yang sangat dioptimalkan" atau "MATLAB menggunakan MKL" untuk sekali di Stack Overflow.
Sejarah:
Perkalian matriks (bersama-sama dengan matriks-vektor, perkalian vektor-vektor dan banyak dari penguraian matriks) adalah masalah yang paling penting dalam aljabar linier. Insinyur telah memecahkan masalah ini dengan komputer sejak awal.
Saya bukan ahli dalam sejarah, tetapi tampaknya saat itu, semua orang hanya menulis ulang versi FORTRAN-nya dengan loop sederhana. Beberapa standardisasi kemudian muncul, dengan identifikasi "kernel" (rutinitas dasar) yang paling dibutuhkan masalah aljabar linier agar dapat dipecahkan. Operasi dasar ini kemudian distandarisasi dalam spesifikasi yang disebut: Basic Linear Aljabar Subprograms (BLAS). Insinyur kemudian dapat memanggil rutin BLAS standar ini yang telah teruji baik dalam kode mereka, membuat pekerjaan mereka jauh lebih mudah.
BLAS:
BLAS berevolusi dari level 1 (versi pertama yang mendefinisikan operasi skalar-vektor dan vektor-vektor) ke level 2 (operasi matriks-vektor) ke level 3 (operasi matriks-matriks), dan semakin banyak menyediakan "kernel" sehingga standar dan lebih banyak operasi aljabar linier mendasar. Implementasi FORTRAN 77 asli masih tersedia di situs web Netlib .
Menuju kinerja yang lebih baik:
Jadi selama bertahun-tahun (terutama antara rilis BLAS level 1 dan level 2: awal 80-an), perangkat keras berubah, dengan munculnya operasi vektor dan hierarki cache. Evolusi ini memungkinkan untuk meningkatkan kinerja subrutin BLAS secara substansial. Vendor yang berbeda kemudian datang dengan implementasi rutinitas BLAS mereka yang semakin efisien.
Saya tidak tahu semua implementasi historis (saya tidak dilahirkan atau masih kecil saat itu), tetapi dua yang paling menonjol keluar pada awal 2000-an: Intel MKL dan GotoBLAS. Matlab Anda menggunakan Intel MKL, yang merupakan BLAS yang sangat bagus, dioptimalkan, dan itu menjelaskan kinerja hebat yang Anda lihat.
Rincian teknis tentang perkalian Matriks:
Jadi mengapa Matlab (MKL) begitu cepat
dgemm
(multiplikasi matriks-matriks umum presisi ganda) Secara sederhana: karena menggunakan vektorisasi dan caching data yang baik. Dalam istilah yang lebih kompleks: lihat artikel yang disediakan oleh Jonathan Moore.Pada dasarnya, ketika Anda melakukan perkalian dalam kode C ++ yang Anda berikan, Anda sama sekali tidak ramah terhadap cache. Karena saya curiga Anda membuat array pointer ke array baris, akses Anda di loop batin Anda ke kolom k-th "matice2":
matice2[m][k]
sangat lambat. Memang, ketika Anda mengaksesmatice2[0][k]
, Anda harus mendapatkan elemen k-th dari array 0 dari matriks Anda. Kemudian dalam iterasi berikutnya, Anda harus mengaksesmatice2[1][k]
, yang merupakan elemen k-th dari array lain (array 1). Kemudian di iterasi berikutnya Anda mengakses array lain, dan seterusnya ... Karena seluruh matriksmatice2
tidak dapat ditampung di cache tertinggi (ini8*1024*1024
byte besar), program harus mengambil elemen yang diinginkan dari memori utama, kehilangan banyak waktu.Jika Anda baru saja memindahkan matriks, sehingga akses akan berada di alamat memori yang berdekatan, kode Anda akan berjalan jauh lebih cepat karena sekarang kompiler dapat memuat seluruh baris dalam cache pada saat yang sama. Coba saja versi modifikasi ini:
Jadi Anda dapat melihat bagaimana hanya cache lokalitas meningkatkan kinerja kode Anda secara substansial. Sekarang
dgemm
implementasi nyata mengeksploitasi itu ke tingkat yang sangat luas: Mereka melakukan perkalian pada blok dari matriks yang didefinisikan oleh ukuran TLB (buffer lookaside terjemahan, cerita panjang pendek: apa yang secara efektif dapat di-cache), sehingga mereka mengalir ke prosesor persis jumlah data yang dapat diproses. Aspek lainnya adalah vektorisasi, mereka menggunakan instruksi yang di-vektor-kan prosesor untuk throughput instruksi yang optimal, yang tidak dapat Anda lakukan dari kode C ++ cross-platform Anda.Akhirnya, orang mengklaim bahwa itu karena algoritma Strassen atau Coppersmith-Winograd salah, kedua algoritma ini tidak dapat diterapkan dalam praktik, karena pertimbangan perangkat keras yang disebutkan di atas.
sumber
Ini sebabnya . MATLAB tidak melakukan perkalian matriks naif dengan mengulangi setiap elemen seperti yang Anda lakukan pada kode C ++.
Tentu saja saya berasumsi bahwa Anda hanya menggunakan
C=A*B
alih-alih menulis fungsi perkalian sendiri.sumber
Matlab memasukkan LAPACK beberapa waktu lalu, jadi saya menganggap perkalian matriks mereka menggunakan sesuatu yang setidaknya secepat itu. Kode sumber dan dokumentasi LAPACK sudah tersedia.
Anda juga dapat melihat makalah Goto dan Van De Geijn "Anatomi Pengganda Matriks Berkinerja Tinggi" di http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.140.1785&rep=rep1&type=pdf
sumber
Jawabannya adalah perpustakaan LAPACK dan BLAS membuat MATLAB sangat cepat di operasi matriks, bukan kode kepemilikan oleh orang-orang di MATLAB.
Gunakan perpustakaan LAPACK dan / atau BLAS dalam kode C ++ Anda untuk operasi matriks dan Anda harus mendapatkan kinerja yang sama seperti MATLAB. Perpustakaan-perpustakaan ini harus tersedia secara bebas di sistem modern apa pun dan bagian-bagiannya dikembangkan selama beberapa dekade di dunia akademis. Perhatikan bahwa ada beberapa implementasi, termasuk beberapa sumber tertutup seperti Intel MKL .
Diskusi tentang bagaimana BLAS mendapatkan kinerja tinggi tersedia di sini.
BTW, itu adalah rasa sakit yang serius dalam pengalaman saya untuk memanggil perpustakaan LAPACK langsung dari c (tapi layak). Anda perlu membaca dokumentasi SANGAT tepat.
sumber
Ketika melakukan perkalian matriks, Anda menggunakan metode perkalian naif yang membutuhkan waktu
O(n^3)
.Ada algoritma multiplikasi matriks yang dibutuhkan
O(n^2.4)
. Yang berarti bahwa padan=2000
algoritma Anda membutuhkan ~ 100 kali lebih banyak perhitungan daripada algoritma terbaik.Anda harus benar-benar memeriksa halaman wikipedia untuk perkalian matriks untuk informasi lebih lanjut tentang cara-cara efisien untuk mengimplementasikannya.
sumber
Tergantung pada versi Matlab Anda, saya yakin itu mungkin sudah menggunakan GPU Anda.
Hal lain; Matlab melacak banyak properti dari matriks Anda; apakah diagonal, hermetian, dan sebagainya, dan mengkhususkan algoritmanya berdasarkan padanya. Mungkin itu mengkhususkan berdasarkan nol matriks yang Anda lewati, atau sesuatu seperti itu? Mungkin itu caching panggilan fungsi berulang, yang mengacaukan timing Anda? Mungkin itu mengoptimalkan produk matriks yang tidak digunakan berulang?
Untuk mencegah hal-hal seperti itu terjadi, gunakan matriks angka acak, dan pastikan Anda memaksakan eksekusi dengan mencetak hasilnya ke layar atau disk atau semacamnya.
sumber
A.*B
. Jadi OP hampir pasti melakukan sesuatu.MATLAB menggunakan implementasi LAPACK yang sangat optimal dari Intel yang dikenal sebagai Intel Math Kernel Library (Intel MKL) - khususnya fungsi dgemm . Kecepatan Perpustakaan ini memanfaatkan fitur prosesor termasuk instruksi SIMD dan prosesor multi-core. Mereka tidak mendokumentasikan algoritma spesifik apa yang mereka gunakan. Jika Anda memanggil Intel MKL dari C ++ Anda akan melihat kinerja yang sama.
Saya tidak yakin perpustakaan apa yang digunakan MATLAB untuk perkalian GPU tetapi mungkin sesuatu seperti nVidia CUBLAS .
sumber
Jawaban umum untuk "Mengapa matlab lebih cepat dalam melakukan xxx daripada program lain" adalah matlab memiliki banyak fungsi bawaan yang dioptimalkan.
Program lain yang digunakan sering tidak memiliki fungsi-fungsi ini sehingga orang menerapkan solusi kreatif mereka sendiri, yang ternyata lebih lambat daripada kode yang dioptimalkan secara profesional.
Ini dapat ditafsirkan dalam dua cara:
1) Cara umum / teoretis: Matlab tidak jauh lebih cepat, Anda hanya melakukan tolok ukur yang salah
2) Cara realistis: Untuk hal ini Matlab lebih cepat dalam praktik karena bahasa seperti c ++ terlalu mudah digunakan dengan cara yang tidak efektif.
sumber
Kontras yang tajam tidak hanya karena optimasi Matlab yang luar biasa (seperti yang sudah dibahas oleh banyak jawaban lain), tetapi juga dalam cara Anda merumuskan matriks sebagai objek.
Sepertinya Anda membuat matriks daftar daftar? Daftar daftar berisi pointer ke daftar yang kemudian mengandung elemen matriks Anda. Lokasi daftar yang ada ditetapkan secara sewenang-wenang. Ketika Anda mengulangi indeks pertama Anda (nomor baris?), Waktu akses memori sangat signifikan. Sebagai perbandingan, mengapa Anda tidak mencoba mengimplementasikan matriks sebagai daftar tunggal / vektor menggunakan metode berikut?
Dan
Algoritma multiplikasi yang sama harus digunakan sehingga jumlah kegagalan adalah sama. (n ^ 3 untuk matriks ukuran persegi n)
Saya meminta Anda untuk mengatur waktu agar hasilnya sebanding dengan yang Anda miliki sebelumnya (pada mesin yang sama). Dengan perbandingan, Anda akan menunjukkan dengan tepat seberapa signifikan waktu akses memori!
sumber
Ini lambat di C ++ karena Anda tidak menggunakan multithreading. Pada dasarnya, jika A = BC, di mana mereka semua matriks, baris pertama A dapat dihitung secara independen dari baris ke-2, dll. Jika A, B, dan C semuanya matriks n, n Anda dapat mempercepat perkalian dengan faktor n ^ 2, sebagai
a_ {i, j} = sum_ {k} b_ {i, k} c_ {k, j}
Jika Anda menggunakan, katakanlah, Eigen [ http://eigen.tuxfamily.org/dox/GettingStarted.html ], multithreading built-in dan jumlah utas dapat disesuaikan.
sumber
Karena MATLAB adalah bahasa pemrograman pada awalnya dikembangkan untuk aljabar linear numerik (manipulasi matriks), yang memiliki perpustakaan khusus dikembangkan untuk perkalian matriks. Dan sekarang MATLAB juga dapat menggunakan GPU (Graphics processing unit) untuk tambahan ini.
Dan jika kami melihat hasil perhitungan Anda:
maka kita dapat melihat bahwa tidak hanya MATLAB yang begitu cepat dalam perkalian matriks: CUDA C (bahasa pemrograman dari NVIDIA) memiliki beberapa hasil yang lebih baik daripada MATLAB. CUDA C juga memiliki perpustakaan yang khusus dikembangkan untuk perkalian matriks dan menggunakan GPU.
Sejarah singkat MATLAB
Apa itu CUDA C
CUDA C juga menggunakan perpustakaan yang dikembangkan khusus untuk perkalian matriks seperti OpenGL (Open Graphics Library). Ini juga menggunakan GPU dan Direct3D (di MS Windows).
Membandingkan Kecepatan Eksekusi CPU dan GPU
Dari pengantar untuk Panduan Pemrograman CUDA C:
Bacaan lanjutan
Subprogram Aljabar Linier Dasar (BLAS)
Anatomi Penggandaan Matriks Kinerja Tinggi , dari Kazushige Goto dan Robert A. Van De Geijn
Beberapa segi menarik
sumber
"additionally"
. Artinya: bisa digunakan. Ini juga berarti bahwa perkalian matriks normal masih menggunakan pustaka perangkat lunak. Apakah Anda pikir saya harus mengubah posting saya agar lebih dimengerti? Terima kasih atas komentar Anda!