Soru Birleştirilmiş döngüye göre elementel eklemeler ayrı döngülerde neden daha hızlıdır?


varsaymak a1, b1, c1, ve d1 yığın belleğe işaret eder ve sayısal kodum aşağıdaki çekirdek döngüye sahiptir.

const int n = 100000;

for (int j = 0; j < n; j++) {
    a1[j] += b1[j];
    c1[j] += d1[j];
}

Bu döngü başka bir dıştan 10,000 kez yürütülür. for döngü. Hızlandırmak için kodu değiştirdim:

for (int j = 0; j < n; j++) {
    a1[j] += b1[j];
}

for (int j = 0; j < n; j++) {
    c1[j] += d1[j];
}

MS üzerinde derlenmiş Visual C ++ 10.0 tam optimizasyon ve SSE2 üzerinde 32 bit için etkin Intel Core 2 Duo (x64), ilk örnek 5.5 saniye sürer ve çift döngü örneği sadece 1.9 saniye sürer. Sorum şu: (Lütfen alt kısımda benim yazdığım soruya bakın)

Not: Bu yardımcı olursa, emin değilim:

İlk döngü için demontaj temel olarak şu şekilde görünür: (bu blok, tam programda yaklaşık beş kez tekrarlanır):

movsd       xmm0,mmword ptr [edx+18h]
addsd       xmm0,mmword ptr [ecx+20h]
movsd       mmword ptr [ecx+20h],xmm0
movsd       xmm0,mmword ptr [esi+10h]
addsd       xmm0,mmword ptr [eax+30h]
movsd       mmword ptr [eax+30h],xmm0
movsd       xmm0,mmword ptr [edx+20h]
addsd       xmm0,mmword ptr [ecx+28h]
movsd       mmword ptr [ecx+28h],xmm0
movsd       xmm0,mmword ptr [esi+18h]
addsd       xmm0,mmword ptr [eax+38h]

Çift döngü örneğinin her döngüsü bu kodu üretir (aşağıdaki blok yaklaşık üç kez tekrarlanır):

addsd       xmm0,mmword ptr [eax+28h]
movsd       mmword ptr [eax+28h],xmm0
movsd       xmm0,mmword ptr [ecx+20h]
addsd       xmm0,mmword ptr [eax+30h]
movsd       mmword ptr [eax+30h],xmm0
movsd       xmm0,mmword ptr [ecx+28h]
addsd       xmm0,mmword ptr [eax+38h]
movsd       mmword ptr [eax+38h],xmm0
movsd       xmm0,mmword ptr [ecx+30h]
addsd       xmm0,mmword ptr [eax+40h]
movsd       mmword ptr [eax+40h],xmm0

Sorun, dizinin (n) ve CPU önbelleğinin boyutlarına bağlı olduğu için, hiçbir alakası yoktur. Yani daha fazla ilgi varsa, ben şu soruyu yeniden yazarım:

Aşağıdaki grafikte beş bölge tarafından gösterildiği gibi farklı önbellek davranışlarına yol açan ayrıntılara bazı sağlam bilgiler verebilir misiniz?

Bu CPU'lar için benzer bir grafik sağlayarak, CPU / önbellek mimarileri arasındaki farklılıkları belirtmek de ilginç olabilir.

PPS: İşte tam kod. Kullanır TBB  Tick_Count Daha yüksek çözünürlüklü zamanlama için, TBB_TIMING Makro:

#include <iostream>
#include <iomanip>
#include <cmath>
#include <string>

//#define TBB_TIMING

#ifdef TBB_TIMING   
#include <tbb/tick_count.h>
using tbb::tick_count;
#else
#include <time.h>
#endif

using namespace std;

//#define preallocate_memory new_cont

enum { new_cont, new_sep };

double *a1, *b1, *c1, *d1;


void allo(int cont, int n)
{
    switch(cont) {
      case new_cont:
        a1 = new double[n*4];
        b1 = a1 + n;
        c1 = b1 + n;
        d1 = c1 + n;
        break;
      case new_sep:
        a1 = new double[n];
        b1 = new double[n];
        c1 = new double[n];
        d1 = new double[n];
        break;
    }

    for (int i = 0; i < n; i++) {
        a1[i] = 1.0;
        d1[i] = 1.0;
        c1[i] = 1.0;
        b1[i] = 1.0;
    }
}

void ff(int cont)
{
    switch(cont){
      case new_sep:
        delete[] b1;
        delete[] c1;
        delete[] d1;
      case new_cont:
        delete[] a1;
    }
}

double plain(int n, int m, int cont, int loops)
{
#ifndef preallocate_memory
    allo(cont,n);
#endif

#ifdef TBB_TIMING   
    tick_count t0 = tick_count::now();
#else
    clock_t start = clock();
#endif

    if (loops == 1) {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++){
                a1[j] += b1[j];
                c1[j] += d1[j];
            }
        }
    } else {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                a1[j] += b1[j];
            }
            for (int j = 0; j < n; j++) {
                c1[j] += d1[j];
            }
        }
    }
    double ret;

#ifdef TBB_TIMING   
    tick_count t1 = tick_count::now();
    ret = 2.0*double(n)*double(m)/(t1-t0).seconds();
#else
    clock_t end = clock();
    ret = 2.0*double(n)*double(m)/(double)(end - start) *double(CLOCKS_PER_SEC);
#endif

#ifndef preallocate_memory
    ff(cont);
#endif

    return ret;
}


void main()
{   
    freopen("C:\\test.csv", "w", stdout);

    char *s = " ";

    string na[2] ={"new_cont", "new_sep"};

    cout << "n";

    for (int j = 0; j < 2; j++)
        for (int i = 1; i <= 2; i++)
#ifdef preallocate_memory
            cout << s << i << "_loops_" << na[preallocate_memory];
#else
            cout << s << i << "_loops_" << na[j];
#endif

    cout << endl;

    long long nmax = 1000000;

#ifdef preallocate_memory
    allo(preallocate_memory, nmax);
#endif

    for (long long n = 1L; n < nmax; n = max(n+1, long long(n*1.2)))
    {
        const long long m = 10000000/n;
        cout << n;

        for (int j = 0; j < 2; j++)
            for (int i = 1; i <= 2; i++)
                cout << s << plain(n, m, j, i);
        cout << endl;
    }
}

(Farklı değerler için FLOP / s gösterir. n.)

enter image description here


1996
2017-12-17 20:40


Menşei


Her eriştiğinizde fiziksel belleği ararken yavaşlayan ve aynı kilitlemeye ikincil erişim durumunda önbellek gibi bir şey olan işletim sistemi olabilir. - AlexTheo
Optimizasyonlarla derleme yapıyor musunuz? Bu O2 için çok fazla asm kodu gibi görünüyor ... - Luchian Grigore
Seçici olmak için, bu iki kod snippet'leri potansiyel olarak çakışan işaretçiler nedeniyle eşdeğer değildir. C99 sahip restrict bu gibi durumlar için anahtar kelime. MSVC'nin benzer bir şey olup olmadığını bilmiyorum. Tabii ki, eğer konu bu olsaydı, SSE kodu doğru olmazdı. - user510306
Bu bellek takma ile ilgili bir şey olabilir. Bir döngü ile, d1[j] ile aliase olabilir a1[j]Bu nedenle derleyici bazı bellek optimizasyonları yapmaktan vazgeçebilir. Yazıları iki döngüye ayırarak bu olmazsa olmaz. - rturrado
@RocketRoy İnsanları bir şeyler yapmakla suçlamaktan önce, neden bazı detaylara dikkat etmeyi denemiyorsunuz? Cevabında, çoğaltamayacağını söylüyorsun. Bu soru 5 yaşında. O zamandan beri işlemcilerin gelişme ihtimali var mı? Cevabıma bakın, Çekirdek 2'de büyük zaman ürettiğini, ancak Nehalem'de ve sonrasında daha az olduğunu gösterir. - Mysticial


Cevaplar:


Bunun daha fazla analizi üzerine, bunun, dört işaretçinin veri hizalamasının neden olduğu (en azından kısmen) olduğuna inanıyorum. Bu, bazı önbellek banka / yol çakışmalarına neden olur.

Dizilerinizi nasıl tahsis ettiğinizi doğru tahmin ettiyseniz, onlar büyük olasılıkla sayfa satırına hizalanmalıdır.

Bu, her döngüdeki tüm erişiminizin aynı önbellek yoluna düşeceği anlamına gelir. Ancak, Intel işlemciler bir süreliğine 8 yollu L1 önbellek ilişkilendirmesine sahipti. Ama gerçekte, performans tamamen düzgün değil. 4-yollara erişmek hala 2 yoldan daha yavaştır.

DÜZENLEME: Aslında tüm dizileri ayrı olarak ayırıyor gibi görünüyor. Genellikle, bu gibi büyük tahsisler istendiğinde, ayırıcı işletim sisteminden yeni sayfalar isteyecektir. Bu nedenle, bir sayfa sınırından aynı mahsupda büyük tahsislerin ortaya çıkma olasılığı yüksektir.

İşte test kodu:

int main(){
    const int n = 100000;

#ifdef ALLOCATE_SEPERATE
    double *a1 = (double*)malloc(n * sizeof(double));
    double *b1 = (double*)malloc(n * sizeof(double));
    double *c1 = (double*)malloc(n * sizeof(double));
    double *d1 = (double*)malloc(n * sizeof(double));
#else
    double *a1 = (double*)malloc(n * sizeof(double) * 4);
    double *b1 = a1 + n;
    double *c1 = b1 + n;
    double *d1 = c1 + n;
#endif

    //  Zero the data to prevent any chance of denormals.
    memset(a1,0,n * sizeof(double));
    memset(b1,0,n * sizeof(double));
    memset(c1,0,n * sizeof(double));
    memset(d1,0,n * sizeof(double));

    //  Print the addresses
    cout << a1 << endl;
    cout << b1 << endl;
    cout << c1 << endl;
    cout << d1 << endl;

    clock_t start = clock();

    int c = 0;
    while (c++ < 10000){

#if ONE_LOOP
        for(int j=0;j<n;j++){
            a1[j] += b1[j];
            c1[j] += d1[j];
        }
#else
        for(int j=0;j<n;j++){
            a1[j] += b1[j];
        }
        for(int j=0;j<n;j++){
            c1[j] += d1[j];
        }
#endif

    }

    clock_t end = clock();
    cout << "seconds = " << (double)(end - start) / CLOCKS_PER_SEC << endl;

    system("pause");
    return 0;
}

Karşılaştırma sonuçları:

EDIT: Sonuçlar bir gerçek Çekirdek 2 mimarlık makinesi:

2 x Intel Xeon X5482 Harpertown @ 3.2 GHz:

#define ALLOCATE_SEPERATE
#define ONE_LOOP
00600020
006D0020
007A0020
00870020
seconds = 6.206

#define ALLOCATE_SEPERATE
//#define ONE_LOOP
005E0020
006B0020
00780020
00850020
seconds = 2.116

//#define ALLOCATE_SEPERATE
#define ONE_LOOP
00570020
00633520
006F6A20
007B9F20
seconds = 1.894

//#define ALLOCATE_SEPERATE
//#define ONE_LOOP
008C0020
00983520
00A46A20
00B09F20
seconds = 1.993

Gözlemler:

  • 6.206 saniye bir döngü ile ve 2.116 saniye iki döngü ile. Bu OP'nin sonuçlarını tam olarak yeniden üretir.

  • İlk iki testte, diziler ayrı olarak tahsis edilir.Hepsinin sayfaya göre aynı hizaya sahip olduğunu fark edeceksiniz.

  • İkinci iki testte, diziler bu hizalamayı kırmak için birlikte paketlenir. Burada her iki döngünün daha hızlı olduğunu göreceksiniz. Ayrıca, ikinci (çift) döngü, normalde beklediğiniz gibi daha yavaş olanıdır.

@Stephen Cannon, yorumlarda belirttiği gibi, bu hizalamanın neden olabileceği olasılığı çok yüksektir. yanlış takma yük / mağaza birimlerinde veya önbellekte. Bunun için uğraştım ve Intel’in aslında kısmi adres takma adı tezgahları:

http://software.intel.com/sites/products/documentation/doclib/stdxe/2013/~amplifierxe/pmw_dp/events/partial_address_alias.html


5 Bölgeler - Açıklamalar

Bölge 1:

Bu kolay. Veri kümesi o kadar küçük ki, performans baş üstü döngü ve dallanma gibi baskındır.

Bölge 2:

Burada, veri boyutları arttıkça, göreceli havai miktar azalır ve performans "doygunluk" olur. Burada iki döngü daha yavaştır, çünkü iki kat daha fazla döngü ve dallanma yükü vardır.

Burada neler olup bittiğinden emin değilim ... Hizalama, Agner Fog’dan bahsederken hala etkili olabilir önbellek banka çakışmaları. (Bu bağlantı Sandy Bridge hakkındadır, ancak fikir hala Core 2'ye uygulanmalıdır.)

Bölge 3:

Bu noktada, veriler artık L1 önbelleğine sığmaz. Bu yüzden performans, L1 <-> L2 önbellek bant genişliği ile sınırlandırılmıştır.

Bölge 4:

Tek döngüsündeki performans düşüşü, gözlemlediğimiz şeydir. Ve belirtildiği gibi, bu (büyük olasılıkla) neden olan hizalamadan kaynaklanmaktadır yanlış takma işlemci yükleme / depo birimlerindeki tezgahlar.

Ancak, yanlış takma adının gerçekleşmesi için, veri kümeleri arasında yeterince büyük bir adım olmalıdır. Bu yüzden 3. bölgede bunu görmüyorsun.

Bölge 5:

Bu noktada, hiçbir şey önbellekte uymuyor. Yani bellek bant genişliği ile bağlısınız.


2 x Intel X5482 Harpertown @ 3.2 GHz Intel Core i7 870 @ 2.8 GHz Intel Core i7 2600K @ 4.4 GHz


1546
2017-12-17 21:17



+1: Bence bu cevap. Diğer bütün cevapların ne söylediğinin tersine, doğal olarak daha fazla önbellek eksikliğine sahip tek döngü varyantı değil, önbellek kayıplarına neden olan dizilerin özel hizalanmasıyla ilgili. - Oliver Charlesworth
Bu; bir yanlış takma durak en olası açıklamadır. - Stephen Canon
@VictorT. Bağlantılı OP kodunu kullandım. Excel'de açabileceğim ve ondan bir grafik oluşturabileceğim bir .css dosyası oluşturur. - Mysticial
@Nawaz Bir sayfa genellikle 4KB'dir. Yazdırtığım onaltılık adreslere bakarsanız, ayrı olarak ayrılmış testlerin tümü aynı modulo 4096'ya sahiptir. (4 KB sınırının başlangıcından 32 bayt) Belki de GCC bu davranışa sahip değildir. Bu, neden farklılıkları görmediğinizi açıklayabilir. - Mysticial
İlgilenenler için Burada bellek hizalama üzerinde iyi okuma ve burada birkaç  yoldaki bağlantılar  veriler bellekte önbelleğe alınır - New Alexandria


Tamam, doğru cevap kesinlikle CPU önbelleği ile bir şeyler yapmak zorunda. Ancak önbellek argümanını kullanmak özellikle veri olmadan oldukça zor olabilir.

Pek çok cevap var, bu çok tartışmaya neden oldu, ancak bununla yüzleşelim: Önbellek sorunları çok karmaşık olabilir ve tek boyutlu değildir. Onlar büyük ölçüde veri büyüklüğüne bağlı, bu yüzden benim soru haksızlık oldu: Bu önbellek grafikte çok ilginç bir noktada olduğu ortaya çıktı.

@ Mysticial'ın cevabı, pek çok insanı (benim de dahil olmak üzere) ikna etti, muhtemelen gerçeklere dayanıyor gibi görünen tek kişi olduğu için, ancak gerçeğin sadece bir "veri noktası" idi.

İşte bu yüzden testini (sürekli ve ayrı bir tahsisat kullanarak) ve @James'in Cevaplarını bir araya getirdim.

Aşağıdaki grafikler, cevapların çoğunun ve özellikle soruların ve cevapların yorumlarının çoğunun, kullanılan tam senaryo ve parametrelere bağlı olarak tamamen yanlış veya doğru olarak değerlendirilebileceğini göstermektedir.

İlk sorumun şu anda n = 100.000. Bu nokta (kaza ile) özel davranış sergiler:

  1. Bir ve iki loop'ed versiyonu (neredeyse üç kat) arasındaki en büyük tutarsızlığa sahiptir.

  2. Tek döngünün (sürekli ayırma ile) iki döngü halini attığı tek nokta budur. (Bu Mysticial'ın cevabını mümkün kıldı.)

Başlangıç ​​verileri kullanılarak sonuç:

Enter image description here

Başlatılmamış verileri kullanarak sonuç (Bu, Mysticial'nin test ettiği şey):

Enter image description here

Ve bu açıklanması zor bir konu: Başlangıçta birleştirilmiş olan ve farklı vektör boyutundaki her bir test durumu için bir kez ayrılan ve yeniden kullanılan veriler:

Enter image description here

öneri

Yığın taşmasıyla ilgili her bir düşük seviyeli performansla ilgili soru, tüm önbellek ilgili veri boyutları için MFLOPS bilgisi sağlamak için gerekli olmalıdır! Bu, herkesin zamanın cevaplarını düşünmek için harcadığı bir israftır ve özellikle bu bilgiler olmadan başkalarıyla tartışır.


195
2017-12-18 01:29



+1 Güzel analiz. Verileri ilk başta başlatılmamış halde bırakmak istemedim. Az önce allocator onları zaten sıfırladı. Böylece başlatılan veriler önemlidir. Cevabımı sadece bir sonuçla düzenledim. gerçek Çekirdek 2 mimarlık makinesi ve gözlemlediğiniz şeylere çok daha yakındırlar. Başka bir şey, bir dizi boyut test ettim n ve aynı performans boşluğunu gösterir. n = 80000, n = 100000, n = 200000, vb... - Mysticial
@Mysticial Bence olası süreçler arası casusluktan kaçınmak için bir süreçte yeni sayfalar verirken OS, sayfa sıfırlamayı uygular. - v.oddou


İkinci döngü çok daha az önbellek aktivitesi içerir, bu nedenle işlemcinin bellek taleplerini takip etmesi daha kolaydır.


63
2017-12-17 20:47



İkinci varyantın daha az önbellek kaçırdığını mı söylüyorsun? Niye ya? - Oliver Charlesworth
@Oli: İlk versiyonda, işlemcinin bir kerede dört bellek hattına erişmesi gerekiyor. a[i], b[i], c[i] ve d[i] İkinci varyantta, sadece ikiye ihtiyacı var. Bu eklerken bu satırları yeniden doldurmak için çok daha uygun hale getirir. - Puppy
Ancak, diziler önbellekte çakışmadıkça, her bir değişken aynı sayıda okuma gerektirir ve ana bellekten / belleğe yazar. Sonuç olarak, bu iki dizinin her zaman çarpıştığını sanıyorum. - Oliver Charlesworth
Ben takip etmem. Talimat başına (ör. x += y), iki okur ve bir yazım var. Bu her iki değişken için de geçerlidir. Önbellek <-> CPU bant genişliği gereksinimi aynıdır. Çakışma olmadığı sürece, önbellek <-> RAM bant genişliği gereksinimi de aynıdır. - Oliver Charlesworth
Belirtildiği gibi stackoverflow.com/a/1742231/102916, Pentium M'in donanım ön yüklemesi 12 farklı ileri akışı izleyebilir (ve daha sonra donanımın en az yetenekli olmasını beklerdim). Loop 2 hala dört yayını okumakta, yani bu sınırın içinde. - Brooks Moses


Bir makinede çalıştığınızı hayal edin n sadece dizilerinizin iki tanesini bir kerede bellekte tutabilmek için doğru değerdi, ancak disk önbellekleme yoluyla elde edilebilen toplam bellek hala dörtünü tutmak için yeterliydi.

Basit bir LIFO önbelleğe alma politikası varsayarsak, bu kod:

for(int j=0;j<n;j++){
    a[j] += b[j];
}
for(int j=0;j<n;j++){
    c[j] += d[j];
}

ilk sebep olur a ve b RAM'e yüklenecek ve daha sonra tamamen RAM'de çalışılacak. İkinci döngü başladığında, c ve d daha sonra diskten RAM'e yüklenir ve çalıştırılır.

diğer döngü

for(int j=0;j<n;j++){
    a[j] += b[j];
    c[j] += d[j];
}

diğer ikisinde iki diziyi ve sayfayı gösterir döngü etrafında her zaman. Bu açıkçası çok Yavaş.

Muhtemelen testlerinizde disk önbelleğe almayı görmüyorsunuz, ancak muhtemelen diğer bazı önbellekleme biçimlerinin yan etkilerini görüyorsunuz.


Burada biraz kafa karışıklığı / yanlış anlaşılma var gibi görünüyor, bu yüzden bir örnek kullanarak biraz detaylandırmaya çalışacağım.

Söylemek n = 2 ve baytlarla çalışıyoruz. Benim senaryoda bu yüzden önbellek sadece 4 bayt ve hafızamızın geri kalanı önemli ölçüde daha yavaştır (100 kez daha uzun erişim).

Oldukça aptal bir önbellekleme politikası olduğunu varsayarsak bayt önbellekte değilse, oraya koyun ve biz de şu baytı alın. senaryoya benzer bir senaryo alacaksın:

  • İle

    for(int j=0;j<n;j++){
     a[j] += b[j];
    }
    for(int j=0;j<n;j++){
     c[j] += d[j];
    }
    
  • önbellek a[0] ve a[1] sonra b[0] ve b[1] ve set a[0] = a[0] + b[0] önbellekte - şimdi önbellekte dört bayt var, a[0], a[1] ve b[0], b[1]. Maliyet = 100 + 100.

  • set a[1] = a[1] + b[1] önbellekte. Maliyet = 1 + 1.
  • İçin tekrarla c ve d.
  • Toplam maliyet = (100 + 100 + 1 + 1) * 2 = 404

  • İle

    for(int j=0;j<n;j++){
     a[j] += b[j];
     c[j] += d[j];
    }
    
  • önbellek a[0] ve a[1] sonra b[0] ve b[1] ve set a[0] = a[0] + b[0] önbellekte - şimdi önbellekte dört bayt var, a[0], a[1] ve b[0], b[1]. Maliyet = 100 + 100.

  • çıkarmak a[0], a[1], b[0], b[1] önbellek ve önbellekten c[0] ve c[1] sonra d[0] ve d[1] ve set c[0] = c[0] + d[0] önbellekte. Maliyet = 100 + 100.
  • Nereye gittiğimi görmeye başladığına şüpheliyim.
  • Toplam maliyet = (100 + 100 + 100 + 100) * 2 = 800

Bu klasik bir önbellek thrash senaryosudur.


37
2017-12-18 01:36



Bu yanlış. Bir dizinin belirli bir öğesine yapılan bir başvuru, tüm dizinin diskten (veya önbelleğe alınmamış bellekten) disk belleğine alınmasına neden olmaz; Yalnızca ilgili sayfa veya önbellek satırı disk belleği. - Brooks Moses
@Brooks Moses - Bütün dizide yürürseniz, burada olduğu gibi, o zaman olacak. - OldCurmudgeon
Evet, evet, ama tüm operasyonda olan bu, döngüde her seferinde gerçekleşen şey değil. İkinci formun "döngü boyunca her seferinde iki dizide iki diziyi ve sayfayı sayfalandıracağını" iddia ettiniz ve buna itiraz ediyorum. Genel dizilerin büyüklüğüne bakılmaksızın, bu döngünün ortasında, RAM'iniz dört dizinin her birinden bir sayfa tutuyor olacak ve döngü bittikten sonra iyi olana kadar hiçbir şey diske alınmayacaktır. - Brooks Moses
Özel durumda nerede n sadece dizilerinizden sadece birini aynı anda bellekte tutabilmeniz için doğru değerdi sonra tüm öğelere erişme dört Bir döngüde diziler kesinlikle thrashing sona ermelidir. - OldCurmudgeon
Neden bu döngüde 2 sayfa kalıyorsun? a1 ve b1 İlk atama için, her birinin sadece ilk sayfasından değil? (5 baytlık sayfalar alıyorsunuz, yani sayfa RAM'inizin yarısı mı? Bu sadece ölçekleme değil, gerçek bir işlemciden tamamen farklı.) - Brooks Moses


Farklı bir kod yüzünden değil, önbellek nedeniyle: RAM, CPU kayıtlarından daha yavaştır ve bir bellek değiştiğinde RAM'in yazılmasını önlemek için CPU'nun içinde bir önbellek bulunur. Ancak, önbellek RAM kadar büyük değil, bu nedenle, sadece bir kısmını eşler.

İlk kod, her bir döngüde onları değiştiren uzak bellek adreslerini değiştirir, böylece önbelleği kalıcı olarak geçersiz kılar.

İkinci kod değişmez: sadece bitişik adreslerde iki kez akar. Bu, tüm işin önbellekte tamamlanmasını, ancak ikinci döngü başladıktan sonra geçersiz kılmasını sağlar.


27
2017-12-17 20:49



Neden bu önbellek sürekli olarak geçersiz kılınır? - Oliver Charlesworth
@OliCharlesworth: Önbelleğe bitişik bellek adreslerinin bir kopyası olarak düşünün. Bir parçası olmayan bir adrese sahipmiş gibi davranıyorsanız, önbelleği yeniden yüklemeniz gerekir. Önbellekteki bir şey değiştirildiyse, RAM'e geri yazılmalı veya kaybolur. Örnek kodda, 100'000 tamsayı (400kBytes) 4 vektörü büyük olasılıkla L1 önbelleğinin (128 veya 256K) kapasitesinden daha fazladır. - Emilio Garavaglia
Önbellek boyutunun bu senaryoda etkisi yoktur. Her dizi elemanı sadece bir kez kullanılır ve bundan sonra tahliye edilip edilmediği önemli değildir. Önbellek boyutu yalnızca geçici konumunuz varsa (yani gelecekte aynı öğeleri yeniden kullanacaksanız) önemlidir. - Oliver Charlesworth
@OliCharlesworth: Önbellekte yeni bir değer yüklemem gerekiyorsa ve değiştirilmiş bir değer zaten varsa, önce bunu yazmam gerekiyor ve bu da yazımın gerçekleşmesini beklememi sağlıyor. - Emilio Garavaglia
Ancak OP'nin kodunun her iki değişkeninde, her bir değer tam olarak bir kez değiştirilir. Her varyantta aynı sayıda geri yazma işlemi yaparsınız. - Oliver Charlesworth


Burada tartışılan sonuçları kopyalayamıyorum.

Zayıf kriter kodunun suçlu olup olmadığını bilmiyorum, ya da şu iki yöntem, aşağıdaki kodu kullanarak benim makinemde birbirinin% 10'u içinde, ve bir döngü genellikle ikiden biraz daha hızlıdır. bekliyoruz.

Dizi boyutları, sekiz döngü kullanılarak 2 ^ 16 ile 2 ^ 24 arasındaydı. Kaynak dizilerini başlatmak için çok dikkatliyim += atama sormadı FPU çift ​​olarak yorumlanan bellek çöpü eklemek.

Atama koyarak gibi çeşitli şemalarla oynadım b[j], d[j] için InitToZero[j] döngüler içinde ve ayrıca kullanarak += b[j] = 1 ve += d[j] = 1ve oldukça tutarlı sonuçlar aldım.

Tahmin edebileceğiniz gibi, başlangıç b ve d kullanarak döngü içinde InitToZero[j] Kombine yaklaşıma bir avantaj sağladı, çünkü ödevlerden önce arka arkaya yapıldılar a ve cama yine de% 10 içinde. Git rakamı.

Donanım Dell XPS 8500 nesil 3 ile Çekirdek i7 @ 3.4 GHz ve 8 GB bellek. Sekiz döngü kullanarak 2 ^ 16 ila 2 ^ 24 için kümülatif zaman sırasıyla 44.987 ve 40.965 idi. Visual C ++ 2010, tamamen optimize edilmiş.

Not: Döngüler sıfıra kadar saymak için değiştirdim ve birleştirilmiş yöntem marjinal olarak daha hızlıydı. Kafamı tırmalamak. Yeni dizi boyutlandırma ve döngü sayılarını not alın.

// MemBufferMystery.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
#include <cmath>
#include <string>
#include <time.h>

#define  dbl    double
#define  MAX_ARRAY_SZ    262145    //16777216    // AKA (2^24)
#define  STEP_SZ           1024    //   65536    // AKA (2^16)

int _tmain(int argc, _TCHAR* argv[]) {
    long i, j, ArraySz = 0,  LoopKnt = 1024;
    time_t start, Cumulative_Combined = 0, Cumulative_Separate = 0;
    dbl *a = NULL, *b = NULL, *c = NULL, *d = NULL, *InitToOnes = NULL;

    a = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
    b = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
    c = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
    d = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
    InitToOnes = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
    // Initialize array to 1.0 second.
    for(j = 0; j< MAX_ARRAY_SZ; j++) {
        InitToOnes[j] = 1.0;
    }

    // Increase size of arrays and time
    for(ArraySz = STEP_SZ; ArraySz<MAX_ARRAY_SZ; ArraySz += STEP_SZ) {
        a = (dbl *)realloc(a, ArraySz * sizeof(dbl));
        b = (dbl *)realloc(b, ArraySz * sizeof(dbl));
        c = (dbl *)realloc(c, ArraySz * sizeof(dbl));
        d = (dbl *)realloc(d, ArraySz * sizeof(dbl));
        // Outside the timing loop, initialize
        // b and d arrays to 1.0 sec for consistent += performance.
        memcpy((void *)b, (void *)InitToOnes, ArraySz * sizeof(dbl));
        memcpy((void *)d, (void *)InitToOnes, ArraySz * sizeof(dbl));

        start = clock();
        for(i = LoopKnt; i; i--) {
            for(j = ArraySz; j; j--) {
                a[j] += b[j];
                c[j] += d[j];
            }
        }
        Cumulative_Combined += (clock()-start);
        printf("\n %6i miliseconds for combined array sizes %i and %i loops",
                (int)(clock()-start), ArraySz, LoopKnt);
        start = clock();
        for(i = LoopKnt; i; i--) {
            for(j = ArraySz; j; j--) {
                a[j] += b[j];
            }
            for(j = ArraySz; j; j--) {
                c[j] += d[j];
            }
        }
        Cumulative_Separate += (clock()-start);
        printf("\n %6i miliseconds for separate array sizes %i and %i loops \n",
                (int)(clock()-start), ArraySz, LoopKnt);
    }
    printf("\n Cumulative combined array processing took %10.3f seconds",
            (dbl)(Cumulative_Combined/(dbl)CLOCKS_PER_SEC));
    printf("\n Cumulative seperate array processing took %10.3f seconds",
        (dbl)(Cumulative_Separate/(dbl)CLOCKS_PER_SEC));
    getchar();

    free(a); free(b); free(c); free(d); free(InitToOnes);
    return 0;
}

MFLOPS'un neden ilgili bir metrik olduğuna karar verildiğinden emin değilim. Fikir, bellek erişimlerine odaklanmak olsa da, kayan nokta hesaplama zamanını en aza indirmeye çalıştım. İçinde bıraktım +=ama emin değilim neden.

Hesaplama gerektirmeyen düz bir atama, bellek erişim süresinin daha temiz bir testi olabilir ve döngü sayısından bağımsız olarak tekdüze bir test oluşturur. Belki konuşmada bir şey özledim, ama iki kere düşünmeye değer. Artı, ödevden çıkarılırsa, birikimli zaman, her biri 31 saniyede hemen hemen aynıdır.


16
2017-12-30 01:34



Burada bahsettiğiniz yanlış hizalama cezası, yanlış hizalanmış (yükü olmayan SSE yükleri / depoları dahil) tek bir yük / mağaza olduğunda. Ancak, performans farklı dizilerin göreceli hizalamalarına duyarlı olduğundan bu durum böyle değildir. Talimat seviyesinde yanlış hizalama yoktur. Her bir yük / depo düzgün şekilde hizalanmıştır. - Mysticial


Çünkü CPU'nun pek çok önbellek eksikliği yok (dizilim verilerinin RAM çiplerinden gelmesini beklemek zorunda). Dizilerin boyutlarını sürekli olarak ayarlamanız sizin için ilginç olacaktır. seviye 1 önbellek (L1) ve sonra seviye 2 önbellek (L2), CPU'nuzun ve kodunuzun dizilerin boyutlarına karşı çalıştırılması için harcanan süreyi çizin. Grafik beklediğiniz gibi düz bir çizgi olmamalıdır.


14
2017-12-17 20:52



Önbellek boyutu ve dizi boyutu arasında herhangi bir etkileşim olduğuna inanmıyorum. Her dizi elemanı sadece bir kez kullanılır ve daha sonra güvenli bir şekilde tahliye edilebilir. Önbellek arasında bir etkileşim olabilir. hat boyut ve dizi boyutu, eğer dört dizinin çakışmasına neden oluyorsa. - Oliver Charlesworth
Haklısın, bu etkiyi göstermek için yanlış bir örnek. - James