Günümüzde büyük veri kümeleri üzerinde hızlı arama yapmak, özellikle biyoinformatik gibi alanlarda kritik öneme sahiptir. Statik veriler (örneğin bir referans genomu) üzerinde yapılan milyonlarca sorgunun saniyede işlenmesi gerekebilir. Klasik ikili arama algoritması, O(log n) karmaşıklığına rağmen modern CPU'larda bellek erişim gecikmeleri ve dal tahmin hataları nedeniyle potansiyelinin altında kalır. Bu makalede, Algorithmica'da tanıtılan S+ ağaçları (statik B-ağaçları) kullanılarak ikili aramaya kıyasla 40 kata kadar daha yüksek verim elde eden bir uygulama geliştiriyoruz.
Problem tanımı oldukça basittir: Sıralanmış 32 bitlik işaretsiz tamsayılar listesi (vals) verildiğinde, bir sorgu değeri q için listede q'dan büyük veya eşit en küçük elemanı (veya yoksa u32::MAX) döndüren bir veri yapısı tasarlıyoruz. Performans ölçütümüz ise saniye başına cevaplanan bağımsız sorgu sayısı, yani iş hacmidir. Genellikle bu, sorgu başına düşen süre (ns/query) cinsinden ifade edilir. Tüm kaynak kod, benchmark ve grafik çizim kodlarıyla birlikte GitHub'da mevcuttur.
İkili arama temel alınarak başlanan çalışmada, ilk adım Eytzinger düzenine geçmek olmuştur. Bu düzen, ikili arama ağacının düğümlerini bellekte özel bir sıraya dizer: kök 1. indekste, onun çocukları 2 ve 3. indekslerde, torunları 4-7. indekslerde vb. Bu sayede arama sırasında ardışık adımlarda erişilen veriler birbirine yakın bellek bölgelerinde yer alır. Böylece, bir sonraki önbellek satırını (cache line) henüz hangi yöne gideceğimizi bilmeden önceden getirebiliriz (prefetch). Örneğin, 4 seviye ilerideki düğümleri içeren önbellek satırını prefetch ederek bellek gecikmelerini büyük ölçüde gizleyebiliriz.
Eytzinger düzenindeki prefetch optimizasyonu önemli kazançlar sağlasa da, asıl büyük sıçrama S+ ağaçları ile gelir. S+ ağaçları, her düğümde birden fazla anahtar (örneğin 16, 32 veya 64) tutarak ağaç derinliğini azaltır. Bu, hem daha az bellek erişimi hem de SIMD (AVX2) talimatlarıyla bir düğüm içindeki anahtarları paralel olarak karşılaştırma imkanı sunar. Düğüm boyutu, CPU'nun önbellek satırı boyutuna (genelde 64 bayt) ve SIMD register genişliğine göre ayarlanır. 16 anahtarlı bir düğüm (64 bayt) tam bir önbellek satırına sığar ve AVX2 ile tek seferde 8 anahtar karşılaştırılabilir. Bu, dal tahmin hatalarını da azaltır çünkü döngü sayısı sabittir.
Optimizasyonun bir sonraki aşaması, toplu sorgu (batching) tekniğidir. Tek tek sorgular yerine, birden fazla sorguyu aynı anda işleyerek dal tahmin hatalarını ve bellek gecikmelerini daha etkin bir şekilde gizleyebiliriz. Örneğin, 4 veya 8 sorguyu paralel olarak ağaçta gezdiririz. Her adımda, tüm sorgular için gerekli verileri prefetch ederiz. Bu yöntem, özellikle sorgu sayısı arttıkça bellek bant genişliğini daha verimli kullanır. Benchmark sonuçları, toplu sorgu ile Eytzinger düzenine kıyasla 4 kata kadar, ikili aramaya kıyasla ise 40 kata kadar hız artışı sağlandığını göstermektedir.
Detaylar ve Etkileri
Sonuç olarak, statik S+ ağaçları, özellikle büyük ve statik veri kümeleri üzerinde yüksek iş hacmi gerektiren uygulamalar için son derece etkili bir çözümdür. Bu çalışma, biyoinformatikte sık kullanılan sonek dizisi (suffix array) aramalarının hızlandırılmasına yönelik bir adımdır. Gelecek çalışmalar, AVX-512 gibi daha geniş SIMD talimatlarını kullanarak daha büyük düğüm boyutlarına geçmeyi veya farklı veri tipleri için uyarlamalar yapmayı içerebilir. Kod ve benchmark detaylarına GitHub reposundan ulaşabilirsiniz.
Kaynak: curiouscoding.nl
