Mengapakah transposisi matriks 513x513 lebih cepat daripada transposisi matriks 512x512?

Memahami Perbezaan Prestasi dalam Transposisi Matriks untuk Saiz Matriks 512x512 dan 513x513

Matriks segi empat sama pelbagai saiz mempamerkan perbezaan masa yang unik apabila ia datang memindahkan mereka. Menariknya, matriks dengan dimensi 2^n cenderung mempunyai masa transposisi yang lebih perlahan berbanding dengan matriks dengan dimensi 2^n 1. Walaupun perbezaan ini mungkin kelihatan tidak ketara untuk nilai n yang kecil, ia menjadi ketara pada dimensi yang lebih besar, seperti yang dibuktikan oleh MATSIZE 512 .

Untuk memahami sebab asas perbezaan prestasi ini, kami menyelidiki konsep caching.

Organisasi Cache dan Pemetaan Set

Cache disusun dalam set dan baris. Setiap set mengandungi berbilang baris yang boleh menyimpan data. Untuk mencari set yang dimiliki oleh alamat memori tertentu, kami menggunakan formula berikut:

set = (address / lineSize) % numberOfsets

Akibatnya, alamat memori memetakan kepada set dalam cara yang agak seragam.

Cache Misses dan Line Evictions

Apabila mengakses lokasi memori, cache menyemak sama ada data sudah ada. Jika tidak, kehilangan cache berlaku, dan baris yang sepadan dibaca dari memori dan diletakkan dalam cache. Walau bagaimanapun, apabila cache penuh, ia mengusir baris Paling Kurang Digunakan Baru-baru Ini (LRU) untuk menampung data baharu.

Langkah Kritikal

Langkah kritikal mewakili jarak antara pembolehubah yang bersaing untuk baris cache yang sama. Ia dikira seperti berikut:

criticalStride = numberOfSets * lineSize

Pembolehubah yang dijarakkan mengikut langkah kritikal atau gandaannya lebih berkemungkinan menyebabkan pengusiran cache.

Transposisi Matriks dan Langkah Kritikal

Bayangkan matriks 64x64 dengan cache 8kB dan empat baris setiap ditetapkan. Setiap baris boleh memuatkan lapan integer 64-bit. Langkah kritikal dalam senario ini ialah 2048 bait, bersamaan dengan empat baris matriks.

Apabila memindahkan matriks, kami menukar baris dan lajur. Semasa kami memproses setiap baris dan menukarnya dengan lajur yang sepadan, elemen yang dipisahkan oleh langkah kritikal (empat baris) menghadapi pengusiran cache. Ini menghasilkan sejumlah besar muat semula cache, yang membawa kepada transposisi yang lebih perlahan.

Kesimpulan

Juza dalam masa transposisi antara matriks 512x512 dan 513x513 berpunca daripada hubungan antara dimensi matriks dan langkah kritikal cache. Matriks dengan dimensi yang bukan gandaan bagi langkah kritikal mengalami pengusiran cache dan, akibatnya, masa transposisi yang lebih cepat.

Atas ialah kandungan terperinci Mengapakah transposisi matriks 513x513 lebih cepat daripada transposisi matriks 512x512?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!