İşlemci Önbelleği

Önceki iki ders iki gerçeği yan yana koydu: işlemci yalnızca yazmaçlar üzerinde işlem yapar, ve ana bellek erişimi yüzlerce saat çevrimi sürebilir. Bu iki gerçek doğrudan birleştirilseydi, işlemci zamanının neredeyse tamamını beklemekle geçirirdi.

Bu dersin konusu, aradaki farkı kapatan katmandır: önbellek (cache). Önbellek donanım tarafından yönetilir ve programa görünmez; ancak programın davranışı, önbelleğin işe yarayıp yaramayacağını belirler. Bu yüzden görünmez bir katman olmasına karşın öğrenilmesi gerekir.

Yerellik İlkesi

Önbelleğin çalışması tek bir gözleme dayanır: programların bellek erişimleri rastgele değildir. İki eğilim gözlenir.

Zamansal yerellik (temporal locality): Kısa süre önce erişilen bir adrese yeniden erişilme olasılığı yüksektir. Bir döngü sayacı, döngü boyunca her turda okunur ve yazılır.

Uzamsal yerellik (spatial locality): Bir adrese erişildiyse, komşu adreslere de erişilme olasılığı yüksektir. Bir diziyi baştan sona gezen döngü, ardışık adresleri sırayla okur; komutlar da bellekte ardışık durduğundan komut akışı aynı eğilimi gösterir.

Önbellek, bu iki eğilimden yararlanır: kısa süre önce kullanılan veriyi saklar (zamansal) ve bir veri istendiğinde komşularını da getirir (uzamsal).

Önbellek Satırı

Önbellek ile ana bellek arasındaki alışveriş tek bayt üzerinden yapılmaz. Transfer birimi önbellek satırıdır (cache line); genişliği donanıma göre değişir ve tipik olarak onlarca bayttır.

Bunun doğrudan bir sonucu vardır: bir bayt istendiğinde, o baytın bulunduğu satırın tamamı getirilir. Dört baytlık bir tam sayıyı okumak ile aynı satırda bulunan on altı tam sayıyı okumak, bellek trafiği açısından aynı maliyettedir.

Erişim iki sonuçtan birini verir:

• İsabet (hit): İstenen veri önbellektedir; erişim hızlıdır.
• Iska (miss): Veri önbellekte değildir; bir alt katmandan satır getirilir ve işlemci bu süre boyunca bekler.

Önbellek doluyken yeni bir satır getirmek, var olan bir satırı çıkarmayı gerektirir. Hangi satırın çıkarılacağına tahliye politikası karar verir; en yaygın yaklaşım, en uzun süredir kullanılmayan satırı çıkarmaktır. Aynı ilke, önbellekleme kavramının geçtiği her katmanda — veritabanı önbelleği, içerik dağıtım ağı, tarayıcı önbelleği — tekrar karşınıza çıkar.

Katmanlar

Önbellek tek bir birim değildir; hızdan kapasiteye doğru kademelenmiş katmanlardan oluşur. Çekirdeğe en yakın katman en küçük ve en hızlıdır; uzaklaştıkça kapasite büyür, gecikme artar. Alt katmanlar genellikle çekirdekler arasında paylaşılır.

Bu kademelenme, önceki derste verilen bellek hiyerarşisinin ortasını doldurur. Sayısal değerler donanıma göre değişir; değişmeyen ilke, her katmanın bir üsttekinin daha yavaş ve daha büyük bir kopyası olmasıdır.

Ayrı bir ayrım daha vardır: komutlar ve veriler çoğu tasarımda çekirdeğe en yakın düzeyde ayrı önbelleklerde tutulur. Komut akışı ile veri akışının erişim örüntüleri farklıdır ve birbirlerinin satırlarını atmamaları istenir.

Erişim Düzeninin Sonucu

Yerellik ilkesi, aynı işi yapan iki programın başarımının neden farklı olabileceğini açıklar. İki boyutlu bir tabloyu toplamayı düşünün. Tablo bellekte satır satır saklanır: bir satırın elemanları ardışık adreslerdedir, alt satır ise bir satır uzunluğu ötededir.

Satır boyunca gezinme, ardışık adresleri okur. İlk erişim ıska verir, satırın tamamını getirir; sonraki erişimler isabet eder.

Sütun boyunca gezinme, her adımda bir satır uzunluğu atlar. Getirilen önbellek satırının yalnızca bir elemanı kullanılır, gerisi kullanılmadan tahliye edilebilir.

İki döngü aynı sayıda toplama yapar; fark, bellek trafiğindedir. Bu fark, süre ölçmeden de hesaplanabilir: getirilen önbellek satırı sayısı sayılır.

SATIR_BAYT = 64          # örnek bir önbellek satırı genişliği
ELEMAN_BAYT = 8          # bir tam sayının genişliği
N = 1024                 # N x N tablo

eleman_sayisi = SATIR_BAYT // ELEMAN_BAYT      # bir satıra sığan eleman: 8

# Satır boyunca: getirilen her satırın sekiz elemanı da kullanılır.
satir_boyunca = N * N // eleman_sayisi

# Sütun boyunca: ardışık iki erişim arası uzaklık N * ELEMAN_BAYT bayt.
# Tablo önbelleğe sığmıyorsa, getirilen satırın yalnızca bir elemanı kullanılır.
sutun_boyunca = N * N

print(satir_boyunca, sutun_boyunca)            # 131072 1048576
print(sutun_boyunca / satir_boyunca)           # 8.0

Aynı sayıda toplama için taşınan veri miktarı sekiz kat farklıdır ve bu çarpan, bir önbellek satırına sığan eleman sayısıdır. Elemanlar daraldıkça çarpan büyür: dört baytlık elemanlarda on altı, tek baytlık elemanlarda altmış dörttür.

Bu hesap, gerçek süreyi doğrudan vermez. Ölçülen fark; önden getirme (prefetching), adres çevirisi ve bellek denetleyicisinin davranışıyla birlikte belirlenir. Yorumlanan dillerde ise eleman başına düşen yorumlama maliyeti, farkın büyük bölümünü örter; bu yüzden yerellik etkisi en açık biçimde, elemanları bitişik saklayan ve eleman başına yorumlama maliyeti taşımayan dillerde ölçülür.

Yazma Politikaları

Buraya kadar okuma anlatıldı. Yazma, ek bir karar gerektirir: değiştirilen veri alt katmana ne zaman aktarılacaktır?

İçinden yazma (write-through) politikasında her yazma, hem önbelleğe hem alt katmana işlenir. Katmanlar her an tutarlıdır; bedeli, her yazmanın yavaş katmana erişmesidir.

Arkadan yazma (write-back) politikasında yazma yalnızca önbelleğe yapılır; satır kirli olarak işaretlenir ve alt katmana ancak tahliye edilirken yazılır. Aynı satıra arka arkaya yapılan yazmalar tek bir aktarıma iner; buna karşılık, alt katman bir süre eski değeri taşır.

Aynı iki seçenek, önbelleğin geçtiği her katmanda karşınıza çıkar; veritabanı ve uygulama önbelleklerinde de aynı adlarla anılır.

Çok çekirdekli sistemlerde ek bir sorun doğar: aynı bellek satırının kopyası birden çok çekirdeğin önbelleğinde bulunabilir. Bir çekirdek kopyasını değiştirdiğinde diğerlerinin elindeki kopya geçersizleşir. Donanım, bu tutarlılığı çekirdekler arası bir protokolle sürdürür. Görünen sonucu şudur: farklı çekirdeklerde çalışan iş parçacıklarının aynı önbellek satırına sık yazması, mantıksal olarak paylaşılan bir veri olmasa bile başarımı düşürür.

Programa Yansıyan Sonuçlar

Önbellek doğrudan denetlenemez, ancak veri yerleşimi ve erişim sırası seçilebilir. Önbellek dostu kodun ortak nitelikleri şunlardır:

• Bitişik yerleşim. Elemanları bitişik saklayan diziler, her elemanı ayrı yerde duran ve işaretçilerle bağlanan yapılara göre daha az ıska üretir. Bu, veri yapıları kursunda bağlı liste ile dizi karşılaştırmasının başarım boyutudur.
• Erişim sırası ile yerleşim sırasının uyumu. Veri hangi sırayla okunacaksa, o sırayla yerleştirilir.
• Sıcak veriyi küçük tutmak. Döngünün her turunda dokunulan veri kümesi bir önbellek katmanına sığıyorsa, döngü boyunca yalnızca isabet alınır.
• Gereksiz alanları taşımamak. Yapı içinde kullanılmayan alanlar, satır başına düşen yararlı veri miktarını azaltır.

Bu ilkelerin hiçbiri erken eniyileme gerektirmez. Anlamlı olan sıra şudur: önce doğru çalışan ve okunabilir kod, sonra ölçüm, sonra ölçümün gösterdiği yerde bu ilkelerin uygulanması.

Özet

• Önbellek, işlemci ile ana bellek arasındaki hız farkını kapatan, donanım tarafından yönetilen bir ara katmandır.
• Çalışmasının dayanağı yerellik ilkesidir: zamansal yerellik kısa süre önce kullanılanın tekrar kullanılacağını, uzamsal yerellik komşu adreslere erişileceğini öngörür.
• Transfer birimi önbellek satırıdır; bir bayt istendiğinde satırın tamamı getirilir.
• İsabet hızlı, ıska pahalıdır; önbellek dolduğunda tahliye politikası hangi satırın çıkarılacağına karar verir.
• Aynı işi yapan iki döngü, erişim düzenlerine göre farklı sürelerde çalışır; ardışık erişim sıçramalı erişimden hızlıdır.
• Önbellek doğrudan denetlenemez; denetlenebilen, veri yerleşimi ve erişim sırasıdır.

Sonraki Adım

Buraya kadar işlemci, komutları kendi belirlediği sırayla yürüten kapalı bir sistem gibi ele alındı. Oysa dış dünya — klavye, disk, ağ arayüzü, zamanlayıcı — işlemcinin dikkatini talep eder. Sonraki ders, bu talebin nasıl iletildiğini ve akışın nasıl kesildiğini ele alacak.