Farklı boyutlarda Kare matris üzerinde bazı deneyler sonra, bir desen çıktı. Her zaman,boyutta bir matris aktarılması 2^n boyutu 2^n 1 aktaran yavaştır. n küçük değerleri için fark önemli.

Büyük farklar ancak 512 değeri üzerinden oluşur. (en azından benim için)

Yasal Uyarı: Bu fonksiyonu aslında öğelerin iki takas nedeniyle matrisi devrik olmadığını biliyorum, ama hiç fark etmez.

Takip kodu:

#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;
}

MATSIZE değişen ABD boyutu (duh!) değiştirmenizi sağlar. İdeone üzerinde iki sürümü yayınlanmıştır:

• boyutu 512- ortalama2.46 ms- http://ideone.com/1PV7m
• boyutu 513- ortalama0.75 ms- http://ideone.com/NShpo

Benim ortamda (MSVS 2010, tam iyileştirme), fark benzer :

• boyutu 512- ortalama2.19 ms
• boyutu 513- ortalama0.57 ms

Neden böyle oluyor?

Açıklama Optimizing software in C Agner Fog geliyor ve önbellekte erişilen nasıl depolandığını azaltır.

Şartlar ve ayrıntılı bilgi için, ben wiki entry on caching, buraya dar görüyor.

Bir önbellek düzenlenmektedirayarlarveçizgiler. Bir anda, sadece bir set içerir hattı herhangi kullanılabilecek dışında kullanılır. Bir kere satır satır sayısını yansıtabilirsiniz bellek bize önbellek boyutu verir.

Belirli bir bellek adresi, bu formül ile yansıtılmış olması gerektiğini hesaplayabiliriz:

set = ( address / lineSize ) % numberOfsets

Formül bu tür setler arasında, her bir bellek adresi okumuş olma olasılığı (dedim . çünkü dağılmasını sağlıyor ve ideal üniforma ^em>ideal).

Çakışıyor oluşabilecek açık. Bir cache durumda Bayan, önbellek okuma ve eski değeri değiştirilir. Her set olan en son kullanılan en az bir yazılır satır sayısı, yeni okuma hafıza var hatırlıyorum.

Biraz Agner örneği takip etmeye çalışacağım:

Her set 4 satır, her 64 bayt holding varsayalım. Biz ilk adresi giren 0x2710, *10 set* okuma denemesi. Ve sonra biz de adresleri0x2F00, 0x3700, 0x3F00 0x4700 okuma denemesi. Bunların hepsi aynı kümeye ait. 0x4700, okumadan önce kümesindeki tüm hatlar meşgul olurdu. Bellek okuma kümesindeki varolan bir satır, başlangıçta 0x2710 tutan hat çıkarır. Sorun (bu örnek için) 0x800 birbirinden adresleri okuduk gerçeği yatıyor. Bukritik adım(yine, bu örnek için).

Kritik adım da hesaplanabilir:

criticaStride = numberOfSets * lineSize

Değişkenler criticalStride aralıklı ya da birden fazla ayrı aynı önbellek hatları için uğraşmak.

Bu teorinin bir parçasıdır. Gelecek, açıklama (Agner, yakından hataları yapmaktan kaçınmaya takip ediyorum):

64 bayt 8kb bir önbellek ile 64x64 (, etkileri hatırlıyorum değişir önbellek göre), 4 set başına satır * satır matris boyutu varsayalım. Her satır matris elemanlarının 8 (64-bit int) tutabilir.

Kritik adım matris hafıza sürekli olan) 4 satır karşılık gelen 2048 bayt olacaktır.

Satır 28 çalışıyoruz varsayalım. Bu satır öğeleri almak ve sütun 28 öğeleri ile onları takas için çalışıyoruz. Satırın ilk 8 elemanları önbellek satırını oluşturan, ama sütun 28 8 farklı önbellek satırları yaparlar. Unutmayın, kritik adım 4 satır ayrı bir sütunda 4 ardışık elemanları).

Eleman 16 sütun ve 4 satır başına 4 önbellek satırları ayrı = bela) ulaşıldığında ex-0 öğe önbellekten çıkarılacak. Sütun sonuna vardığımızda, önceki tüm önbellek çizgiler kaybolmuş ve bir sonraki eleman (bütün çizgi üzerine yazılır) erişim yeniden gerekirdi.

Kritik adım katları olmayan bir boyutu olan bu kadar bozulurmükemmel bir senaryoartık önemli birer unsur ile karşı karşıyayız gibi afet için ayrı dikey adımlarla yürümek, önbelleği yeniden yükler sayısı ciddi şekilde azalır.

Başka bir uyarı- Ben sadece açıklama kafamı var ve umarım ben seçildim, ama yanılıyor olabilirim. Neyse, cevap (veya onay) Mysticial dan bekliyorum. :)