Mengapa Memindahkan Matriks 512x512 Secara Ketara Lebih Lambat Daripada Memindahkan Matriks 513x513?

Mengapa Transposing 512x512 Matriks Lebih Lambat Daripada Transposing 513x513

Satu pemerhatian yang pelik dalam transposing matriks timbul selepas menjalankan eksperimen pada matriks yang berbeza-beza saiz^ dengan transposing saiz: n secara pengiraan lebih mahal daripada transposing satu dengan dimensi 2^n 1. Percanggahan menjadi ketara apabila n sama dengan 512.

Kod yang disediakan untuk operasi transposisi adalah seperti berikut:

#define SAMPLES 1000
#define MATSIZE 512

#include <time.h>
#include <iostream>
int mat[MATSIZE][MATSIZE];

void transpose()
{
   for ( int i = 0 ; i < MATSIZE ; i++ )
   for ( int j = 0 ; j < MATSIZE ; j++ )
   {
       int aux = mat[i][j];
       mat[i][j] = mat[j][i];
       mat[j][i] = aux;
   }
}

int main()
{
   //initialize matrix
   for ( int i = 0 ; i < MATSIZE ; i++ )
   for ( int j = 0 ; j < MATSIZE ; j++ )
       mat[i][j] = i+j;

   int t = clock();
   for ( int i = 0 ; i < SAMPLES ; i++ )
       transpose();
   int elapsed = clock() - t;

   std::cout << "Average for a matrix of " << MATSIZE << ": " << elapsed / SAMPLES;
}

Dengan mengubah makro MATSIZE, saiz matriks boleh diubah suai. Penanda aras berikut menggambarkan perbezaan yang ketara:

• Saiz 512: Purata 2.46 ms
• Saiz 513: Purata 0.75 ms

Cache Contention dan Critical Stride

Sebab di sebalik anomali ini terletak pada tingkah laku cache dan konsep perbalahan cache. Berikut ialah pecahan:

Cache distrukturkan ke dalam set dan baris. Pada bila-bila masa, hanya satu set diakses, dan mana-mana baris dalam set itu boleh digunakan. Jumlah saiz cache ditentukan oleh bilangan baris yang didarab dengan saiz setiap baris.
• Untuk mengira set yang mempunyai alamat memori tertentu, formula berikut digunakan: set = ( address / lineSize ) % numberOfsets.
• Apabila berbilang alamat memori mengakses set yang sama, konflik cache timbul. Dalam senario sedemikian, baris yang paling kurang digunakan baru-baru ini dalam set ditimpa dengan data yang baru diambil.
• Langkah kritikal, yang mewakili bilangan akses memori yang mengakibatkan konflik cache, dikira sebagai criticalStride = numberOfSets * lineSize.
• Dalam kes matriks 64x64 dengan cache 8kb, kritikal langkah akan diselaraskan dengan sempurna dengan baris matriks, membawa kepada pemuatan semula cache yang berlebihan semasa transposisi.
• Walau bagaimanapun, apabila saiz matriks ditingkatkan kepada 65x65, langkah kritikal tidak lagi sejajar dengan sempurna, mengurangkan kekerapan cache konflik dan meningkatkan prestasi.

Oleh itu, operasi pemindahan menjadi jauh lebih perlahan untuk matriks dengan dimensi gandaan 2^n disebabkan perbalahan cache.

Atas ialah kandungan terperinci Mengapa Memindahkan Matriks 512x512 Secara Ketara Lebih Lambat Daripada Memindahkan Matriks 513x513?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!