Bölüm 6:Cache Nasıl Çalışır

Bir önceki bölümde bellek piramidini yukarıdan aşağı gezdik ve her katmanda gecikmenin bir mertebe arttığını gördük. Ama asıl soruyu erteledim.

CPU bir adres istediğinde cache, o adresin elinde olup olmadığını nasıl anlıyor? Veri oraya ne zaman geldi, yerini kime bırakıyor, ve iki çekirdek aynı veriye aynı anda dokunduğunda kim haklı çıkıyor?

Bu bölüm o mekanizmanın içi. Aynı algoritmayı çalıştıran iki programın neden farklı hızlarda koştuğunu da burada göreceğiz — cevap neredeyse her zaman burada.

Bu bölümde neyi çözüyoruz?

• Cache’in neden tek tek bayt değil, 64 baytlık bloklar hâlinde çalıştığını göreceğiz.
• Bir adresin cache içinde nasıl arandığını (tag, index, offset) çözeceğiz.
• Locality’nin ne olduğunu ve cache-friendly kodun neden hızlı olduğunu göstereceğiz.
• Çok çekirdekli bir işlemcide aynı verinin kopyalarının nasıl tutarlı tutulduğunu bağlayacağız.

Cache Line: Cache’in Çalışma Birimi

Cache’ler tek tek byte’ları değil, cache line denen bloklar hâlinde veri taşır. x86-64’te tipik cache line boyutu 64 byte’tır.

Neden? Çünkü programlar genelde komşu verilere sırayla erişir. CPU tek bir bayt istese bile, cache o baytın içinde bulunduğu 64 baytlık bloğun tamamını getirir; böylece bir sonraki erişim büyük ihtimalle cache’te bulunur.

Buradaki blok gelişigüzel değil, hizalıdır. Bellek, başlangıç adresi 64’ün katı olan bloklara bölünmüş kabul edilir ve cache bu blokları ancak bütün hâlinde taşır. Yani istediğin bayt bloğun ortasına denk geliyorsa, ondan öncekiler de sonrakiler de aynı anda gelir. Bu ayrıntı önemsiz görünüyor ama bölümün sonunda göreceğimiz false sharing sorununun tam olarak sebebi budur.

Cache Veriyi Nasıl Buluyor?

Şu ana kadar cache’i “hızlı bir kutu” gibi anlattım. Peki CPU bir adres istediğinde cache, o adresin içinde olup olmadığını nasıl anlıyor? Bütün satırları tek tek taramak mümkün değil; o kadar zamanı olsa zaten RAM’e gitmek yeterdi.

Numara, adresi üç parçaya bölmekte. 64 baytlık satırlar kullanan bir cache için:

• Offset (son 6 bit). Bulunan satırın içinde kaçıncı bayttasın? 64 bayt için tam 6 bit gerekir, çünkü 2⁶ = 64. 1. bölümde ikinin kuvvetleriyle çalışırken kullandığımız hesabın aynısı.
• Index (ortadaki bitler). Bu adres cache’in hangi kümesine düşer? Cache, satırları kümelere böler ve bir adres yalnızca tek bir kümeye düşebilir. Böylece arama, koca cache yerine tek bir kümeyle sınırlanır.
• Tag (kalan üst bitler). Aynı kümeye düşen çok sayıda farklı adres var. Kümedeki satırın gerçekten senin istediğin adres olup olmadığını tag söyler.

Yani cache bir arama yapmıyor; index ile doğrudan doğru kümeye gidiyor ve orada yalnızca birkaç tag karşılaştırıyor. Hepsi tek saat çevriminde bitiyor.

Adımları tek tek izlemek istersen:

Şimdi asıl tasarım sorusu: bir kümede kaç satır olmalı?

• Direct-mapped (küme başına 1 satır). En basit ve en hızlı: her adresin gidebileceği tek bir yer var, tek bir tag karşılaştırması yeter. Kusuru ağır: aynı kümeye düşen iki veriyi dönüşümlü kullanırsan, ikisi sürekli birbirini kovar. Cache’in geri kalanı bomboş dururken bu iki adres birbirini yiyip bitirir. Buna conflict miss denir.
• Fully associative (tek küme, bütün satırlar). Her adres her yere gidebilir, conflict miss diye bir şey kalmaz. Ama her erişimde bütün tag’lerin karşılaştırılması gerekir; bu da pahalı ve yavaştır. Yalnızca çok küçük yapılarda (örneğin bazı TLB’lerde) kullanılır.
• N-way set associative (küme başına N satır). İkisinin arası ve gerçek işlemcilerin tercihi. Tipik bir L1 8-way, L3 ise 16-way olabilir. Bir adres N farklı yerden birine düşebilir; conflict miss ihtimali dramatik biçimde azalır, karşılaştırma maliyeti ise N ile sınırlı kalır.

Son soru: küme doluyken yeni bir satır gelirse hangisi atılır? İdeal cevap LRU’dur (Least Recently Used) — en uzun süredir dokunulmayanı at. Ama gerçek donanımda tam LRU tutmak, her erişimde kullanım sırasını güncellemek demektir ve bu, 16 yollu bir kümede pahalıya patlar. Bu yüzden işlemciler LRU’nun ucuz yaklaşıklarını kullanır: her satıra bir “yakında kullanıldı” biti koyup sırayla temizleyen pseudo-LRU gibi düzenekler. Sonuç LRU kadar iyi değildir, ama farkı ölçülemeyecek kadar küçük ve maliyeti kat kat düşüktür.

Yazma Nereye Gider?

Okumayı anlattık, peki CPU bir değere yazdığında ne oluyor? İki seçenek var ve aralarındaki tercih bölümün ilerisi için kritik.

Write-through — her yazma hem cache’e hem de bir alt katmana aynı anda gider. Basit ve güvenli: alt katman hiçbir zaman bayat kalmaz. Bedeli, her yazmanın yavaş katmanın hızına mahkûm olması.

Write-back — yazma yalnızca cache’te yapılır ve satır “kirli” (dirty) olarak işaretlenir. Alt katmana ancak o satır cache’ten atılırken yazılır. Aynı değişkene arka arkaya bin kez yazarsan, RAM’e yalnızca bir kez gidilir.

Modern L1/L2/L3’ün tamamı write-back çalışır; fark, RAM trafiğinde kat kat azalma demek. Ama bunun bir bedeli var ve o bedeli birazdan ödeyeceğiz: cache’teki değer ile RAM’deki değer bir süre boyunca farklı olabilir. Tek çekirdekli bir dünyada bu kimseyi ilgilendirmez. Sekiz çekirdek aynı veriye baktığında ise tam bir soruna dönüşür.

Prefetch: İstenmeden Getirmek

Cache’in hikâyesinde bir parça daha var ve satır bazlı döngünün neden bu kadar hızlı olduğunun yarısı burada saklı.

Modern işlemcilerde prefetcher denen bir devre, senin erişim düzenini izler. Ardışık adreslere eriştiğini ya da sabit bir adım aralığıyla ilerlediğini fark ederse, sıradaki cache line’ları sen istemeden çekmeye başlar. Tahmini tutarsa veri sen isteyene kadar çoktan cache’e gelmiş olur; yani gecikme ortadan kalkmaz, sadece görünmez olur — CPU beklerken değil, çalışırken taşınmıştır.

Tahmin tutmazsa bedelini de ödersin: boşuna taşınan satırlar hem bellek bant genişliğini yer hem de cache’te işine yarayacak başka satırların yerini kapar. Prefetcher’ın rastgele erişim düzenlerinde işe yaramamasının, hatta bazen zarar vermesinin sebebi budur.

Locality: Hızın Sırrı

Cache’lerin işe yaramasının nedeni iki locality prensibidir:

1. Temporal Locality (Zamansal Yakınlık): Az önce kullandığın bir veriyi yakında tekrar kullanma ihtimalin yüksektir. Örneğin bir döngüdeki sayaç değişkeni.
2. Spatial Locality (Mekânsal Yakınlık): Kullandığın verinin komşusuna da yakında erişme ihtimalin yüksektir. Örneğin bir dizinin elemanlarını sırayla okumak.

Hit ve miss. İstediğin veri cache’te bulunursa buna cache hit, bulunamayıp bir alt katmana inmek gerekiyorsa cache miss denir. Toplam erişimlerin ne kadarının hit olduğu da cache hit rate’tir. Bir cache miss bedava değildir: bulunamayan veri, o katmanın kendi alt katmanından istenir ve zincir gerekirse RAM’e kadar iner. Aynı algoritmayı çalıştıran iki programın hız farkı çoğu zaman tam olarak burada saklıdır — aynı işlemci, aynı sayıda işlem, farklı erişim düzeni.

Cache-Friendly ve Cache-Unfriendly Kod

Locality prensibi pratikte nasıl işler? Aşağıdaki iki C kodu aynı matrisi topluyor ve neredeyse aynı görünüyor; aralarındaki tek fark iki döngünün sırası. Buna rağmen büyük matrislerde biri diğerinden kat kat hızlı çalışır ve sebebi tamamen cache’tir.

Cache-friendly örnek (satır bazlı erişim):

for (int i = 0; i < N; i++)
  for (int j = 0; j < N; j++)
    sum += matrix[i][j];  // Sequential access = cache hit

Cache-unfriendly örnek (sütun bazlı erişim):

for (int j = 0; j < N; j++)
  for (int i = 0; i < N; i++)
    sum += matrix[i][j];  // Strided access = cache miss

Neden satır bazlı (row-major) daha hızlı? C dilinde çok boyutlu diziler satır bazlı saklanır. matrix[i][j] erişimi komşu bellek adreslerine sırayla erişir; bu spatial locality sağlar. Bir cache line (64 byte) içinde ardışık veriler gelir ve CPU bir sonraki erişimde cache’de bulur. Sütun bazlı erişimde ise iki ardışık okuma arasındaki adres mesafesi bir matris satırının tamamı kadardır. Bu mesafeye stride (adım aralığı) denir. Stride bir cache line’dan büyük olduğu anda spatial locality tamamen kaybolur: getirilen 64 baytın yalnızca birini kullanır, kalan 63’ünü çöpe atarsın. Sonuç, neredeyse her erişimde bir cache miss — üstelik prefetcher da bu düzeni çoğu zaman takip edemez.

Bellek Kanalları ve Bant Genişliği

CPU ile RAM arasında veri, bellek kanalları (memory channels) üzerinden taşınır. Çift kanallı (dual-channel) bellek, iki kanalı paralel kullanarak teorik bant genişliğini iki katına çıkarır.

Burada çok sık yapılan bir çıkarım hatası var, onu baştan kapatalım: çift kanal, tek bir erişimi hızlandırmaz. İki farklı şeyden söz ediyoruz.

• Gecikme (latency), tek bir isteğin cevabının gelmesi için geçen süredir. Kanal sayısı bunu değiştirmez; istediğin bayt yine ~80 nanosaniye sonra gelir.
• Bant genişliği (bandwidth), birim zamanda taşınabilen toplam veri miktarıdır. Kanal sayısı yalnızca bunu artırır.

Benzetmesi otoyol: şerit eklemek arabaların hızını artırmaz, sadece aynı anda daha çok araba geçmesini sağlar. Bu yüzden tek bir çekirdek genellikle bant genişliğini tek başına doyuramaz; kanal sayısına asıl duyarlı olanlar çok çekirdekli iş yükleri ve sistem belleğini paylaşan entegre GPU’lardır.

Bant genişliği, birim zamanda taşınabilen veri miktarıdır. DDR5-5600 bellek, kanal başına ~45 GB/s bant genişliği sunabilir.

Çok Çekirdek: Aynı Veriyi Kim Doğru Biliyor?

Şimdiye kadar tek bir çekirdeğin bellek görüşünü anlattık. Ama modern bir işlemcide sekiz çekirdek var ve her birinin kendi L1 cache’i var. Aynı değişkeni iki çekirdek birden okuduysa iki ayrı kopyası oluşur. Biri o kopyayı değiştirirse ne olur?

Cevap, çekirdekler arasında sessizce dönen bir konuşmadır: cache coherence (cache tutarlılığı). Donanım, bir cache line’ın her kopyasına bir durum etiketi tutturur ve çekirdekler birbirini haberdar eder. En yaygın anlatım MESI protokolüdür ve dört durumu vardır:

Bir çekirdek yazmaya kalktığında önce diğerlerine “bu satır artık benim” der; onlar da kendi kopyalarını Invalid işaretler. Bu konuşma bedava değildir ve bedelini ödeyen çoğu zaman farkında bile olmaz.

TLB: Adres Çevirisinin Hızlı Sözlüğü

Bellekle ilgili bir cache daha var ve hiyerarşinin parçası olduğu için burada anmam gerekiyor — tam hikâyesi ise sanal belleği anlatmadan tamamlanmıyor.

Kısaca durum şu: CPU’nun kullandığı adresler doğrudan RAM’deki konumlar değildir. Programın gördüğü adres ile RAM’deki gerçek adres arasında bir çeviri yapılır ve bu çevirinin tablosu da bellekte durur. Yani her bellek erişimi aslında iki erişim demektir: önce çeviriyi bul, sonra veriyi al.

TLB (Translation Lookaside Buffer) bu çevirilerin sonucunu saklayan küçük ve çok hızlı bir tablodur. Tipik olarak birkaç yüz giriş tutar — evet, sadece birkaç yüz. Bir TLB isabeti neredeyse bedavadır, çünkü çeviri araması cache erişimiyle paralel yürütülür; CPU veriyi ararken adresi de çeviriyordur.

TLB’yi asıl önemli kılan ise ıskalamanın maliyeti. Sıradan bir cache miss’te veri bir alt katmandan gelir. TLB miss’te ise CPU’nun çeviriyi bulmak için belleğe birden fazla ek erişim yapması gerekir; yani asıl veriye ulaşmadan önce birkaç tur atarsın. Bu yüzden birkaç yüz girişlik minik bir tablo, gigabaytlarca RAM’i olan bir makinede performansı belirleyebilir.

Bir ipucu daha vereyim: TLB kapasitesini artırmanın en etkili yolu tabloyu büyütmek değil, sayfaları büyütmektir. Tek bir TLB girişi 4 KiB yerine 2 MiB’lık bir alanı kapsarsa, aynı tabloyla beş yüz kat geniş bir bellek alanını çevirebilirsin. Bu mekanizmanın nasıl çalıştığını ve neden her zaman iyi bir fikir olmadığını 13. bölümde ayrıntısıyla göreceğiz.

Bir yana: Neden Cache Line 64 Byte?

Cache line boyutu tarihsel olarak evrimleşmiştir. Pentium 4 döneminde 32 byte kullanılırken, modern x86-64 işlemcilerde standart 64 byte’tır. Bazı ARM tasarımlarında ise 128 byte denenmektedir.

Daha büyük cache line = daha fazla spatial locality avantajı (komşu veriler tek seferde gelir). Ancak erişilen verinin komşuları gerçekten kullanılmayacaksa daha büyük line, daha fazla gereksiz byte taşımak ve bant genişliği harcamak demektir. 64 byte, modern x86 sistemlerde bu denge için yaygın bir sweet spot’tur; başka mimarilerde farklı line boyutları görülebilir.

Kendi Sisteminde Cache’leri Keşfet

Buraya kadar anlattığım katmanlar soyut sayılar olarak kalmasın. Okuduğun her şeyin karşılığı kendi makinende duruyor ve birkaç komutla görebilirsin. Linux kullanıyorsan doğrudan aşağıdakileri dene; çıktıdaki rakamları bölümün başındaki tabloyla yan yana koy.

Cache line boyutu:

getconf LEVEL1_DCACHE_LINESIZE

Tüm cache hiyerarşisi:

lscpu | grep -i cache

Beklenen çıktıya örnek:

L1d cache:                       384 KiB (8 instances)
L1i cache:                       256 KiB (8 instances)
L2 cache:                        4 MiB (8 instances)
L3 cache:                        32 MiB (2 instances)

Bu çıktıyı okurken iki şey kafa karıştırır, ikisini de açalım.

“(8 instances)” ne demek? Sekiz ayrı çekirdekte sekiz ayrı kopya var demek — ve gösterilen boyut bu kopyaların toplamı. Yani çekirdek başına L1d aslında 384 / 8 = 48 KiB. Bölümün başında “L1 genelde 32-128 KiB” derken kastettiğim de çekirdek başına düşen bu değerdi. L3’ün “(2 instances)” çıkması ise cache’in iki ayrı dilime bölündüğü anlamına gelir; AMD işlemcilerde her çekirdek kümesinin (CCX) kendi L3 dilimi olur ve bir çekirdeğin komşu dilime erişmesi kendi dilimine erişmesinden yavaştır.

Neden L1d ve L1i ayrı? Çünkü CPU aynı saat çevriminde hem sıradaki talimatı okumak hem de veri üzerinde çalışmak ister. İkisi tek bir cache’i paylaşsaydı her çevrimde birbirlerini beklerlerdi. Ayırmak, ikisine aynı anda erişebilmeyi sağlar. 2. bölümdeki von Neumann tartışmasını hatırlıyorsan: mimari düzeyde tek bir bellek var, ama çekirdeğin içinde iş ikiye bölünüyor. Modified Harvard denen şey tam olarak budur ve lscpu çıktısında gözünle gördüğün kanıtı bu iki satır.

Tek satırda cache bilgisi:

cat /proc/cpuinfo | grep -m1 cache

Özet

Peki, ne öğrendik?

• Cache tek tek bayt değil, hizalı cache line’lar hâlinde çalışır; x86-64’te bir satır 64 bayttır.
• Bir adres cache içinde aranırken offset, index ve tag olmak üzere üçe bölünür.
• Associativity, bir adresin cache’te kaç farklı yere düşebileceğini söyler. Arttıkça çakışma azalır, karşılaştırma maliyeti artar.
• Locality, cache’in çalışmasının tek sebebidir: programlar yakın zamanda ve yakın adreste kullandıklarına tekrar dokunur.
• Yazmalar genelde write-back yapılır; bu yüzden cache’teki değer ile RAM’deki değer bir süre farklı olabilir.
• Çok çekirdekte tutarlılığı MESI gibi protokoller sağlar ve bu tutarlılık cache line düzeyinde çalışır. False sharing tam olarak buradan doğar.
• Cache miss CPU pipeline’ını duraksatır; bunu 8. bölümde işleyeceğiz. TLB’nin arkasındaki sayfa tablolarını ise 14. bölümde açacağız.

Bellek tarafını burada kapatıyoruz. Sırada kitabın en başında sorduğumuz o ilk soru var:

CPU birden fazla process’i takip etmiyorsa ve sadece talimat üstüne talimat yürütüyorsa, neden tek bir programın içinde sıkışıp kalmıyor? Birden fazla program aynı anda nasıl çalışabiliyor?

Cevap şu: saatler. Coldplay’in Clocks’uyla aynı cevap — ama burada kastettiğim timer’lar. Bu şakayı yapmayacağıma dair kimseye söz vermemiştim.