CPU’yu Gerçekten Öfkelendiren Veri Erişim Desenleri

 (blog.weineng.me)
1 puan yazan GN⁺ 3 시간 전 | 1 yorum | WhatsApp'ta paylaş
  • Aynı tamsayı toplama döngüsünde yalnızca erişim sırasını değiştirmek bile çalışma süresini büyük ölçüde değiştiriyor; deney, rastgele erişimden %30’dan fazla daha yavaş bir permütasyon oluşturulabildiğini gösteriyor
  • Doğrusal erişim 133 milyon çevrim ile hızlıyken, rastgele erişimde CPU’nun bir sonraki konumu tahmin etmesi zorlaştığı için süre 1,57 milyar çevrime kadar çıkıyor
  • Önbellek satırı ve sayfa sınırları kullanılarak erişim aralıkları açıldığında prefetcher ve önbellek yeniden kullanımı zayıflıyor; ayrıca set-associative cache özelliği nedeniyle L1d’nin fiilen kullanılabilen kapasitesi 768B düzeyine düşüyor
  • Sayfa stride değeri 8 yapıldığında PTE önbellek satırı yerelliği de bozuluyor ve süre 2,06 milyar çevrime çıkıyor; bu da basit bir rastgele karıştırmadan daha kötü bir desen oluşturuyor
  • DRAM bank/row çatışmasını hedefleyen yaklaşık desen 2,08 milyar çevrim ile biraz daha yavaştı; ancak fiziksel adresin DRAM’e eşlenmesi platforma bağlı olduğundan bunu tamamen denetlemek zor

Deney koşulları ve ölçüt

  • Amaç, data dizisindeki tamsayıları toplayan sabit accumulator fonksiyonunda yalnızca positions permütasyonunu değiştirerek en yavaş çalışma süresini oluşturmaktı
  • positions oluşturma süresi hariç tutuldu; yalnızca biriktirme fonksiyonunun çalışma süresi rdtsc çevrim sayacıyla ölçüldü
  • Veri boyutu 2^26 adet uint32_t tamsayıdan oluşuyor
    • 65.536 sayfa kullanılıyor
    • Her sayfa 4.096 bayt
    • Her sayfada 1.024 tamsayı bulunuyor
  • huge pages devre dışı bırakıldı
  • Ölçüm yapılan makine, Intel Core Ultra 7 268V tabanlı bir x86_64 sistem
    • 8 CPU çekirdeği
    • Toplam L1d 320KiB, toplam L1i 512KiB
    • Toplam L2 14MiB
    • L3 12MiB
  • Tüm kod GitHub deposunda yer alıyor ve örnek g++ -std=c++2a -O3 slowest.cc && taskset -c 3 sudo ./a.out komutuyla çalıştırılıyor
  • Temel döngü, positions[i] tarafından işaret edilen data[pos] değerlerini sırayla toplayan basit bir yapıdan oluşuyor

Doğrusal erişim ile rastgele erişim arasındaki fark

  • En basit linear desende positions[i] = i atanıyor ve dizi baştan sona sırasıyla erişiliyor
  • Doğrusal erişim 132,752,394 çevrim sürdü; CPU sıralı erişim için güçlü biçimde optimize edildiğinden en hızlı sınıfta yer alıyor
  • fisher_yates_shuffle ile positions rastgele bir permütasyona dönüştürüldüğünde CPU’nun sıradaki erişimi tahmin etmesi zorlaşıyor
  • Rastgele erişim 1,572,108,618 çevrim sürdü ve doğrusal erişimden 10 kattan fazla daha yavaştı
  • Deney burada durmayıp, rastgeleden daha kötü bir permütasyonun kasıtlı olarak üretilebileceğini test ediyor

Önbellek satırı ve sayfa düzeyinde erişimi seyrekleştirmek

  • İlk kötüleştirme deseni, ardışık erişimlerin her seferinde tam bir önbellek satırı aralıklı olacağı şekilde positions yerleştiriyor
  • Bu desende 64 baytlık önbellek satırından yalnızca tek bir 4 baytlık tamsayı kullanılıyor, ardından bir sonraki önbellek satırına geçiliyor
    • Aynı önbellek satırına geri dönüldüğünde yeniden kullanılabilir verinin önbellekten atılmış olma ihtimali yüksek
  • Önbellek satırı aralıklı erişim 718,804,156 çevrim sürdü ve doğrusal taramadan 4 kattan fazla daha yavaştı
  • Yine de bu durumda donanımsal prefetcher, data üzerindeki basit akış desenini algılayıp gelecekteki önbellek satırlarını önceden getirebiliyor
  • Birçok Intel donanım veri prefetcher’ı 4KiB sayfa sınırını aşan prefetch yapmıyor
  • Bir sonraki desen, erişim aralığını önbellek satırı yerine tam sayfa olacak şekilde açıyor
    • Her sayfa 4.096 bayt
    • Sayfa başına aynı ofsete önce erişilecek şekilde page_index * elements_per_page + element_index biçimi kullanılıyor
  • Sayfalar arası aralıklı erişim 1,411,153,154 çevrim ile belirgin biçimde daha yavaş oldu

Set-associative cache ve yeniden kullanım mesafesi

  • Deney makinesindeki çekirdek başına L1d önbelleği 48KB, 12-way ve 64 set yapısında
  • L1d’de 64 set olduğundan, A ve A + 4096 bayt adresleri aynı L1d set’ine eşleniyor
    • 4.096 bayt, 64 sets * 64-byte cache line değerine eşit
  • Sayfa düzeyindeki stride, her iç döngünün tüm 64 sete dengeli dağılmak yerine sürekli aynı set üzerine gitmesine neden oluyor
  • Bir sette yalnızca 12 way bulunduğundan, 12’den fazla etkin önbellek satırı rekabete girdiğinde CPU satırları tekrar tekrar dışarı atıp yeniden yüklemek zorunda kalıyor
  • L1d’nin toplam kapasitesi 48KB olsa da, bu erişim deseninde işe yarar biçimde kullanılabilen L1d kapasitesi 12 ways * 64B yani 768B düzeyine düşüyor
  • separated_by_a_page deseni, 65.536 önbellek satırına eriştikten sonra aynı önbellek satırına geri döndüğü için önbellek satırı yeniden kullanım mesafesi 65.536 oluyor
  • Sayfa içindeki önbellek satırlarını da ayıran separated_by_a_page_and_cacheline deseni, yeniden kullanım mesafesini 65536 pages * 4096 page size / 64 cacheline size düzeyine çıkarıyor
  • Buna rağmen sonuç 1,408,519,172 çevrim ile sayfa düzeyli erişime neredeyse eşit kaldı
  • Deney çekirdek 3 üzerinde çalıştırıldı ve bu çekirdekte 2,5MB L2 ile 48KB L1 bulunuyor
    • 65.536 sayfada bir tur atmak 4MB veriye erişmek anlamına geliyor
    • Bu miktar ilgili çekirdeğin private L1/L2 kapasitesinden büyük
    • Dolayısıyla bir sonraki gerekli önbellek satırının private cache içinde kalma olasılığı düşük
  • Private cache yeniden kullanımının ancak önbellek satırı yeniden kullanım mesafesi yaklaşık ((2560+48)*1024/64) yani 40 bin civarından küçük olduğunda beklenebileceği belirtiliyor

Sayfa stride, PTE ve DRAM’e kadar zorlamak

  • Bir sonraki varyasyon, ardışık sayfalar yerine N sayfa aralıklı erişen separated_by_stride_pages_and_cacheline deseni
  • Çeşitli stride değerleri ölçüldüğünde en kötü sonucun sayfa stride değeri 8 iken çıktığı ve bunun rastgele erişimden de yavaş olduğu görüldü
  • -DSTRIDE=8 ile tek başına çalıştırıldığında süre 2,058,425,640 çevrim oldu
  • Stride 8’de tepe oluşmasının olası nedenlerinden biri adres çevirimi
    • Sanal adres erişimleri MMU tarafından fiziksel adrese çevriliyor
    • Bu çeviri için page table entry (PTE) kullanılıyor
    • PTE 8 bayt ve tek bir önbellek satırında 8 PTE bulunuyor
    • 8 sayfalık stride kullanıldığında, yalnızca veri önbellek satırları değil, sayfa eşlemeleri için gereken ayrı önbellek satırları da her seferinde yeniden getiriliyor olabilir
  • Son aşama, DRAM controller davranışını da bozmayı hedefliyor
  • DRAM; channel, rank, chip, bank, row ve column bileşenlerinden oluşuyor
    • Her bank içinde birden çok row bulunuyor
    • Belirli bir row’a erişmek için önce o row etkinleştirilip row buffer’a kopyalanıyor
    • Aynı bank içinde farklı bir row’a erişmek için mevcut row’un precharge ile kapatılıp yeni row’un etkinleştirilmesi gerekiyor
  • Aynı bank içindeki row’lar arasında gidip gelindiğinde row-buffer conflict oluşuyor ve DRAM controller’ın yanıtı yavaşlıyor
  • Buna karşılık zaten açık olan row’a erişmek row-buffer hit oluşturuyor; ayrıca birden çok bank aynı anda kullanılabildiğinde memory controller işleri örtüştürerek yürütebiliyor
  • Yavaş bir desen üretmek için strateji şu şekilde
    • Sanal page number, page table üzerinden fiziksel frame number (PFN) değerine çevriliyor
    • page offset korunarak fiziksel adres oluşturuluyor
    • Fiziksel adres DRAM channel, rank, bank group, bank, row ve column olarak yorumlanıyor
    • Aynı bank içindeki farklı row’lara tekrar tekrar erişilerek neredeyse her istekte precharge ve activation zorlanmaya çalışılıyor
  • Ancak fiziksel adresten DRAM channel, rank, bank ve row’a giden eşleme belgelenmiş değil ve platforma bağlı
    • CPU, bellek türü, BIOS/firmware ayarları, channel/rank yapısı ve address hashing’e göre değişebiliyor
    • DRAMA veya Sudoku gibi araçlar kullanılabilir, ancak bu deney makinesinde çalıştırılamamış
  • DRAMA makalesi ve yerel deneyler temel alınarak 4 bank group, grup başına 4 bank ve DRAM_ROW_SHIFT = 18 kullanılarak yaklaşık bir model kuruldu
  • DRAM bank/row çatışmalarını da hesaba katan desen 2,082,308,014 çevrim ile stride 8’den tutarlı biçimde biraz daha yavaştı, ancak fark büyük değildi
  • Tam bir row conflict oluşturulamamasının birkaç kısıtı var
    • bank group hash, bank hash ve row shift tahminleri doğru olmayabilir
    • 8 sayfalık stride yaklaşık 32KB aralıklı erişim anlamına geldiğinden aynı DRAM row içinde kalmak zor
    • Intel’in bank hashing mekanizması nedeniyle gerçekte birden çok bank aynı anda kullanılıyor olabilir
  • Tam çalıştırma örneği şu sonuçları verdi
    • linear: 132,752,394
    • fisher_yates_shuffle: 1,572,108,618
    • separated_by_a_cacheline: 718,804,156
    • separated_by_a_page: 1,411,153,154
    • separated_by_a_page_and_cacheline: 1,408,519,172
    • stride=8 separated_by_stride_pages_and_cacheline: 2,058,425,640
    • separated_by_stride_bank_conflicts_and_cacheline: 2,082,308,014
  • Önbellek, prefetcher, önbellek satırı yeniden kullanımı, PTE erişimi ve DRAM bank/row özellikleri sırayla kötüleştirildiğinde, rastgele erişimden %33 daha yavaş bir toplama deseni üretilebiliyor
  • Güç tasarrufu moduna geçiş gibi biriktirmeyi daha da yavaşlatan yöntemler de var, ancak bunlar yalnızca erişim desenini değiştirmeye odaklanan bu deneyden ayrı tutuluyor

İlgili okumalar

1 yorum

 
GN⁺ 3 시간 전
Lobste.rs yorumları

  • İçerideki Windows 11 geliştirme araştırmaları böyle görünüyormuş demek; keyifle okudum /s

  • https://github.com/ob/cache’i yaparken bunu öğrenmiştim

    • README’deki iki cümleyi nasıl anlamak gerektiğini merak ediyorum
      Biri, gecikme süresi sayılarını üretme tekniğini ilk kez Computer Architecture: A Quantitative Approach kitabının 476. sayfasındaki 5.2 alıştırmasında gördüğünü söylüyor; diğeri ise fikrin Rafael Héctor Saavedra‑Barrera’nın doktora tezinden geldiğini söylüyor
      Bunların farklı şeylerden mi bahsettiğini, çelişki mi olduğunu, yoksa aynı şey olup Saavedra-Barrera’nın CA:AQA’da alıntılanıp alıntılanmadığını doğrulamak istiyorum
      Claude programının README yazımından dışlanıp dışlanmadığı da belirsiz; ayrıca depo katkıcısı olarak da göründüğü için önce referansın gerçek olup olmadığını kontrol etmek istiyorum

  • Özel önbellek hiyerarşisi erişimini denemek isterseniz, yaptığım simülatörü de öneririm
    https://github.com/TheCloudlet/Stratum

  • İndeks hesaplama ek yükünü gerçek erişim maliyetinden nasıl ayırdıklarını merak ediyorum

    • positions oluşturma süresini de dahil etmeden yalnızca accumulator döngülerini nasıl ölçtüğümü soruyorsanız, önce reset ve arrange_positions çalıştırıp rdtsc_start() ile rdtsc_end() arasına yalnızca accumulator(data, positions) koyan bir makro kullandım
      Ardından sonucu yazdırıp sum == linear_scan_sum doğrulamasını yaptım ve do_not_optimize(sum) ile optimizasyonun bunu ortadan kaldırmasını engelledim

  • Profesörlerin öğrettiği veri erişim desenleriyle de deneyecek olursak, önce SafeNumber.java sınıfını yapmak gerekiyor; ardından add(SafeNumber b) üyesine ihtiyaç duyuluyor
    Gelecek dönem bunu Redis’in arkasına koyup web ölçeğinde performans veren bir mimari öğreniriz herhalde
    Claude sayesinde benchmark’ı Java’ya taşıdım; Java SafeNumber[], doğrusal erişimde C++ uint32_t[]’den yaklaşık 3,6 kat yavaştı, Fisher-Yates shuffle’da ise C++ doğrusal erişime göre 52,2 kat yavaştı
    Mutlak süreler 67 milyon eleman için C++ doğrusal 10.258.584 ns, Java doğrusal 36.740.667 ns, C++ shuffle 264.856.042 ns, Java shuffle 535.724.208 ns idi; beklediğimden daha çok “sadece 4 kat” seviyesinde kalması etkileyici

    • Java çarpanı pek iyi değil ama Project Valhalla çıkınca belki daha yakın hale gelebilir