Son günlerde klasik algoritma optimizasyonlarının ötesine geçerek donanıma daha yakın, özellikle CPU cache mimarilerine duyarlı algoritmalar üzerine çalışıyorum.

Bilindiği gibi modern işlemcilerde multi-level cache (L1, L2, L3) yapıları, algoritmaların teorik zaman karmaşıklığından bağımsız olarak ciddi performans farkları yaratabiliyor. Bu yüzden, klasik O(n log n) algoritmalar bazen O altı gibi davranışlar sergileyebiliyor.

Bu bağlamda iki farklı yapı üzerine test yaptım:
  1. Cache-aware quicksort: Burada, cache line boyutlarını (örneğin 64 byte) göz önünde bulundurarak recursive bölünme derinliğini bu yapıya göre sınırladım. Sonuç olarak branch misprediction ve cache miss oranlarında %30’a varan iyileşme elde ettim.
  2. Cache-oblivious matrix multiply (divide and conquer yaklaşımıyla): Tile/block yapısı kullanmadan, sadece bellek hiyerarşisinin doğal erişim desenlerine dayanan bir model oluşturdum. Bu yapı, özellikle inclusive cache mimarilerinde oldukça başarılı sonuçlar verdi.

Benchmark’larda ilginç olan şu oldu: Cache-aware algoritma küçük veri setlerinde açıkça daha hızlı, fakat veri seti büyüdükçe cache-oblivious yaklaşım daha stabil ve ölçeklenebilir sonuçlar verdi. Özellikle valgrind ile cachegrind çıktıları bunu net ortaya koydu.

Bu çalışmalarımı roofline model çerçevesinde yorumlamaya başladım. Önümüzdeki hafta L2 eviction ve LRU heuristics’e dayalı yeni bir varyasyon denemeyi planlıyorum.

Benzer konularla uğraşan varsa, özellikle kendi yazdığı cache-aware algoritmaları varsa, fikir alışverişine açığım.