Bölüm 9 · Yazılımın içi · Ders 40

Önbellek (LRU)

Harita karolarını yakında tutmak: biraz bellek, çok hız

Veri. Depoda dolaşan robot, haritayı 8×5 = 40 karoya bölünmüş olarak sunucudan çekiyor. Her adımda bulunduğu karoyu istiyor: sunucudan gelmesi 80 ms, robotun kendi belleğinden okunması 2 ms. Robot 120 adım yürüyor ve çoğu zaman yakın karolara geri dönüyor. Bellekte yalnız birkaç karoya yer var: hangisini tutmalı?

robotun yolu: 120 karo isteği, 40 karoluk haritaönbellek 4 karo · isabet 2 ms, ıska 80 ms

1 / 130

Önbellek boyu (karo) 4

onbellek.pypython

import numpy as np
from collections import OrderedDict # sıralı sözlük
rng = np.random.default_rng(3)
x, y, req = 3, 2, [] # haritanın ortası
moves = [(0, 0), (1, 0), (-1, 0), (0, 1), (0, -1)] # dur ya da komşuya geç
for _ in range(120): # robot 120 adım yürür
dx, dy = moves[rng.integers(5)]
x, y = min(max(x + dx, 0), 7), min(max(y + dy, 0), 4) # 8×5 karo
req.append((x, y)) # karoyu iste
def lru(size):
cache, hits = OrderedDict(), 0 # baş: en eski, son: en yeni
for t in req:
if t in cache:
hits += 1 # isabet: 2 ms
cache.move_to_end(t) # en yeni yap
else:
cache[t] = "karo" # ıska: sunucudan 80 ms
if len(cache) > size:
cache.popitem(last=False) # en eskiyi at
return hits / len(req)
for s in (1, 2, 4, 8, 12):
h = lru(s) # isabet oranı
print(s, round(h, 2), round(2*h + 80*(1-h), 1), "ms") # ortalama gecikme

Sahnedeki her sayı, aynı algoritmanın tarayıcında yapılan gerçek çalıştırmasından gelir (sabit tohum, her seferinde aynı sonuç). Python kodunu kendi bilgisayarında çalıştırırsan rastgele başlangıçlar farklı olacağı için sayılar biraz değişebilir.

Veri seti

Tüm veri setleri →

Bu dersin kodu verisini kendi içinde üretir; indirilecek dosya yok. Kodu yine de aşağıda tarayıcında çalıştırabilirsin.

Kodu tarayıcıda çalıştırPython · NumPy · matplotlib · Pyodide

Python ve NumPy bu sayfada, tarayıcında çalışır (Pyodide). Kodu değiştirip yeniden çalıştırabilirsin; dersin veri setleri çalışma klasöründe hazır. Kod matplotlib kullanırsa grafikler çıktının altında görünür, yazdığı dosyalar (ör. egitim_gecmisi.csv) indirilebilir.

onbellek.pypython

import numpy as np
from collections import OrderedDict           # sıralı sözlük
rng = np.random.default_rng(3)
x, y, req = 3, 2, []                          # haritanın ortası
moves = [(0, 0), (1, 0), (-1, 0), (0, 1), (0, -1)]  # dur ya da komşuya geç
for _ in range(120):                          # robot 120 adım yürür
    dx, dy = moves[rng.integers(5)]
    x, y = min(max(x + dx, 0), 7), min(max(y + dy, 0), 4)  # 8×5 karo
    req.append((x, y))                        # karoyu iste
def lru(size):
    cache, hits = OrderedDict(), 0            # baş: en eski, son: en yeni
    for t in req:
        if t in cache:
            hits += 1                         # isabet: 2 ms
            cache.move_to_end(t)              # en yeni yap
        else:
            cache[t] = "karo"                 # ıska: sunucudan 80 ms
            if len(cache) > size:
                cache.popitem(last=False)     # en eskiyi at
    return hits / len(req)
for s in (1, 2, 4, 8, 12):
    h = lru(s)                                # isabet oranı
    print(s, round(h, 2), round(2*h + 80*(1-h), 1), "ms")  # ortalama gecikme

Kendi CSV’ni yükle

Çıktı

Çıktı burada görünecek.

Nasıl çalışır

İstenen karo önbellekteyse isabet: 2 ms, karo listenin başına (en yeni) taşınır.
Yoksa ıska: 80 ms bekleyip sunucudan çekilir, listenin başına eklenir.
Yer dolduysa listenin sonundaki, en uzun süredir kullanılmayan (LRU) karo atılır. Yakın geçmişte kullanılan, yakın gelecekte yine kullanılır: zamansal yerellik.
LRU’da büyük önbellek, küçüğün tuttuğu her şeyi de tutar; bu yüzden boyut arttıkça isabet oranı hiç düşmez. Ama robotun hiç görmediği karolar için ilk istek her zaman ıskadır.
Şunu dene: önbellek boyunu 1’den 4’e çıkar; ortalama gecikme ~50 ms’den ~30 ms’ye iner. 8’den sonra eğri düzleşir: geri kalan ıskalar robotun ilk kez gördüğü karolar.

Neden önemli

İşlemcinin L1/L2 önbellekleri, web tarayıcıları, CDN'ler, veritabanı tamponları ve robotlarda harita karoları, çıkarım sonuçları ve dönüşüm ağaçları hep aynı fikirle çalışır. Bedeli bayatlıktır: sunucudaki harita güncellenirse önbellekteki kopya eskir; bu yüzden gerçek sistemler ayrıca bir yaşam süresi (TTL) koyar.

ESOF 323, 11. hafta: robotlarda derin öğrenme →