Neden bir döngü iki döngü daha yavaş gerçekleşiyor? | Netgez.com
SORU
17 Aralık 2011, CUMARTESİ


Neden bir döngü iki döngü daha yavaş gerçekleşiyor?

a1, b1, c1, ve d1 yığın bellek işaret sanırım sayısal kodu aşağıdaki temel döngü vardır.

const int n=100000;

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

Bu döngü for başka bir dış döngü ile 10.000 kez yürütülür. Bunu 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];
}

Derlenmiş MS Visual C 10.0 ile tam optimizasyon ve SSE2 etkin için 32-bit bir Intel Core 2 Duo (64), ilk örnek alır 5.5 saniye ve çift döngü örnek alır sadece 1.9 saniye. Benim sorum: (alttaki benim tekrar gözden geçirilmesi soru bakın Lütfen

PS: eğer bu yardımcı olur: emin değilim, ben

Çözümü ilk döngü için temel olarak bu gibi görünüyor (bu blok tam program içinde 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ği, her döngü bu kod (aşağıdaki bloğu üç kez tekrar ilgili) üretir:

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

DÜZENLEME:Soru davranış ciddi diziler (n) ve CPU önbellek boyutlarına bağlı olarak hiç bir ilgisi olduğu ortaya çıktı. Eğer daha fazla ilgi varsa, ben soruyu düzeltiyorum:

Aşağıdaki grafikte beş bölgelerin gösterildiği gibi farklı önbellek davranışlara yol bu detaylara biraz sağlam bir fikir verebilir misiniz?

Ayrıca bu İşlemciler için de benzer bir grafik vererek İŞLEMCİ/önbellek mimarileri arasındaki farkları belirtmek için ilginç olabilir.

PPS:tam koduhttp://pastebin.com/ivzkuTzG. Bu tanımlama değil özürlü mümkün olan en yüksek çözünürlük zamanlama için 22 ** Tick_Count kullanır TBB_TİMİNG Makro.

(*. *15) farklı değerleri için FLOP/s gösteriyor

enter image description here

CEVAP
17 Aralık 2011, CUMARTESİ


Bu daha fazla analiz üzerine, bu olduğuna inanıyorum (en azından kısmen) dört işaretçiler veri uyumu nedeniyle. Bu önbellek banka/yol çatışmaları belli bir düzeyde neden olur.

Eğer düzgün bir dizi tahsis etmek gerekir, onlar tahmin etmiştimsayfa satır . hizalanmış olması muhtemeldir .

Bu her döngüde tüm erişir aynı önbellek yolda düşecek anlamına gelir. Ancak, Intel işlemciler 8-way birleşim bir süre L1 önbelleği var. Ama gerçekte, performans tamamen üniforma değil. 4-yollar erişim hala 2-Yol demek daha yavaştır.

EDİT : tüm diziler ayrı ayrı tahsis etmek gibi aslında görünüyor. Genelde böyle büyük ayırmalarını rica olunur, ayırıcı OS yeni bir sayfa talep edecek. Bu nedenle, büyük ayırmalarını aynı sayfa-sınır uzaklığı karşınıza çıkacak olan yüksek bir şans var.

Ä°ÅŸ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;
}

Deney Sonuçları:

EDİT: bir SonuçgerçekCore 2 mimarisi makinesi:

2 x Intel @ 3.2 GHz: "çok çekirdekli Harpertown X5482

#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 saniyebir döngü ile2.116 saniyeiki döngü ile. Bu tam olarak OP sonuçlar üretir.

  • Ä°lk iki test, diziler ayrı ayrı tahsis edilir.Hepsi aynı hizalama sayfa göreceli olduÄŸunu fark edeceksiniz.

  • Ä°kinci iki test, diziler birlikte bu uyumu bozmak için paketlenir.Burada her iki döngüler daha hızlı olduÄŸunu fark edeceksiniz. Ayrıca, (çift) ikinci döngü normalde beklediÄŸiniz gibi ÅŸimdi daha yavaÅŸ.

@Stephen Cannon yorum işaret ettiği gibi, bu uyumu neden olan bir çok olasılık varyanlış yumuşatmaload/store birimleri veya önbelleği. Etrafta bunun için Araştırdım ve Intel aslında bir donanım sayaç içinkısmi Adres yumuşatmatezgahları:

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


5 Bölgeleri - Açıklamalar

Bölge 1:

Bu çok kolay. Veri kümesi performans döngü gibi havai hakim ve dallanma o kadar küçük.

Bölge 2:

Burada, veri boyutları arttıkça, bağıl yük miktarı düşer ve performans "". doyurur Burada iki döngüler iki kat daha fazla döngü olduğundan daha yavaş ve havai dallanma.

Burada tam olarak neler olduğundan emin değilim... Uyum hala Agner Fog cache bank conflicts bahseder gibi bir etkisi oynayabilir. (Bağlantı Sandy Bridge, ama fikir hala Çekirdek için geçerli olmalıdır 2.) hakkında

Bölge 3:

Bu noktada, verilerin artık L1 önbellek sığar. Performans L1 < tarafından kapatılmış;->L2 önbellek bant genişliği.

Bölge 4:

Tek-döngü içinde performans düşüşü izliyoruz. Ve belirtildiği gibi, bu (büyük ihtimalle) neden olan uyumu nedeniyleyanlış yumuşatmaişlemci yük tezgahları/adet mağaza.

Yanlış aliasing gerçekleşebilmesi için, ancak veri setleri arasında yeterince büyük bir adım olmalı. Bu bölgede bu 3 görüşmüyorsunuz.

Bölge 5:

Bu noktada, hiçbir şey önbelleğinde uyuyor. Bellek bant genişliği bağlı kalacaksınız.


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

Bunu PaylaÅŸ:
  • Google+
  • E-Posta
Etiketler:

YORUMLAR

SPONSOR VÄ°DEO

Rastgele Yazarlar

  • ★ByScrapi★ Designs

    ★ByScrapiâ

    27 AÄžUSTOS 2013
  • Awesomesauce Network

    Awesomesauce

    4 EKÄ°M 2012
  • michal lelkowski

    michal lelko

    9 Temmuz 2006