Şuna benzer bir matris çarpma kodu var:

for(i = 0; i < dimension; i  )
    for(j = 0; j < dimension; j  )
        for(k = 0; k < dimension; k  )
            C[dimension*i j]  = A[dimension*i k] * B[dimension*k j];

Burada, matrisin boyutu dimensionile temsil edilir. Eğer matris boyutu bu kod parçası çalıştırmak için 147 saniye sürer, eğer matris boyutu ise 2000, şimdi, Eğer 2048, 447 saniye sürer. O zaman hiçbir farkı. (2048*2048*2048)çarpımları./(2000*2000*2000) = 1.073, zamanlama farkı olduğunu 447/147 = 3. Birisi bu neden olmuyor açıklayabilir misiniz? Olmaz ki bu doğrusal ölçek için bekliyordum. En hızlı matris çarpma kodu, sadece bunun neden olduğunu anlamaya çalışarak yapmaya çalışıyorum.

Özellikleri: çift çekirdekli düğüm (2.2 GHz), 2G RAM, v 4.5.0 gcc AMD yaptığı bir Açıklamada

Program gcc -O3 simple.c olarak derlenmiş

Intel ıcc derleyici bu da çalıştırın ve benzer sonuçlar gördüm.

DÜZENLEME:

Yorum/cevap olarak önerilen, boyut ile kodu=2060 koştum ve 145 saniye sürer.

İşte tam programı:

#include <stdlib.h>
#include <stdio.h>
#include <sys/time.h>

/* change dimension size as needed */
const int dimension = 2048;
struct timeval tv; 

double timestamp()
{
        double t;
        gettimeofday(&tv, NULL);
        t = tv.tv_sec   (tv.tv_usec/1000000.0);
        return t;
}

int main(int argc, char *argv[])
{
        int i, j, k;
        double *A, *B, *C, start, end;

        A = (double*)malloc(dimension*dimension*sizeof(double));
        B = (double*)malloc(dimension*dimension*sizeof(double));
        C = (double*)malloc(dimension*dimension*sizeof(double));

        srand(292);

        for(i = 0; i < dimension; i  )
                for(j = 0; j < dimension; j  )
                {   
                        A[dimension*i j] = (rand()/(RAND_MAX   1.0));
                        B[dimension*i j] = (rand()/(RAND_MAX   1.0));
                        C[dimension*i j] = 0.0;
                }   

        start = timestamp();
        for(i = 0; i < dimension; i  )
                for(j = 0; j < dimension; j  )
                        for(k = 0; k < dimension; k  )
                                C[dimension*i j]  = A[dimension*i k] *
                                        B[dimension*k j];

        end = timestamp();
        printf("\nsecs:%f\n", end-start);

        free(A);
        free(B);
        free(C);

        return 0;
}

İşte vahşi tahminim:önbellek

Önbelleğe 2000 doubles 2 satır sığacak olabilir. Kısıtlı 32 KB L1 önbellek ve daha az olan. oda diğer gerekli şeyleri bırakarak ()

Ama 2048, o kadar bump zaman kullanırtümönbellek (ve diğer şeyler için oda lazım çünkü bazı dökmek)

Önbellek ilkesi LRU olduğunu varsayarsak, önbelleği biraz dökülüp tüm satırı defalarca temizlenip neden olur ve L1 önbelleğine yeniden.

Diğer olasılık önbellek birleşim bu iki güç nedeniyle. Bu işlemci 2-yollu L1 ilişkili olduğunu düşünüyorum ama bu durumda önemli olduğunu sanmıyorum. (ama fikir zaten dışarıya atmak) vereceğim

Olası Açıklama 2:Çatışma önbellek L2 önbellek süper uyum nedeniyle özlüyor.

B dizi sütunu yinelenen ediliyor. Erişim strided. Toplam veri boyutu yaklaşık 32 MB olan matris başına 2k x 2k. Bu L2 önbelleği çok daha büyük.

Ne zaman veri değildir hizalanmış mükemmel, sen-ecek var iyi mekansal yerellik B. Ancak sen atlamalı satır ve sadece kullanarak bir öğe başına cacheline, cacheline kalır L2 önbellek yeniden kurtardığınız tarafından bir sonraki döngü, orta döngü.

Verileri mükemmel bir şekilde hizalanmış olduğunda ancak, (2048), bu aynı "yol" ve far L2 aşacaktır önbellek birleşim. önbellek arazi tüm şerbetçiotu Bu nedenle, B erişilen önbellek satırları sonraki yineleme için önbellek kalmaz.Bunun yerine, ram her şekilde çekilmiş olması gerekir.