← perfect_hashing/
[28] 2022 #70F

Perfect Hash Function Generation on the GPU with RecSplit

Lehmann, Sanders, Walzer

RecSplit ile GPU Üzerinde Mükemmel Hash Fonksiyonu Oluşturma

Yüksek Lisans Tezi

Dominik Bez

Enformatik Bölümü'nde
Teorik Enformatik Enstitüsü

Değerlendiriciler:
Prof. Dr. Peter Sanders
Jun.-Prof. Dr. Thomas Bläsius

Danışmanlar:
Dr. Florian Kurpicz
M.Sc. Hans-Peter Lehmann

Yazarlık Beyanı

Ich versichere wahrheitsgemäß, die Arbeit selbstständig verfasst, alle benutzten Hilfsmittel vollständig und genau angegeben und alles kenntlich gemacht zu haben, was aus Arbeiten anderer unverändert oder mit Abänderungen entnommen wurde sowie die Satzung des KIT zur Sicherung guter wissenschaftlicher Praxis in der jeweils gültigen Fassung beachtet zu haben.

Özet

Minimal mükemmel hash fonksiyonları (MPHF'ler), keyfi anahtarlardan oluşan statik bir S kümesini ilk |S| doğal sayıya bire bir eşleyerek dönüştürür; yani her hash değeri tam olarak bir kez kullanılır. Birçok uygulamada yararlıdırlar; örneğin, garanti edilen sabit erişim süresine sahip hash tabloları gerçekleştirmek için kullanılabilirler. MPHF'ler oldukça kompakt olabilir — anahtar başına 2 bitten daha az kullanım mümkündür. Öte yandan MPHF'ler, verilen bir anahtarın S içinde olup olmadığını belirleyemez.

Günümüzde pratikte en yüksek alan verimliliğine sahip MPHF yöntemi RecSplit'tir. Bu yöntem, bellek kullanımı, oluşturma süresi ve sorgu süresi arasında çeşitli dengeler sunar. Örneğin RecSplit, anahtar başına 1.56 bit kullanan bir MPHF'yi anahtar başına 2 ms'den daha kısa sürede oluşturabilir. Ancak bu hız büyük girdiler için yeterli değildir.

Bu tezde, oluşturma süresini iyileştirmek amacıyla çok iş parçacıklılığı (multithreading), SIMD ve GPU gücünü kullanan yeni RecSplit gerçekleştirimleri sunulmaktadır. Yeni bijection rotation tekniğimizle birlikte, RecSplit'in özgün sıralı gerçekleştirimine kıyasla 8 çekirdekli bir CPU üzerindeki SIMD gerçekleştirimimizde 333 kata kadar, GPU gerçekleştirimimizde ise 1873 kata kadar hızlanma elde ediyoruz. Bu sayede anahtar başına 1.56 bit kullanan bir MPHF'yi anahtar başına 1.5 µs'den daha kısa sürede oluşturabiliyoruz.

Almanca Özet

Minimal mükemmel hash fonksiyonları (MPHF'ler), keyfi anahtarlardan oluşan statik bir S kümesini ilk |S| doğal sayıya bire bir eşleyerek dönüştürür; yani her hash değeri tam olarak bir kez kullanılır. Birçok uygulamada yararlıdırlar; örneğin, garanti edilen sabit erişim süresine sahip hash tablolarını gerçekleştirmek için kullanılabilirler. MPHF'ler oldukça kompakt olabilir — anahtar başına 2 bitten daha az kullanım mümkündür.

Öte yandan MPHF'ler, verilen bir anahtarın S kümesine ait olup olmadığını belirleyemez. Günümüzde RecSplit en bellek verimli MPHF yöntemidir. RecSplit, bellek tüketimi, oluşturma süresi ve sorgu süresi arasında çeşitli dengeler sunar. Örneğin RecSplit, anahtar başına 1.56 bit kullanan bir MPHF'yi anahtar başına 2 ms'den daha kısa sürede oluşturabilir. Ancak bu büyük girdiler için çok yavaştır.

Bu çalışma, oluşturma süresini iyileştirmek amacıyla çok iş parçacıklılığı, SIMD ve GPU'ların işlem gücünü kullanan yeni RecSplit gerçekleştirimleri sunmaktadır. Yeni bijection-rotation yöntemimizle birlikte, özgün sıralı RecSplit gerçekleştirimine kıyasla 8 çekirdekli bir CPU üzerindeki SIMD gerçekleştirimimizde 333 kata kadar, GPU gerçekleştirimimizde ise 1873 kata kadar hızlanma elde ediyoruz. Bu sayede anahtar başına 1.56 bit kullanan MPHF'leri anahtar başına 1.5 µs'den daha kısa sürede oluşturabiliyoruz.

Teşekkür

Danışmanlarım Dr. Florian Kurpicz ve M.Sc. Hans-Peter Lehmann'a bu ilginç konuyu sağlamaları ve tezime ayrıntılı geri bildirim vermeleri için teşekkür ederim. Ayrıca kendilerine ve Prof. Dr. Peter Sanders'a verimli fikirler önerdikleri için teşekkür ederim.

Bu tezi değerlendirdikleri için Prof. Dr. Peter Sanders ve Jun.-Prof. Dr. Thomas Bläsius'a teşekkür ederim. Son olarak Lucas Alber, Julius Häcker, Anne Herrmann ve Wendy Yi'ye tezimi gözden geçirip dil denetimi yaptıkları için teşekkür ederim.

Bu çalışma, Baden-Württemberg Bilim, Araştırma ve Sanat Bakanlığı ile Almanya Baden-Württemberg Eyaleti Üniversiteleri tarafından finanse edilen bwUniCluster hesaplama kaynağı üzerinde, bwHPC çerçeve programı kapsamında gerçekleştirilmiştir.

İçindekiler

1. Giriş

2. Ön Bilgiler

3. İlgili Çalışmalar

4. RecSplit

5. Gerçekleştirim

6. Değerlendirme

7. Sonuç

1. Giriş

Keyfi anahtarlardan oluşan m elemanlı bir S kümesi verildiğinde, minimal mükemmel hash fonksiyonu (MPHF)

h: S → {0, 1, ..., m − 1}

S içindeki her anahtarı 0 ile m − 1 arasındaki farklı bir sayıya eşler; yani h bire bir bir fonksiyondur. Bu fonksiyon, hash değerleri arasında çakışma oluşamayacağı için bir hash tablosunu basit bir dizi olarak gerçekleştirmek amacıyla kullanılabilir. MPHF h, S kullanılarak oluşturulan statik bir veri yapısıdır.

Minimal mükemmel hash fonksiyonlarının temel özelliği, oldukça yüksek alan verimliliği sağlayabilmeleridir. Nitekim pratik MPHF'ler anahtar başına yalnızca 1.56 bit gerektirirken teorik alt sınır log2(e) ≈ 1.44 bit/anahtardır.

Bu avantajın bir bedeli vardır. MPHF h, verilen bir x anahtarının S içinde olup olmadığını kontrol etmek için kullanılamaz; çünkü bunun için S kümesinin saklanması gerekir. Eğer x ∉ S ise yalnızca rastgele bir sayı döndürür. Bu nedenle MPHF'ler yalnızca x ∈ S olup olmadığı zaten biliniyorsa veya x ∉ S olsa bile h fonksiyonunun kullanılmasının sorun olmadığı durumlarda uygulanabilir.

İkinci durum, yaklaşık üyelik sorgusu (AMQ) filtresi (örneğin Bloom filtresi) kullanılarak S kümesine ait olmayan anahtarların çoğunu elemek suretiyle iyileştirilebilir. AMQ filtreleri de oldukça yüksek alan verimliliği sağlayabilir.

MPHF'lerin tipik bir uygulaması bellek hiyerarşisinden yararlanmaktır. S anahtarlarından oluşan büyük bir statik hash tablosunu ana belleğe sığmayacak şekilde saklamak istediğinizi varsayalım. Bu durum örneğin S kümesindeki anahtarların uzun karakter dizileri olması halinde ortaya çıkabilir. Ana belleğe sığabilen bir MPHF h oluşturularak hash tablosu disk üzerinde basit bir A dizisi olarak saklanabilir.

Dizinin her i indeksinde, h(x) = i hash değerine sahip S kümesindeki x anahtarı ve hash tablosunda saklanması gereken ilgili bilgi birlikte tutulur.

Keyfi bir y anahtarı verildiğinde, diskten ilgili bilgi A[j] yüklenmeden önce h fonksiyonu kullanılarak A içindeki doğru j indeksi hesaplanabilir. Ardından y'nin A[j] konumunda saklanan anahtarla eşit olup olmadığı kontrol edilir. Eşit değilse y ∉ S'tir.

Bir AMQ filtresi kullanılarak S içinde olmayan anahtarlar için yapılan disk erişimlerinin çoğu önlenebilir. MPHF kullanımı bellek hiyerarşisinin diğer seviyelerinde de yararlı olabilir; burada h daha küçük fakat daha hızlı bir belleğe sığarken A daha büyük bir bellekte bulunur. Örneğin h önbelleğe sığabilir ve A ana bellekte olabilir; ya da h yerel diskte bulunurken A yalnızca ağ üzerinden erişilebilen bir konumda olabilir.

MPHF üzerinde karmaşık bir AMQ filtresi kullanmak gerekli değildir. Aslında MPHF'nin kendisi ek bir dizi ile birlikte bir AMQ filtresi olarak kullanılabilir. y anahtarının hash değeri j, S içindeki tüm anahtarların fingerprint değerlerini içeren B dizisine indeks olarak kullanılabilir. Fingerprint, rastgele bir hash fonksiyonu tarafından üretilen ω bitlik bir sözcüktür.

B[j] konumunda saklanan fingerprint, y'nin fingerprint değerinden farklıysa y anahtarı S içinde değildir. Yanlış pozitif oranı ε, iki fingerprint'in eşleşmesine rağmen y ∉ S olması olasılığıdır.

Her fingerprint ω bit içerir ve kullanılan hash fonksiyonunun rastgele bir fonksiyondan ayırt edilemez olduğu varsayılırsa ϵ = 2^−ω olur. Bu değer teorik alt sınıra eşittir [36].

Sonuç olarak MPHF'ler statik AMQ filtreleri gerçekleştirmek için kullanılabilir ve eğer bir MPHF zaten gerekiyorsa bu yaklaşım ω ile ϵ arasındaki denge açısından en iyi sonucu sağlar.

Yukarıda belirtilen amaçları verimli şekilde gerçekleştirmek için genellikle MPHF'nin sabit zamanda sorgulanabilmesi ve doğrusal zamanda oluşturulabilmesi gerekir. Bu gereksinimler çoğu zaman beklenen çalışma sürelerini kapsayacak şekilde gevşetilir. Bellek gereksinimi, sorgu süresi ve oluşturma süresi farklı minimal mükemmel hash fonksiyonu tekniklerini değerlendirmek ve karşılaştırmak için temel ölçütlerdir.

Günümüzde pratikte en yüksek alan verimliliğine sahip MPHF yöntemi RecSplit'tir [46]. Anahtar başına 1.56 bit seviyesine ulaşabilirken sorgu ve oluşturma süreleri açısından diğer tekniklerle rekabet edebilir durumdadır. RecSplit bu kadar alan verimli bir MPHF'yi oluşturmak için anahtar başına 2 milisaniyeden daha az süre gerektirir. Ancak bu, 100 milyon anahtar için yaklaşık 50 saate karşılık gelir; dolayısıyla böyle bir alan verimliliği hedeflendiğinde büyük girdiler için RecSplit'in pratikliği tartışmalıdır.

Neyse ki RecSplit oluşturma süreci oldukça kolay paralelleştirilebilen bir problemdir. Anahtarlar önce birbirinden bağımsız olarak işlenebilen bucket'lara ayrılır. Bu durum paralelleştirme için uygun bir ortam sağlar. Her bucket için bir ağaç oluşturulur. Bu ağaçtaki her düğüm için, düğümdeki anahtarlar üzerinde belirli bir özelliği sağlayan bir hash fonksiyonu bulmak amacıyla çeşitli normal hash fonksiyonları denenir. Bu hash fonksiyonlarının denenmesi single instruction, multiple data (SIMD) kullanılarak hızlandırılabilir.

Buna rağmen RecSplit'in halka açık bir paralel gerçekleştirmesi henüz mevcut değildir. Bu tez, modern paralel donanımların işlem gücünden tam olarak yararlanmak için RecSplit oluşturma sürecini gerçekleştirmeye odaklanmaktadır. Bu amaçla iki yeni gerçekleştirim geliştirilmiştir.

İlki, Central Processing Unit (CPU) üzerinde oluşturma sürecini hızlandırmak için çok iş parçacıklılığı ve SIMD kullanır. Buna SIMD gerçekleştirmesi veya SIMDRecSplit adı verilir. İkinci gerçekleştirim Graphics Processing Unit (GPU) işlem gücünü kullanır. Bu yaklaşım böyle bir donanımın bulunmasını gerektirir ancak oluşturma sürecini önemli ölçüde hızlandırabilir. İkinci gerçekleştirim GPU gerçekleştirmesi veya GPURecSplit olarak adlandırılır. Her iki yaklaşım da Vigna tarafından sağlanan Sux kütüphanesindeki özgün gerçekleştirim ile karşılaştırılmaktadır [13].

Bir sonraki bölümde GPU'ların çalışma prensipleri de dahil olmak üzere gerekli temel bilgiler sunulmaktadır. Bölüm 3 önemli mükemmel hash fonksiyonu tekniklerini tanıtır. Ancak bu teknikleri anlamak bu tezin anlaşılması için zorunlu değildir. Bu tezde paralelleştirilen MPHF tekniği olan RecSplit, Bölüm 4'te ayrıntılı şekilde açıklanır. Bölüm 5'te yeni RecSplit gerçekleştirimlerimizin uygulama ayrıntıları anlatılır. Elde edilen sonuçlar Bölüm 6'da deneysel olarak incelenir. Son olarak bu tez Bölüm 7'de özetlenir ve gelecekte yapılabilecek çalışmalar için bazı öneriler sunulur.

1.1 Katkı

1.2 Yapı

Bu bölümde tezin geri kalanını anlamak için gerekli temeller sunulmaktadır.

Bu kısım, tez boyunca kullanılan kavramları ve gösterimleri tanıtır.

Bu tezde random-access machine (word RAM) modeli kullanılmaktadır [52]. Böyle bir makine w bitlik sözcükler üzerinde çalışır. Bu sözcükler üzerinde yapılan aritmetik ve bit düzeyindeki işlemler sabit zamanda gerçekleştirilebilir.

0 dahil ve n hariç olmak üzere doğal sayıların kümesi için kullanılan gösterim:

[n] = {0, ..., n − 1}.

a değerini bir üst tam sayıya yuvarlama ⌈a⌉ ile, aşağı yuvarlama ise ⌊a⌋ ile gösterilir. ← operatörü bir değişkene değer atamak için kullanılır; yani

a ← a + b

ifadesi a + b değerini a değişkenine atar. Toplama işleminde a'nın eski değeri kullanılır ve ardından üzerine yazılır.

Taşma (overflow) durumunda değerler 2^w moduna göre indirgenir; burada w bir sözcükteki bit sayısıdır. Yani yalnızca en az anlamlı w bit saklanır, daha yüksek anlamlı bitler atılır (değer "sararak" devam eder).

Bir a sözcüğünün bitleri n bit sola şu sözdizimiyle kaydırılabilir:

a << n

ve n bit sağa şu şekilde kaydırılabilir:

a >> n

Boş kalan konumlar 0 bitleri ile doldurulur. Eğer taşma oluşmazsa n bit sola kaydırma işlemi 2^n ile çarpmaya eşdeğerdir. Benzer şekilde

a >> n

ifadesi ⌊a / 2^n⌋ ile eşdeğerdir.

Sözcüklerin bitlerini değiştiren çeşitli bit düzeyi işlemler vardır. Bit düzeyindeki OR operatörü |, yalnızca işlenenlerden en az birinin aynı konumda 1 biti varsa o konumdaki biti 1 yapar. Örneğin:

3 | 6 = 011₂ | 110₂ = 111₂ = 7

Burada alt indis 2 sayının ikili tabanda olduğunu gösterir. Benzer şekilde ⊕ bit düzeyinde exclusive OR (XOR) işlemini, & ise bit düzeyinde AND işlemini hesaplar.

2. Ön Bilgiler

Bir sözcüğün en az anlamlı m biti rotₘⁿ döndürme operatörü ile sola doğru n bit döndürülebilir. a'nın alt m biti dışındaki bitlerin sıfır olduğu varsayılırsa şu şekilde uygulanabilir:

rotₘⁿ(a) = ((a << n) | (a >> (m − n))) & ((1 << m) − 1).

popcount işlemi bir sözcükteki 1 bitlerinin sayısını hesaplar. Örneğin

25 = 11001₂

değerinin popcount sonucu 3'tür. x86 komut kümesinin SSE4.2 uzantısı, 64 bit değerler için bir popcount komutu içerir ve çoğu modern x86 CPU'da mevcuttur [21, 24].

Bir sözcüğün sondaki sıfırlarının sayısı, en az anlamlı 1 bitinin indeksine eşdeğerdir. a değerinin sondaki sıfır sayısını ρ(a) ile gösteririz. x86 komut kümesi bu değeri sabit zamanda hesaplayan komutlar içerir [21].

En düşük anlamlı 1-bitini sıfıra ayarlama işlemine clear_rho denir. x86'nın bir komut kümesi genişlemesi olan Bit Manipulation Instruction Set 1 (BMI1), bu işlemi doğrudan gerçekleştiren bir komut içerir [21]. Alternatif olarak şu şekilde uygulanabilir:

clear_rho(a) = a & (a − 1).

Bir sözcüğün n. en düşük anlamlı 1-bitini bulma işlemine ρₙ denir. ρ₀ = ρ olduğuna dikkat edin. Bu işlem, ρ çağrılmadan önce clear_rho işleminin n kez çağrılmasıyla uygulanabilir.

Ancak bu işlem yalnızca üç komut kullanılarak da uygulanabilir: bir bit kaydırma işlemi, Bit Manipulation Instruction Set 2 (BMI2) içindeki parallel bits deposit instruction (PDEP) [21] ve ρ [46]. Bu tezin bağlamında bu uygulamanın ayrıntılarını anlamak gerekli değildir. Bu nedenle burada daha fazla açıklanmamaktadır.

İki algoritmanın performansını karşılaştırmak için kullanılan önemli bir kavrama speedup denir. T(A), A algoritmasının ihtiyaç duyduğu süreyi; T(B) ise aynı görev için B algoritmasının ihtiyaç duyduğu süreyi göstersin. B'nin A'ya göre hızlanması S(A, B) şu şekilde hesaplanır:

S(A, B) = T(A) / T(B).

Bu, A algoritmasının B'ye göre S(A, B) kat daha uzun süreye ihtiyaç duyduğu anlamına gelir. Speedup değeri 1'den küçük de olabilir; bu durumda A daha hızlıdır. Speedup özellikle paralel algoritmalar için kullanılır; yani belirli sayıda iş parçacığına sahip paralel bir algoritmanın ardışık bir algoritma ile karşılaştırılması için.

Birçok kod parçası skaler değerler üzerinde çalışır. Örneğin, bir kod parçası iki tam sayı a ve b'yi toplayabilir. Bazen aynı işlemin bir değer kümesi üzerinde yapılması gerekir; örneğin iki dizinin değerlerini noktasal olarak toplamak. Bu basit bir döngü ile gerçekleştirilebilir. Ancak ilgili komutların donanım tarafından her eleman için çözümlenmesi gerekir ve aynı anda yalnızca bir eleman işlenir.

Bu durum single instruction, multiple data (SIMD) kullanılarak iyileştirilebilir [48]. Tek bir komut kullanılarak aynı işlem birden fazla elemana uygulanır. Bu, iki skaler değeri toplamak yerine her biri birden fazla tam sayı içeren iki vektörün toplanması anlamına gelir. Böylece çözümlenmesi gereken komut sayısı azalır ve donanımın tüm vektörü paralel olarak işlemesine olanak tanınır. SIMD kullanımı birçok durumda yüksek speedup değerleri sağlayabilir; örneğin iki dizinin toplanmasında.

SIMD yalnızca toplama gibi basit işlemlerle sınırlı değildir. Vektördeki elemanların yerlerini değiştirme, bitişik olmayan verileri yükleme ve saklama (gather ve scatter), iki vektörün içeriklerini harmanlama veya diğer gelişmiş işlemleri gerçekleştirme gibi işlemler de sağlayabilir. Tam işlem kümesi, SIMD modelinin somut uygulamasına bağlıdır.

Bir SIMD vektörü içindeki tek bir elemana lane deriz. Bir lane, belirli sayıda bite sahip bir sözcüktür. Örneğin bir vektör, her biri 16 bit olan 32 lane içerebilir; yani vektör toplamda 512 bit içerir. İşlem verimini en üst düzeye çıkarmak için mümkün olduğunca çok lane kullanılması tavsiye edilir. Bu, daha fazla lane kullanılmasına izin veriyorsa her bir lane'in boyutunu küçültmeyi de içerebilir.

SIMD kullanma eylemine vectorization da denir. Belirli bir kod parçasını vektörleştirmek için çeşitli yöntemler vardır [25]:

2.2 SIMD

2.2.1 Advanced Vector Extensions (AVX)

Advanced Vector Extensions (AVX) [14], birçok Intel ve AMD işlemcisi tarafından kullanılan x86 komut kümesi mimarisine yapılan komut kümesi genişletmeleridir. Bu genişletmeler, sürüme bağlı olarak 256 veya 512 bit içeren vektörler için birçok komut sağlar.

AVX'in birkaç sürümü vardır ve her sürüm önceki sürüme yeni komutlar ekler veya vektör boyutunu artırır. Çoğu kayan nokta komutu için 32-bit ve 64-bit lane kullanılabilir. Birçok tam sayı komutu ise 8, 16, 32 ve 64 bit boyutlarında lane kullanımına izin verir.

AVX'in ilk sürümü tam sayı komutları içermez ve bu nedenle SIMD uygulamamız açısından ilgili değildir. Bunun yerine SIMD uygulamamız AVX2 ve AVX-512 [15] destekleyen CPU'lar için optimize edilmiştir.

AVX2, 256-bit vektörler üzerinde birçok tam sayı işlemine izin verir. AVX-512 bu işlemleri 512-bit vektörlere genişletir ve birçok yeni komut ekler; örneğin belirli lane'leri maskelemek için maskelerin kullanılmasına olanak tanır. Ancak AVX-512 destekleyen her CPU tüm komutları desteklemez. AVX-512 birçok küçük alt kümeye ayrılmıştır ve her işlemci bunların yalnızca bir kısmını destekleyebilir.

Uygulamamız için faydalı olan bu alt kümelerden biri AVX512VPOPCNTDQ'dur; bu uzantı 32 ve 64 bit boyutunda lane içeren 512-bit vektörlerde popcount işlemini sağlar. Bu uzantı olmadan popcount hiçbir bit boyutundaki vektör için mevcut değildir.

Vector Class Library (VCL), esas olarak Fog tarafından yazılmış bir C++ kütüphanesidir [26, 27]. SIMD vektörlerini nesneler olarak kapsüller; bu da intrinsics'e kıyasla sözdizimini basitleştirir çünkü her işlem için vektör ve lane boyutunu belirtme gerekliliğini ortadan kaldırır. Ayrıca toplama ve XOR gibi birçok yaygın işlem için infix gösterimi sağlar. Vector Class Library özellikle eleman başına dallanma, belirli bir özelliği sağlayan ilk lane'i bulma veya bir lookup table içinde değer arama gibi ileri düzey amaçlar için faydalıdır.

Intrinsics yazmaya kıyasla belki de en etkileyici özellik taşınabilirliktir. Vector Class Library 128, 256 ve 512 bit boyutunda vektörler içerir ve bunlar üzerinde işlemleri tanımlar. Belirli boyutta vektörleri içeren bir komut kümesi mevcut değilse, VCL bunu daha küçük vektörler kullanarak taklit eder. Bu nedenlerle SIMD uygulamamız için Vector Class Library kullanıyoruz.

En azından VCL, x86'nın SSE2 instruction set extension'ını gerektirir ve AVX-512 dahil olmak üzere daha yeni x86 genişletmelerinden yararlanabilir. Ne yazık ki ARM gibi diğer komut kümeleri desteklenmemektedir.

Vector Class Library, yerel vektör boyutunu sorgulama imkânı sunmaz; yani AVX2 için 256 bit ve AVX-512 için 512 bit. Bu işlevi derleme zamanında biz gerçekleştirdik. Bu bizim durumumuzda faydalıdır çünkü işlem verimini en üst düzeye çıkarmak için mümkün olduğunca büyük vektörler kullanmak istiyoruz ancak aynı zamanda mümkün olduğunca az ek yükle.

Belirli bir özelliği sağlayan bir hash fonksiyonu bulunana kadar hash fonksiyonlarını SIMD biçiminde denememiz gerekir. Bu durum, AVX-512 mevcut değilse VCL'nin taklidine güvenerek her zaman 512-bit vektörler kullanmamızı caydırır; çünkü uygun bir hash fonksiyonu ilk yarıda zaten bulunmuş olabilir ancak taklit işlemi ikinci yarıyı işlemeye devam eder.

Bu nedenle AVX-512 mevcutsa 512-bit vektörler, aksi halde 256-bit vektörler kullanırız. AVX2 bile mevcut değilse VCL'nin taklidine güveniriz.

Her komut Vector Class Library tarafından desteklenmez. Bu özellikle yalnızca daha yeni komut kümesi genişletmelerinde bulunan ve eski genişletmeler üzerinde taklit edilmesi zor olan komutlar için geçerlidir. Neyse ki VCL vektör nesneleri, intrinsics tarafından kullanılan intrinsic vektör türlerine hem örtük hem de açık şekilde ve hiçbir ek yük olmadan dönüştürülebilir. Bu, intrinsics'in doğrudan VCL nesneleri üzerinde kullanılmasına olanak tanır.

Bu tekniği, AVX512VPOPCNTDQ mevcutsa popcount kullanmak ve en azından AVX2 mevcutsa her lane için farklı olan ve ikinci bir vektör tarafından sağlanan bit sayısıyla yapılan left bit shift işlemini kullanmak için değerlendiriyoruz.

Graphics Processing Units (GPUs) başlangıçta bilgisayar grafiği uygulamaları için tasarlanmış özel işlemcilerdir. Bilgisayar grafiğinde birçok işlem çok sayıda eleman üzerinde yapılmak zorundadır; örneğin bir görüntünün her pikseli veya bir çokgen ağının her köşesi için. Bu durum SIMD kullanılarak paralelleştirmeye olanak tanır.

Son on yıllarda GPU'lar yüksek derecede paralelleştirilebilir görevler için genel amaçlı işlemcilere dönüşmüştür. Özel programlama modelleri kullanılarak programlanabilirler.

2.2.2 Vector Class Library

Programlama dilleri ve Application Programming Interfaces (API'ler). Bu API'lerden biri CUDA'dır [71, 3]. Nvidia tarafından geliştirilmiştir ve Nvidia GPU'larını programlamak için kullanılabilir. GPURecSplit'i uygulamak için CUDA kullanıyoruz ve bu tez boyunca CUDA terminolojisini kullanıyoruz. Bu bölümdeki bilgiler CUDA C++ Programming Guide [3] ve Nvidia Ampere GA102 GPU Architecture teknik dokümanına [17] dayanmaktadır.

Bu bölümde tipik modern bir GPU'nun yapısı açıklanmaktadır. Kesin yapı farklı modeller arasında değişebilir. Modern bir GPU'nun boyutlarını kavratmak için Nvidia RTX 3090 [17] için birçok ölçüte ait kesin sayılar verilmiştir. Bu GPU, Bölüm 6'daki deneylerde kullanılmaktadır.

Bir GPU birkaç streaming multiprocessor (SM) içerir (RTX 3090: 82). Her SM, hesaplamaları gerçekleştirmek için birçok arithmetic logic unit (ALU) içerir. RTX 3090, SM başına 32-bit kayan nokta matematiği için 128 ALU'ya sahiptir, ancak SM başına 32-bit tam sayı matematiği için yalnızca 64 ALU bulunur. Bu, bir CPU ile karşılaştırıldığında çok büyük sayıda ALU anlamına gelir.

2.3 GPUs

2.3.1 Bir GPU'nun Yapısı

Single Instruction, Multiple Threads (SIMT)

GPU'lar SIMD makineleridir. Daha doğrusu, single instruction, multiple threads (SIMT) makineleridir. Temel fark thread kavramıdır.

SIMD terminolojisinde bir thread, birden fazla lane içeren vektörler üzerinde çalışan SIMD işlemlerini içerebilen bir işlem akışıdır. SIMT terminolojisinde ise her SIMD lane için tek bir thread vardır ve tüm vektörden sorumlu "üst" bir thread bulunmaz.

SIMD ile aynı avantajları sağlamak için birkaç thread (RTX 3090: 32) kilit adımda çalışır; yani aynı anda aynı komutu yürütürler. Bu tür bir thread kümesine warp denir.

Masking, bir warp içindeki farklı thread'lerin farklı komutlar yürütmesini sağlamak için kullanılır; örneğin if ifadesi gibi kontrol akışlarını uygulamak için. Masking, warp içindeki her thread'in her komutu yürütmesi anlamına gelir; ancak yürütmemesi gereken komutlar için aktif değildir (maskelenmiştir). Örneğin if koşulu yanlış olduğunda.

Bir warp içindeki bazı thread'lerin aktif olmamasına divergence denir. Divergence mümkün olduğunca kaçınılmalıdır çünkü performansı düşürür. Bir if-else durumunda, warp içindeki en az bir thread için koşul doğru ve başka bir thread için yanlışsa, warp içindeki her thread her iki durumu da yürütmek zorunda kalır ve yanlış durumda aktif değildir. Daha da kötüsü, döngülerde warp içindeki her thread, en fazla yineleme sayısına sahip thread kadar yineleme yapmak zorundadır.

Hardware Multithreading

Bir GPU'da çok sayıda ALU bulunduğundan (RTX 3090: 5248 adet 32-bit tam sayı ALU), bunları kullanabilmek için çok sayıda thread gereklidir. Ancak ALU sayısına eşit sayıda thread yeterli değildir. Her işlemin bir gecikmesi vardır ve bu özellikle bellek işlemleri için yüksektir. Bir thread son işleminin tamamlanmasını beklerken bir ALU'yu kullanamaz.

Modern CPU'lar gecikmeleri mümkün olduğunca azaltmaya çalışır ve düşük gecikmeli bellek, hızlı ve büyük önbellekler, derin pipeline'lar, superscalar teknikler, branch prediction ve out-of-order mimariler kullanarak tek bir thread'in ihtiyaç duyduğu süreyi optimize eder.

GPU'ların ise her thread'in tamamlanma süresini azaltması gerekmez. Amaçları işlem verimini en üst düzeye çıkarmaktır; yani tek bir thread'in ne kadar sürdüğünden bağımsız olarak belirli bir sürede mümkün olduğunca çok thread işlemektir.

GPU'lar gecikmeleri azaltmak yerine, bir warp önceki işlemin tamamlanmasını beklerken başka bir warp planlayarak gecikmeleri aşar. Buna latency hiding denir ve her SM'nin ALU sayısından çok daha fazla thread ile aşırı yüklenmiş olduğu anlamına gelir.

Farklı warp'lar arasında geçiş yapılırken ek yük oluşmasını önlemek için her SM çok sayıda 32-bit register içerir (RTX 3090: 65.536) ve her thread tamamlanana kadar değerlerini kendisine ayrılmış register'larda tutar. Her saat döngüsünde birkaç warp (RTX 3090: en fazla dört) planlanır. Bu warp'ların planlanmaya hazır olması gerekir; yani bir sonraki işlemleri tamamlanmamış bir önceki işleme bağlı olmamalıdır.

SM başına maksimum thread sayısı çok yüksek olabilir (RTX 3090: 1536; yani 32-bit kayan nokta ALU sayısının 12 katı). Yüksek bellek gecikmelerini gizlemek için thread sayısının ideal olarak bu sayıya ulaşması gerekir.

Bazı modern CPU'lar da çok iş parçacıklı ortamlarda her CPU çekirdeğinin kaynaklarını daha iyi kullanmak için benzer bir thread aşırı yükleme yaklaşımı kullanır. Buna genellikle simultaneous multithreading (SMT) veya hyper-threading denir. Çoğu durumda çekirdek başına yalnızca iki thread mümkündür.

Global Memory

Global memory, GPU üzerindeki en büyük ve en yavaş bellektir. Modern GPU'larda genellikle birkaç gigabayt büyüklüğündedir (RTX 3090: 24 GB). GPU'lar latency hiding kullandığından global memory gecikmeyi en aza indirmek için değil, bant genişliğini en üst düzeye çıkarmak için optimize edilmiştir (RTX 3090: 936 GB/s bant genişliği).

Bu durum, aynı anda GPU üzerinde yerleşik olabilen çok sayıdaki thread'e hizmet verebilmek için önemlidir (RTX 3090: 125.952).

Bu bant genişliğini mümkün olduğunca verimli kullanmak için her bellek erişimi coalesced olmalıdır.

32 iş parçacığından oluşan bir warp düşünün; her iş parçacığı global bellekte bir kelimeye erişmektedir. Donanım bu istekleri mümkün olan en az sayıda bellek işlemiyle karşılar; her işlem 32, 64 veya 128 bayt aktarır (kesin ayrıntılar modele bağlıdır). Bu aktarımlar hizalıdır; yani ilk baytın adresi işlem büyüklüğünün bir katıdır.

Performansı artırmak için, bellek erişim deseni mümkün olduğunca az sayıda işleme yol açmalı ve bu işlemler mümkün olduğunca az kullanılmayan bayt içermelidir.

Önbellekler

Bir GPU, sık erişilen veriler için gecikmeyi azaltmak ve bant genişliğini artırmak amacıyla birkaç önbellek içerebilir. Örneğin RTX 3090 toplamda 6144 KiB L2 önbelleğe sahiptir.

Ayrıca her SM üzerine yerleştirilmiş daha hızlı bir L1 önbelleğe de sahiptir; yani aynı SM üzerinde bulunan iş parçacıkları bir L1 önbelleği paylaşır. L1 önbelleğinin boyutu SM başına 128 KiB’ye kadar çıkabilir, ancak bunun bir kısmı paylaşılan bellek olarak kullanılabilir.

Paylaşılan Bellek

Paylaşılan bellek genellikle her SM üzerinde bulunan hızlı bir bellektir. Aynı SM üzerinde bulunan bir iş parçacığı grubu paylaşılan belleği elle yönetilen bir önbellek olarak veya veri paylaşmak için kullanabilir.

Ayrıca yavaş global belleği kullanmadan, bir indeksle erişilmesi gereken verileri (yani kayıtlarla mümkün olmayan bir dizi gibi) depolamak için de kullanılabilir.

Tipik bir kullanım, bir iş parçacığı grubunun üzerinde işlem yaptığı veriyi paylaşılan belleğe yüklemektir.

RTX 3090’da paylaşılan bellek, 128 KiB içeren birleşik bir veri önbelleğinin parçasıdır. Paylaşılan bellek miktarı otomatik olarak 0, 8, 16, 32, 64 veya 100 KiB olarak yapılandırılır ve kalan kısım L1 önbellek olarak kullanılır.

Bank Çakışmaları

Paylaşılan bellekteki veriler 32 bellek bankına bölünmüştür. Bu sayı diğer GPU modelleri için farklı olabilir, ancak son 10 yılın tüm CUDA cihazları için doğrudur.

Bellek banklara 32 bitlik parçalar halinde bölünür. Bu, ilk 32 bitin birinci bankta, sonraki 32 bitin ikinci bankta olduğu anlamına gelir ve bu şekilde devam eder. 33. 32 bitlik parça tekrar birinci banktadır.

Aynı warp içindeki n iş parçacığı aynı komutta aynı bank içindeki farklı kelimelere eriştiğinde n-yollu bank çakışması oluşur. Bu durumda erişimlerin seri hale getirilmesi gerekir ve tüm warp beklemek zorunda kalır; bu da performansı olumsuz etkiler.

Birden fazla iş parçacığı aynı kelimeyi okursa bu bir bank çakışması değildir; çünkü kelime farklı iş parçacıklarına yayınlanabilir.

Bank çakışmaları özellikle adımlı bellek erişimi (strided memory access) durumunda meydana gelir.

Paylaşılan bellekte satır satır depolanmış 32×32 boyutunda bir matris düşünün. 32 iş parçacığından oluşan bir warp içindeki her iş parçacığının bir satır üzerinde yineleme yaptığını varsayalım; birinci iş parçacığı birinci satır üzerinde, ikinci iş parçacığı ikinci satır üzerinde ve bu şekilde devam eder. Matrisin her elemanının 32 bitlik bir kelime olduğunu kabul edelim.

Her kelimenin boyutu bir banktaki kelime boyutuna eşit ve matrisin genişliği bank sayısına eşit olduğundan, matrisin her sütunu tek bir bankta depolanır. Her yinelemede her iş parçacığı aynı banktaki farklı bir kelimeye erişir — bu da 32-yollu bank çakışması oluşturur.

Strided adı, warp içindeki her iş parçacığının erişimlerinin belirli sayıda bayt aralıkla olması gerçeğinden gelir (burada 128); bu durum özellikle adım değeri iki kuvveti olduğunda bank çakışmalarına yol açabilir.

2.3.2 CUDA

CUDA, Nvidia GPU’larını genel amaçlı hesaplamalar için programlamak amacıyla kullanılan bir API’dir. GPU hesaplamalarını basitleştirmek için C++ gibi programlama dilleriyle entegrasyon sağlar. C++’ın CUDA uzantısına CUDA C++ adı verilir ve GPU uygulamamızda kullanılmaktadır.

CUDA’da GPU’ya device, GPU’yu içeren sisteme (CPU ve ana bellek) ise host denir.

Kernel’ler

Cihaz üzerinde çalıştırılabilen fonksiyonlara kernel adı verilir. Bunlar host tarafından normal C++ fonksiyonlarına benzer şekilde tanımlanır ve çağrılır.

arg0 ve arg1 fonksiyon argümanlarıyla kernelTest kernel’ini çağırmak için

kernelTest<<<b, t>>>(arg0, arg1)

sözdizimi kullanılabilir. Bu ifade, her iş parçacığı bloğunda t iş parçacığı bulunan b adet iş parçacığı bloğundan oluşan bir grid oluşturur. Grid içindeki her iş parçacığı kernelTest içindeki kodu yürütür. Grid’ler ve iş parçacığı blokları iki veya üç boyutlu da olabilir, ancak bu tez için bu durum önemli değildir.

Her iş parçacığının sabit olarak kullanabileceği bir kimliği vardır; örneğin bir dizi indeksi olarak. Bu sayede farklı iş parçacıkları farklı veriler üzerinde işlem yapabilir.

Bir iş parçacığı bloğu, iş parçacıklarının doğal sırasına göre warp’lara bölünür. Warp boyutunun 32 olduğunu varsayalım. İş parçacığı bloğunun ilk 32 iş parçacığı aynı warp’a, sonraki 32 iş parçacığı başka bir warp’a ve bu şekilde devam eder. Bir warp içinde kullanılmayan iş parçacıklarını önlemek için iş parçacığı bloğunun boyutu warp boyutunun bir katı olmalıdır.

Bir iş parçacığı bloğu içindeki iş parçacıklarının aynı SM üzerinde bulunması garanti edilir. Bu da onların işbirliği yapabilmesini sağlar. Özellikle senkronize olabilirler ve aynı paylaşılan belleğe erişebilirler.

Senkronizasyon, özel bir senkronizasyon fonksiyonunun çağrılmasıyla sağlanır. Bu fonksiyon çağrıldıktan sonra, çağıran iş parçacığı yalnızca kendi iş parçacığı bloğundaki tüm iş parçacıkları aynı fonksiyonu çağırdıktan sonra devam edebilir. Fonksiyon, senkronizasyondan önce paylaşılan veya global belleğe yapılan tüm bellek işlemlerinin senkronizasyondan sonra iş parçacığı bloğundaki tüm iş parçacıkları tarafından görülebilir olmasını garanti eder.

Bir kernel çağrısına aynı zamanda launch etmek de denir ve bu işlem asenkron bir işlemdir. Bu, host tarafından bir kernel başlatıldıktan sonra host’un kernel’in bitmesini beklemeden hemen kendi işine devam edebileceği anlamına gelir.

CUDA çalışma zamanı, kodu ve parametreleri cihaza aktarmakla ilgilenir. Kernel tarafından üretilen sonuçları kullanmak için host, kernel’in tamamlanmasını beklemek amacıyla cihazla senkronize olabilir.

Stream’ler

Kernel başlatmalarına benzer şekilde, host ve device belleği arasında veri aktarımı da asenkron olarak yapılabilir.

Cihazla senkronize edilmeden önce birden fazla kernel başlatıldığında ve veri aktarımı yapıldığında, tüm işlemler sıralı olarak gerçekleştirilir. Örneğin kernelA, kernelB’den önce başlatılırsa, kernelB yalnızca kernelA tamamen bittikten sonra çalışmaya başlar. Bu durum, kernelB sonuçları kernelA’ya bağlıysa doğruluğu sağlamak açısından önemlidir.

Ancak bazen farklı kernel’ler ve veri aktarımları tamamen bağımsızdır ve yeterli kaynak varsa aynı anda yürütülebilir. Bu durum CUDA’daki stream yapıları kullanılarak sağlanabilir.

Kullanıcı host üzerinde birden fazla stream oluşturabilir ve kernel’leri ile veri aktarımlarını bu stream’lere başlatabilir. Belirli bir stream içinde başlatılan işlemler sıralı olarak yürütülür, ancak farklı stream’lerdeki işlemler açık bir senkronizasyon yapılmadığı sürece keyfi biçimde üst üste gelebilir.

Asenkron Veri Kopyaları

Daha önce belirtildiği gibi, host ve device belleği arasında veri asenkron olarak aktarılabilir. Bir başka olası asenkron bellek kopyası ise memcpy_async kullanılarak global bellek ile paylaşılan bellek arasında yapılır.

Bir iş parçacığı bloğundaki iş parçacıkları, paylaşılan belleğe asenkron bir aktarım başlatmak için birlikte çalışabilir. Veri aktarılırken iş parçacıkları başka hesaplamalara devam edebilir. Yüklenen veriyi kullanmadan önce iş parçacıklarının özel bir senkronizasyon fonksiyonu kullanması gerekir. Bu fonksiyon veri hazır olana kadar engeller.

memcpy_async kullanımı veri aktarımının yüksek gecikmesini gizleyebilir ve global bellek ile paylaşılan bellek arasında ara birim olarak her iş parçacığı için fazladan bir kayıt kullanılmasını önler.

Compute Capability

Farklı GPU modelleri farklı CUDA compute capability seviyelerini destekler. Daha yeni modeller genellikle daha yüksek compute capability değerlerini destekler. Daha yüksek compute capability; daha gelişmiş fonksiyonlar, daha büyük önbellekler, daha fazla paylaşılan bellek, SM başına daha fazla kayıt vb. sağlayabilir.

Örneğin yukarıda açıklanan memcpy_async API’si yalnızca compute capability 8.0 veya daha yüksek olan cihazlarda donanım hızlandırmasına sahiptir. Diğer cihazlar bu davranışı, veriyi önce global bellekten kayıtlara yükleyip ardından paylaşılan belleğe yazarak taklit eder. İş parçacıkları tüm veri yüklenmeden devam edemez; yani bellek kopyası asenkron değildir.

RTX 3090’ın compute capability değeri 8.6’dır.

2.4 Prefix Sum

i ∈ [k] için tanımlı x_i sayı dizisi olsun. Dahilî prefix sum (\hat{X}_j) şu şekilde tanımlanır:

(\hat{X}j = \sum{i=0}^{j} x_i)

ve hariç tutulan prefix sum (X_j) şu şekilde tanımlanır:

(X_j = \sum_{i=0}^{j-1} x_i).

Bu, her j için önceki tüm elemanların toplamını (yani öneki) gösterdikleri anlamına gelir; burada x_j yalnızca dahilî prefix sum içinde yer alır. Ayrıca (X_0 = 0) olduğunu unutmayın.

Dahilî prefix sum, değerlerin sola kaydırılmasıyla hariç tutulan prefix sum’dan elde edilebilir; yani

(\hat{X}j = X{j+1}).

Prefix sum’lar algoritmalarda ve veri yapılarında sıkça kullanılır. MPHF yapımız için verinin bir kısmını prefix-sum biçiminde saklarız. Ayrımın önemsiz olduğu veya bağlamdan açıkça anlaşıldığı durumlarda prefix sum’ın dahilî mi yoksa hariç tutulan mı olduğunu belirtmeyiz.

2.5 Pareto Front

Görselleştirmelerimizde Pareto front kavramını kullanıyoruz. Bu kavramı anlamak için aşağıdaki tanımları inceleyelim.

A ⊂ ℝⁿ n-boyutlu Öklid uzayının bir alt kümesi ve x, y ∈ A olsun. Eğer x_i ≤ y_i tüm i ∈ [n] için sağlanıyorsa, x noktasının y noktasına baskın olduğu söylenir.

Eğer A içinde x’e baskın gelen başka bir nokta yoksa, x Pareto optimal olarak adlandırılır. Pareto front, A kümesindeki tüm Pareto-optimal noktaların kümesidir.

Pareto front’ların bir görselleştirmesi Şekil 2.1’de gösterilmektedir. Pareto front temelde aynı kümeye ait tüm noktaların sol-alt sınırıdır.

Pareto front’ları zaman ile bellek tüketimi gibi iki ölçüt arasındaki ödünleşimi göstermek için kullanırız.

3 İlgili Çalışmalar

Bu bölüm birkaç önemli minimal perfect hash fonksiyonunu açıklar. Amaç, bir sonraki bölümde açıklanan ve bu tezin odaklandığı MPHF olan RecSplit’i minimal perfect hash fonksiyonları alanındaki bağlamına yerleştirmek için genel bir bakış sağlamaktır. Ayrıca Bölüm 3.6’da MPHF’lerin bazı uygulamalarını da sunuyoruz.

Kendilerinden önceki bazı yazarlar gibi [68, 38, 35], Genuzio ve arkadaşları (GOV olarak anılır) [54] minimal perfect hash fonksiyonları oluşturmak için rastgele doğrusal sistemler kullanır. n, S kümesindeki anahtar sayısı, m = (1 + ε)n (ε > 0), F₂ iki elemanlı sonlu alan ve hθ : S → F₂^m bir hash fonksiyonu ailesinden (θ ile indekslenmiş) seçilmiş bir hash fonksiyonu olsun; her x ∈ S için hθ(x) tam olarak r adet 1 ve m − r adet 0 içerir. r sayısı sabittir.

S içindeki tüm anahtarların hash değerlerini H ∈ F₂^{n×m} matrisinin satırları olarak yazalım. Eğer ε yeterince büyükse, H yüksek olasılıkla satır basamak biçimine dönüştürülebilir; örneğin Gaussian elimination kullanılarak. Bu durumda her satıra (yani S içindeki her anahtara) benzersiz bir sütun (yani [m] içinde bir değer) atanabilir. Yapmamız gereken tek şey, hθ(x) içindeki r adet 1’den hangisinin doğru olduğunu saklamaktır. Eğer satır basamak biçimine dönüştürme başarısız olursa, farklı bir θ ile tekrar denenir.

Sabit zamanda erişime izin veren kompakt bir biçimde bu değerleri saklamak için benzer bir fikir kullanılır. Genel olarak statik fonksiyon f : S → [2^b]’yi saklamak için doğrusal denklem

HW = V

W için çözülür; burada H ∈ F₂^{n×m}, W ∈ F₂^{m×b} ve V ∈ F₂^{n×b}’dir. W matrisi doğrudan saklanır. f(x) hesaplanırken hθ(x), W’nin XOR ile birleştirilmesi gereken r satırını ortaya çıkarır ve böylece f(x) elde edilir.

Özetlemek gerekirse, H matrisi satır basamak biçimine dönüştürülerek her x anahtarı için j ∈ [r] sayısı hesaplanır; bu sayı hθ(x) içindeki hangi 1’in nihai hash değerinin konumunda olduğunu söyler. H ve V matrisleri (satır olarak j’yi içerir) bir doğrusal denklemde kullanılarak W hesaplanır ve saklanır. Daha sonra W kullanılarak j elde edilir ve bu da nihai hash değerini belirler.

Ancak nihai hash değeri [n] değil [m] aralığındadır. Bu nedenle yapı şu ana kadar bir perfect hash fonksiyonudur, ancak minimal perfect hash fonksiyonu değildir. Perfect hash fonksiyonunu minimal hale getirmek için bir sıralama (ranking) yapısı kullanılabilir. k ∈ [m] sayısı verildiğinde, bu yapı k’dan küçük olan ve gerçekten kullanılan hash değerlerinin sayısını sabit zamanda hesaplayabilir. Hesaplanan bu sayı daha sonra minimal perfect hash değeri olarak kullanılır.

3.1 GOV

Önceki çalışmalarda ε değeri doğrusal denklemin hipergraph peeling kullanılarak doğrusal zamanda çözülebileceği şekilde seçilir. Genuzio ve arkadaşları [54] daha küçük bir ε kullanır, ancak Gaussian elimination’ın çalışma süresinin O(n³) olması gerçeğiyle uğraşmak zorundadır.

İlk adım, giriş verisini daha küçük kümelere dağıtmak için bir hash fonksiyonu kullanmak ve MPHF’yi her küme üzerinde ayrı ayrı hesaplamaktır. Bu, çalışma süresini O(n)’e düşürür. Pratik performans açısından katkıları, tek bir kelime içinde SIMD’e benzer çalışan broadword programlama kullanmaları ve lazy Gaussian elimination adını verdikleri geliştirilmiş bir Gaussian elimination algoritmasıdır.

GOV MPHF anahtar başına 2.24 bit değerine ulaşabilir. RecSplit’in yazarlarının gösterdiği gibi [46], RecSplit daha küçük bir MPHF üretebilir ve sorgu süresi daha hızlıdır; bunun karşılığında oluşturma süresi daha uzundur. Bu tezde önerilen geliştirilmiş RecSplit uygulamaları kullanıldığında, RecSplit üç ana ölçütte de GOV’u geride bırakabilir.

3.2 CHD

Compressed hash-and-displace (CHD) algoritması [31], Pagh tarafından önerilen hash-and-displace yöntemine [73] dayanır. Öncelikle anahtarlar bir hash fonksiyonu kullanılarak beklenen boyutu küçük olan bucket’lara dağıtılır. Daha sonra bu bucket’lar boyutlarına göre azalan sırada ele alınır.

Her bucket için, mevcut bucket üzerinde injektif olan ve daha önceki bir bucket tarafından kullanılan bir hash değerini kullanmayan bir hash fonksiyonu bulmak amacıyla bir hash fonksiyonu ailesi üzerinde brute-force arama yapılır. Her bucket’ın hash fonksiyonu indeksi, Fredriksson ve Nikitin tarafından önerilen bir teknik kullanılarak sıkıştırılmış bir dizide saklanır [53].

Beklenen doğrusal oluşturma süresini garanti etmek için hash fonksiyonlarının değer kümesi [m] olarak seçilir; burada m = (1 + ε)n ve ε > 0’dır. Bu nedenle sonuç yalnızca bir perfect hash fonksiyonudur, MPHF değildir. GOV’ta olduğu gibi, MPHF elde etmek için bir ranking veri yapısı kullanılır.

CHD, pratik oluşturma süreleriyle anahtar başına yaklaşık 2 bit boyutunda MPHF’ler oluşturabilir ve teorik olarak anahtar başına 1.44 bit olan alt sınıra ulaşabilir. RecSplit’in yazarları [46], RecSplit’in oluşturma süresi, sorgu süresi ve bellek tüketimi gibi ana ölçütlerde CHD’ye büyük farklarla üstün olduğunu göstermiştir. Pratik açıdan bakıldığında CHD artık eski kabul edilebilir.

3.3 BBHash

BBHash’in yazarları [66], fingerprinting fikrinin [69] verimli ve paralel bir uygulamasını sunar. n₀ adet anahtar içeren S₀ kümesi verildiğinde, tüm anahtarlar üzerinde h₀ : S₀ → [n₀] hash fonksiyonu kullanılır ve yalnızca başka bir anahtarla aynı hash değerine sahip olan n₁ anahtar S₁ kümesine yerleştirilir. Geri kalan anahtarların işlemi tamamlanır. Tamamlanan her anahtar için n₀ bitlik bir bit dizisinde bir bit 1 yapılır.

S₁ içindeki anahtarlar daha sonra aynı şekilde h₁ : S₁ → [n₁] hash fonksiyonu ve n₁ bitlik bir bit dizisi kullanılarak işlenir. Bu işlem tüm anahtarlar tamamlanana kadar devam eder.

BBHash'i bir x anahtarıyla sorgulamak için, ilk bit dizisindeki biti bulmak amacıyla h₀(x) kullanılır. Eğer bu bit 1 ise, nihai hash değeri h₀(x) olur. Aksi takdirde ikinci bit dizisindeki biti bulmak için h₁(x) kullanılır ve eğer bu bit 1 ise, nihai hash değeri n₀ + h₁(x) olur ve bu şekilde devam eder.

GOV ve CHD'ye benzer şekilde, sonuç yalnızca bir mükemmel hash fonksiyonudur; minimal mükemmel hash fonksiyonu değildir. Bir MPHF elde etmek için bit dizileri birleştirilir ve üzerlerinde bir sıralama veri yapısı kullanılır.

BBHash'in diğer algoritmalara göre avantajı, oluşturma ve sorgulama işlemlerinin hızlı olmasıdır. Ancak BBHash anahtar başına 3 bitten fazla alana ihtiyaç duyar; bu, bu tezde incelenen diğer algoritmalara göre belirgin biçimde daha fazladır. Yazarlar, birçok kullanım senaryosunda anahtar başına 1.44 ile 3 bit arasındaki farkın, MPHF tarafından indekslenen gerçek verinin kapladığı alanla karşılaştırıldığında önemsiz olduğunu savunur.

RecSplit [46], BBHash'in en fazla alan verimliliği sağlayan yapılandırmasına kıyasla benzer oluşturma süresi ve daha yavaş sorgularla daha küçük bir MPHF elde edebilir. n < 10⁸ için RecSplit'in oluşturma süresi biraz daha yavaştır, ancak aksi durumda daha hızlıdır. Bu tezdeki iyileştirmelerle, özellikle Bölüm 6.2'de RecSplit sorgusundaki bir performans hatasının düzeltilmesiyle, doğru parametreler seçilerek RecSplit bu BBHash yapılandırmasına üstünlük sağlayabilir.

3.4 PTHash

PTHash [76], Bölüm 3.2'de bahsedilen hash-and-displace tekniğinin bir öncülü olarak görülebilecek FCH [50] temeline dayanır. Şimdiye kadar tartışılan diğer tekniklerde olduğu gibi anahtarlar önce bir hash fonksiyonu kullanılarak farklı bucket'lara dağıtılır; ancak bu kez dağılım uniform değildir. Özellikle, anahtarların yaklaşık %60'ı bucket'ların %30'una eşlenir.

Önce, sahte rastgele hash fonksiyonu hₛ kullanılarak hiçbir bucket'ta hash çakışması olmayacak şekilde bir s tohumu seçilir. Ardından bucket'lar azalan boyut sırasına göre işlenir. Her bir Bᵢ bucket'ı için, aşağıdaki konumun

(hₛ(x) ⊕ hₛ(kᵢ)) mod n

her x ∈ Bᵢ için henüz kullanılmamış olduğu bir kᵢ tam sayısı aranır. Bulunan kᵢ, i ile indekslenen bir dizide saklanır. Bu dizi, birkaç olası sıkıştırma şemasından biri (veya bucket'lar iki diziye bölündüğü için iki tanesi) kullanılarak sıkıştırılır [45, 47, 53]; böylece sorgu süresi ile alan tüketimi arasında farklı ödünleşimler elde edilir.

PTHash'in ilan edilen amacı hızlı sorgu süreleridir. Uygun bir sıkıştırma şeması kullanıldığında, kᵢ değerini bulmak için yalnızca tek bir bellek erişimi gerekir ve kalan işlemler basit hash fonksiyonu değerlendirmeleri ile aritmetik işlemlerdir.

Yazarlar PTHash'i [76] FCH [50], CHD [31], GOV [54], BBHash [66], RecSplit [46] ve hipergraph peeling [29] tabanlı bir teknik olan EMPHF ile karşılaştırmıştır. Karşılaştırılabilir sorgu sürelerine sahip tek teknik FCH'dir; ancak PTHash çok daha hızlı oluşturulabilir ve daha az alan gerektirecek şekilde yapılandırılabilir.

RecSplit ile karşılaştırıldığında PTHash anahtar başına 0.5 ile 2.5 bit daha fazla alan tüketir; ancak iki ila dört kat daha hızlı sorgular sunar ve daha kısa sürede oluşturulabilir. Daha yeni sonuçlara göre [75], PTHash üç temel ölçütün tamamında BBHash'e üstün görünmektedir. RecSplit anahtar başına daha az bit gerektirir ve bu tezdeki teknikler kullanılarak hızlandırılabilir; ancak PTHash'in sorgu sürelerine ulaşamaz.

3.5 GPU Teknikleri

Bildiğimiz kadarıyla, henüz GPU üzerinde bir MPHF oluşturan bir teknik bulunmamaktadır. GPU'lar ile mükemmel hashing'i birleştiren literatür ya MPHF'leri uygular ya da GPU üzerinde sorgulanacak bir MPHF sağlar.

Örneğin, perfect spatial hashing [63] iki veya üç boyutlu uzamsal veriler için bir mükemmel hashing tekniğidir. Birbirine yakın noktalar, bellek birleştirmesini mümkün kılmak ve böylece GPU'larda verimli sorgular elde etmek için tutarlı biçimde sorgulanır. Ancak oluşturma işlemi CPU üzerinde gerçekleştirilir.

Weaver ve Heule, SAT tabanlı bir MPHF oluşturma yöntemi önermiştir [81]; bu yöntem pratik oluşturma süresiyle birlikte anahtar başına yaklaşık 1.83 bit elde eder. Üç ana ölçütte RecSplit [46] tarafından geride bırakılır; ancak yine de teorik açıdan ilginçtir. SAT tabanlı yaklaşım GPU kullanabilen SAT çözücüleriyle birleştirilirse [72, 74], GPU kullanarak bir MPHF oluşturmak mümkün olabilir. Bununla birlikte, bu durumda bile RecSplit büyük olasılıkla SAT tabanlı yaklaşıma üstünlük sağlayacaktır.

3.6 Uygulamalar

Bölüm 1'de tartışıldığı gibi, MPHF'lerin tipik bir uygulaması bellek hiyerarşisinden yararlanarak verimli hash tabloları elde etmektir; burada MPHF, gerçek hash tablosuna kıyasla daha hızlı fakat daha küçük bir bellekte saklanır.

Yaklaşık üyelik sorgusu filtreleri de mükemmel hash fonksiyonları kullanılarak uygulanabilir. Bu, Graf ve Lemire tarafından pratikte değerlendirilmiştir [58].

Mükemmel hash fonksiyonlarının daha özel uygulamaları da vardır; örneğin:

4. RecSplit

Bu bölümde MPHF RecSplit [46] açıklanmaktadır.

RecSplit oluşturma sürecinin ilk adımı, girişteki her elemana başlangıç hash fonksiyonu uygulayarak aynı uzunlukta anahtarlar elde etmektir (bkz. Bölüm 4.1). Bu anahtarlar, bir bucket-atama fonksiyonu kullanılarak sabit beklenen boyuta sahip farklı bucket'lara dağıtılır (bkz. Bölüm 4.2).

Her bucket için bir bölme ağacı (splitting tree) oluşturulur (bkz. Bölüm 4.3). Bu ağacın her iç düğümü, anahtarları belirli bir şekilde alt düğümlere dağıtan bir hash fonksiyonu olan bir bölmeyi brute-force yöntemiyle arar. Her yaprak düğüm yalnızca birkaç anahtar içerir. Bir yaprağın m anahtarı üzerinde bir MPHF, anahtarları [m] aralığına birebir eşleyen bir eşleme brute-force aranarak hesaplanabilir.

Bir RecSplit örneği, bir elemanın hash değerini sorgulamak için önce başlangıç hash fonksiyonunu uygulayarak karşılık gelen x anahtarını elde eder. Bu anahtar üzerinde bucket-atama fonksiyonu kullanılarak doğru bucket bulunur. Ardından bu bucket'taki bölme ağacı, her düğümde saklanan bölmeler uygulanarak kökten başlayıp x'i içeren yaprağa kadar izlenir.

Her adımda, daha küçük hash değerine sahip anahtarların sayısı toplanır; yani daha küçük kimliklere sahip tüm bucket'lardaki anahtarların sayısı ve her bölme için x'i içeren alt düğümün solunda bulunan alt düğümlerdeki anahtarların sayısı. Bu birikmiş değer, yapraktaki bijeksiyonun x üzerine uygulanmasının sonucuna eklenir. Eğer eleman bu RecSplit örneğini oluşturmak için kullanılan kümede bulunuyorsa elde edilen değer o elemanın doğru hash değeridir.

RecSplit örneği için gerekli tüm veriler, hızlı erişime izin verirken aynı zamanda kompakt olacak şekilde saklanmalıdır. Bölmeler ve bijeksiyonlar Rice Bit Vector adı verilen bir bit vektöründe saklanır. Her bölme veya bijeksiyon bir Golomb–Rice kodu [57, 78, 79] olarak kodlanır (bkz. Bölüm 4.4).

Her bucket'taki anahtar sayıları bir prefix sum olarak saklanır. Bu, daha küçük kimliklere sahip bucket'lardaki anahtar sayısını sabit zamanda elde etmek için gereklidir. Son olarak, her bucket'ın bölme ağacının başladığı bit konumu saklanmalıdır; çünkü tüm bölme ağaçları Rice Bit Vector içinde ardışık biçimde saklanır.

Bu durumun, her bucket için bit sayılarının exclusive prefix sum'ı ile aynı olduğu unutulmamalıdır. Prefix-sum biçimindeki anahtar sayıları ile bit konumları birlikte özelleştirilmiş bir Elias–Fano gösterimi [45, 47, 46] içinde saklanır. RecSplit yazarları bu özelleştirmeye Double Elias–Fano adını verir; Bölüm 4.5'te açıklanır.

Girdi elemanları tamamen keyfi olabilir. Örneğin elemanlar uzun dizgiler olabilir ve uzunlukları birbirinden farklı olabilir. Daha kullanışlı değerler elde etmek için her elemana bir başlangıç hash fonksiyonu uygulanır. Ortaya çıkan anahtarlar sabit uzunluktadır. İyi istatistiksel özelliklere sahip bir başlangıç hash fonksiyonu kullanıldığında anahtarlar rastgele değerler gibi ele alınabilir. RecSplit'in Sux kütüphanesindeki [13] özgün uygulaması bu amaçla Jenkins tarafından geliştirilen SpookyHash V2'yi [60] kullanır. Bu fonksiyon hızlıdır ve iyi istatistiksel özelliklere sahiptir. Ortaya çıkan hash değerleri 128 bitten oluşur. Bu önemlidir; çünkü 5 milyar adet 64 bit rastgele değerden oluşan bir kümede çakışma olasılığı (iki eşit değer) yaklaşık %50'dir (birthday paradox [65]). Bu durum yalnızca 64 bit anahtarlar kullanıldığında büyük RecSplit örneklerinin oluşturulmasını imkânsız hâle getirir.

SpookyHash kriptografik bir hash fonksiyonu değildir. Bir saldırgan SpookyHash tarafından üretilen aynı hash değerine sahip iki farklı eleman bulabilir. Bu durumda RecSplit bir MPHF üretemez; çünkü iki anahtar ayırt edilemez. RecSplit'in özgün uygulamasında bu durum sonsuz bir döngüye yol açar. Bu, fiilen bir hizmet reddi saldırısıdır. Bu nedenle giriş elemanları güvenilmeyen bir kaynaktan geliyorsa SpookyHash uygun değildir (en azından önce çakışmalar kontrol edilmeden). Bir alternatif SipHash'tir [28]. Bu da kriptografik bir hash fonksiyonu değildir; ancak saldırganların hash çakışmaları bulmasını engellemek için gizli anahtarlar kullanır. Bu tezde saldırganlar dikkate alınmadığı için tehlikelerine rağmen SpookyHash kullanılmaktadır. Ancak RecSplit pratikte kullanılırken bunun akılda tutulması önemlidir.

Bu tezin geri kalanında yalnızca hash fonksiyonunun sonucu olan 128 bit anahtarlar ele alınacaktır; orijinal giriş elemanları değil. Anahtarlar rastgele elemanlar gibi değerlendirilir.

Kullanıcı beklenen bucket boyutu b değerini belirtir. n anahtar, bucket-atama fonksiyonuna göre ⌈n/b⌉ bucket içine dağıtılır. Bu fonksiyon 128 bit anahtarların en anlamlı 64 bitini kullanır. u, anahtar x'in en anlamlı 64 bitini temsil etsin. Anahtar x, aşağıdaki kimliğe sahip bucket'a atanır:

u · ⌈n/b⌉ >> 64

Burada 128 bit çarpma kullanılır. u rastgele kabul edildiğinden, bu işlem anahtarların bucket'lar arasında pratik olarak yanlılıksız dağıtılmasını sağlar. Kavramsal olarak bu bir tersleme (inversion) işlemidir [44] ve başka projelerde de kullanılmıştır [64]. 64 bit anahtar, ondalık kısmı olarak yorumlanarak 0 (dahil) ile 1 (hariç) arasında bir gerçek sayı olarak düşünülebilir. Bu değerin bucket sayısı ⌈n/b⌉ ile çarpılması ve aşağı yuvarlanması 0 (dahil) ile ⌈n/b⌉ (hariç) arasında bir sayı verir. Burada aşağı yuvarlama yerine ondalık kısım, sonuç 64 bit sağa kaydırılarak kaldırılır.

Beklenen bucket boyutu b, [1, 2000] aralığıyla sınırlandırılmıştır. Deneyler daha büyük b değerlerinin faydalı olmadığını göstermektedir [46]. Rastgele dağılım nedeniyle bucket boyutları farklı olabilir. Daha kesin olarak, belirli bir bucket'ın boyutu n ve p = 1/⌈n/b⌉ ≈ b/n parametrelerine sahip bir binom dağılımını izler. n → ∞ için bucket boyutu b parametreli Poisson dağılımına uyar [49]. b = 2000 ve çok sayıda anahtar için bile 3000 veya daha fazla anahtarın aynı bucket'a atanma olasılığı neredeyse sıfırdır. Bu durum özgün uygulamada [13] kabul edilmiştir ve burada geliştirilen uygulamalarda da aynı şekilde kabul edilir.

Oluşturmanın geri kalanında yalnızca 128 bit anahtarların en az anlamlı 64 biti kullanılır. Bu, her bucket içindeki 64 bit anahtarların birbirinden tamamen bağımsız olmasını sağlar.

4.2 Bucket Assignment

u · ⌈n/b⌉ >> 64

4.3 Splitting Trees

Her bucket için diğer bucket'lardan bağımsız bir MPHF oluşturulur. Bu MPHF, anahtarları giderek daha küçük kümelere ayıran bir bölme ağacıdır; ta ki bireysel kümeler üzerlerinde makul sürede bir bijeksiyon bulunabilecek kadar küçük olana kadar.

Yaprak boyutu ℓ, RecSplit'in kullanıcı tarafından sağlanan derleme zamanı parametresidir ve bir yapraktaki maksimum anahtar sayısını belirtir. Daha büyük yaprak boyutu, büyük yapraklarda bijeksiyon aramak pahalı olduğu için daha uzun oluşturma süresine yol açar. Öte yandan daha büyük yaprak boyutları, daha alan verimli bölme ağaçları ve daha hızlı sorgular sağlar. Bölme ağacı hızlı sorgulara olanak vermek için iyi tanımlanmış bir şekle sahiptir. Bu şekil yalnızca yaprak boyutu ve bucket'taki anahtar sayısı tarafından belirlenir.

Bir bölme ağacı birkaç seviyeden oluşur. Ağaç yukarıdan aşağıya doğru dolaşılır. En alt seviyeye leaf level denir ve bölme ağacının yapraklarından oluşur. Her yaprak, muhtemelen sonuncusu hariç, ℓ anahtar içerir. Yaprakların üzerindeki seviyeye first aggregation level denir. Bir iç düğümün sahip olduğu alt düğüm sayısına fanout denir.

Birinci toplulaştırma seviyesindeki maksimum fanout s₁ şu şekildedir:

s₁ = max{2, ⌈0.35ℓ + 0.5⌉}

Birinci toplulaştırma seviyesindeki her düğüm, muhtemelen sonuncusu hariç, s₁ fanout'a sahiptir ve özellikle s₁ℓ anahtar içerir. Fanout, bölmeyi bulmak için gereken beklenen iş miktarının tüm alt düğümlerdeki toplam iş miktarına yaklaşık eşit olacak şekilde optimize edilmiştir. Ayrıntılar için özgün makaleye bakınız [46]. Daha büyük fanout daha sığ bir ağaç anlamına gelir; dolayısıyla daha hızlı sorgular ve daha sonra göreceğimiz gibi (bkz. Bölüm 4.4.1) daha alan verimli bir MPHF sağlar.

Birinci toplulaştırma seviyesinin üzerinde second aggregation level bulunur ve benzer yapıdadır. Fanout s₂, beklenen iş miktarının tüm alt düğümlerin toplam iş miktarına eşit olacak şekilde yeniden optimize edilir. Sonuç:

Yine bu seviyedeki her düğüm, sonuncusu hariç, s₂ fanout'a sahiptir ve s₂ s₁ ℓ anahtar içerir.

Kalan tüm düğümler higher levels olarak kabul edilir. Daha üst seviyelerde fanout her zaman 2'dir. Toplulaştırma seviyelerinde olduğu gibi benzer bir optimizasyon yapılmaz; çünkü bu durum sorguda ek bir dallanma gerektirir. Bu pek değerli değildir; çünkü üst seviyelerdeki düğüm sayısı nispeten küçüktür ve daha fazla anahtar için daha fazla iş gerektiğinden fanout zaten alt seviyelere göre daha küçük olacaktır. Üst seviyelerdeki bir düğüm için sol alt düğümdeki anahtar sayısı s₂ s₁ ℓ'nin bir katı olarak seçilir.

Örnek olarak ℓ = 8 yaprak boyutu için 202 anahtarlı bir bölme ağacı Şekil 4.1'de gösterilmiştir.

Düğüm Seviyesi Belirleme

Bir düğümün karşılık gelen seviyesi, sahip olduğu anahtar sayısına göre aşağıdaki formülle hesaplanabilir. Bir ağaç her seviyeyi içermeyebilir. Örneğin ℓ veya daha az anahtar içeren bir bucket'ın bölme ağacı yalnızca tek bir düğümden oluşur.

Yaprak boyutu 2 ≤ ℓ ≤ 24 koşulunu sağlayacak şekilde sınırlandırılmıştır. Daha büyük yapraklar pratik amaçlar için fazla maliyetlidir; çünkü çok sayıda anahtar üzerinde bijeksiyon bulmak zordur. Bu aralığa sınırlama getirilmesi uygulama açısından avantajlar sağlar.

Bölmeler ve bijeksiyonlar için yapılan brute-force aramaları, rastgele ve birbirinden bağımsız hash fonksiyonlarından oluşan bir aile kullanır:

hᵢᵐ : [2⁶⁴] → [m], i ∈ {0, 1, 2, ...}

Gereksinimleri sağlayan ilk hash fonksiyonunun indeksi i (aynı zamanda hash fonksiyonu tanımlayıcısı olarak da adlandırılır) Rice Bit Vector içinde saklanır.

Şekil 4.1

Yaprak boyutu ℓ = 8 için 202 anahtarlı bölme ağacı. Her düğüm, içerdiği anahtar sayısıyla etiketlenmiştir. En alttaki kırmızı düğümler yapraklardır. İlk toplulaştırma seviyesi, üstteki mavi düğümlerden oluşur. Sonuncusu dışında bu seviyedeki tüm düğümlerin fan-out değeri 4’tür. Üstteki iki sarı düğüm ikinci toplulaştırma seviyesini oluşturur. Bunların fan-out değeri 3’tür. En üstteki iki beyaz düğüm daha yüksek seviyeleri oluşturur. Her zaman olduğu gibi, daha yüksek seviyelerde fan-out değeri 2’dir.

4.3.1 Analiz

Aşağıda RecSplit’i matematiksel olarak inceliyoruz. Tüm ayrıntılar ve türetimler gösterilmemiştir. Daha fazla bilgi için orijinal RecSplit makalesine [46] bakınız.

Bijections

X kümesi m anahtardan oluşsun ve h : X → [m] ifadesi X üzerinde rastgele bir hash fonksiyonu olsun. Bu biçimde m^m olası hash fonksiyonu vardır. Bu fonksiyonların her biri h olma açısından eşit olasılığa sahiptir. Bu fonksiyonlar arasından m! tanesi bijeksiyondur çünkü m elemanın m! permütasyonu vardır. Sonuç olarak h’nin bir bijeksiyon olma olasılığı

m! / m^m

şeklindedir.

Algoritma, rastgele hash fonksiyonları ailesinden bijeksiyon bulunana kadar hash fonksiyonlarını dener ve 0 indeksli hash fonksiyonundan başlar. İlk bijeksiyonun indeksi geometrik olarak dağılmıştır [49]. Bu nedenle denenmesi gereken hash fonksiyonlarının beklenen sayısı

m^m / m!

olur.

Stirling yaklaşımı kullanıldığında bu yaklaşık olarak

e^m / √(2πm)

şeklindedir.

Özellikle, yapılan iş miktarı anahtar sayısına göre üstel olarak artar.

Bir yan not olarak, bu durum n anahtarlı tüm girdi üzerinde tek bir bijeksiyon bulmanın (yani bucket boyutu ve yaprak boyutu her ikisi de n) MPHF’nin alan kullanımı açısından en iyi durum olduğunu gösterir. Saklanması gereken hash fonksiyonu tanımlayıcısı ortalama olarak yaklaşık

e^n / √(2πn)

düzeyindedir ve bunun saklanması için yaklaşık

log₂(e^n / √(2πn)) ≈ 1.44n

bit gerekir; yani anahtar başına 1.44 bit — teorik alt sınır [51]. Elbette bu pratik değildir. Oluşturma süresi üstel büyür ve sorgu süresi n içinde doğrusaldır çünkü herhangi bir anahtarın hash değerini sorgulamak için MPHF’nin her bitinin kullanılması gerekir.

Fan-out değeri s olan m anahtarlı bir bölme için ve i ∈ {0, ..., s − 1} çocuk düğümünün kᵢ anahtar içerdiği durumda, denenmesi gereken hash fonksiyonlarının beklenen sayısı şu değere orantılıdır

((2π)^(s−1) · ∏ kᵢ) / m

Bu değer, tüm çocuklar eşit büyüklükte olduğunda en yüksek olur; yani dengeli bölmelerin bulunması dengesiz bölmelere göre daha maliyetlidir.

4.4 Rice Bit Vector

Hash fonksiyonu tanımlayıcıları, hızlı erişime izin verirken alan açısından verimli olacak şekilde saklanır. Önemli bir nokta, bölme ağaçlarının şekillerinin açıkça saklanmamasıdır. Bunun yerine preorder biçiminde saklanırlar; yani önce kök, ardından ilk çocuğun tüm alt ağacı, sonra ikinci çocuğun tüm alt ağacı ve bu şekilde devam eder. Yalnızca hash fonksiyonu tanımlayıcıları saklanır. Tüm bölme ağaçlarının kodlamaları Rice Bit Vector adı verilen tek bir bit vektöründe birleştirilir.

4.4.1 Golomb-Rice Kodları

Her hash fonksiyonu tanımlayıcısı bir Golomb-Rice kodu [57, 78, 79] olarak kodlanır. Bir Golomb parametresi τ ve hash fonksiyonu tanımlayıcısı d verildiğinde, d’nin τ en düşük anlamlı biti doğrudan saklanır ve kalan en yüksek anlamlı bitler unary biçimde kodlanır.

Unary kısmı (d >> τ) adet 0-bit içerir ve ardından son bir 1-bit gelir.

Örnek: τ = 3 için d = 1010₂ değeri

şeklindedir.

Golomb-Rice kodları keyfi büyüklükte sayıları saklamaya olanak tanır; bu önemlidir çünkü hash fonksiyonu tanımlayıcıları teorik olarak sınırsız büyüklüğe ulaşabilir. Ayrıca Golomb-Rice kodlarının kullanılması yararlıdır çünkü hash fonksiyonu tanımlayıcıları geometrik dağılım izler. Golomb kodları [57] geometrik dağılımlar için en uygun kodlardır ve Golomb-Rice kodları [78] bunun daha hızlı çalışan ve alan verimliliği neredeyse aynı olan özel bir durumudur.

En uygun Golomb parametresi τ, verilen bir hash fonksiyonunun geçerli bir bölme veya bijeksiyon olma olasılığına bağlıdır. Olasılık p için en uygun parametre

τ(p) = max(0, ⌈log₂( −log₂ φ / log₂(1 − p) )⌉)

şeklindedir ve burada altın oran

φ = (√5 + 1) / 2.

Orijinal makalede [46] gösterildiği gibi, büyük n değerleri için RecSplit’in alan tüketimi optimuma yaklaşır; ancak her bölme/bijeksiyon başına yaklaşık 2 bit kayıp vardır. Alan kullanımını iyileştirmek için toplam bölme ve bijeksiyon sayısı azaltılmalıdır. Bu, yaprak boyutunu ℓ artırarak gerçekleştirilebilir. Bu durum bijeksiyon sayısını azaltır ve toplulaştırma seviyelerinde daha büyük fan-out değerlerine yol açarak daha az bölme yapılmasını sağlar.

Başka bir bakış açısıyla, her bölme/bijeksiyon başına daha fazla anahtar bulunduğundan 2 bitlik maliyet daha fazla anahtara yayılır. Daha büyük yaprak boyutları ayrıca daha hızlı sorgular sağlar çünkü toplulaştırma seviyelerindeki daha büyük fan-out değerleri nedeniyle bölme ağaçları daha sığ olur.

Bir anahtarın hash değerini hesaplamak için bölme ağacının kökten yaprağa hızlı bir şekilde dolaşılması gerekir. Bu, her bölme ağacının fixed ve unary kısımlarının ayrı ayrı saklanması ile mümkün olur: önce fixed kısmı, ardından bölme ağacındaki tüm Golomb-Rice kodlarının unary kısmı. Her ikisi de preorder biçiminde saklanır.

Kritik nokta şudur: bölme ağacındaki bir v düğümü verildiğinde, v köküne sahip alt ağacın şekli yalnızca v’deki anahtar sayısına bağlıdır. Buna şunlar dahildir:

Her iki değer de Golomb parametresiyle birlikte anahtar sayısına göre indekslenen bir lookup table içinde saklanabilir.

Bir sorguda bir bölme değerlendirildikten sonra hangi çocuk düğüm c’nin sırada değerlendirileceği belirlenir. c düğümünün hash fonksiyonu tanımlayıcısını bulmak için bir veya daha fazla alt ağacı atlamak gerekebilir. c bölmenin ilk çocuğuysa hiçbir alt ağacın atlanması gerekmez. Fixed ve unary kısımlarındaki bir sonraki değerler doğru hash fonksiyonu tanımlayıcısını çözer.

Aksi durumda c’nin solunda bulunan aynı bölmeye ait tüm çocukların alt ağaçları atlanmalıdır. Daha yüksek seviyelerde bu yalnızca bir alt ağaçtır. Toplulaştırma seviyelerinde birden fazla alt ağaç olabilir, ancak bu alt ağaçların hepsi aynı sayıda anahtar içerir ve dolayısıyla aynı şekle sahiptir.

Fixed kısmında bir alt ağacı atlamak için alt ağacın fixed kısmının kapladığı bit sayısı lookup table’dan alınır. Eğer birden fazla sol çocuk varsa atlanacak bit sayısı sol çocuk sayısıyla çarpılır.

Unary kısmında bir alt ağacı atlamak bir seçim işlemi kullanılarak yapılabilir. Hatırlayın ki her hash fonksiyonu tanımlayıcısının unary kısmı tam olarak bir 1-bit içerir. Bu nedenle bir alt ağaçtaki düğüm sayısı unary kısmındaki 1-bit sayısına eşittir. Düğüm sayısı anahtar sayısına göre indekslenen lookup table’da saklandığından yalnızca tabloda belirtilen sayıda 1-bit atlamamız gerekir.

m adet 1-bit atlamak, m’inci 1-bit’i (sıfırdan indeksli) bulmaya eşdeğerdir. Bu işlem, unary kısmını temsil eden 64 bitlik sözcükler üzerinde popcount çağrısı yapılarak ve en az m adet 1-bit bulunana kadar devam edilerek gerçekleştirilir. Ardından Bölüm 2.1’de açıklanan verimli seçim işlemi kullanılarak unary kısmındaki m’inci 1-bit’in tam bit konumu bulunur.

Daha önce açıklandığı gibi, her bölme ağacının fixed ve unary kısımları ardışık olarak saklanır. Tüm bölme ağacının unary kısmının başlangıcını açıkça saklamadan bulmak için, fixed kısmında alt ağaç atlama ile aynı fikir kullanılır. Sadece lookup table’dan tüm bölme ağacının fixed kısmının boyutuna bakılır ve bu değer fixed kısmın başlangıcına eklenir (bu başlangıç Double Elias-Fano gösteriminde saklanır; bkz. Bölüm 4.5).

Örnek olarak Şekil 4.1’deki gibi ℓ = 8 durumunu düşünelim. Mevcut düğümün 90 anahtar içerdiğini varsayalım. Bu sayıdan bunun ikinci toplulaştırma seviyesinin bir parçası olduğu çıkarılabilir. Lookup table’daki 90 indeksinde bu düğümün Golomb parametresinin 6 olduğu belirtilir; yani Rice Bit Vector’un fixed kısmındaki sonraki 6 bit hash fonksiyonu tanımlayıcısının en düşük anlamlı bitleridir ve unary kısmında bir sonraki 1-bit’e kadar olan 0-bit sayısını sayarak en yüksek anlamlı bitleri elde ederiz.

Hash fonksiyonu tanımlayıcısı, giriş anahtarının hash değerini hesaplamak için kullanılır; bu değer [90] aralığındadır. Örneğin hash değeri 72 olabilir; bu durumda

⌊72 / 32⌋ = 2

indeksindeki çocuk düğüm giriş anahtarını içerir.

Bölme işlemi 32’ye yapılır çünkü bu, birinci toplulaştırma seviyesindeki düğüm başına anahtar sayısıdır.

İki alt ağacı atlamamız gerekir. 32 indeksindeki lookup table girdisi her alt ağacın beş düğüm içerdiğini söyler. Unary kısmındaki bit konumu 10 adet 1-bit bulunana kadar ilerletilir; yani yeni konum 10. 1-bit’ten sonraki bittir. Lookup table tekrar kullanıldığında her alt ağacın fixed kısmında 39 bit bulunduğu görülür. Böylece fixed kısmındaki bit konumu 78 bit ilerletilir.

Oluşturma algoritması ve özellikle sorgu algoritması için, belirli sayıda anahtara sahip bir bölme/bijeksiyonun Golomb parametresinin hızlı hesaplanması gerekir. Ayrıca sorgu algoritması, anahtar sayısı verildiğinde herhangi bir bölme ağacındaki düğüm sayısını ve fixed kısmındaki bit sayısını bilmeye ihtiyaç duyar. Hızlı erişim için bu üç değer lookup table’da saklanır. Bu lookup table’ın çok fazla alan kullanmaması önemlidir; aksi takdirde MPHF’nin alan verimliliği azalır.

Örnek

Bu üç değerin tamamı her düğüm boyutu için tek bir 32-bit sözcük içine sığar. Golomb parametresi yalnızca 5 bit gerektirir çünkü ℓ ≤ 24 koşulu ve Denklem (4.1) bunu sağlar. Düğüm sayısı 11 bit kullanır ve kalan 16 bit fixed kısmın boyutu için ayrılır.

Hiçbir bucket’ın 3000 veya daha fazla anahtar içermediğini varsaydığımız için lookup table yalnızca 3000 giriş gerektirir. Her biri 32 bit olduğunda tüm lookup table 12 kilobayt yer kaplar. Bir milyon anahtar için bu yaklaşık anahtar başına 0.1 bit eder. Ancak bunu MPHF’nin gerekli alanına dahil etmiyoruz çünkü aslında MPHF’nin gerçek bir parçası değildir (lookup table anahtarlardan bağımsız olarak herhangi bir zamanda yeniden hesaplanabilir), fakat ana bellekte ve önbellekte yer kaplar.

RecSplit, bucket boyutlarının prefix toplamını ve her bucket’ın bölme ağacının Rice Bit Vector içindeki başlangıç bit konumunu saklamak için özelleştirilmiş bir Elias-Fano gösterimi [45, 47] kullanır. Bu özelleştirmeye Double Elias-Fano denir. Bu yapı, az alan kullanarak sabit zamanlı erişim sağlar. RecSplit için yapılan özelleştirmeyi açıklamadan önce genel Elias-Fano gösterimini açıklıyoruz.

4.5 Double Elias-Fano

4.5.1 Elias-Fano Gösterimi

Bir Elias-Fano gösterimi, aşağıdaki gibi monoton bir tam sayı dizisini saklamak için kullanılabilir

0 ≤ x₀ ≤ x₁ ≤ … ≤ x_κ

ve burada κ ≥ 0’dır.

Golomb-Rice kodlarına benzer şekilde her değerin en düşük anlamlı bitleri doğrudan saklanır. Daha açık olarak

μ = max(0, ⌊log₂(x_{κ+1} / (κ + 1))⌋)

değerindeki μ adet en düşük anlamlı bit her değer için bitişik biçimde lower-bits array içinde saklanır ve doğrudan erişilebilir.

Kalan en yüksek anlamlı bitler upper-bits array içinde unary farkları olarak kodlanır. Bu, upper-bits array’in dizideki her değer için bir 1-bit içerdiği ve iki değerin 1-bit’leri arasındaki 0-bit sayısının bu iki değerin en yüksek anlamlı bitleri arasındaki fark olduğu anlamına gelir.

Örneğin 0 ≤ i < j ≤ κ için upper-bits array içindeki i’inci ve j’inci 1-bit (sıfırdan indeksli) arasındaki 0-bit sayısı

(x_j >> μ) − (x_i >> μ)

şeklindedir.

Başka bir ifadeyle x_i’ye karşılık gelen 1-bit şu konumdadır:

(x_i >> μ) + i

Upper-bits array’deki i’inci 1-bit’in konumu ν sabit zamanda bulunabilsin diye bir selection data structure kullanılır. Çünkü

ν = (x_i >> μ) + i

olduğundan x_i’nin üst bitleri ν − i olarak hesaplanabilir.

4.5.2 Özelleştirme

RecSplit, bucket boyutlarının prefix toplamını ve her bölme ağacının başlangıç bit konumunu tek bir birleşik Elias-Fano gösterimi içinde saklar; bu nedenle adı Double Elias-Fano’dur.

λ_i prefix-toplam dizisi ve σ_i bit-konum dizisi olsun; burada i ∈ [κ + 1] ve bucket sayısı

κ = ⌈n / b⌉.

Burada λ₀ = σ₀ = 0, λ_κ = n toplam anahtar sayısıdır ve σ_κ Rice Bit Vector’un toplam bit sayısıdır.

σ_i dizisi doğrudan saklanmaz. Bunun yerine

ψ_i = σ_i − βλ_i

dizisi saklanır; burada

β = σ_κ / λ_κ

bölme ağaçlarının anahtar başına gerektirdiği ortalama bit sayısıdır. Bu yöntem iki dizi arasındaki bağımlılığı kullanarak σ_i’yi sıkıştırır. Ancak ψ_i monoton olmayabilir; bu durum aşağıda çözülür.

Sonraki adımda her iki dizi, ardışık elemanlar arasındaki farkların en küçük fark kadar azaltılmasıyla yeniden ölçeklendirilir:

δ_λ = min_{i ∈ {1,…,κ}} (λ_i − λ_{i−1})

δ_ψ = min_{i ∈ {1,…,κ}} (ψ_i − ψ_{i−1})

Daha sonra λ_i dizisi şu diziyle değiştirilir

φ_i = λ_i − iδ_λ

ve ψ_i dizisi şu diziyle değiştirilir

χ_i = ψ_i − iδ_ψ.

Bu işlem özellikle b büyük olduğunda λ_i’nin aralığını azaltır. Örneğin b = 2000 ise bir bucket’ın 1500’den az anahtar içermesi olasılığı neredeyse sıfırdır. Bu nedenle yüksek olasılıkla δ_λ ≥ 1500 olur; bu da her değeri ortalama olarak dörtte birine indirir ve bucket başına yaklaşık iki bit tasarruf sağlar.

Eğer ψ_i monoton değilse δ_ψ negatif olur ve yeniden ölçeklendirilmiş χ_i dizisi tekrar monoton hale gelir.

Her iki dizinin lower-bits array’leri iç içe geçirilir; yani i ∈ [κ + 1] için χ_i, tek bir lower-bits array içinde φ_i’nin hemen ardından saklanır. Bu, olası bir cache miss’i azaltabilir. Upper-bits array’ler ise ayrı ayrı saklanır.

RecSplit’in yazarları her iki dizinin de oldukça düzenli olduğunu belirtir. Bu durum basit bir seçim veri yapısının kullanılmasına olanak tanır. Bu veri yapısı her 2¹⁴’üncü 1-bit’in ve aradaki her 256’ncı 1-bit’in konumunu sağlar. İlk konum 64-bit sözcük olarak saklanır; ikinci konum ise ilkine göre göreli olup yalnızca 16 bit gerektirir.

Daha önce olduğu gibi, olası bir cache miss’i azaltmak amacıyla her iki upper-bits array için konumlar da iç içe geçirilir.

ζ_φ(γ) ifadesi φ_i dizisinin upper-bits array’indeki γ’inci 1-bit’in konumu olsun; yani φ_γ’ye karşılık gelen 1-bit. Benzer şekilde ζ_χ(γ) değeri χ_i için tanımlanır. Bu konumları içeren diziye jump array adı verilir.

Bu dizinin j indeksindeki tek bir girdisi birkaç değer içerir:

İlk iki giriş her zaman sıfırdır. Bu, seçim veri yapısının açıklamasını tamamlar.

Depolanan verileri kullanarak φ_i, φ_{i+1} ve χ_i değerlerinin beklenen sabit zamanda nasıl hesaplanacağını açıklamaya geçiyoruz. Bu üç değer daha sonra önceki dönüşümler geri alınarak λ_i, λ_{i+1} ve σ_i değerlerini hesaplamak için kullanılabilir.

Her üç değerin de en az anlamlı bitleri, lower-bits dizisinde yapılan bir arama ile doğrudan elde edilebilir. φ_i ve χ_i değerlerinin en anlamlı bitlerini hesaplamak için upper-bits dizilerindeki ilgili 1-bit konumlarının bulunması gerekir.

Seçim veri yapısı, depolanmış en yakın 1-bit'i bulmak için kullanılır (her 256. 1-bit). Daha sonra doğru konum, her iki upper-bits dizisindeki 64-bit sözcükler üzerinde popcount ve selection kullanılarak doğrusal olarak aranır (bkz. Bölüm 2.1).

φ_{i+1} değerine karşılık gelen 1-bit, φ_i'nin 1-bit'ini takip eder ve bu nedenle hızlı bir şekilde bulunabilir. Daha sonra en anlamlı ve en az anlamlı bitler birleştirilerek nihai değerler elde edilir.

Analiz

Tanımlayalım:

μ_φ = max(0, ⌊log₂(φ_{κ+1} / (κ + 1))⌋)

μ_χ = max(0, ⌊log₂(χ_{κ+1} / (κ + 1))⌋).

lower-bits dizisinin alan tüketimi

(κ + 1)(μ_φ + μ_χ) bittir.

upper-bits dizileri ise

κ + 1 + (φ_κ >> μ_φ)

veya

κ + 1 + (χ_κ >> μ_χ)

bit gerektirir. Her iki upper-bits dizisinin bit sayısı en fazla 3κ + 2'dir.

jump dizisi şu kadar alan gerektirir:

2κ(64 + 16) / (2¹⁴ · 256) + O(1) = 17/128 κ + O(1)

bit.

Double Elias-Fano gösteriminin toplam alan tüketimine lower-bits dizisi hâkimdir. Bunun için gereken alan

O(κ log b) = O((n log b) / b)

bittir.

Bu, b artırılarak Double Elias-Fano tarafından kullanılan alanın azaltılabileceği anlamına gelir. Ancak bu durum, değerlendirme bölümünde daha sonra tartışıldığı gibi, kurulum ve sorgu süresini de artırır.

Double Elias-Fano sorgulamasında açıkça sabit zaman gerektirmeyen tek bölüm, seçim veri yapısı kullanıldıktan sonra upper-bits dizilerinde yapılan doğrusal aramadır. Bu adımın çalışma süresi, bulunan 1-bit ile sorgulanan kovayı temsil eden 1-bit arasındaki mesafe ile doğrusal olarak artar.

Her iki upper-bits dizisi de O(κ) bit içerdiğinden ve her biri tam olarak κ + 1 adet 1-bit barındırdığından, bu mesafe ortalama olarak O(1)'dir. Saklanan dizilerin düzenliliği beklenen sabit çalışma süresini garanti eder.

5. Gerçekleme

Bu bölümde RecSplit'in farklı gerçeklemelerinin nasıl çalıştığını daha ayrıntılı olarak açıklıyoruz. Her adım, belirli donanım mimarilerine ilişkin ayrıntılar tartışılmadan önce genel olarak açıklanır. Son olarak, RecSplit örneğinin oluşturulması için adımların nasıl birleştirildiğine dair bir genel bakış sunulur.

GPU gerçekleme, CUDA 11 [71] kullanır. SIMD gerçekleme, Fog tarafından geliştirilen vector class library [26, 27] kullanır, yalnızca x86 CPU'ları destekler ve AVX2 ile AVX-512 için optimize edilmiştir.

Sux kütüphanesindeki [13] özgün RecSplit gerçeklemesi, anahtarları kova numaralarına göre sıralamak için C++ standart kütüphanesinin sıralama fonksiyonunu kullanır. Örneğin GCC derleyicisi tarafından kullanılan libstdc++ standart kütüphanesi, quicksort tabanlı olan ve çalışma süresi O(n log n) olan introsort [70, 56] algoritmasını kullanır.

Kesin olarak ifade etmek gerekirse, bu durum gerçeklemeye beklenen doğrusal çalışma süresi özelliği kazandırmaz. Ancak çoğu kullanışlı parametre kombinasyonu için sıralama süresi, algoritmanın geri kalanına kıyasla ihmal edilebilir düzeydedir.

Anahtarları yalnızca ilgili kova numaralarına göre dağıtmak istediğimiz ve her kovanın içindeki anahtarları sıralamamız gerekmediği için, doğal olarak daha hızlı bir alternatif bucket sort yöntemidir. Daha özel olarak, counting sort [80] olarak bilinen bir varyant kullanılır.

Bu yerinde olmayan (out-of-place) algoritmanın özel gerçeklememiz üç aşamadan oluşur.

5.1 Sıralama

  1. Her kovaya hashlenen anahtar sayısını A dizisinde say.
  2. Kova boyutlarının A dizisi için kapsayıcı prefix toplamını hesapla.
  3. Girdi üzerinde dolaşarak anahtarları doğru kovalara yerleştir; her anahtar için kova numarasını hesapla, A tarafından verilen çıktı konumuna yerleştir ve A içindeki konumu azalt.

Anahtarların yalnızca son 64 biti kovaya yerleştirilir; çünkü diğer yarısı yalnızca kova numarasını belirlemek için kullanılır. Bu aşamadan sonra A, kova boyutlarının exclusive prefix sum değerini içerir.

Counting sort, sabit boyutlu anahtarlar için doğrusal çalışma süresine sahiptir. Ancak önbellek boyutunu aşan girdiler için introsort'tan daha kötü performans gösterebilir; çünkü counting sort anahtar başına birkaç rastgele erişim gerçekleştirir. Buna karşılık introsort girdiyi doğrusal biçimde dolaşır ve önbelleği daha verimli kullanabilir [62].

Bu sorun, 1 ve 3 aşamalarında prefetching kullanılarak ve önbellek kaçırmalarının gecikmesi gizlenerek azaltılabilir.

Bunun için immintrin.h başlığındaki mm_prefetch [22] içsel fonksiyonu kullanılır; bu fonksiyon x86 mimarisinde bir prefetch komutu üretir. Birinci aşamada giriş verisi 32 boyutlu partiler hâlinde işlenir. Önce ilgili sayaçların adresleri hesaplanır, önceden getirilir ve ardından artırılır. Üçüncü aşama benzer şekilde gerçekleştirilir; ancak biri A içindeki indeksler, diğeri çıktı için olmak üzere iki prefetch döngüsü içerir.

Daha iyi performansa ek olarak counting sort'un başka bir avantajı daha vardır. Counting sort tamamlandıktan sonra A dizisi kova boyutlarının exclusive prefix toplamını, yani her kovanın başlangıç indeksini içerir. Bu bilgi daha sonra Elias–Fano gösterimi için gereklidir ve özgün gerçeklemede ayrıca hesaplanması gerekiyordu. Ayrıca kova konumlarının önceden bilinmesi SIMDRecSplit'in paralelleştirilmesi için gereklidir (bkz. Bölüm 5.8).

Counting sort'un bu gerçeklemesinin bir dezavantajı, yerinde çalışmaması ve sıralanmış çıktıyı depolamak için yaklaşık %50 ek bellek tüketmesidir.

Özgün RecSplit makalesinde [46] yapılan olasılıksal analiz yalnızca tüm hash fonksiyonu değerlendirmeleri birbirinden bağımsızsa geçerlidir. Farklı anahtarlar için ve özellikle farklı kovalar için bu koşul sağlanır; çünkü anahtarlar başlangıç hash fonksiyonunun sonucudur ve bu nedenle korelasyonları azaltılmıştır (bkz. Bölüm 4.1). Ancak aynı anahtar kendi kovası içinde farklı seviyelerde kullanılır. Anahtar her kullanıldığında kullanılan hash fonksiyonlarının farklı olduğundan emin olunmalıdır. Özgün gerçekleme [13], şu anda incelenen bölme veya birebir eşlemenin seviyesini izler ve seviyeye bağlı olarak rastgele üretilmiş fakat sabit bir başlangıç tohumunu arama tablosundan alır. Bu başlangıç tohumu, hash fonksiyonu kimliğine (daha sonra Rice Bit Vector içinde saklanır) ve hashlenmesi gereken anahtara eklenir. En üst bölmenin seviyesi 0'dır.

GPU sürümünde tüm yapraklar (son yaprak farklı boyutta olabilir) tek bir kernel çağrısıyla işlenir. Aynı durum yaprakların üzerindeki iki toplama seviyesi için de geçerlidir. Yaprakların aynı seviyeye sahip olması gerekmez; çünkü seviye üstten başlayarak sayılır ve ağaç her zaman tam dengeli değildir. Kernel içindeki her yaprağa başlangıç tohumu göndermemek için tüm yapraklar için rastgele seçilmiş ancak derleme zamanında sabit olan tek bir başlangıç tohumu kullanılır. Benzer şekilde yaprak seviyesinin üzerindeki iki toplama seviyesi için de farklı başlangıç tohumları üretilir. Daha üst seviyeler hâlâ özgün sürümdeki aynı başlangıç tohumu arama tablosunu kullanır. Bu değişikliğin herhangi bir korelasyon getirmediğine dikkat edilmelidir; çünkü aynı başlangıç tohumlarını kullanan bölmeler ve birebir eşlemeler farklı anahtarlar kullanır.

Bu değişiklikleri içermek için sorgu fonksiyonu biraz değiştirilmelidir. Son üç seviyede arama tablosu yerine sabit başlangıç tohumları kullanılır. Bunun önceki sürümden daha yavaş olması beklenmez. Aslında sabit değer derleme zamanında bilindiği için tablodan alınmasına gerek kalmaz ve bu nedenle biraz daha hızlı olması beklenir. Ayrıca seviye sayacının iki artırımı ortadan kaldırılabilir. Bu nedenle ve her iki sürümün de tamamen aynı MPHF sonucunu üretmesini sağlamak için SIMD sürümü de bu tekniği kullanır.

Özgün RecSplit gerçeklemesi [13], hash fonksiyonlarını gerçekleştirmek için 64 bitlik bir remix fonksiyonu [8, 41] kullanır. Bu remix fonksiyonu f : [2^64] → [2^64], 64 bitlik bir sözcük alır ve giriş bitlerini kaydırmalar, XOR işlemleri ve sabitlerle çarpımlar kullanarak karıştırarak yine 64 bitlik bir sözcük döndürür. Bu, tüm 64 bitlik sözcüklerin sahte rastgele bir permütasyonu olarak düşünülebilir. RecSplit bunu h : [2^64] → [m] biçimindeki hash fonksiyonlarını gerçekleştirmek için kullanır; burada m < 2^16 koşulu vardır. Bunun için giriş üzerinde remix fonksiyonu uygulanır, en anlamlı 16 bit sıfırlanır, sonuç m ile çarpılır ve 48 bit sağa kaydırılır.

5.2 Başlangıç Tohumları

Bu işlem fiilen f(x) değerini, ondalık noktası en anlamlı 16 bitten sonra gelen ve sıfır dâhil bir ile bir hariç arasında bulunan sabit noktalı bir ondalık sayı olarak yorumlar [46]. m ile çarpıldığında sonuç sıfır (dâhil) ile m (hariç) arasında sabit noktalı bir sayı olur. 48 bit sağa kaydırma işlemi, ondalık noktasının solundaki kısmı çıkarır; bu da 0 dâhil m hariç aralığında bir tam sayıdır.

Remix fonksiyonu f iki adet 64 bit tamsayı çarpımı kullanır; yani h hash fonksiyonunun her değerlendirmesi için üç adet 64 bit çarpma gerekir. Bu durum GPU gerçeklemesi için sorun oluşturur; çünkü çoğu GPU 32 bit işlemler için optimize edilmiştir (kayan nokta ve tamsayı). 64 bit tamsayıların kaydırma, XOR ve toplama işlemleri yalnızca birkaç 32 bit komutla gerçekleştirilebilir. Ancak 64 bit çarpma işlemleri çok daha fazla komut gerektirir ve bu nedenle GPU'larda oldukça maliyetlidir [12].

Bu sorun g : [2^32] → [2^32] biçiminde bir 32 bit remix fonksiyonu kullanılarak çözülebilir. Neyse ki 64 bit remix fonksiyonunun kökeni olan MurmurHash3 aynı zamanda bir 32 bit remix fonksiyonu da içerir [8]. Bu fonksiyon f ile aynı işlemleri 32 bit sözcükler üzerinde farklı sabitlerle gerçekleştirir. g fonksiyonu, yukarıdaki yöntemin aynısı kullanılarak h fonksiyonunu gerçekleştirmek için kullanılabilir; yalnızca 48 sabiti 16 ile değiştirilir ve 32 bit işlemler kullanılır. Bu şekilde h, herhangi bir 64 bit tamsayı çarpımı olmadan gerçekleştirilebilir. Bu yalnızca GPU sürümüne değil, SIMD sürümüne de fayda sağlar; çünkü remix fonksiyonunun verimi etkili biçimde iki katına çıkarılabilir. GPU gerçekleme için sağlanan avantaj Bölüm 6.5.1'de gösterilmiştir.

Ancak h fonksiyonunun girdisi her zaman 64 bitlik bir sözcüktür ve g kullanılmadan önce 32 bitlik bir sözcüğe dönüştürülmelidir. En anlamlı 32 biti yok sayıp yalnızca en az anlamlı 32 biti kullanmak iyi bir yaklaşım değildir. Örneğin ℓ = 24 için bu durum sorun oluşturur. Rastgele bir hash fonksiyonunun 24 anahtar üzerinde birebir eşleme olma olasılığının

24! / 24^24 ≈ √(2π·24) / e^24

olduğunu hatırlayın.

Bu nedenle 2^32'den fazla hash fonksiyonunun denenmesi gerekme olasılığı yaklaşık olarak

(1 − √(2π·24) / e^24)^(2^32) ≈ 0.137

olur.

Girdinin en anlamlı 32 biti yok sayılırsa fiilen yalnızca 2^32 farklı hash fonksiyonu vardır. Daha fazlasına ihtiyaç duyulursa artık olası bir çözüm bulunamaz. Bizim gerçeklememizde bu durum sonsuz bir döngü ile sonuçlanır.

Daha ciddi bir sorun ise anahtarların en anlamlı 32 bitinin fiilen yok sayılmasıdır. Bu nedenle en az anlamlı 32 biti aynı olan iki anahtar aynı kovaya düşerse, her zaman tam olarak aynı hash koduna dönüştürülürler. Bu da tekrar çözüm bulunmasını imkânsız hâle getirir; çünkü her iki anahtar aynı yaprağa düşer ve birebir eşleme mümkün olmaz. 2000 adet rastgele 32 bit anahtar içeren bir kovada en az iki anahtarın aynı olma olasılığı

1 − (2^32)! / ((2^32 − 2000)! (2^32)^2000) ≈ 0.000465.

On milyon anahtar, yani 5000 kova verildiğinde bu durumun ortaya çıkma olasılığı

1 − (1 − 0.000465)^5000 ≈ 0.902.

Bu kabul edilemez bir risktir.

Bu sorunlar, girdinin en anlamlı 32 biti ile en az anlamlı 32 bitinin XOR'u kullanılarak çözülebilir. Örnekte h fonksiyonunun girdisinin hash fonksiyonu kimliği d (0'dan başlayarak) ile hashlenmesi gereken anahtar y'nin toplamı olduğunu hatırlayın (burada başlangıç tohumunu göz ardı ediyoruz). Hem d hem de y 64 bit sözcüklerdir. Eğer d + y toplamının en anlamlı 32 biti yok sayılırsa d + t·2^32, her tam sayı t için aynı hash fonksiyonuna karşılık gelir. Ancak en anlamlı ve en az anlamlı 32 bitlerin XOR'u kullanılırsa bu durum gerçekleşmez; çünkü toplama işlemi daha anlamlı bitlere taşıma bilgisi aktarır. Bu taşıma anahtar y'ye bağlıdır. 64 bitten 32 bite geçişte bilgi kaybının kaçınılmaz olduğuna dikkat edilmelidir. Ancak kritik nokta, dönüşümün farklı anahtarlar y için farklı görünmesidir. Bunun çalışabilmesi için d ve y değerlerinin toplama işlemi ile birleştirilmesi (XOR veya diğer bit düzeyi işlemlerle değil) ve XOR işleminin toplama işleminden sonra yapılması önemlidir.

5.3 32 Bit Hash Fonksiyonu

h(x) = ((f(x) & ((1 << 48) − 1)) * m) >> 48

64 bit remix fonksiyonunun sabitleri Strafford tarafından ardışık iki sözcüğün sonuçlarının mümkün olduğunca az korelasyonlu olması için optimize edilmiştir [41]. Bu RecSplit için yararlıdır; çünkü ardışık olarak denenen iki hash fonksiyonu ardışık sözcükler kullanır (d her yeni hash fonksiyonu için bir artırılır). 32 bit hash fonksiyonu için de benzer bir yaklaşım uygulanabilir. Ancak XOR ve başlangıç tohumu nedeniyle sözcükler ardışık olmadığından bu daha karmaşık olur. Ayrıca deneyler, özgün sürüm (64 bit remix fonksiyonu kullanan) ile SIMD/GPU sürümleri (32 bit fonksiyon kullanan) arasında MPHF boyutları açısından anlamlı bir fark göstermemektedir; bkz. Bölüm 6.5.1. Bu durum 32 bit remix sabitlerini optimize ederek büyük bir kazanç elde edilemeyeceğini gösterir.

Şimdi SIMD gerçeklemesi için remix fonksiyonunun ayrıntılarını inceleyelim. SIMD sürümü sabit bit sayısına sahip vektörler üzerinde çalışır. Örneğin x86 komut kümesi genişlemesi AVX-512 düşünülsün. Her vektör 512 bitten oluşur. Bu nedenle bir vektör sekiz adet 64 bit sözcük veya on altı adet 32 bit sözcük içerebilir. Bir vektör işlemi, vektördeki tüm sözcükler üzerinde aynı işlemi gerçekleştirir. Verimi artırmak için tercihen 32 bit sözcükler kullanılmalıdır. 32 bit hash fonksiyonunu kullanabilmek için 64 bit girişin önce yukarıda açıklandığı gibi XOR kullanılarak 32 bite dönüştürülmesi gerekir. Bu, girişin 64 bit sözcükler içeren iki vektörden oluştuğu anlamına gelir. Bu iki vektörü, hash fonksiyonunun girdisi olarak kullanılabilecek doğru 32 bit sözcükleri içeren tek bir vektöre dönüştürmek için çeşitli uygulama yöntemleri vardır.

5.3.1 SIMD Gerçeklemesi

İlk gerçekleştirim, Vector Class Library’nin compress fonksiyonunu kullanır [27]. Bu fonksiyon, 64 bitlik sözcükler içeren iki vektörü alır ve her sözcüğün en az anlamlı 32 bitini paketleyerek 32 bitlik sözcükler içeren tek bir vektör meydana getirir. Girdi vektörleri x ve y verildiğinde, dönüşüm şu şekilde uygulanabilir:

compress(x >> 32, y >> 32) ⊕ compress(x, y).

Kaydırma işlemi, vektördeki bireysel 64 bitlik sözcükler üzerinde çalışır.

İkinci gerçekleştirim blend16 fonksiyonunu kullanır [27]. Bu fonksiyon iki vektör ve 16 adet şablon parametre indeksi alır. Sonuç, indeksler tarafından seçilen 32 bitlik sözcüklerin ardışık birleştirilmesidir. 16 veya daha büyük bir indeks, ikinci girdi vektöründeki ilgili sözcüğün seçildiği anlamına gelir. Bu fonksiyon, her 64 bitlik sözcüğün en az veya en çok anlamlı 32 bitini tek bir vektörde paketlemek için kullanılabilir. blend16even, şablon parametreleri olarak 0’dan 30’a kadar tüm çift indeksleri içeren fonksiyon olsun ve blend16odd ise tüm tek indeksleri içeren fonksiyon olsun. Bu durumda dönüşüm şu şekilde görünür.

Deneylere göre (bkz. Bölüm 6.4.1), ikinci gerçekleştirim daha hızlıdır ve bu nedenle kullanılmaktadır. Eğer AVX2 mevcut ancak AVX‑512 yoksa, dört adet 64 bitlik sözcük veya sekiz adet 32 bitlik sözcük içeren 256 bitlik vektörler kullanılır. blend16 yerine blend8 kullanılır. Eğer AVX2 de mevcut değilse, 256 bitlik vektörler Vector Class Library tarafından, eğer varsa SSE komut kümeleri kullanılarak taklit edilir.

5.4 Yaprak Seviyesi

Her bir yaprak için, yaprak anahtarları X = {x1, …, xm} üzerinde bir bijeksiyon bulunmalıdır. h : X → [m] bir karma fonksiyonu olsun. h fonksiyonunun bir bijeksiyon olup olmadığını belirlemek için aşağıdaki algoritma kullanılır:

  1. a ← 0 olarak başlat.
  2. Her x ∈ X için, a değişkeninin h(x) indeksindeki bitini 1 yap, yani a ← a | (1 << h(x)).
  3. h fonksiyonu ancak ve ancak a değişkeninin en az anlamlı m bitlerinin tamamı 1 ise bir bijeksiyondur; yani a = (1 << m) − 1 ise.

5.4.1 Bijection Midstop

Büyük m değerleri için bu prosedür hızlandırılabilir. İlk p = p(m) (p < m) anahtar işlendikten sonra zaten bir çakışma meydana gelmiş olabilir; yani aynı karma değerine sahip iki veya daha fazla anahtar olabilir. Bu durumda a içinde ayarlanmış bit sayısının p’den az olduğunu unutmayın. Bu nedenle, ilk p anahtar işlendiğinde popcount komutu kullanılarak çakışmalar tespit edilebilir. Eğer bir çakışma bulunursa algoritma bir sonraki karma fonksiyonuyla devam eder. Aksi halde kalan anahtarlar karmalanır ve 3. adım her zamanki gibi uygulanır. Bu algoritmaya bijection midstop adını veriyoruz.

Orijinal RecSplit gerçekleştiriminde [13], bijection midstop m ≥ 9 için kullanılır. p = p(m) = ⌈2√m⌉ parametresi, bir çakışmanın bulunma olasılığı yaklaşık %90 olacak şekilde seçilir.

5.4.2 GPU Gerçekleştirimi

Aynı boyuta sahip tüm yaprakların bijeksiyonlarını bulmak için her kova başına bir kernel çağrısı kullanılır. Her thread bloğu tam olarak bir yaprağı işler. Öncelikle yaprak anahtarları X, Bölüm 2.3.2’de açıklandığı gibi memcpy_async kullanılarak paylaşımlı belleğe yüklenir. Verinin gelmesi için geçen süre, thread’ler tarafından başlatma işlemleri için kullanılır. Bellek erişimi tam olarak eşzamanlı (coalesced) değildir çünkü tüm yaprakların anahtarları dolgu yapılmadan ardışık biçimde saklandığından uygun hizalama garanti edilmez. Bununla birlikte, kernel tarafından global bellekten yüklenen neredeyse her bayt thread bloklarından biri tarafından kullanılır; bu da önbellekleme verimliliğini artırır.

Paylaşımlı bellekte bulunan bir karma fonksiyonu tanımlayıcısı d, mümkün olan en büyük değerle başlatılır. Her thread, blok içindeki thread indeksine göre tanımlanan farklı bir karma fonksiyonunu dener. Bir thread bir bijeksiyon h bulursa, d değerini atomik olarak d ile h’nin kimliği arasındaki minimum değere ayarlar. Ardından her thread, bloktaki thread sayısı kadar artırılmış bir sonraki karma fonksiyonunu dener. k denemeden sonra thread’ler senkronize olur, bir bijeksiyon bulunup bulunmadığını kontrol eder ve bulunmuşsa d değerini global belleğe yükler. k değeri m = |X|’e bağlıdır. X kümesi ne kadar fazla anahtar içerirse, ortalama olarak bir bijeksiyon bulmak için daha fazla deneme gerektiğinden k o kadar büyük olur. Bu durum büyük yapraklar için senkronizasyon sayısını azaltır. m < 14 olduğunda veya bijection rotation kullanıldığında (bkz. Bölüm 5.5), k = 1 seçilir.

Bir warp kilit-adım (lock-step) şeklinde çalıştığından, bijection midstop yalnızca warp içindeki tüm thread’ler bir çakışma tespit ederse etkili olur. Eğer en az bir thread çakışma tespit etmezse, tüm warp kalan anahtarları işlemeye devam etmek zorundadır. Bu nedenle orijinal sürümdeki [13] aynı midstop parametresini kullanmak uygun değildir. Bunun yerine p = p(m) = ⌈3√m⌉ kullanılır; bu da warp içindeki tüm thread’lerin bir çakışma bulma olasılığını yine yaklaşık %90 yapar. Bu parametrenin deneylerde de neredeyse optimal olduğu görülmüştür (bkz. Bölüm 6.5.2). Bijection midstop yalnızca m ≥ 14 için kullanılır.

5. Gerçekleştirim

GPU gerçekleştirimine benzer şekilde, ardışık karma fonksiyonu tanımlayıcıları 64 bitlik sözcüklerden oluşan bir vektöre yüklenerek aynı anda birkaç karma fonksiyonu denenir. X içindeki her anahtar için, anahtar önce vektöre eklenir. İkinci bir vektör, bir vektördeki 64 bitlik sözcük sayısı eklenerek üretilir. Her iki vektör, Bölüm 5.3.1’de açıklandığı gibi karma fonksiyonu uygulanmadan önce 32 bitlik sözcükler içeren tek bir vektörde birleştirilir. Her SIMD hattı için sonuç [m] aralığında bir sayıdır. Diğer gerçekleştirimlerde olduğu gibi, indeks olarak yorumlanan bu sayının karşılık geldiği bit 1 yapılmalıdır.

AVX2 ve AVX‑512, bir vektörün içeriğini başka bir vektörde belirtilen bit sayısı kadar kaydırmak için VPSLLVD adlı bir komut içerir [14, 21]. Ne yazık ki Vector Class Library bu komutu desteklemez ve yalnızca bir vektörün içeriğini tüm hatlar için aynı miktarda kaydırmaya izin verir [27]. Ancak bu komut yine de mm256_sllv_epi32 veya mm512_sllv_epi32 içsel fonksiyonları kullanılarak kullanılabilir [22]. Biz bu komutu, belirtilen indekse bir adet 1 bitini kaydırmak için kullanıyoruz. Geri dönüş seçeneği olarak, ne AVX2 ne de AVX‑512 mevcutsa, iki kuvvetlerini içeren bir tabloda arama yapılır. 1 sayısını x bit sola kaydırmanın 2^x hesaplamasına eşdeğer olduğunu unutmayın.

Tüm elemanlar işlendiğinde, bir bijeksiyon olup olmadığını kontrol etmek, SIMD hattının içeriğini en az anlamlı m biti 1 olan sözcükle karşılaştırarak yapılır. Sonuç, her hat için bir boolean içeren ve bir bijeksiyon bulunup bulunmadığını belirten bir boolean vektördür. Herhangi bir SIMD hattında bir bijeksiyon bulunup bulunmadığını kontrol etmek için Vector Class Library’nin horizontal_or fonksiyonu kullanılır. Bu fonksiyon ancak ve ancak hatlardan en az biri true içeriyorsa true döndürür. Eğer true dönerse, horizontal_find_first fonksiyonu kullanılarak true içeren ilk hattın indeksi hesaplanır ve bu indeks bir bijeksiyonla sonuçlanan ilk karma fonksiyonu tanımlayıcısını hesaplamak için kullanılır.

5.4.3 SIMD Gerçekleştirimi

Bijection Midstop

Bijection midstop, SIMD gerçekleştiriminde diğer gerçekleştirimlere göre biraz farklı çalışır. GPU gerçekleştiriminde, bir warp içindeki herhangi bir thread çakışma bulamazsa tüm warp yaprağın kalan kısmını işlemeye devam etmek zorunda kalır. SIMD gerçekleştiriminde bu durum bir backlog kullanılarak önlenebilir. Midstop sonrasında, çakışma göstermeyen tüm sözcükler bir backlog içinde saklanır. Backlog içinde tam bir vektörü dolduracak kadar anahtar olduğunda, bu vektör her zamanki şekilde işlenerek bir bijeksiyon bulunmaya çalışılır. Bu sayede çoğu hattın ilgisiz olduğu vektörlerde vektör işlemleri boşa harcanmaz.

Popcount hesaplamak için komut kümesine bağlı olarak iki farklı gerçekleştirim vardır. Eğer AVX512VPOPCNTDQ komut kümesi uzantısı mevcutsa, 32 bitlik sözcükler içeren 512 bitlik vektörler üzerinde popcount kullanılabilir [21]. Daha sonra popcount değerleri midstop parametresiyle karşılaştırılır. Vector Class Library’nin to_bits fonksiyonu kullanılarak, çakışma bulunmayan her indeks için 1 bit içeren 16 bitlik bir bit maskesi elde edilir. Bit maskesi sıfır olmadığı sürece, ρ (bkz. Bölüm 2.1) kullanılarak çakışma olmayan ilk sözcüğün indeksi bulunur, ilgili bit clear_rho ile temizlenir ve sözcük backlog içine kaydedilir.

Eğer AVX512VPOPCNTDQ mevcut değilse, vektörler üzerinde popcount kullanılamaz. Bunun yerine tüm sözcükler bir diziye aktarılır ve ardından sıralı olarak işlenir.

Bijection midstop’tan daha hızlı bir yaklaşım olan yeni bir yöntem bijection rotation olarak adlandırılır. Temelde bijection rotation, m ≤ w (makinenin sözcük boyutu) koşulunda m anahtar üzerinde bir MPHF bulma yöntemidir. Fikir, FCH’ye [50] (bkz. Bölüm 3.4) benzerdir. Anahtarları rastgele iki kümeye, A ve B’ye, her anahtarın paritesini hesaplayarak dağıtırız. Anahtar diğer tüm yerlerde bir karma fonksiyonu ile birlikte kullanıldığından, burada doğrudan anahtarı kullanmak korelasyon oluşturmaz.

Bir h karma fonksiyonu verildiğinde, A içindeki tüm anahtarların karma değerlerini hesaplarız ve a sözcüğündeki ilgili bitleri 1 yaparız. Bijection midstop’ta olduğu gibi, a’nın popcount değeri hesaplanarak h geçerli bir bijeksiyon adayı olarak elenebilir. B kümesi de aynı şekilde işlenir ve bitler b sözcüğünde ayarlanır. b’nin mümkün olan tüm m döndürmeleri için bir bijeksiyon bulunup bulunmadığını test ederiz. Bu durum ancak ve ancak

a | rotr_m(b)

ifadesinin en az anlamlı m bitlerinin tamamı 1 olduğunda gerçekleşir; burada döndürme r ∈ [m] aralığındadır.

r değerini verimli biçimde saklamak için yalnızca her m’inci karma fonksiyonu denenir; yani karma fonksiyonunun numarası m modülüne göre sıfıra denktir. Bu sayı ile r’nin toplamı Rice Bit Vector içinde saklanır. Daha sonra r, mod m hesaplanarak geri elde edilir ve karma fonksiyonu r çıkarılarak geri elde edilir.

Bijection rotation yalnızca tam yapraklar için kullanılır; yani m = ℓ ise. Bu durum sorguda ek bir dallanma oluşturur ancak küçük yapraklarda bijection rotation kullanılmasını önler. Ayrıca ℓ derleme zamanı sabiti olduğundan mod işlemlerini hızlandırabilir.

Basit bir analiz için m’nin çift olduğunu ve |A| = |B| olduğunu varsayalım. Ayrıca A işlendikten sonra a’nın m farklı döndürmeye sahip olduğunu varsayalım; yani tüm r ∈ [m] \ {0} için rotr_m(a) ≠ a. Aşağıdaki olayları tanımlıyoruz:

İspat. h fonksiyonu, A üzerinde enjeksiyon ise ve kalan boşlukları B ile dolduruyorsa, bijection rotation kullanılarak X üzerinde bir bijeksiyondur. Dolayısıyla

P(Q) = P(R) · m · P(S | R) = P(R) · m · P(S)

çünkü S ve R bağımsızdır ve a içindeki boşlukları doldurmak için b’nin m farklı döndürmesi vardır. Daha açık olmak gerekirse, her biri farklı bir T kümesine sahip S biçiminde m farklı olay vardır. T kümesi, a’da kalan boşlukların m olası döndürmelerinden birini içerir. b’yi döndürmenin a’yı döndürmekle aynı etkiye sahip olduğunu unutmayın; dolayısıyla bu bakış açısı eşdeğerdir. Bu m olay birbirinden ayrıdır çünkü en fazla biri gerçekleşebilir. Bu durum yalnızca a’nın m farklı döndürmeye sahip olduğu varsayımı sayesinde doğrudur. Bu m olaydan herhangi birinin gerçekleşme olasılığı, olasılıkların toplamına eşittir. Her birinin olasılığı P(S) olduğundan toplam mP(S) olur.

Bu, varsayımlar sağlandığında denenmesi gereken karma fonksiyonlarının beklenen sayısının m kat azalacağı anlamına gelir; bu da yapım sürecini önemli ölçüde hızlandırabilir. Pratikte kazançlar daha küçüktür çünkü |A| ve |B|’nin eşit olması garanti değildir ve a m’den daha az farklı döndürmeye sahip olabilir. Örneğin ikili gösterimde:

rot^2_4(1010₂) = 1010₂

Tüm m döndürmeleri denemekten kaçınmak için t adlı bir arama tablosu kullanılabilir. a’nın tüm olası değerleri için bu tablo, rot^{t[a]}_m(a) değerinin en küçük olmasını sağlayan bir t[a] döndürme parametresi içerir. Eğer bir x değeri döndürülerek y değerine ulaşılabiliyorsa, o zaman rot^{t[x]}_m(x) = rot^{t[y]}_m(y) olur.

c = (1 << m) − 1 ifadesi, en az anlamlı m biti 1 olan sözcüğü temsil etsin. b̂ = b ⊕ c değeri, b’nin en az anlamlı m bitlerinin ters çevrilmiş halidir. b’nin a içindeki boşlukları doldurabilmesi ancak ve ancak b̂’nin döndürülerek a ile eşleşebilmesi durumunda mümkündür. b için gerekli döndürme artık yalnızca iki tablo erişimi ile hesaplanabilir. Bir bijeksiyon bulunmuş olması ancak ve ancak

a | rot((t[b̂] − t[a]) mod m)_m(b) = c

koşulu sağlandığında gerçekleşir.

Ancak bu arama tekniği bizim gerçekleştirimlerimizde kullanılmaz. Çoğu zaman, özellikle büyük yapraklarda, döndürmeleri hesaplamak gerekli değildir çünkü h A veya B üzerinde enjeksiyon değildir; bu durum erken durdurma için popcount ile tespit edilebilir. Ayrıca arama tablosu 2^ℓ bayttan oluşur ve sözde rastgele biçimde erişilir. Bu durum önbellek kaçırmalarına yol açabilir; özellikle ℓ ≥ 16 olduğunda çünkü birçok işlemcinin L1 veri önbelleği 2^16 B = 64 KiB’den küçüktür. Örneğin deneylerimizde kullandığımız Intel Core i7‑11700 işlemcisinin çekirdek başına 48 KiB L1 veri önbelleğine sahip olduğu lscpu komutu tarafından rapor edilir [20]. Arama tablosu kullanıldığında sıralı ve skaler gerçekleştirimde iyileşme ölçemedik (bkz. Bölüm 6.3.2).

GPU ve SIMD gerçekleştirimlerinde döndürmeler daha sık hesaplanmalıdır çünkü erken durdurma o kadar iyi çalışmaz. Buna rağmen arama tekniği umut verici değildir. SIMD durumunda, arama tablosundan değerleri vektör kayıtlarına yüklemek için gather komutları gerekir. Bu komutlar, döndürme için kullanılan basit komutlara kıyasla görece pahalıdır. GPU durumunda ise global bellek işlemleri birkaç komutu tasarruf etmek için fazla maliyetlidir. Constant memory, bir warp içindeki tüm thread’lerin yalnızca birkaç veya tek bir elemana eriştiği durumlar için optimize edilmiştir. Shared memory ise sınırlı bir kaynaktır ve yine de kayıtçılardan önemli ölçüde daha yavaştır. Bu nedenle arama tekniği GPU gerçekleştiriminde de kullanılmaz.

5.5.3 SIMD Gerçekleştirimi

Şimdi SIMD gerçekleştiriminde bijection rotation’a özgü ayrıntıları açıklıyoruz. Diğer gerçekleştirimlerde, her küme işlendikten sonra çakışmaları erken tespit etmek için popcount kullanılır. Ne yazık ki SIMD gerçekleştiriminde bu durum o kadar basit değildir. İlk küme işlendiğinde bazı SIMD hatları zaten bir çakışma bulmuş olabilir. Ancak en az bir hatta çakışma yoksa diğer kümenin de işlenmesi gerekir. Benzer şekilde ikinci küme için de çakışma içermeyen hatlar olabilir. Her hat için bir veya iki kümede de çakışma bulunduğunda ancak erken durdurma mümkündür. Bu nedenle çakışmalar yalnızca her iki küme de işlendiğinde ancak döndürmeler denenmeden önce kontrol edilir. Vektörler üzerinde popcount komutu gerekli olduğundan bu optimizasyon yalnızca AVX512VPOPCNTDQ komut kümesi mevcutsa kullanılır.

Rice Bit Vector içinde saklanan sayının, karma fonksiyonu kimliği ile rotasyonun toplamı olduğunu unutmayın. Alan israfını önlemek için bu sayı mümkün olduğunca küçük olmalıdır. Bunu sağlamak ve ortaya çıkan MPHF'nin GPU uygulaması tarafından üretilenle aynı olmasını garanti etmek için rotasyonlar denenirken dikkatli olunmalıdır. Bu hedefe, rotasyonları teker teker deneyip her rotasyondan sonra bir bijeksiyon bulunup bulunmadığını kontrol ederek ulaşılamaz. Daha küçük bir lane kimliğine sahip başka bir lane, daha yüksek bir rotasyon numarası için bir bijeksiyon bulabilir; bu da toplamda daha küçük bir sayıya yol açar. Bu nedenle tüm rotasyonlar denenir ve yalnızca en sonunda bir bijeksiyon bulunup bulunmadığı kontrol edilir.

Aynı kelimenin birden fazla rotasyonu bijeksiyon sağlayabilir. Örneğin, ℓ = 4 ve aşağıdaki iki kelimeyi düşünün:

b'yi, b içindeki 1-bitlerin a içindeki 0-bitlerle eşleşmesi için döndürmemiz gerekir. Eşleşme bulmak için b kelimesi sola sıfır bit veya iki bit döndürülebilir. Her zaman en küçük rotasyonun bulunmasını sağlamak için en yüksek rotasyondan başlanır. Daha açık ifade etmek gerekirse, her yinelemede b'yi bir bit sağa döndürmek için sola döndürme yerine sağa döndürme kullanılır. Vector Class Library'nin select fonksiyonu, bir bijeksiyon bulunduysa mevcut rotasyonu sonuçta saklamak için kullanılır. Bu fonksiyon girdi olarak bir boolean vektör ve iki ek veri vektörü alır ve boolean vektördeki değere bağlı olarak her lane için iki veri vektöründen birinin değerini seçer.

5.6 Toplama Seviyeleri

Bölme ağacındaki yaprak seviyesinin üzerinde iki adet sözde toplama seviyesi bulunur. Birinci toplama seviyesindeki her düğüm, kovadaki bir alt kümeyi yapraklara böler. İkinci toplama seviyesindeki her düğüm ise daha büyük bir alt kümeyi birinci toplama seviyesindeki düğümlere böler. Alt kümelerin boyutu (unit olarak adlandırılır) derleme zamanında sabittir; yalnızca seviye başına son alt küme daha küçük olabilir. Aynı durum fanout için de geçerlidir; yani alt kümenin kaç parçaya bölündüğünü ifade eden değer için.

Toplama seviyelerinde, anahtarları X olan bir düğümü düşünelim; burada |X| = m, unit u ve fanout s olsun. Verilen bir h: X → [m] karma fonksiyonunun geçerli bir bölme olup olmadığını kontrol etmek için aşağıdaki algoritma kullanılır:

  1. A dizisini başlat; bu dizi her biri sıfıra eşit s kelimeden oluşur. A içindeki değerlere sayımlar denir.
  2. Her x ∈ X için A[⌊h(x) / u⌋] değerini bir artır.
  3. h fonksiyonu ancak ve ancak tüm i ∈ [s − 1] için A[i] = u ise geçerli bir bölmedir.

Karma fonksiyonu doğrudan [s] aralığında bir değer üretmez; çünkü bu durumda bir anahtarın herhangi bir alt düğüme hash edilme olasılığı tüm alt düğümler için aynı olurdu. Ancak son alt düğüm u'dan daha küçük olabilir ve belirli bir karma fonksiyonunun geçerli bir bölme olma olasılığını en üst düzeye çıkarmak için bu durum olasılıklara yansıtılmalıdır. Bu, [m] aralığına hash edilip ardından 2. adımda u'ya bölünerek sağlanır. A dizisindeki son sayımı kontrol etmeye gerek yoktur; çünkü diğer tüm sayımlar kontrol edildikten sonra değeri belirlenmiş olur.

5.6.1 Tamsayı Bölmesi

Genellikle tamsayı bölmesi, tamsayı çarpımından çok daha yavaş bir işlemdir. Ancak özellikle bölen derleme zamanında biliniyorsa, kaydırmalar, toplamalar ve çarpmalar kullanılarak hızlandırılabilir [59]. En basit durum, bölenin iki kuvveti olmasıdır, yani 2^j. Bu durumda işlem j bit sağa kaydırma ile değiştirilebilir. Diğer bölenler için

⌊x / y⌋ ≈ ⌊x · 2^q / y⌋

formülü kullanılabilir ve yuvarlama hatalarını önlemek için gerekli düzeltmeler derleme zamanında hesaplanabilir. Çalışma zamanında yalnızca çarpma, sağa kaydırma ve gerekli düzeltmeler yürütülür [27].

Neyse ki uygulamalarımızda gerekli olan tek bölme, yukarıdaki algoritmada unit u ile yapılan bölmedir ve bu değer derleme zamanı sabitidir. Bu nedenle iyi bir optimize edici derleyici bu işlem için verimli kod üretebilir.

bu bölme işlemini böyle optimize edilmiş bir komut dizisiyle değiştirecektir [59]. Assembly incelendiğinde bunun GPU uygulaması için de geçerli olduğu görülmektedir. SIMD uygulamasında hesaplamalar Vector Class Library tarafından yapılır [26]. Çoğu adımın derleme zamanında gerçekleştirilmesini sağlamak için bölen const_uint makrosu ile sarmalanmalıdır. Aksi halde Vector Class Library, mevcut vektör uzantısında bölme komutu bulunmayabileceği için tüm adımları çalışma zamanında gerçekleştirir [27].

Vector Class Library 64 bit tamsayı bölmesini desteklemez, ancak bizim yalnızca 32 bit bölmeye ihtiyacımız vardır. Ayrıca işaretsiz bölme işaretli bölmeden daha hızlıdır ve 16 bit bölme, 8 veya 32 bit bölmeden daha hızlıdır. Bizim durumda bölünen değer 32 bit işaretsiz bir tamsayıdır. Ancak bölünen değer maksimum kova boyutu olan 3000 ile sınırlı olduğu için 16 bit bölme kullanılabilir. Bunun için karma fonksiyonunun sonucu önce en anlamlı 16 bit kesilerek 16 bit kelimeler içeren bir vektöre dönüştürülür. Bu vektör bölme işleminde kullanılır ve daha sonra işleme devam edebilmek için lane başına 32 bite genişletilmelidir.

16 bit bölmenin kullanılması oluşturma süresini belirgin biçimde iyileştirmedi (bkz. Bölüm 6.4.5) ve bu nedenle nihai uygulamada kullanılmaz.

Sayım değerleri için bir dizi kullanmak SIMD sürümünde sorunludur. Her SIMD lane'in kendi dizisine ihtiyacı olur ve sayımları artırmak için maliyetli gather ve scatter komutları gerekir. Bu sorun, sayımları vektör kayıtlarında saklayarak azaltılabilir. Bu tekniğin verimli kullanılabilmesi için önce her sayım için tek bir baytın yeterli olduğunu gösteririz.

Teorem 5.2. Verilen (u < 256) koşulu altında, (h)'nin geçerli bir bölme olup olmadığını doğru şekilde doğrulamak için her sayım için 8 bit yeterlidir.

Her kelimesi 8 bit olan A dizisinde (i ∈ [s − 1]) için (A[i] = u) olsun. İlk (s − 1) alt düğümün her birine hash edilen anahtar sayısının gerçekten (u) olduğunu göstermemiz gerekir. Her sayım değeri (u) olduğu halde gerçek sayıların farklı olmasının tek yolu bir taşma (overflow) olmasıdır.

(j ∈ [s − 1]) sayımında bir taşma olduğunu varsayalım. Değerler taşma durumunda başa sardığı ve (A[j] = u) olduğu için sayım (j)'nin gerçek değeri (u + 256z) olur; burada (z ≥ 1) bir tamsayıdır. Bu fazladan (256z) anahtar diğer sayımlara katkıda bulunamaz. Bu da başka bir sayımın geçerli bir bölmede olması gerekenden daha az anahtar içerdiği anlamına gelir. Ancak ilk (s − 1) sayımın her biri (u)'dur; yani gerçek değer en az (u)'dur. Potansiyel olarak bazı anahtarları eksik olabilecek tek alt düğüm son sayımdır; çünkü bu değer hiç kontrol edilmez. Ancak geçerli bir bölmede onun anahtar sayısı en fazla (u)'dur ve bu değer 256'dan küçüktür.

Fanout (s) ((2 ≤ s ≤ 9)) yaprak boyutuna, toplama seviyesine ve düğümün boyutuna bağlıdır. Karma fonksiyonu için 32 bit kullandığımızı hatırlayın. Her sayım için bir bayt yeterli olduğundan, bunları 32 bitlik bir kelime içinde paketleyerek tek bir vektörde lane başına dört sayım saklayabiliriz. Son sayım gerekli değildir; bu nedenle (s ≤ 5) için tek bir vektör yeterlidir, aksi halde iki vektör yeterlidir.

(j ∈ [s]) verildiğinde, (A[j]) sayımını artırabilmemiz gerekir. Bunun için şu dizi kullanılır:

[ B = [0, 0, 0, 0, 1, 2^8, 2^{16}, 2^{24}, 0, 0, 0, 0, 0]. ]

B içindeki her değer 32 bitlik bir kelimedir. Eğer (s ≤ 5) ise, paketlenmiş sayımlara (B[4 + j]) eklenerek (A[j]) artırılır. Her zamanki gibi bu işlem tüm SIMD lane'lerde paralel gerçekleşir ve her lane için (j) farklı olabilir. (B[4 + j]) değerinin, sayım (j)'nin başladığı konumda tek bir bit içerdiğine dikkat edin. Eğer (s = 5) ve (j = 4) ise son sayım önemli olmadığı için hiçbir sayım artırılmaz.

5.6.2 SIMD Uygulaması

Kanıt. Eğer (h) geçerli bir bölme ise ilk (s − 1) sayım doğru biçimde (u)'dur; çünkü taşma gerçekleşmez.

Eğer (s > 5) ise sayımlar için iki vektör gerekir. İlk vektör ilk dört sayımı, ikinci vektör kalan sayımları içerir. (j ∈ [s]) için ilk vektör, (B[4 + j]) eklenerek öncekiyle aynı şekilde işlenir. Eğer (j ≥ 4) ise hiçbir değişiklik olmaz. (B[j]) değeri ikinci vektöre eklenir. Eğer (j < 4) veya (j = 8) ise hiçbir değişiklik olmaz. Aksi halde doğru sayım artırılır.

Teorem 5.2'nin bu yaklaşımın doğruluğunu kanıtlamak için yeterli olmadığını unutmayın. Bir sayım (j) taşma yaparsa (yani 256 değerine ulaşırsa), 256 artış tamamen kaybolmaz. Taşma yapan sayım, vektörlerden birinde lane'in dördüncü sayımı değilse (yani (j \notin {3, 7})), bir bit sonraki sayıma taşınır. Ancak bu durumda (j) için 256 artış kaybolur ve (j + 1) sayımına bir ek artış eklenir.

Biraz daha sıkı olan (u < 255) koşulu kullanıldığında aynı kanıtın bu durum için de uygulanabileceği açıktır; çünkü 255 artış kaybolur. Neyse ki (\ell ≤ 24) koşuluna sahibiz ve bu koşul ile yaprak boyutuna göre fanout hesaplayan formüllerden (s ≤ 9) sonucuna ulaşabiliriz. Dolayısıyla birinci toplama seviyesi için (u ≤ 24) ve ikinci toplama seviyesi için (u ≤ 9 · 24 = 216) olur.

B dizisindeki arama işlemi için Vector Class Library'nin lookup fonksiyonu kullanılır. (j ≤ 8) olduğundan B değerleri, bir dizide saklamaya kıyasla daha hızlı erişim için bir veya iki vektör içinde tutulur.

Tüm anahtarlar işlendiğinde, sonuncusu hariç tüm sayımların (u) olup olmadığını kontrol etmemiz gerekir. Bunun için geçerli bir bölmeyi temsil eden vektördeki 32 bitlik kelimenin/kelimelerin değeri önceden hesaplanır. Ardından en az bir lane'in geçerli bir bölme bulup bulmadığını belirlemek için yalnızca bir veya iki eşitlik kontrolü ve bir horizontal_or işlemi yeterlidir.

Geçerli bir bölme (h) bulunduğunda anahtarların sıralanması gerekir; böylece ilk (u) anahtar (h) tarafından ilk alt düğüme, sonraki (u) anahtar ikinci alt düğüme vb. hash edilir. Bu, her kovadaki (alt düğüm) eleman sayısının önceden bilindiği bir bucket sort biçimidir.

Önce, her alt düğümde bir sonraki anahtarın konumunu gösteren C dizisi şu değerlerle başlatılır:

[ 0, u, 2u, \ldots, (s − 1)u. ]

Daha sonra yeniden dağıtılacak bir sonraki anahtarlarla iki vektör yüklenir. Bu vektörler, karşılık gelen alt düğümleri hesaplamak için Bölüm 5.3.1'deki gibi işlenir. Aynı fonksiyon vektörü işlemek için kullanılsa da kavramsal olarak farklı bir işlem gerçekleştiğine dikkat edin. Burada aynı karma fonksiyonu aynı anda birden fazla anahtara uygulanır; oysa bölme ararken aynı anahtara aynı anda farklı karma fonksiyonları uygulanır.

Elde edilen hash değerleri daha sonra sıralı olarak işlenmek üzere bir diziye yazılır. Her anahtar, anahtarın hash değeri olan (i) için geçici bir dizide (C[i]) konumuna yerleştirilir. Bir sonraki anahtar işlenmeden önce (C[i]) artırılır. Bu işlem sıralıdır; çünkü vektördeki birkaç anahtar aynı alt düğüme hash edilebilir. Bu durumda aynı konum birkaç kez artırılır ve anahtarların farklı konumlara yerleştirilmesi gerekir. Bunu SIMD ile gerçekleştirmek kolay değildir.

Anahtarlar iki vektöre yüklenirken, yeterli anahtar kalmamış olsa bile her iki vektör de tamamen doldurulur. Bu durumda diğer düğümlerden anahtarlar veya dolgu verisi yüklenir. Bu bir sorun değildir; son gerçek anahtar işlendiğinde işlem durdurulur. Daha sonra geçici dizi kovaya kopyalanır.

Yaprak seviyesinde olduğu gibi GPU'daki toplama seviyeleri de her bölme için bir thread block kullanır. Geçerli bir bölme bulma işlemi SIMD uygulamasına benzer şekilde çalışır. Her thread'in kendi c değişkenine sahip olduğu bir c kelimesi sıfırla başlatılır. Eğer fanout (s) en fazla beş ise c 32 bit içerir, aksi halde 64 bit içerir. Tüm sayımlar c içinde paketlenir ve her sayım bir bayt kullanır.

SIMD uygulamasından farklı olarak burada bir arama tablosu kullanılmaz; çünkü bu kullanım için bellek çok yavaştır. Bunun yerine sayım (j) ((j ∈ [s])) önce sekiz ile çarpılır, ardından 1-bit bu değer kadar sola kaydırılır ve c'ye eklenir:

[ c \leftarrow c + (1 << (j << 3)). ]

Eğer (s = 5) ve (j = 4) ya da (s = 9) ve (j = 8) ise kaydırma miktarı sırasıyla 32 veya 64 bittir. Bu durumda c'ye eklenecek hesaplanan değerin sıfır olması gerekir. Ancak CUDA tanımı bunu garanti etmez. Bu davranışı sağlamak için (s = 5) ve (s = 9) durumları birbirinden ve diğer durumlardan biraz farklı ele alınır.

Eğer (s = 5) ise bir funnel shift kullanılır; özellikle _funnelshift_lc intrinsic'i [4]. Bu işlem üç adet 32 bit argüman alır. İlk iki argüman birleştirilerek 64 bitlik bir kelime oluşturulur; burada ilk argüman en az anlamlı bitleri, ikinci argüman ise en anlamlı bitleri temsil eder. Üçüncü argüman bu 64 bit değerin sola kaç bit kaydırılacağını belirtir. Sonuç, kaydırılmış değerin en anlamlı 32 bitidir. 32 bit veya daha fazla kaydırma işlemi, 32 bit kaydırmaya eşit olarak tanımlıdır; yani ilk argüman döndürülür. Bu nedenle istenen sonuç şu şekilde elde edilebilir:

[ c \leftarrow c + _funnelshift_lc(0, 1, j << 3). ]

(s = 9) için kaydırma miktarının 64 bit olup olmadığını kontrol eden ek bir dallanma bulunur.

Paylaşılan Bellek Kullanarak Alternatif Uygulama

Farklı bir yaklaşım olarak sayımlar paylaşılan bellekte saklanabilir. Her thread, sayımları içeren A dizisi olarak kullanabileceği paylaşılan belleğin bir bölümünü alır. Teorem 5.2 kullanılarak her sayım için bir bayt kullanılır.

Paylaşılan belleğin 32 banktan oluştuğunu hatırlayın. Her bank yuvası 32 bit içerir. Farklı thread'lerin sayımları arasına dolgu eklenir; böylece her thread'in ilk sayımı bir bankın başlangıcında yer alır.

Bu nedenle (s ≤ 4) ise belirli bir thread'in tüm sayımları tek bir bank içinde bulunur. Bu durumda bank çakışması oluşmaz. Eğer (5 ≤ s ≤ 8) ise her thread sayımları saklamak için iki bank kullanır. Bu durum bazı zamanlarda bank çakışmalarına yol açabilir.

İlk olarak, sayımlar sıfıra başlatıldığında her seferinde (s) adet iki yönlü bank çakışması meydana gelir. Warp içindeki indeksi (i) olan thread ((i < 16)) ile indeksi (i + 16) olan thread aynı iki bankı kullandığından, her sayım sıfıra ayarlandığında bir bank çakışması oluşur. Bank çakışmalarının sayısı ve toplam iş miktarı, her baytı ayrı ayrı sıfırlamak yerine her bank yuvasını 32 bitlik bir tamsayı olarak ele alıp sıfıra ayarlayarak azaltılabilir. Bu yöntem başlatma başına bank çakışması sayısını ikiye düşürür.

Bir diğer çakışma, geçerli bir bölme bulunup bulunmadığını kontrol ederken oluşur. Başlatmada olduğu gibi her seferinde (s) adet iki yönlü bank çakışması meydana gelir. Yine her bankı 32 bitlik bir tamsayı olarak ele almak ve geçerli bir bölmeyi temsil eden bank değerlerini önceden hesaplamak, bank çakışmalarının sayısını ve toplam işi azaltabilir. Kalan bank çakışması sayısı yine ikidir.

Son çakışma, her sayaç artırıldığında ortaya çıkar. Bu durumun her seferinde bir banka çakışmasına yol açacağı garanti değildir. Ancak bir warp içindeki (i) ve (i + 16) iş parçacıklarından ikisinin de birinci bankaya ya da ikisinin de ikinci bankaya erişmesi olasılığı oldukça yüksektir. Örneğin, eğer (s = 8) ise her iki banka için olasılık eşittir. Her iş parçacığı için hangi sayaca erişildiğinin sözde rastgele olduğunu hatırlayın. Dolayısıyla belirli bir iş parçacığı çifti ((i, i + 16))'nin bir banka çakışmasına yol açma olasılığı %50'dir. Bir warp başına bu tür 16 çift bulunduğundan, bir warp'ın bir sayacı yüklerken veya saklarken banka çakışmasına yol açma olasılığı %99.99'dan fazladır.

Bir sayacı artırmak için önce paylaşılan bellekten yüklenmesi, artırılması ve ardından tekrar paylaşılan belleğe yazılması gerekir. Bu, bir sayaç artırıldığında (neredeyse) her seferinde iki adet iki yönlü banka çakışması olduğu anlamına gelir.

Figure 5.1

Sayaçların bankalara atanmasını gösterir. Soldaki şekil, iş parçacığı başına iki banka kullanıldığında ortaya çıkan durumu; sağdaki şekil ise iş parçacığı başına üç banka kullanıldığında ortaya çıkan durumu göstermektedir. Gösterim amacıyla, warp başına yalnızca 8 iş parçacığı ve 8 banka varsayılmıştır.

Her sütun, üst kısmında banka numarası bulunan bir bankayı temsil eder. Her banka yuvası, iş parçacığı kimliği ve ardından o iş parçacığının banka numarası ile etiketlenmiştir; yani 2-1, 2 numaralı iş parçacığının ikinci bankasının banka yuvasıdır (sıfırdan başlayan indeksleme). Her iş parçacığı aynı anda birinci (ya da ikinci veya üçüncü) bankasına erişirse banka çakışması oluşmaz; çünkü her sütundaki ikinci sayı, aynı sütundaki diğer sayılardan farklıdır.

Neyse ki ilk iki durumda banka çakışmaları, warp başına ilk 16 iş parçacığından sonra dolgu (padding) kullanılarak tamamen önlenebilir. Bu dolgu, kullanılmayan tek bir bankadan oluşur. Bunun etkisi şudur: Bir warp'ın ilk yarısındaki bir iş parçacığının birinci bankası, warp'ın ikinci yarısındaki bir iş parçacığının ikinci bankası ile aynı bankadır ve bunun tersi de geçerlidir.

Her iş parçacığı birinci bankasına eriştiğinde, her biri toplam 32 bankanın farklı birine erişir. Örneğin, iş parçacığı 0 banka 0'a, iş parçacığı 16 banka 1'e, iş parçacığı 1 banka 2'ye vb. erişir. Dolayısıyla başlatma sırasında ve bir bölmenin bulunup bulunmadığı kontrol edilirken banka çakışmaları oluşmaz.

Görselleştirme için Figure 5.1a'ya bakın.

Dolgu kullanımı, bir sayaç artırılırken banka çakışması olasılığını da azaltabilir. Örneğin (s = 5) durumunu ele alalım. İki paragraf önceye benzer bir analiz yapıyoruz. Eğer dolgu kullanılmazsa, bir warp içindeki belirli bir iş parçacığı çifti ((i, i + 16))'nin banka çakışmasına yol açma olasılığı (4/5)'tir. Dolayısıyla bir warp içindeki 16 iş parçacığı çiftinden herhangi birinin banka çakışmasına yol açma olasılığı %99.99999'dan fazladır.

Dolgu kullanıldığında olasılıklar değişir. Belirli bir iş parçacığının birinci bankasına erişme olasılığı hâlâ (4/5)'tir; ancak aynı bankayı kullanan diğer iş parçacığı için bu onun ikinci bankasıdır ve dolayısıyla (1/5) olasılıkla erişilir. Bu nedenle (i < 16) olan belirli bir (i) iş parçacığının banka çakışması yaşama olasılığı şöyledir:

[ 2 \cdot \left(\frac{4}{5} \cdot \frac{1}{5}\right) = 0.32. ]

Buna bağlı olarak bir warp'ın banka çakışmasına yol açma olasılığı:

[ 1 − (1 − 0.32)^{16} \approx 0.998. ]

Tartışmalı olarak, dolgusuz sürüme göre fark ihmal edilebilir düzeydedir. Ancak bu, dolgunun en azından durumu kötüleştirmediğini gösterir.

Eğer (s = 9) ise, her iş parçacığı sayaçları saklamak için üç banka kullanır. Banka çakışmalarını önlemek için (her iş parçacığının ilk sayacının bir bankanın başlangıcında başlamasını sağlayan dolgu dışında) ek bir dolgu gerekli değildir. Bunun nedeni, 32 (toplam banka sayısı) ile 3'ün (her iş parçacığının kullandığı banka sayısı) aralarında asal olmasıdır. Görselleştirme için Figure 5.1b'ye bakın.

Banka çakışmalarının ortaya çıkabileceği tek durum, bir sayacın artırılmasıdır. Ancak bu durumdan kaçınılamaz. Ne yazık ki bu durumda üç yönlü banka çakışmaları bile mümkündür; ancak dolgu kullanmamak yapabileceğimiz en iyi seçenektir çünkü bu, 32 bankanın her biri için 32 iş parçacığından tam olarak birinin üçüncü bankasının o banka olmasını garanti eder.

5.6 Aggregation Levels

5 Implementation

Genel olarak, yukarıda belirtilen tüm optimizasyonlar uygulandıktan sonra tüm yapı içinde banka çakışmalarının oluşabileceği tek yerler şunlardır: toplama seviyelerinde bir sayaç artırılırken (eğer s > 4), geçerli bir bölme veya birebir eşleme bulunduğunda sonuç içine hash fonksiyonu kimliğinin atomik olarak yazılması sırasında (bu nadiren gerçekleşir) ve geçerli bir bölme veya birebir eşleme bulunduğunda anahtarları yeniden dağıtmak için konumlara atomik erişim yapılırken (bir sonraki paragrafa bakın).

Buna rağmen deneyler, sayaçları paylaşılan bellekte saklamanın, tüm sayaçları paketlenmiş biçimde içeren tek bir 32 veya 64 bitlik sözcük kullanmaktan daha yavaş olduğunu göstermektedir; bkz. Bölüm 6.5.3. Bunun nedeni kaçınılmaz banka çakışmaları ve paylaşılan belleğin genel olarak yazmaçlardan daha yavaş olmasıdır. Bu nedenle, nihai uygulamamızda sayaçlar paylaşılan bellekte saklanmamaktadır.

Geçerli bir bölme h bulunduğunda, anahtarlar çocuk düğüm numaralarına göre sıralanmış biçimde tekrar global belleğe yazılır. Bunun için

C ← [0, u, 2u, ..., (s − 1)u]

boyutu s olan bir dizi başlatılır. Her iş parçacığı, iş parçacığı indeksinin gösterdiği kovadaki konumdan (varsa) anahtarı paylaşılan bellekten yükler, çocuk düğüm numarasını hesaplar, C içindeki karşılık gelen sayacı atomik olarak okur ve artırır ve anahtarı sayacın gösterdiği konumda global belleğe yazar. Bu işlem, kovaya ait son anahtara ulaşılana kadar son indekse iş parçacığı bloğundaki iş parçacığı sayısı eklenerek sonraki anahtarlar için tekrarlanır.

Bir iş parçacığı bloğundaki tüm iş parçacıkları C içindeki aynı s sayacına eşzamanlı eriştiğinden, yüksek düzeyde çekişme beklenir. Bu sorun warp-aggregated atomics [10] kullanılarak hafifletilebilir. Bu teknikte, bir warp içindeki iş parçacıkları her sayacı kaç iş parçacığının artırdığını hesaplar. Ardından sayaç başına yalnızca bir iş parçacığı sayacı hesaplanan miktar kadar atomik olarak artırır. Bu, gerekli atomik işlem sayısını önemli ölçüde azaltır. Her iş parçacığı için doğru konum daha sonra, eski değerin ilgili sayaç için her iş parçacığına yayınlanması ve sayaçla ilişkili iş parçacıkları grubundaki iş parçacığının indeksinin eklenmesiyle hesaplanır.

Bu teknik cooperative groups [9] kullanılarak oldukça kolay uygulanabilir. Her iş parçacığı 0'dan s − 1'e kadar olan değerler üzerinde yineleme yapar ve değerin mevcut anahtarın çocuk düğüm numarasına eşit olup olmadığını kontrol eder. Bu durumun gerçekleştiği yinelemede, aynı warp içindeki ve aynı çocuk düğüm numarasına sahip tüm iş parçacıkları birlikte gruplanır; yani diğer tüm iş parçacıkları pasifken bu iş parçacıkları aktiftir.

1 Tam olarak söylemek gerekirse, aynı çocuk düğüm numarasına sahip tüm iş parçacıklarının aktif olması gerekmez. Ayrışmış olabilirler; bu durumda aynı atomik işlem aynı warp tarafından tek bir yineleme içinde birkaç kez artırılabilir [11].

Ancak warp-aggregated atomics yapım süresini iyileştirmez; bkz. Bölüm 6.5.4. Bunun nedeni, Nvidia geliştirici blogunda [10] belirtildiği gibi, NVCC derleyicisinin güncel sürümlerinin bazı durumlarda uygun olduğunda warp-aggregated atomics uygulamasını otomatik olarak yapmasıdır. NVCC tarafından üretilen kod, elle yazılmış koda göre daha hızlıdır. Bu nedenle warp-aggregated atomics tekniği uygulamamızda açıkça kullanılmamıştır. Yan not olarak, testler sayaçlar 32 bit yerine 64 bit sözcükler olduğunda elle yazılmış kodun daha hızlı göründüğünü göstermiştir. Ancak bu durum uygulamamız açısından önemli değildir.

Key Redistribution

5.7 Higher Levels

Daha üst seviyeler, yani iki toplama seviyesinin üzerindeki bölmeler, nispeten basittir. Fan-out her zaman ikidir. Bu nedenle sayaçları saklamak için bir dizi gerekli değildir. Buna rağmen orijinal RecSplit uygulaması [13] boyutu iki olan bir dizi kullanır.

|X| = m olan X anahtarları, birim u (ilk çocuk düğüme hashlenmesi gereken anahtar sayısı) ve h: X → [m] hash fonksiyonu verildiğinde, h fonksiyonunun geçerli bir bölme olup olmadığını kontrol etmek için aşağıdaki algoritma kullanılır:

  1. Her biri sıfıra eşit iki sözcükten oluşan A dizisini başlat. A içindeki değerlere counts denir.
  2. Her x ∈ X için, h(x) ≥ u ifadesi doğruysa bir, değilse sıfır olacak şekilde A[h(x) ≥ u] değerini bir artır.
  3. h fonksiyonu ancak ve ancak A[0] = u ise geçerli bir bölmedir.

İki sayacı saklamak için bir dizi kullanmak yerine SIMD ve GPU uygulaması yalnızca h(x) değeri u'dan küçükse artırılan tek bir sayaç c kullanır.

Genellikle “true” mantıksal değeri bir ile, “false” mantıksal değeri ise sıfır ile kodlanır. Bu durum, h(x) ile u karşılaştırmasının sonucuna bağlı olarak bir dallanma kullanmadan sayaç c'yi koşullu olarak artırmak için kullanılır. Ancak Vector Class Library içinde “true” mantıksal değeri yalnızca 1-bitlerinden oluşan bir sözcük olarak kodlanır. Bu, iki'nin tümleyeni gösteriminde −1'i temsil eder. Dolayısıyla tüm anahtarlar işlendiğinde ancak ve ancak c = −u ise h hash fonksiyonu geçerli bir bölmedir.

Karışıklığı önlemek için, alışılmış bir yerine negatif bir değerin eklenmesi işlemi Vector Class Library'nin if_add fonksiyonu kullanılarak açıkça belirtilir [27]. Bu fonksiyon ilk argüman olarak koşulu alır ve koşul doğruysa üçüncü argümanı ikinci argümana ekler; aksi halde ikinci argümanı değiştirmeden döndürür. Sayaç şu şekilde artırılır:

c ← if_add(h(x) < u, c, −1)

Ortaya çıkan makine kodu, koşulu doğrudan c'ye eklemekle aynıdır. if_sub kullanarak bir çıkarmak veya if_add ile bir ekleyip daha sonra u ile karşılaştırmak gibi diğer uygulamalar daha karmaşık makine kodu üretmiştir.

Anahtarların yeniden dağıtımı toplama seviyelerine benzer şekilde çalışır. Ancak hash fonksiyonu uygulanıp değer u ile karşılaştırıldıktan sonra sonuç sıfır veya bir değil, sıfır veya eksi birdir. Bu değer kullanılarak anahtarın geçici dizide doğru konuma yazılması sırasında bunun dikkate alınması gerekir.

Karşılaştırmanın tam sonucunu daha sonra işlenmek üzere bir dizide saklamak yerine, değerler Vector Class Library'nin to_bits fonksiyonu kullanılarak her lane için tek bir bite indirgenir. Bunun nedeni, Vector Class Library'nin mantıksal bir vektörün bir dizi içinde saklanmasına izin vermemesidir. Sonuç, yalnızca koşul doğruysa bir olan ve her lane için bir bit içeren bir d sözcüğüdür.

Şu anda işlenen vektördeki her anahtar için sıfır veya bir elde etmek üzere bu sözcüğün bitleri üzerinde yineleme yapılır; bu değer anahtarın birinci mi yoksa ikinci çocuk düğüme mi hash edildiğini gösterir. j yinelemesinde bit şu şekilde hesaplanır:

(d >> j) & 1

Bölüm 4.3, bir bölme ağacının yapısını açıklar ve örnek olarak Figure 4.1'i verir; bu şekil Figure 5.2a'da tekrar gösterilmiştir. Dikkatle bakıldığında ağacın mümkün olduğunca dengeli olmadığı görülür. Kök bölmenin sağ çocuğu, herhangi bir özelliği ihlal etmeden 96 ek anahtar alabilir. Sonuç Figure 5.2b'de gösterilmiştir.

Bölme sayısı da alt seviyelerdeki hiçbir şey de değişmemiştir. Değişen tek şey, üst seviyelerdeki iki bölmedir. Aşağıda, dengeli bölmelerin neden yararlı olduğunu göstermek için bu özel örneği analiz ediyoruz; bu durum sezgisel olarak da anlamlıdır.

5.7.1 SIMD Implementation

5.7.2 Balanced Splittings

Original Splitting Tree

(a) Orijinal RecSplit uygulamasında [13] kullanılan özgün bölme ağacı. Bu, Figure 4.1 ile aynı çizimdir.

Balanced Splitting Tree

(b) GPU ve SIMD uygulamasında kullanılan dengeli bölme ağacı.

Figure 5.2: Yaprak boyutu ℓ = 8 olan ve 202 anahtar içeren dengesiz (üstte) ve dengeli (altta) bölme ağacı. Her düğüm içerdiği anahtar sayısı ile etiketlenmiştir.

Alan tüketimi incelendiğinde (Bölüm 4.4.1'de tartışıldığı gibi), bölme ağaçlarının alan tüketimi her bölme/birebir eşleme başına yaklaşık iki bitlik bir kayıp dışında optimaldir. Bölme ve birebir eşleme sayısı değişmediği için kullanılan bit sayısının beklenen değeri önemli ölçüde değişmemelidir.

Gerçekten de Bölüm 4.3.1'deki formüller kullanıldığında, kök için geçerli bir bölme bulmak amacıyla denenmesi gereken hash fonksiyonlarının beklenen sayısı özgün bölme ağacı için 7.728, dengeli ağaç için 17.791'dir; üst seviyedeki diğer bölme ise ortalama olarak sırasıyla 17.366 veya 7.544 deneme gerektirir. Bu, dengeli ağacın kök bölmesi için yaklaşık 2.302 kat daha fazla deneme gerektirdiği, ancak özgün ağacın diğer bölme için yaklaşık 2.302 kat daha fazla deneme gerektirdiği anlamına gelir. Deneme sayısı alan tüketimini belirlediğinden, dengeli ağacın yaklaşık aynı alanı kullanması beklenir.

Yapım süresi açısından bakıldığında dengeli ağaç daha iyidir. Maliyet metriği olarak hash fonksiyonu değerlendirmelerinin beklenen sayısını kullanıyoruz.

Dolayısıyla dengeli ağaç daha hızlı oluşturulabilir. Ancak bu fark pratikte oldukça küçüktür.

En büyük iyileşme sorgu süresinde görülür. Dengeli bölme, değerlendirilmesi gereken ortalama bölme sayısını azaltabilir. Böyle bir bölme ağacı içeren bir kovadan rastgele bir anahtar düşünelim.

Bu, bu özel bölme ağacı için ortalama olarak 0.4 hash fonksiyonu değerlendirmesi tasarruf edilebileceği anlamına gelir. Elbette somut sayılar bölme ağacına, yani anahtar sayısına ve ℓ değerine bağlıdır. Deneyler analizi doğrulamaktadır (bkz. Bölüm 6.3.3).

Üst seviyelerdeki dengeli bölmeler ek herhangi bir hesaplama olmadan uygulanabilir.

Üst seviyelerde m anahtar içeren bir bölmeyi ele alalım. η, ikinci toplama seviyesindeki tam bir düğümün anahtar sayısı olsun; önceki örnekte bu değer 96'dır. RecSplit'in özgün uygulamasında [13], sol çocuğun anahtar sayısı şu şekilde hesaplanır:

⌈m / 2⌉ değeri η'nin bir sonraki katına aşağı doğru yuvarlanır.

Eğer ⌈m / 2⌉ değeri η'nin bir katından biraz daha büyükse, bölme oldukça dengesiz olur. Dengeli bir bölme, η'nin bir sonraki katına aşağı veya yukarı yuvarlanarak elde edilebilir. Bu, değiştirilmiş formül ile mümkündür.

η'nin derleme zamanı sabiti olduğunu unutmayın. Dolayısıyla özgün formüldekiyle tamamen aynı işlemler yapılır; yalnızca (m >> 1) değerine başka bir sabit eklenir.

5.8 CPU Parallelization

Bir bölme ağacının bölmelerini ve birebir eşlemelerini bulmak için gerekli tüm adımları gördük; bu genellikle yapım sürecinin en fazla zaman alan kısmıdır. Özgün RecSplit uygulaması [13] yalnızca tek bir iş parçacığı kullanır. Bu durum, çoğu modern işlemcinin birden fazla işlem çekirdeği içermesi nedeniyle önemli miktarda işlem gücünün kullanılmadan kalmasına yol açar.

Orijinal RecSplit makalesinde belirtildiği gibi, RecSplit’i paralelleştirmek oldukça kolaydır çünkü farklı kovalar için bölme ağaçlarının oluşturulması tamamen birbirinden bağımsızdır. SIMDRecSplit’i paralelleştirmek için birden fazla iş parçacığı başlatıyor ve kovaların ardışık bir bölümünü her bir iş parçacığına atıyoruz. Her iş parçacığının girdideki ilk kovasının başlangıcını bilmesi gerekir; bu bilgi, girdinin counting sort ile sıralanmasının ardından (bkz. Bölüm 5.1) zaten sağlanmaktadır.

Kendi kovalarını işlemeyi bitirene kadar tüm iş parçacıkları tamamen birbirinden bağımsız çalışır; herhangi bir senkronizasyona gerek yoktur. Ancak bir bölme veya bijeksiyon bulunduğunda bunun Rice Bit Vector içinde saklanması gerekir. Senkronizasyondan kaçınmak için her iş parçacığı kendi yerel Rice Bit Vector’ünü kullanır ve girdisini sanki tüm girdi buymuş gibi ele alır. Bu, her kovası için bit sayısının ön ekini karşılık gelen P dizisinde sakladığı anlamına da gelir. Double Elias-Fano representation hesaplanmadan önce P içindeki değerlerin düzeltilmesi gerekir.

Bir iş parçacığı tüm kovalarını işledikten sonra kritik bölgeye girmeye çalışır. Aynı anda kritik bölgede yalnızca bir iş parçacığının bulunmasına izin verilir. Ayrıca iş parçacıklarının kritik bölgeye iş parçacığı kimliklerinin sırasına göre girmesi sağlanır.

İlk iş parçacığı yalnızca kendi yerel Rice Bit Vector’ünü uygun işaretçileri doğru şekilde ayarlayarak global Rice Bit Vector içinde saklar. Diğer iş parçacıkları ise kritik bölgede kendi yerel Rice Bit Vector’lerini global Rice Bit Vector’ün sonuna ekler. Kritik bölgeden çıktıktan sonra P içindeki değerlerini düzeltirler.

P içindeki tüm değerlerine önceki iş parçacığının son değerini (Double Elias-Fano representation’dan elde edilebilir) ekleyerek bu düzeltmeyi gerçekleştirirler.

Kritik bölüm bir mutex ve bir koşul değişkeni kullanılarak gerçekleştirilir. Kritik bölgeye girmek için mutex, C++ Standard Library’deki std::lock_guard [18] kullanılarak kilitlenir. Bu işlem, çağıran iş parçacığını başka bir iş parçacığı kritik bölgede olmadığı ana kadar bekletir, mutex’i kilitler ve std::lock_guard kapsam dışına çıktığında mutex’i otomatik olarak serbest bırakır. İlk iş parçacığı dışında tüm iş parçacıkları mutex’i kilitledikten sonra koşul değişkenini kullanarak sıranın kendilerinde olup olmadığını kontrol eder; yani önceki tüm iş parçacıklarının kritik bölümü tamamlayıp tamamlamadığını denetler. Bu, paylaşılan bir o tamsayısının iş parçacığının kendi kimliğini içerip içermediğini kontrol ederek basitçe uygulanır. Eğer sıra henüz o iş parçacığında değilse, bildirim gelene kadar koşul değişkeni tarafından engellenir. Rice Bit Vector kritik bölgede saklandıktan veya eklendikten sonra her iş parçacığı o değerini artırır ve koşul değişkenini kullanarak bekleyen iş parçacıklarını bilgilendirir.

GPU uygulaması da bu CPU paralelleştirme biçimini kullanır. Bu, darboğazın çoğunlukla CPU tarafında olduğu durumlarda yararlıdır. CPU veriyi hazırlamaktan, kernel’leri başlatmaktan ve sonuçları Rice Bit Vector içinde kodlamaktan sorumludur. Küçük yaprak boyutu, küçük kova boyutu veya birden fazla güçlü GPU’nun yavaş bir CPU ile birlikte kullanılması durumunda CPU darboğaz olabilir. Ancak performans üzerindeki genel etkinin küçük olduğu görülmektedir. GPU uygulaması esas olarak nispeten büyük yaprak ve kova boyutları için faydalıdır (bkz. Bölüm 6.6.1). Bu nedenle CPU paralelleştirmesinin GPU uygulamasının oluşturma süresi üzerindeki etkisi deneylerle resmi olarak değerlendirilmemiştir.

Tüm kovalar tamamlandıktan sonra Double Elias-Fano representation [45, 47, 46] oluşturulur (bkz. Bölüm 4.5). Bu yapı, her kovadaki anahtar sayısının ön ekini ve her kovayı Rice Bit Vector içinde başlatan bit konumunu içerir. Bu yapı dört döngü içerir ve bunların tümü önemli ölçüde iyileştirilebilir.

İlk döngü, dizilerdeki ardışık iki değer arasındaki farkların minimumunu (δλ ve δψ) hesaplar. Bu işlem SIMD kullanılarak hızlandırılabilir.

İkinci döngü değerleri üç farklı bit dizisinde saklar: alt bitler dizisi ve iki üst bit dizisi. Bu döngü için SIMD kullanmak çok daha karmaşıktır çünkü her değer için yalnızca bir kelimenin bir kısmı değiştirilmelidir. Bu nedenle ardışık değerler için aynı kelimeye erişilebilir. Döngü doğrudan vektörleştirilirse bilgi kaybı meydana gelebilir. Bununla birlikte döngü, SIMD’den fayda sağlayabilecek başka işlemler de içerir (kaydırmalar, maskelerin uygulanması, indeks hesaplama vb.). Vektörleştirilemeyen kısımlar ise seri olarak yürütülür.

Üçüncü döngü, anahtar sayısının prefix sum’ı için jump dizisini hesaplar. Bu dizi, üst bit dizilerine erişimi hızlandırmak için seçim veri yapısı olarak kullanılır. κ kova sayısı olsun. Döngü, prefix sum için üst bit dizisindeki her bit üzerinde yineleme yapar. Bölüm 4.5.2’de türetilen formüller ve deneysel gözlemlere göre bu dizi yaklaşık 2κ ile 3κ bit içerir. Tam olarak κ bit 1 olarak ayarlanmıştır. Eğer bir bit ayarlanmış değilse herhangi bir işlem yapılmasına gerek yoktur. Bu durum çok sayıda dal tahmin hatasına yol açabilir. Ayrıca her 256’ncı 1-bit dışında gerçek bir işlem yapılması gerekmez (bitin kontrol edilmesi ve bir sayacın artırılması dışında).

Her biti kontrol etme gibi gereksiz işlem, 256 adet 1-bit bulunana kadar 64-bit değerler üzerinde popcount kullanılarak önlenebilir. Ardından 256’ncı bitin tam konumunun hesaplanması gerekir. Seçim algoritması (bkz. Bölüm 2.1), 256’ncı 1-bit’i içeren 64-bit kelime üzerinde uygulanarak bu amaçla kullanılabilir. Hesaplanan değer jump dizisini ayarlamak için kullanılabilir. Dördüncü döngü tam olarak aynı yapıya sahiptir ve bit konumları için jump dizisini hesaplar. Aynı şekilde optimize edilebilir. Bu optimizasyonların sonucu Bölüm 6.3.4’te gösterilmiştir.

5.9 Double Elias-Fano

5.10 GPU Uygulaması – Genel Bakış

Artık GPU kullanarak girdinin minimal perfect hash function’ını hesaplama prosedürünü açıklamak için gerekli tüm yapı taşlarına sahibiz. İlk olarak girdi, Bölüm 5.1’de açıklandığı şekilde sıralanır ve 64-bit anahtarlar içeren A dizisi ile her kovayı A içinde başlatan konumları gösteren başka bir dizi elde edilir. Daha sonra ana makinede (host) ve aygıtta (device) geçici olarak 128 kovayı ve ortaya çıkan hash fonksiyonu kimlik numaralarını saklayacak kadar alan ayırırız.

Ana makine tarafındaki bellek, host ile device arasında eşzamanlı olmayan veri aktarımına izin vermek için pinned (page-locked olarak da adlandırılır) bellek olarak ayrılmalıdır. Ayrıca device’a aktarılacak tampon olarak kullanılan bellek write-combining bellek olarak ayrılır. Bunun, veri yolu gözetimini (bus snooping) önleyerek daha hızlı aktarım sağlaması beklenir. Bu durum burada uygundur çünkü host bu belleğe yalnızca yazma işlemi yapar [3].

Device üzerindeki bellek tek bir blok halinde ayrılır. Orijinal RecSplit uygulamasında [13] olduğu gibi, bir kovadaki maksimum anahtar sayısının 3000 olduğunu varsayıyoruz. Bu sayı aynı zamanda tek bir kovadaki bölme ve bijeksiyon sayısının, yani saklanacak hash fonksiyonlarının sayısının da üst sınırıdır. En yüksek bölme ve bijeksiyon sayısı, bir kovada 3000 anahtar ve yaprak boyutu 2 olduğunda elde edilir.

Bu durumda bölme ağacının ikili bir ağaç olduğunu, yani her düğümün (yaprak düğümler hariç) iki çocuk düğüme sahip olduğunu unutmayın. k yaprak düğümü olan böyle bir ağaçta tam olarak 2k − 1 düğüm bulunur; bu durum tümevarım kullanılarak kanıtlanabilir. 3000 anahtar ve yaprak boyutu 2 için yaprak sayısı 1500’dür; bu da 2999 bölme ve bijeksiyon anlamına gelir. Her bölme ve bijeksiyon daha sonra Rice Bit Vector içinde kodlanmadan önce 64-bit değer olarak saklandığı için, kova anahtarları için ayrılan alan kadar yer ayırırız.

Genel olarak device üzerindeki global bellek tüketimi şöyledir:

2 × 128 × 3000 × 8 byte = 6,144,000 byte.

İlginç bir şekilde, Nvidia RTX 3090’un (deneylerimizde kullandığımız) L2 önbellek miktarı 6144 KiB’dir [17]. Bir KiB 1024 byte’a karşılık geldiği için mevcut L2 önbellek miktarı toplam tüketimden biraz daha büyüktür. Ayrıca kovalar çoğunlukla 3000 anahtardan daha küçük olduğu ve daha yüksek yaprak boyutlarında birleştirme seviyelerindeki fanout değerleri arttığından bölme ve bijeksiyon sayısı çok daha küçük olduğu için genellikle belleğin yalnızca bir kısmı kullanılır.

Uygulama 128 CUDA stream kullanır; yani en fazla 128 kova device’a gönderilmek, device tarafından işlenmek ve sonuçları host’a geri gönderilmek üzere işlem hattında bulunur. Her stream için host üzerinde kovayı tamponlamak amacıyla ilişkili bir pinned ve write-combined bellek bölgesi, sonuçları tamponlamak için host üzerinde bir pinned bellek bölgesi ve kovayı ile sonuçları saklamak için device üzerinde bir bellek bölgesi bulunur.

Host üzerindeki her iş parçacığı, kovalarını işlemek için stream’lerin bir kısmını kullanır. Stream’leri round-robin yöntemiyle sırayla dolaşır. Eğer bir stream henüz kullanılmamışsa CUDA runtime kullanılarak oluşturulur. Aksi halde iş parçacığı stream ile senkronize olur; yani stream içinde daha önce başlatılmış tüm işlemler tamamlanana kadar bekler. Ardından sonuçlar (kovanın bölme ağacındaki tüm bölme ve bijeksiyonların hash kimlik numaraları) ilgili tamponlarda bulunur ve Rice Bit Vector içinde kodlanabilir.

Stream oluşturulduktan veya onunla senkronize olunduktan ve sonuçlar kodlandıktan sonra iş parçacığı bir sonraki kovayı tampon içine kopyalar—eğer başka bir kova varsa. Ardından gerekli işlemleri stream’e başlatır. Bu işlemlerin tümü eşzamanlı değildir; yani çağıran iş parçacığına hemen kontrolü geri verir ve gerekli kaynaklar hazır olduğunda CUDA runtime tarafından yürütülür.

İlk işlem, kovayı içeren tamponun device belleğine aktarılmasıdır. Sonraki işlemler farklı kernel’leri başlatır. İlk olarak daha yüksek seviyeler başlatılır. Bu işlem özyinelemeli bir fonksiyonla yapılır. Eğer kovadaki boyut ikinci birleştirme seviyesinin düğüm boyutundan büyükse, aynı fonksiyon tekrar iki kez özyinelemeli olarak çağrılmadan önce bir üst seviye kernel başlatılır. Kernel tek bir thread block ile başlatılır ve tek bir bölmeyi hesaplar. Stream’ler donanımın yine de verimli kullanılmasına yardımcı olur. Her özyinelemeli çağrı için girişin boyutu, başlangıç indeksi, sonucun indeksi ve seviye (başlangıç seed’ini bulmak için) uyarlanır.

Orijinal uygulamada [13] böyle bir özyinelemeli fonksiyon tüm bölme ağacını oluşturmak için kullanılmıştır. Ancak yaprak seviyesi ve iki birleştirme seviyesi üst seviyelerden farklı ele alınır. Her tekil bölme/bijeksiyon için bir kernel başlatmak yerine, her seviye için o seviyedeki bölme/bijeksiyon sayısı kadar thread block içeren tek bir kernel başlatılır. Bu yaklaşım başlatma maliyetini azaltır ve CUDA GPU’larında eşzamanlı kernel sayısı sınırlı olduğundan kullanım oranını artırabilir [3]. Bu üç seviyede, seviyedeki tüm düğümler için düğüm boyutu ve başlangıç seed’inin sabit olduğunu unutmayın (gerekirse son düğüm için ek bir kernel başlatılabilir). Dolayısıyla bu üç seviye oldukça homojendir.

Buna karşılık üst seviyeler heterojendir. Aynı seviyedeki farklı düğümler için boyut farklı olabilir. Eğer üst seviyelerde her thread block farklı bir bölmeyi hesaplayan birden fazla thread block içeren kernel’ler kullansaydık, bu bilginin her thread block’a verilmesi gerekirdi. Aslında hangi düğümlerin aynı seviyenin parçası olarak görülebileceği bile net değildir çünkü bölme ağacı mükemmel dengeli olmayabilir; yani kökten yaprağa en kısa yolun uzunluğu farklı yapraklar için farklı olabilir. Ayrıca her iç düğüm en az iki çocuk düğüme sahip olduğundan üst seviyelerdeki düğüm sayısı genellikle alt seviyelere kıyasla küçüktür. Bu durum özellikle yüksek yaprak boyutlarında daha belirgindir; çünkü bu aynı zamanda birleştirme seviyelerinde yüksek fanout anlamına gelir. Bu nedenle üst seviyelerde her bölme için yalnızca tek bir blok kullanılır.

Yukarıda açıklandığı gibi en alt üç seviye, seviye başına bir veya iki kernel başlatılarak işlenir. Başlatılan kernel sayısının kova boyutuna ve yaprak boyutuna bağlı olduğunu unutmayın. Küçük bir kovada yalnızca tek bir yaprak olabilir ve dolayısıyla yalnızca tek bir kernel başlatılır. Ancak bu genellikle device’ın tamamını kullanmaya yetmez. Maksimum kullanım ve minimum ek yük için kova boyutu ve yaprak boyutu mümkün olduğunca büyük olmalıdır. Bu aynı zamanda en alan verimli MPHF sonucunu verir. Tüm kernel’ler stream içine başlatıldıktan sonra sonuç host’a aktarılmak üzere planlanır.

Hash fonksiyonu tanımlayıcılarının sonuç içinde saklanma sırası, kernel’lerin stream’e başlatılma sırasıyla ve her kernel için thread block’ların ilkinden sonuncusuna kadar olan sırayla aynıdır. Bu sıra Rice Bit Vector’ün beklediği sıradan farklıdır. Doğru sonuç elde etmek için değerler Rice Bit Vector içinde preorder biçiminde kodlanmalıdır; yani önce kök, ardından sol çocuk, onun sol çocuğu ve ilk yaprağa kadar devam eder, ardından ikinci yaprak kodlanır, birinci birleştirme seviyesindeki ikinci düğüm, onun ilk çocuğu vb. Bu tam olarak bölme ve bijeksiyonları özyinelemeli bir fonksiyonla hesapladığımızda elde ettiğimiz sıradır. Ancak biz özyinelemeli fonksiyonu yalnızca üst seviyeler için kullanırız.

Kalan seviyeler, üst seviyelerin sonuçlarından sonra breadth-first sırasıyla saklanır; yani önce ikinci birleştirme seviyesindeki tüm bölmeler ilk düğümden son düğüme kadar, ardından birinci birleştirme seviyesindeki tüm bölmeler ve son olarak yaprakların tüm bijeksiyonları. Sonuçları doğru şekilde açmak ve Rice Bit Vector içinde kodlamak için bu segmentlerin her birinin başlangıcı daha sonra kullanılmak üzere bir dizide kaydedilir. Sonuçları beklemek için stream ile senkronize olduktan sonra sonuçları açmak için özyinelemeli bir fonksiyon kullanılır. Bu kez özyineleme daha erken bitmez; yapraklarda sona erer. Bu fonksiyon, sonuçları doğru sırada kodlamak için her segmentin kaydedilmiş başlangıçlarını kullanır.

Bir iş parçacığı tüm kovalarını işledikten sonra Bölüm 5.8’de açıklandığı gibi diğer iş parçacıklarıyla senkronize olur. Tüm iş parçacıkları tamamlandıktan sonra CUDA device üzerinde ayrılan bellek serbest bırakılır. Son olarak, her kova için anahtar sayısını ve Rice Bit Vector içindeki bit sayısını prefix-sum biçiminde içeren hesaplanmış diziler kullanılarak Double Elias-Fano representation Bölüm 5.9’da açıklandığı şekilde oluşturulur.

Daha önce açıklandığı gibi girdi device’a kova kova aktarılır. Genel tavsiye, her aktarımın beraberinde getirdiği ek maliyetleri azaltmak için küçük bellek aktarımını tek bir büyük aktarım halinde gruplayarak göndermektir [3]. Kova boyutuna bağlı olarak device’a yapılan her aktarım yalnızca birkaç bayttan birkaç kilobayta kadar veri içerebilir. Bu aktarım işlemlerini gruplamak ek maliyeti önemli ölçüde azaltabilir.

Bu, ilk akışın çekirdekleri başlatılmadan önce tüm akışlar için tek bir bellek aktarımı başlatılarak gerçekleştirilebilir. Kullanılmayan baytların aktarılmasını önlemek için tüm bucket’lar bitişik şekilde paketlenir. Bu, global bellekteki her bucket’ın başlangıç adresinin uyarlanması gerektiği anlamına gelir. Toplu aktarım kullanılmadığında, her bucket kendisinden önceki bucket’tan yalnızca 3000 × 8 bayt sonra başlar. Her akıştaki çekirdeklerin yalnızca bellek aktarımı tamamlandıktan sonra işlemeye başlamasını sağlamak için bir CUDA olayı [3] kullanılır. Bu olay, bellek aktarımıyla aynı akışta kaydedilir ve aktarımın tamamlanıp tamamlanmadığını belirtir. Her bucket için, olayın tamamlanmasını beklemek amacıyla ilk çekirdek başlatılmadan önce bir senkronizasyon çağrısı eklenir.

İş parçacığı tekrar ilk akışa ulaştığında, tüm akışların sonuçlarını işler. Bu, iş parçacığının akışlar üzerinde dolaşması, her akışla senkronize olması ve sonuçlarını Rice Bit Vector içinde kodlaması anlamına gelir. Tüm sonuçlar kodlandıktan sonra bir sonraki toplu veri aktarımı başlatılabilir. İş parçacığı, bir sonraki aktarımı başlatmadan ve yeni çekirdekleri çalıştırmadan önce tüm akışlarla senkronize olduğundan, cihaz ve ana makine ile cihaz arasındaki veri yolu tam olarak kullanılamaz. Olası bir çözüm, her parti için iki aktarım kullanmaktır; yani akışların ilk yarısı için bir aktarım ve ikinci yarısı için bir aktarım başlatmak. Sonuçlar kodlanırken önce yalnızca ilk yarı dikkate alınır, ardından bir sonraki aktarım başlatılır ve yeni çekirdekler çalıştırılır. Bu sırada akışların ikinci yarısı kaynakları kullanmaya devam edebilir. Bizim durumumuzda bu gerekli değildir çünkü birkaç CPU iş parçacığı kullanıyoruz (bkz. Bölüm 5.8) ve bu aynı etkiyi sağlar.

Testler, toplu bellek aktarımı kullanıldığında önemli bir iyileşme göstermemiştir. Görece büyük yaprak ve bucket boyutları için darboğaz, bölünmeleri ve birebir eşlemeleri bulma işlemidir. Bellek aktarımı önemsizdir; bu durum "Nvidia Nsight Systems" [23] profil oluşturma aracı kullanılarak da doğrulanmıştır. Daha küçük yaprak ve bucket boyutlarına sahip yapılandırmalar teorik olarak toplu aktarımlardan daha fazla yarar sağlayabilir, ancak bu durumda da yüksek ek yükler bulunur ve çok sayıda küçük çekirdek çağrısı nedeniyle GPU tam olarak kullanılamaz. Bu durumlarda SIMDRecSplit, GPURecSplit’ten daha hızlıdır (bkz. Bölüm 6.6.1). Bu nedenle, fayda çok açık değilse GPU uygulaması küçük yaprak ve bucket boyutları için daha fazla optimize edilmemiştir. Bu da nihai uygulamamızda toplu bellek aktarımının kullanılmadığı anlamına gelir. Özellikle ters yöndeki bellek aktarımının — yani sonuçların cihazdan ana makineye aktarılmasının — toplu hâle getirilmesi en baştan uygulanmamıştır.

5.10 GPU Uygulaması – Genel Bakış

5.10.1 Toplu Bellek Aktarımı

Aynı GPU’yu aynı anda kullanan çekirdeklerin maksimum sayısı sınırlıdır. Deneylerimizde kullandığımız Nvidia RTX 3090 için bu sayı 128’dir [3]. Ancak iş kuyruğu (eşzamanlı bağlantı) sayısı varsayılan olarak yalnızca 8’dir. Belirli bir akışta başlatılan tüm işlemler tek bir iş kuyruğuna eklenir. Akış içindeki işlemler sıralı olarak işlendiğinden ve her iş kuyruğu için birkaç akış bulunduğundan, eşzamanlı çekirdek sayısı fiilen 8 ile sınırlıdır. Aynı GPU’nun aynı anda birden fazla çekirdek tarafından kullanılmasına büyük ölçüde dayandığımız için bu durum GPU’nun kullanımını ciddi şekilde sınırlar. Özellikle üst seviyelerdeki tek bir çekirdek, iş parçacığı bloklarının sayısı oldukça az olduğundan GPU’nun yalnızca küçük bir bölümünü kullanabilir.

Neyse ki iş kuyruğu sayısı, CUDA_DEVICE_MAX_CONNECTIONS ortam değişkeni istenen değere ayarlanarak değiştirilebilir [3]. Daha yüksek bir değer kullanım oranını artırabilir ancak ek yükleri de yükseltir. Deneyler, GPU uygulamasının en önemli parametreleri için — yani görece büyük yaprak ve bucket boyutları için — 32 iş kuyruğunun iyi performans sağladığını göstermiştir. Daha küçük değerlerde ek yükler zaten yüksektir ve kullanım oranı düşüktür (bkz. Bölüm 6.5.5). Bu nedenle deneylerimizde export komutu kullanılarak ortam değişkeni ayarlanmış ve 32 iş kuyruğu kullanılmıştır [19]. Ortam değişkenini uygun şekilde ayarlamak kullanıcının sorumluluğundadır.

5.10.2 İş Kuyrukları

SIMD uygulamasının yapısı GPU uygulamasına benzerdir. Önce giriş verisi sıralanır. Ardından bazı iş parçacıkları başlatılır ve bunlar hemen kendi bucket’larını işlemeye başlar. Her bucket için özyinelemeli bir fonksiyon çağrılır; bu fonksiyon mevcut boyuta göre ilgili seviyelerin fonksiyonlarını çağırır ve ardından uyarlanmış parametrelerle kendisini yeniden çağırır. GPU uygulamasının aksine, özyineleme yapraklarda sona erer. Bu yaklaşım çok daha basittir ve aynı zamanda özgün uygulamadaki yapıyı da andırır [13]. Bir iş parçacığı tüm bucket’larını işledikten sonra, Bölüm 5.8’de açıklandığı gibi diğer iş parçacıklarıyla senkronize olur. Tüm iş parçacıkları tamamlandığında Double Elias-Fano gösterimi oluşturulur.

5.11 SIMD Uygulaması – Genel Bakış

Yeni RecSplit uygulamalarımızın performansını değerlendiriyor ve bunları Sux kütüphanesindeki özgün RecSplit uygulamasıyla karşılaştırıyoruz [13]. Önce Bölüm 6.1’de deneysel kurulum sunulur, ardından Bölüm 6.2’de özgün RecSplit uygulamasındaki bir performans hatası düzeltilir. Daha sonra Bölüm 6.3’te SIMD ve GPU uygulamalarıyla ilgili çeşitli deneyler gerçekleştirilir. Amaç, farklı yaklaşımların faydasını deneysel olarak doğrulamaktır. Sonraki bölüm özellikle SIMD uygulaması için deneyleri gösterir (Bölüm 6.4), ardından GPU uygulaması için deneyler gelir (Bölüm 6.5). Her iki uygulamayı da Bölüm 6.6’da özgün RecSplit uygulamasıyla karşılaştırıyoruz. Son olarak PTHash ile küçük bir karşılaştırma sunulmaktadır (bkz. Bölüm 3.4).

6 Deneysel Değerlendirme

6.1 Deneysel Kurulum

Aksi belirtilmediği sürece, deneylerde kullanılan makine şu özelliklere sahiptir: 8 çekirdek ve 16 iş parçacığına sahip (hyper‑threading etkin) Intel Core i7‑11700 CPU, 2.5–4.9 GHz, çekirdek başına 48 KiB L1 veri önbelleği, çekirdek başına 32 KiB komut önbelleği, çekirdek başına 512 KiB L2 önbellek ve toplamda 16 MiB L3 önbellek [5, 20]. Makine, AVX512VPOPCNTDQ dahil olmak üzere AVX‑512 komutlarını destekler. Ayrıca 64 GiB çift kanallı DDR4‑3200 RAM ve bir Nvidia RTX 3090 GPU’ya sahiptir [17]. Deneyler Ubuntu 21.10 kullanılarak gerçekleştirilmiştir. Tüm RecSplit uygulamaları C++ ile yazılmıştır; GPU uygulaması CUDA C++ kullanır. C++ derleyicisi olarak GCC 11.2.0 [55] ve CUDA derleyicisi olarak CUDA 11.7 içindeki NVCC [71] kullanılmıştır. Derleyici seçenekleri olarak -march=native ve -O3 kullanılmıştır.

Hatırlatmak gerekirse, yalnızca RecSplit oluşturma süreci SIMD, çok iş parçacığı ve/veya GPU kullanır. Sorgu uygulaması SIMD ve GPU uygulamaları için aynıdır ve özgün uygulamayla neredeyse aynıdır. Süreler, C++ standart kütüphanesindeki chrono::high_resolution_clock kullanılarak gerçek zaman ölçümüyle belirlenir. Genel olarak bu bölümde test edilen her yapılandırma beş kez tekrarlanır ve gösterilen veri noktaları bu beş tekrarın ortalamasını temsil eder; standart sapma ise dikey bir çizgi olarak gösterilir. Farklı tekrarlar için giriş verileri farklıdır, ancak aynı grafikte farklı uygulamaların aynı yapılandırma ve tekrarları için giriş aynıdır. Bu yaklaşım, giriş verisinin çalışma süresi üzerindeki etkisini ölçerken farklı uygulamalar arasında adil bir karşılaştırma sağlar; yani aynı grafikteki farklı çizgiler arasında.

Giriş verisi sahte rastgele 128‑bit anahtarlardan oluşur ve başlangıç hash fonksiyonu (bkz. Bölüm 4.1) atlanır. Bu makuldür çünkü başlangıç hash fonksiyonunun sonucu zaten 128‑bit rastgele bir anahtar olarak ele alınır.

Sorgu süreleri ölçülürken 100 milyon rastgele sorgu gerçekleştirilir ve toplam süre 100 milyona bölünerek ortalama sorgu süresi elde edilir. Bu nedenle rapor edilen standart sapma tekil sorguların standart sapması değildir; her biri 100 milyon sorgunun ortalaması olan beş veri noktasının standart sapmasıdır. Bir sorgunun girdisinin, oluşturma sırasında kullanılan özgün kümenin parçası olmayabileceğini unutmayın. Dağılım aynı olduğundan bunun performans üzerinde bir etkisi olmamalıdır.

Her sorgunun girdisi, önceki sorguların çıktısına bağlıdır (girdi, önceki tüm çıktılarının XOR’u olan bir değişkenle XOR işlemi yapılır). Bu yaklaşım farklı sorgulara ait komutların üst üste binmesini önler (pipeline, out‑of‑order execution, superscalar işlemciler vb.). Böylece elde edilen ortalama, tek bir sorgunun aldığı süreyi, yani gecikmesini daha gerçekçi biçimde temsil eder. Sorgu karşılaştırması, Sux kütüphanesindeki özgün RecSplit uygulamasından uyarlanmıştır [13].

Aksi belirtilmedikçe, uygulamalar önceki bölümde açıklanan şekilde yapılandırılmıştır. Bir istisna dengeli bölünmelerdir (bkz. Bölüm 5.7.2). Bunlar deneylerin çoğu tamamlandıktan sonra fark edildiği ve her deneyi yeniden yapmak mümkün olmadığı için çoğu deneyde kullanılmamıştır. Varsayılan olarak SIMDRecSplit, CPU’nun sahip olduğu donanımsal iş parçacığı sayısı kadar CPU iş parçacığı kullanır (bu durumda 16) ve GPURecSplit 8 CPU iş parçacığı kullanır. İş parçacığı bloğu başına iş parçacığı sayısı üst seviyelerde 64, toplama seviyelerinde 256 ve yaprak seviyesinde 512’dir. Bu değerler testler yoluyla seçilmiştir.

• İsteğe bağlı son ek: grafiğe bağlıdır ve aynı RecSplit uygulamasının farklı yapılandırmalarını ayırt etmek için kullanılır

Örneğin “origRot”, özgün uygulamanın birebir eşleme döndürmesi kullanılan değiştirilmiş sürümüdür.

Bölüm 2.1’de açıklandığı gibi, BMI2 komut seti uzantısı mevcutsa 64 bitlik bir kelime üzerinde seçim işlemi yalnızca üç komutla uygulanabilir. Eğer mevcut değilse, Sux kütüphanesi RecSplit tarafından kullanılan daha yavaş bir geri dönüş yöntemini içerir [13]. Ne yazık ki gerekli PDEP komutunun kullanılabilirliğini derleme zamanında tespit eden kısımda bir hata vardır. Kod, __haswell__ makrosunun tanımlı olup olmadığını kontrol eder. Gerekçe, Intel Core işlemcilerin Haswell ve daha yeni mimariler için BMI2 komut setini desteklemesidir. Ancak GCC

Lejantlarda gösterilen adlar belirli bir adlandırma şemasını takip eder:

Bu makroyu yalnızca Haswell mimarisi için özel olarak derlendiğinde tanımlar; örneğin -march=haswell derleyici seçeneği kullanıldığında. Daha yeni Intel Core mimarileri, AMD mimarileri için derlendiğinde veya BMI2’yi etkinleştirmek için yalnızca -mbmi2 seçeneği kullanıldığında __haswell__ makrosu tanımlanmaz ve bu nedenle yalnızca daha yavaş geri dönüş yöntemi kullanılır.

Derleyici tarafından tanımlanan makroların varlığı örneğin şu komutla kontrol edilebilir:

echo | g++ -dM -E -march=skylake - | grep haswell -i

Bu komut, Ubuntu 20.04.1 LTS üzerinde GCC 9.3.0 [55] ve Clang 10.0.0 [2] için (g++ yerine clang kullanılarak) hiçbir sonuç döndürmez. Aslında Clang, -march=haswell seçeneği kullanıldığında bile __haswell__ makrosunu tanımlamaz.

Özgün RecSplit makalesindeki deneyler [46], GCC 8.8.1 ile derlenmiş ve Intel Core i7‑7770 üzerinde gerçekleştirilmiştir. Bu isimde bir CPU’dan haberdar değiliz, ancak isim benzerliği nedeniyle Intel Core i7‑7700 ile aynı mimariye sahip olduğunu varsayıyoruz [6] (muhtemelen yalnızca bir yazım hatasıdır). Sux kütüphanesindeki makefile, mimariyi derleme zamanında ayarlamak için -march=native kullanır. RecSplit yazarları bu makefile’ı kullandıysa ve ölçümlerini deneylerin gerçekleştirildiği makinede derlediyse, hızlı seçim algoritması muhtemelen kullanılmamıştır.

Bu hatayı, bunun yerine __BMI2__ makrosunu kontrol ederek düzeltiyoruz; bu makro BMI2 mevcut ve etkin olduğunda tanımlanır, örneğin BMI2’nin bulunduğu bir makinede -march=native veya -mbmi2 kullanıldığında. RecSplit oluşturma sürecinde hızlı seçim algoritmasının kullanıldığı tek yer, Double Elias-Fano gösteriminin geliştirilmiş oluşturma yöntemidir (Bölüm 5.9). Bu, tüm oluşturma sürecinin çok küçük bir parçası olduğundan bu hata düzeltmesinin çalışma süresi üzerinde önemli bir etkisi yoktur. Ancak sorgu algoritması, Double Elias-Fano gösterimini sorgularken hızlı seçim algoritmasını iki kez ve bir alt ağaç her atlandığında bir kez kullanır (bkz. Bölüm 4.5). Bu nedenle hızlı seçim algoritmasının kullanılması sorgu algoritmasının performansı üzerinde önemli bir etkiye sahiptir.

Şekil 6.1, performans hatasının düzeltilmesiyle elde edilen iyileşmeyi göstermektedir. “originalImplementation”, Sux kütüphanesindeki değiştirilmemiş uygulamadır [13]. “origNoRot” uygulaması ise özgün uygulamanın çerçevemize entegre edilmiş hâlidir; performans hatası düzeltilmiş ve birebir eşleme döndürmesi kullanma seçeneği eklenmiştir (bu durumda devre dışıdır). Düzeltilmiş sürüm %10–20 daha hızlıdır. Aşağıdaki tüm ölçümlerde düzeltilmiş sürümü özgün uygulama olarak adlandırıyoruz.

Benzer bir performans hatası clear_rho uygulamasında da bulunmaktadır. En düşük anlamlı 1 bitini silmek için geri dönüş yöntemi yerine doğru komutu kullanıyoruz

clear_rho(a) = a & (a − 1)

ve bunu __haswell__ makrosunu __BMI__ ile değiştirerek yapıyoruz. Ancak güncel GCC ve Clang sürümleri bu geri dönüş ifadesini uygun komut mevcutsa otomatik olarak tek bir komuta dönüştürebildiği için bu değişiklik pratikte fark oluşturmaz.

Bu bölüm, her iki uygulamamızla ilgili farklı teknikleri değerlendirir; yani SIMDRecSplit ve GPURecSplit.

Bölüm 5.1’de anahtarları bucket’lara dağıtmak için sıralama yöntemini nasıl geliştirdiğimizi görmüştük. Şekil 6.2’deki grafiklerin gösterdiği gibi, daha hızlı sıralama yöntemimizin özgün yönteme göre sağladığı hızlanma 12 kata kadar çıkmaktadır. Bu daha hızlı yöntem kullanıldığında bile, bölme ağaçlarının oluşturulması için çok iş parçacığı kullanıldığında sıralama toplam SIMDRecSplit oluşturma süresinin %70’inden fazlasını alabilir. Ancak bu yalnızca küçük yaprak boyutları (Şekil 6.2’de yaprak boyutu ℓ = 5) ve küçük bucket boyutları için geçerlidir.

Daha büyük yaprak boyutları için toplam oluşturma süresi içindeki yüzde daha küçüktür çünkü sıralama süresi değişmezken bölme ağaçlarının hesaplanması daha pahalı hâle gelir. Benzer şekilde daha büyük bucket boyutları da yüzdeyi azaltır çünkü daha iyi önbellek verimliliği ve bucket boyutlarının önek toplamını tutan daha küçük bir dizi sayesinde sıralama hızlanır. Özgün uygulamada bu yüzde genellikle daha küçüktür çünkü bölme ağaçlarının oluşturulması daha fazla zaman alır.

Hızlanma, on milyon anahtar için bir milyon anahtara göre daha küçüktür. Bunun muhtemel nedeni önbellek etkileridir. Bir milyon anahtar 16 MB yer kaplar. Counting sort algoritmasının çıktısı bunun yalnızca yaklaşık yarısını gerektirir çünkü çıktıda yalnızca anahtarların en düşük anlamlı bitleri saklanır; buna ek olarak bucket boyutlarının önek toplamını içeren dizi bulunur. Bu veri kullanılan CPU’nun 16 MiB L3 önbelleğine tamamen sığar. On milyon anahtar için ise durum böyle değildir.

Deneylerde SIMD uygulaması kullanılmıştır çünkü GPU uygulaması büyük ek yükler içerir ve yaprak ile bucket boyutları küçük olduğunda genellikle SIMD uygulamasından daha yavaştır. Bu nedenle sıralama süresinin GPURecSplit oluşturma süresi üzerindeki etkisi daha küçüktür.

6.3 Farklı Tekniklerin Değerlendirilmesi

Şekil 6.1

Seçim algoritmasının performans hatası giderilmeden önce ve sonra özgün uygulamanın sorgu süreleri.

“originalImplementation” çizgileri hatanın giderilmesinden önceyi, “origNoRot” ise hatanın giderilmesinden sonrayı gösterir. MPHF bir milyon anahtar ile oluşturulmuştur.

6.3.2 Bijection Rotation – Arama Tablosu

Bölüm 6.6.1'de, bijection rotation'ın oluşturma süresini iyileştirebileceğini göreceğiz. Bölüm 5.5.2'de bijection rotation için bir arama tablosu kullanma olasılığını görmüştük.

Bunu özgün (ardışık) uygulama için gerçekleştirdik çünkü GPU ve SIMD sürümüne kıyasla burada daha umut vericidir. Daha önce tartışıldığı gibi, SIMD veya GPU kodunda bir arama tablosu kullanmak, ardışık koda kıyasla çok daha yavaş olabilir. Bir arama tablosu kullanmanın sağladığı hızlanmalar Şekil 6.3'te gösterilmektedir.

Görülebileceği gibi, oluşturma süresinde anlamlı bir iyileşme elde edilmemektedir. Aslında, büyük arama tablosunun önbellek kullanımı nedeniyle daha büyük leaf boyutlarında oluşturma işlemi belirgin biçimde daha uzun sürmektedir. Sonuç olarak, nihai uygulamalarda arama tablosu kullanmıyoruz.

Test edilen dört bucket boyutu arasında, ℓ = 17 leaf boyutu için performans üzerindeki olumsuz etki bucket boyutu 50 için en büyüktür. Bunun nedeni, bucket boyutu 5 olduğunda arama tablosunun neredeyse hiç kullanılmamasıdır; çünkü bijection rotation genellikle yalnızca “dolu” leaf'ler için, yani boyutu ℓ olan leaf'ler için kullanılır.

500 ve 2000 boyutundaki bucket'lar için, toplulaştırma ve daha üst seviyelerde gereken iş miktarı bucket boyutu 50'ye kıyasla çok daha büyüktür. Arama tablosunun bu seviyelerde hiçbir etkisi yoktur; dolayısıyla olumsuz etki daha küçüktür.

Şekil 6.3

Bijection rotation için bir arama tablosu kullanmanın (“origRotLookup”), arama tablosu kullanılmamasına kıyasla sağladığı hızlanma.

Girdi bir milyon anahtardan oluşmaktadır.

6.3.3 Dengeli Bölmeler

Bölüm 5.7.2'de, üst seviyelerdeki bölmelerin daha dengeli yapılmasını önermiştik. Örnek bölme ağacının matematiksel analizi, oluşturma süresinde ve MPHF'in kullandığı bit sayısında anlamlı bir fark beklemediğimizi göstermiştir.

Deneyler analizi doğrulamaktadır. Dengeli bölmeler kullanıldığında oluşturma süresinde %5'ten daha az fark ölçtük; bazen daha yavaş, bazen daha hızlıdır. Standart sapma göz önüne alındığında bu fark anlamlı değildir. Benzer şekilde, alan tüketimindeki fark da anahtar başına 0.001 bitten daha azdır (artı veya eksi), bu da ihmal edilebilir düzeydedir.

Beklendiği gibi, dengeli bölmeler kullanıldığında sorgular daha hızlıdır. Bu durum SIMD sürümü için Şekil 6.4'te gösterilmektedir. GPU uygulamasının ortaya çıkan MPHF'i, yapılandırma aynıysa SIMDRecSplit sonucuyla aynıdır. Bu nedenle GPU uygulamasını burada değerlendirmek gereksizdir.

Dengeli bölmelerin etkisi bucket boyutu 50 için en büyüktür. Bucket boyutu 5 için üst seviyeler neredeyse önemsizdir; bu da etkinin küçük olduğu anlamına gelir. Büyük bucket boyutlarında ise genel sorgu süreleri artarken dengeli bölmelerin etkisi belirgin biçimde artmadığı için etki küçülür.

İlk bölmeden (kök düğüm) sonra, sol çocukta bulunan anahtar sayısı ikinci toplulaştırma seviyesindeki bir düğümdeki anahtar sayısının bir katıdır. Bu da bu bölmenin her zaman dengeli olacağı anlamına gelir ve burada hiçbir değişiklik yapılmamıştır. Dolayısıyla değişikliğimizden yararlanabilecek tek bölmeler en dıştaki sağ bölmelerdir; bunlar da daha büyük bucket boyutlarında göreli olarak daha azdır.

Double Elias-Fano gösteriminin oluşturma süresini nasıl iyileştirebileceğimizi Bölüm 5.9'da açıklamıştık. Şekil 6.5'te görülebileceği gibi, bu yalnızca küçük leaf ve bucket boyutları için gerçekten önemlidir; örneğin her ikisinin de 5 olduğu durumda daha yavaş Double Elias-Fano oluşturma işlemi toplam SIMDRecSplit oluşturma süresinin %28'ini almaktadır.

Daha büyük leaf boyutları için Double Elias-Fano'nun oluşturulması aynı süreyi alır, ancak bölme ağaçlarının hesaplanması çok daha uzun sürer. Daha büyük bucket boyutları için ise Double Elias-Fano gösteriminin girdi dizileri daha küçüktür; çünkü her iki girdi dizisi de κ bucket için κ + 1 eleman içerir. Bu da oluşturma süresinin azalması anlamına gelir.

Genel olarak, Double Elias-Fano gösteriminin özgün uygulamasına kıyasla elde edilen hızlanma 2 ile 6 arasındadır. Sıralama yöntemi gibi (bkz. Bölüm 6.3.1), burada yalnızca SIMD uygulamasını değerlendirdik. Daha hızlı oluşturmanın toplam çalışma süresi üzerinde önemli etkisi olduğu yapılandırmalarda, yani küçük leaf ve bucket boyutlarında, GPURecSplit'in ek yükü anlamlı ölçümler için fazla büyüktür.

6.4 Farklı Tekniklerin Değerlendirilmesi – SIMD Uygulaması

Bu bölümde SIMD uygulamasıyla ilgili farklı teknikleri değerlendiriyoruz. Daha önce belirtildiği gibi, aksi belirtilmedikçe SIMDRecSplit 16 iş parçacığı kullanır.

6.4.1 32-Bit Hash Fonksiyonu

Bölüm 5.3.1, remix fonksiyonunun girdisi olarak en anlamlı 32 bit ile en az anlamlı 32 bitin XOR'unun nasıl hesaplanacağına dair iki farklı olası uygulama sunmaktadır. Bir uygulama compress fonksiyonunu kullanırken diğeri blend16 fonksiyonunu kullanır.

Şekil 6.6'daki grafikler blend16 kullanan uygulamanın daha hızlı olduğunu açıkça göstermektedir. SIMDRecSplit'in nihai uygulamasında bunu kullanıyoruz.

Özgün 64-bit remix fonksiyonunun kullanımı SIMD uygulaması için değerlendirilmemiştir çünkü bu, kodun birçok bölümünün değiştirilmesini gerektirir. Bununla birlikte, GPU uygulaması için bunu Bölüm 6.5.1'de değerlendiriyoruz.

Bijection midstop faktörü α, bijection midstop parametresini belirlemek için kullanılır

p = p(m) = ⌈α√m⌉

Bu parametre, çarpışma kontrolü yapılmadan önce işlenen anahtar sayısını ifade eder (bkz. Bölüm 5.4.1). Özgün uygulama için α = 2, ve GPURecSplit için

α = 3'tür. Farklı α değerlerinin, bijection midstop kullanılmamasına kıyasla sağladığı hızlanma Şekil 6.7'de gösterilmektedir. Bu grafiklerde bijection midstop'un küçük leaf'ler için bile kullanıldığını unutmayın. Nihai uygulamada bijection midstop yalnızca boyutu en az 12 olan leaf'ler için kullanılmaktadır. Bu makul görünmektedir çünkü çoğu bijection midstop faktörü ℓ ≥ 12 için 1'den büyük bir hızlanma sağlamaktadır. Bu da bucket boyutu 5 için grafikte göründüğü kadar kötü performans göstermediği anlamına gelir.

Bu bölümdeki diğer tüm ölçümler α = 2.6 kullanır. Şekil 6.7'ye bakıldığında bu değer optimal görünmemektedir. Bu değer ön deneylerde en iyi performansı verdiği için seçilmiştir. Bu bölümdeki birçok deney Şekil 6.7'deki ölçümlerden önce yapılmış olduğundan, kalan deneyler için de bu değeri korumaya karar verdik.

Bölüm 5.4.3'te tartışıldığı gibi, popcount yalnızca AVX512VPOPCNTDQ komut kümesi uzantısı mevcutsa vektörler üzerinde kullanılabilir. Aksi halde, hangi hash fonksiyonlarının zaten çarpışma gösterdiğine karar vermek için popcount hesaplanmadan önce ön kelimeler bir diziye dökülür ve ardından her kelime üzerinde tek tek popcount hesaplanır. Vektör popcount komutunun, ardışık yedek yönteme göre sağladığı hızlanma Şekil 6.8'de gösterilmektedir. Beklendiği gibi anlamlı bir fark yalnızca ℓ ≥ 12 için ölçülmektedir çünkü aksi durumda bijection midstop zaten kullanılmamaktadır. Bu durumda hızlanma yaklaşık %10'dur.

Diğer deneylerde gördüğümüz gibi en büyük hızlanma bucket boyutu 50 için elde edilmektedir. Bucket boyutu 5 için çoğu leaf 12'den küçüktür ve bu nedenle bijection midstop hiç kullanılmaz. Büyük bucket boyutlarında ise toplulaştırma ve üst seviyeler daha önemli hale gelir ve bu da yalnızca bijection aramasını iyileştiren etkilerin azalmasına yol açar.

Bijection rotation kullanılırken her iki küme işlendiğinde SIMD uygulaması herhangi bir çarpışma bulunup bulunmadığını kontrol eder. Bu durum bijection midstop ile karıştırılmamalıdır (bijection midstop ve bijection rotation birbirini dışlar), ancak fikir aynıdır; bkz. Bölüm 5.5.3. Bu optimizasyon yalnızca AVX512VPOPCNTDQ komut kümesi uzantısı mevcutsa kullanılabilir ve yalnızca ℓ ≥ 11 için uygulanır. Sonuçlar Şekil 6.9'da görülebilir. Hızlanma %30'a kadar çıkmaktadır. Daha önceki grafiklerde olduğu gibi en büyük hızlanma bucket boyutu 50 için ölçülmüştür. Bucket boyutu 5 için bijection rotation nadiren kullanılır çünkü bijection rotation yalnızca dolu leaf'ler için kullanılır. Büyük bucket'larda ise toplulaştırma ve üst seviyeler oluşturma süresinin daha büyük bir kısmını oluşturur; bu da yalnızca leaf'leri etkileyen iyileştirmelerin etkisini azaltır.

Bölüm 5.6.1'de açıklandığı gibi, teorik olarak daha hızlı olabilecek şekilde toplulaştırma seviyelerinde 16-bit tamsayı bölmesi kullanılabilir. Ancak Şekil 6.10, 16-bit bölme kullanmanın belirgin bir fayda sağlamadığını göstermektedir. Belki de bölme işleminin süresi toplam oluşturma süresine kıyasla önemsizdir. 16-bit bölmeden fayda görmediğimiz için daha basit uygulamayı tercih ediyor ve 32-bit tamsayı bölmesini kullanıyoruz.

Bölme ağaçlarının oluşturulması bucket'ların farklı iş parçacıklarına dağıtılmasıyla paralelleştirilir (bkz. Bölüm 5.8). Bu işlem oldukça basittir ve farklı iş parçacıkları arasında neredeyse hiç iletişim gerektirmez. Bijection rotation olmadan elde edilen hızlanmalar Şekil 6.11'de gösterilmektedir. Bijection rotation ile karşılık gelen grafikler çok benzer göründüğünden burada verilmemiştir. Elde edilen hızlanmalar 7'ye kadar çıkmaktadır. Bucket boyutu 5 için hızlanmalar daha küçüktür çünkü sıralama ve Double Elias-Fano oluşturma daha fazla zaman alır ve bunlar çok iş parçacığı kullanmaz. Leaf boyutu ℓ çok büyük olsa bile, bucket boyutu 5 ise çoğu bucket ℓ'den küçük olacağından hızlı işlenir. Bu da bölme ağaçlarının oluşturulma süresinin büyük bucket boyutlarında olduğu gibi ℓ ile üstel biçimde artmadığı anlamına gelir.

İlginç şekilde, ℓ > 12 ve nispeten büyük bucket boyutları için hızlanma düşmektedir. Ne yazık ki bu davranış için iyi bir açıklamamız yoktur. Bir varsayım, daha büyük leaf boyutları için vektör komutlarının oranının artmasıdır. Tek bir vektör komutu, daha fazla transistör etkin olduğundan tek bir skaler komuttan daha fazla enerji gerektirebilir. Bu da birçok vektör komutu kullanıldığında tek bir çekirdeğin daha fazla güç çekmesine neden olabilir. CPU'nun aşırı ısınmasını önlemek için saat frekansının düşürülmesi gerekebilir. Bu durumda daha fazla iş parçacığı kullanmak da faydayı azaltır çünkü toplam güç tüketimine katkıda bulunurlar.

Benzer bir varsayım da toplam oluşturma süresinin daha büyük leaf boyutları için artması ve CPU'nun tüm oluşturma süresi boyunca saat frekansını koruyamamasıdır. Bir süre sonra frekans düşürülebilir. Farklı ölçümler arasında MPHF her zaman 100 milyon kez sorgulanır. Bu işlem ardışık yapılır; yani CPU bir sonraki oluşturma işleminden önce soğuma fırsatı bulabilir.

Grafikler ayrıca SIMD uygulamasının hyper-threading'den faydalanabildiğini göstermektedir. Kullanılan CPU yalnızca 8 fiziksel çekirdeğe sahip olmasına rağmen 16 iş parçacığı kullanmak, yalnızca 8 iş parçacığı kullanmaya kıyasla biraz daha büyük bir hızlanma sağlamaktadır.

6.4.3 Bijection Midstop Popcount

Şekil 6.8: Bijection midstop için vektör popcount komutunu kullanan SIMDRecSplit'in oluşturma süresi hızlanması; yedek yöntemi kullanan oluşturma süresine göre. Girdi bir milyon anahtardan oluşmaktadır.

6.4.4 Bijection Rotation Midstop

Şekil 6.9: SIMDRecSplit'in bijection rotation midstop kullanarak (bijection midstop ile karıştırılmamalıdır) tüm leaf boyutları ve ℓ ≥ 11 için elde ettiği oluşturma süresi hızlanması; bijection rotation midstop kullanılmayan oluşturma süresine göre. Girdi bir milyon anahtardan oluşmaktadır.

6.4.5 16-Bit Tamsayı Bölmesi

Şekil 6.10: SIMDRecSplit'in 32-bit tamsayı bölmesi yerine 16-bit tamsayı bölmesi kullanarak elde ettiği oluşturma süresi hızlanması. “simdNoRot16BitDivision” hızlanması 32-bit bölme kullanan ve bijection rotation devre dışı bırakılmış sürüme göre, “simdRot16BitDivision” hızlanması ise 32-bit bölme kullanan ve bijection rotation etkin olan sürüme göre hesaplanmıştır. Girdi bir milyon anahtardan oluşmaktadır.

Şekil 6.11: SIMDRecSplit'in farklı sayıda iş parçacığı kullanarak elde ettiği oluşturma süresi hızlanması; yalnızca tek iş parçacığı kullanmaya göre. Girdi bir milyon anahtardan oluşmaktadır.

6.5 Farklı Tekniklerin Değerlendirilmesi – GPU Uygulaması

Bu bölüm GPU uygulamasıyla ilgili farklı tekniklerin değerlendirilmesine ayrılmıştır.

Bölüm 5.3'te yavaş 64-bit tamsayı çarpmalarıyla başa çıkmak için 32-bit bir hash fonksiyonu tasarladık. Şekil 6.12'nin gösterdiği gibi, bu yöntem büyük leaf boyutları için 1.7'ye kadar hızlanma sağlayabilmektedir. Şimdiye kadar değerlendirilen çoğu tekniğin aksine, bu durum ortaya çıkan MPHF ve sorgu algoritması üzerinde de etkiye sahiptir. Sorgu algoritmasının da özgün 64-bit hash fonksiyonu yerine 32-bit hash fonksiyonunu kullanması gerekir. Neyse ki MPHF'in kullandığı bit sayısı üzerinde olumsuz bir etki yoktur. Fark her iki yönde de anahtar başına 0.002 bitten azdır ve bu gürültüden ayırt edilemez.

Ancak sorgu süreleri için durum böyle değildir. Şekil 6.13'te görülebileceği gibi, 32-bit hash fonksiyonu sorgu süresi üzerinde olumsuz bir etkiye sahiptir. 32-bit hash fonksiyonu kullanıldığında sorgular yaklaşık %3 daha uzun sürer. Bunun nedeni ek bir adımın gerekli olmasıdır. 32-bit remix fonksiyonu uygulanmadan önce en anlamlı 32 bit ile en az anlamlı 32 bit XOR ile birleştirilmelidir. 32-bit remix fonksiyonunun kendisi performans üzerinde olumsuz bir etki oluşturmamalıdır çünkü aynı işlemleri gerçekleştirir; sadece 64 bit yerine 32 bit kullanır. Eğer bir etkisi varsa, olumlu olmalıdır çünkü çarpma için kullanılan 32-bit sabitin, 64-bit remix fonksiyonundaki 64-bit sabitin aksine önce bir yazmaç içine taşınması gerekmez.

32-bit hash fonksiyonunun kullanılması oluşturma süresini azaltır ve alan gereksinimlerini etkilemez, ancak sorgu süresini artırır. Bu nedenle sorgu süresi önemli bir kaygı değilse kullanılması faydalıdır; örneğin alan tüketimi en önemli ölçütse. Sorgu süresi önemliyse durum daha belirsizdir. 32-bit ve 64-bit hash fonksiyonlarının oluşturma ve sorgu süresi arasındaki ödünleşimini daha iyi görmek için Şekil 6.14, her iki hash fonksiyonu ile GPURecSplit'in Pareto sınırlarını (bkz. Bölüm 2.5) göstermektedir. Test edilen tüm leaf ve bucket boyutu kombinasyonlarından yalnızca şu noktalar gösterilmektedir: başka hiçbir noktanın hem oluşturma hem de sorgu süresi açısından daha küçük veya eşit değerlere sahip olmadığı ve bu metriklerden en az birinde kesin olarak daha iyi olmadığı noktalar.

Şekil 6.14'ün sonucu, bu ödünleşimde ne 32-bit ne de 64-bit hash fonksiyonunun açıkça daha iyi olmadığını göstermektedir. Örneğin “gpuNoRot32Bit” Pareto sınırı “gpuNoRot64Bit” Pareto sınırının sol-altında olsaydı, bijection rotation kullanılmadığında 32-bit hash fonksiyonunun daha iyi olduğu anlamına gelirdi. Ancak çizgiler birkaç kez kesiştiği için — ve aynı durum “gpuRot32Bit” ile “gpuRot64Bit” için de geçerli olduğundan — açık bir kazanan yoktur.

6.5.2 Bijection Midstop Parametresi

Bölüm 6.4.2'de olduğu gibi bijection midstop faktörü α'nın oluşturma süresi üzerindeki etkisini ölçüyoruz. Ortaya çıkan bijection midstop parametresinin

p = p(m) = ⌈α√m⌉

olduğunu hatırlayın.

Farklı α değerlerinin kullanılmasının, orta durdurma olarak birebir eşleme kullanılmamasına kıyasla sağladığı hızlanma Şekil 6.15’te gösterilmektedir. Bu grafiklerde küçük yapraklar için bile birebir eşleme orta durdurmasının kullanıldığını unutmayın. Nihai uygulamada ise birebir eşleme orta durdurması yalnızca en az 14 boyutundaki yapraklar için kullanılmaktadır. Daha önceki birçok deneyde olduğu gibi, etki en büyük ölçüde kova boyutu 50 için görülmektedir. Kova boyutu 5 için sonuçlar GPU kullanımının ek yükü tarafından belirlenmektedir ve daha büyük kova boyutlarında ise toplama (aggregation) ve üst seviyeler toplam oluşturma süresinin daha büyük bir kısmını oluşturmaktadır.

Bu bölümdeki diğer tüm ölçümlerde α = 3 kullanılmıştır. Şekil 6.15’e bakıldığında α = 2.8 değeri biraz daha iyi olabilir. Ancak 3 değeri, ön deneylerde en iyi performansı verdiği için seçilmiştir. Bu bölümdeki diğer birçok deney Şekil 6.15’teki ölçümlerden önce gerçekleştirilmiştir, bu nedenle kalan deneylerde de aynı değeri korumaya karar verilmiştir.

Sayım değerlerini kayıtçılarda (register) paketlenmiş biçimde tutmak yerine paylaşımlı bellekte saklamak için alternatif bir yaklaşım önerdik (bkz. Bölüm 5.6.3). Aslında başlangıçta toplama seviyesi bu şekilde uygulanmıştı. Yalnızca SIMD uygulaması pahalı gather komutları nedeniyle farklı bir yaklaşımı zorunlu kıldığında, aynı yaklaşımın GPURecSplit performansını da iyileştireceği anlaşılmıştır. Bu durum Şekil 6.16 ile doğrulanmaktadır. Beklendiği gibi, kova boyutu 5 ve 50 için önemli bir fark yoktur çünkü toplama

Şekil 6.16: Oluşturma Süresi Hızlanması

Kova Boyutu 500

Kova Boyutu 2000

Oluşturma Süresi Hızlanması

Yaprak Boyutu: 6, 8, 10, 12, 14, 16

Şekil 6.16: Toplama seviyesinin sayım değerlerini kayıtçılarda paketlenmiş biçimde saklayarak GPURecSplit’in oluşturma süresi hızlanması; paylaşımlı bellekte saklama yaklaşımına göre karşılaştırmalı olarak gösterilmektedir. “gpuNoRot” hızlanması, birebir eşleme rotasyonu olmayan sürüme göre; “gpuRot” hızlanması ise birebir eşleme rotasyonu olan sürüme göre hesaplanmıştır. Girdi bir milyon anahtardan oluşmaktadır.

Bu kadar küçük kovalar için seviyeler önemli bir rol oynamaz. Daha büyük kova boyutları ve görece büyük yaprak boyutları için hızlanma 1.5’e kadar ulaşmaktadır. Küçük yaprak boyutlarında oluşturma süresi GPU kullanımının ek yükü tarafından belirlenir, bu nedenle burada kayda değer bir iyileşme ölçülemez.

Bölüm 5.6.3, geçerli bir bölme (splitting) bulunduğunda anahtarların doğru çocuk düğümlere verimli biçimde dağıtılması için warp-toplulaştırılmış atomik işlemlerin nasıl kullanılacağını açıklamaktadır. Warp-toplulaştırılmış atomik işlemlerin manuel olarak kullanılmasının oluşturma süresini iyileştirmemesi gerektiği daha önce belirtilmişti çünkü derleyici bunu otomatik olarak optimize edebilmektedir. Bu durum Şekil 6.17 ile doğrulanmaktadır. Standart sapmaların da gösterdiği gibi fark gürültüden ayırt edilemeyecek kadar küçüktür.

Bölüm 5.10.2’de iş kuyruğu sayısının varsayılan olarak yalnızca 8 olduğunu görmüştük. Bu durum GPU kullanımını azaltmaktadır çünkü GPU uygulaması, GPU’nun tüm işlem gücünden yararlanabilmek için birçok çekirdeğin eşzamanlı çalışmasına dayanır. İş kuyruğu sayısının artırılmasının etkisi Şekil 6.18’de gösterilmektedir. Bazı yapılandırmalar için hızlanma 3’ten büyüktür. Daha önce birçok kez olduğu gibi, hızlanma kova boyutu 50 için en yüksektir. Kova boyutu 5 olduğunda veya yaprak boyutu küçük olduğunda oluşturma süresi aslında daha uzun sürer. Bunun nedeni, daha fazla iş kuyruğu kullanıldığında çekirdek başlatma ek yükünün artmasıdır ve kova boyutu veya yaprak boyutu küçük olduğunda çekirdek başlatma sayısı yüksektir. Bu daha büyük ek yük, varsayılan iş kuyruğu sayısının yalnızca 8 olmasının nedenidir.

Daha büyük kova boyutları için hızlanma daha küçüktür çünkü uygulama eşzamanlı çekirdeklere daha az bağımlıdır. Büyük bir kovada toplama seviyeleri ve yaprak seviyesi çok sayıda thread block içerir ve bu nedenle GPU’yu küçük kovalara göre daha iyi kullanabilir. Şekil 6.18 yalnızca birebir eşleme rotasyonu olmayan hızlanmaları göstermektedir çünkü rotasyonlu grafikler neredeyse aynıdır. Tek fark, kova boyutu 50 için hızlanmaların biraz daha küçük olmasıdır; 3.5 yerine yalnızca 2.5’e kadar çıkmaktadır. Bunun nedeni, kova boyutu 50 için birebir eşlemeleri bulmanın en pahalı kısım olmasıdır, ancak birebir eşleme rotasyonu kullanıldığında bunlar çok daha hızlıdır. Bu nedenle daha fazla iş kuyruğu kullanmanın getirdiği artmış ek yük, birebir eşleme rotasyonu olmayan duruma göre daha büyük bir etki oluşturur.

6.5 Farklı Tekniklerin Değerlendirilmesi — GPU Uygulaması

Şekil 6.17: Warp-Toplulaştırılmış Atomikler

Kova Boyutu 5
Kova Boyutu 50
Kova Boyutu 500
Kova Boyutu 2000

Gösterge:

Yaprak Boyutu: 6, 8, 10, 12, 14, 16

Şekil 6.17: Warp-toplulaştırılmış atomik işlemlerin manuel olarak kullanılmasıyla GPURecSplit’in oluşturma süresi hızlanması. “gpuNoRotWarpAggregated” değerleri, üst seviyelerde ve toplama seviyelerinde warp-toplulaştırılmış atomik işlemler kullanılarak ölçülmüştür; “gpuNoRotWarpAggregatedHigherLevels” ise warp-toplulaştırılmış atomik işlemleri yalnızca üst seviyelerde manuel olarak kullanır. Girdi bir milyon anahtardan oluşmaktadır.

Şekil 6.18: İş Kuyruğu Sayısının Artırılması

Kova Boyutu 5
Kova Boyutu 50
Kova Boyutu 500
Kova Boyutu 2000

Gösterge:

Yaprak Boyutu: 6, 8, 10, 12, 14, 16

Şekil 6.18: Varsayılan 8 iş kuyruğundan daha fazlasını kullanarak GPURecSplit’in oluşturma süresi hızlanması. Gösterge içindeki sayılar iş kuyruğu sayısını belirtir. Girdi bir milyon anahtardan oluşmaktadır.

6. Değerlendirme

GPURecSplit’in birden fazla GPU ile ne kadar iyi ölçeklendiğini de ölçtük. Birden fazla GPU kullanımını etkinleştirmek için kodda yalnızca birkaç küçük değişiklik gereklidir. Her CPU iş parçacığı, akışlarını (streams) bir GPU üzerinde oluşturur ve tüm çekirdeklerini bu GPU üzerinde başlatır. Teorik olarak farklı iş parçacıkları arasında herhangi bir senkronizasyon gerekmediği için daha fazla GPU ile mükemmel biçimde ölçeklenebilmelidir. Ne yazık ki pratikte durum böyle değildir; Şekil 6.19 bunu göstermektedir. Hızlanmanın 1’den büyük olduğu durumlar yalnızca çok büyük yaprak boyutları ve en azından orta büyüklükte bir kova boyutu olduğunda ya da çok büyük bir girdi kullanıldığında görülmektedir.

Bu deney için kullanılan makine bwUniCluster’ın bir parçasıdır. Makinenin teknik özellikleri [1] kaynağında “GPU x4” adı altında bulunabilir. Sistem, her biri 20 çekirdekli iki adet Intel Xeon Gold 6230 CPU [7], 384 GB ana bellek ve dört adet Nvidia Tesla V100 GPU [16] içermektedir. Bu GPU, RTX 3090’dan bir nesil daha eskidir ancak 32 bit tamsayı ALU sayısı neredeyse aynıdır; 5248 yerine 5120 ALU bulunmaktadır. Bu makinede mevcut en yeni CUDA sürümü 11.4’tür ve bu nedenle bu sürümü kullanıyoruz. CUDA 11.4 resmi olarak yalnızca GCC sürüm 10’a kadar destek verir. GCC 10.3 proje derlenirken dahili bir derleyici hatası verdiği için GCC 10.2 kullanıyoruz. İşletim sistemi Red Hat Enterprise Linux 8.4’tür.

Tüm GPU’ların tam olarak kullanılmasını sağlamak için CPU iş parçacığı sayısını 16’ya ve toplam akış sayısını 256’ya çıkardık. Bu, GPU başına dört CPU iş parçacığı ve 64 akış olduğu anlamına gelir. Bu sayılar özel olarak optimize edilmemiştir; yani iyileştirme için hâlâ alan olabilir. Beklenenden daha düşük iyileşmenin nedeni muhtemelen birden fazla GPU kullanımıyla ilişkili büyük ek yüktür. Bellek tüm cihazlarda ayrılmalı ve daha sonra serbest bırakılmalıdır, daha fazla akış ve iş parçacığı oluşturulup sonlandırılmalıdır, iş parçacıkları tamamlandıktan sonra daha fazla senkronizasyon ek yükü oluşur vb. CPU ile GPU’lar arasındaki veri yolu da kullanılan GPU sayısı arttıkça giderek darboğaz hâline gelebilir. Bu özel sorun, Bölüm 5.10.1’de açıklanan toplu bellek aktarımı kullanılarak hafifletilebilir.

Birçok ek yük sabittir. Bu nedenle bir milyar giriş anahtarı için, bir milyon anahtara göre daha az önemlidirler. Bu durum, daha büyük girdiler için hızlanmaların genellikle neden daha büyük olduğunu açıklar. Şekil 6.19 ayrıca daha büyük kova boyutlarının daha küçük hızlanmalara yol açtığını da göstermektedir. Bunun nedeni, daha büyük kova boyutları için kullanım oranının genellikle daha yüksek olmasıdır. Çok büyük yaprak boyutlarında hızlanma artar çünkü uzun süre çalışan çekirdekler nedeniyle ek yükler giderek önemsiz hâle gelir. Birebir eşleme rotasyonu kullanıldığında yaprak çekirdekleri daha kısa çalışır; bu nedenle hızlanma daha küçüktür.

Bu bölümde son olarak yeni uygulamalarımızı orijinal RecSplit uygulamasıyla karşılaştırıyoruz. Önce oluşturma süresine, ardından bellek tüketimine ve sorgu sürelerine bakıyoruz. Sonunda ise tüm uygulamaların Pareto sınırlarını gösteren bazı grafikler sunarak hangi durumlarda hangi uygulamaların daha uygun olduğuna dair genel bir görünüm sağlıyoruz. Bu bölümdeki ölçümler bir milyon anahtar ve bir milyar anahtar ile gerçekleştirilmiştir. İkinci durumda, oluşturma süresi daha büyük yaprak boyutları için çok uzun olacağı için maksimum yaprak boyutu 17 yerine yalnızca 10’dur. SIMD ve GPU uygulamaları bu bölümde dengeli bölmeleri kullanmaktadır (bkz. Bölüm 5.7.2). Orijinal uygulama (“origNoRot”) ile bizim uygulamalarımız arasındaki farkı daha açık göstermek için orijinal sürüm kesikli çizgilerle gösterilmiştir.

6.5.6 Birden Fazla GPU

Şekil 6.19: Çoklu GPU Hızlanması

Gösterge:

(a) Bir milyon anahtar

Kova Boyutları: 5, 50, 500, 2000
Yaprak Boyutu: 6, 8, 10, 12, 14, 16

(b) Bir milyar anahtar

Kova Boyutları: 5, 50, 500, 2000
Yaprak Boyutu: 5, 6, 7, 8, 9, 10

Şekil 6.19: Dört Nvidia Tesla V100 GPU kullanılarak GPURecSplit’in oluşturma süresi hızlanması; yalnızca bir GPU kullanımıyla karşılaştırılmaktadır. “gpuNoRot4GPUs” hızlanması birebir eşleme rotasyonu olmayan sürüme göre, “gpuRot4GPUs” ise birebir eşleme rotasyonu olan sürüme göre hesaplanmıştır.

6.6 Orijinal RecSplit Uygulaması ile Karşılaştırma

Tablo 6.1: Orijinal Uygulamaya Göre Maksimum Hızlanmalar

Bir milyon anahtar için, birebir eşleme rotasyonu olmayan orijinal uygulamaya kıyasla yeni uygulamalarımızın elde ettiği maksimum hızlanmalar. Bu hızlanmanın elde edilebildiği kova ve yaprak boyutları da gösterilmektedir.

Implementation Maksimum hızlanma Kova boyutu b Yaprak boyutu ℓ
origRot 13 50 17
simdNoRot1Thread 7 5 9
simdRot1Thread 50 50 17
simdNoRot16Threads 46 50 12
simdRot16Threads 333 50 15
gpuNoRot 581 2000 17
gpuRot 1873 50 17

6.6.1 Oluşturma Süresi

Şekil 6.20 uygulamalarımızın oluşturma süresini göstermektedir. Kova boyutu 5 için SIMDRecSplit genellikle diğer uygulamalardan daha hızlıdır. Bu kadar küçük kovalar için GPU kullanımı çok fazla ek yük getirmektedir. Bu nedenle GPU uygulaması yalnızca ek yüklerin daha az etkili olduğu çok büyük yaprak boyutlarında orijinal uygulamadan daha hızlıdır. Bu durumda bile fark büyük değildir çünkü küçük kovalar için GPU kullanım oranı düşüktür.

Kova boyutu 50 için durum dramatik biçimde değişir. Yaprak boyutu 17 ve bir milyon giriş anahtarı ile, birebir eşleme rotasyonu kullanan GPURecSplit’in birebir eşleme rotasyonu olmayan orijinal uygulamaya göre hızlanması Şekil 6.21a ve Tablo 6.1’de görülebileceği gibi 1800’den fazladır.

Hızlanma kova boyutu 50 için daha büyük kova boyutlarına göre daha yüksektir çünkü birebir eşleme rotasyonu bu kova boyutunda en büyük etkiyi oluşturur. Kova boyutu 5 için çoğu yaprak çok küçüktür ve birebir eşleme rotasyonundan fazla yarar sağlamaz. Daha büyük kovalar için ise toplama ve üst seviyeler çalışma süresinin daha büyük bir bölümünü oluşturur ve bunlar birebir eşleme rotasyonundan hiç fayda görmez. Genel olarak birebir eşleme rotasyonu daha kısa oluşturma süresi sağlar. Beklendiği gibi fark daha büyük yaprak boyutlarında daha belirgindir (bkz. Bölüm 5.5.1).

Diğer uygulamaların aksine GPU uygulaması daha büyük kova boyutlarında daha hızlı hâle gelir; bu durum Şekil 6.20b’de oldukça açıktır. Bunun nedeni GPU’nun daha iyi kullanılabilmesi ve yaprak ile toplama seviyelerinin çekirdek çağrılarının daha fazla thread block içermesi sayesinde ek yükün azalmasıdır. Büyük ek yükler ayrıca GPURecSplit’in oluşturma süresinin yaprak boyutu yaklaşık 12’ye kadar artmamasının da nedenidir. Daha küçük yaprak boyutlarında oluşturma süresi ek yük tarafından belirlenir.

Bunun sonucu olarak ℓ < 12 için GPURecSplit kullanmak pratikte faydalı değildir; çünkü ℓ = 12 kullanarak aynı oluşturma süresiyle daha hızlı ve daha kompakt bir MPHF elde edebiliriz.

Küçük yaprak veya kova boyutları için SIMDRecSplit en hızlı uygulamadır; ancak her iki parametre de büyük olduğunda GPU uygulaması onu geçer. Bu durumda GPURecSplit çok büyük hızlanmalar elde edebilir. Ne yazık ki SIMD uygulamasının hızlanması büyük yaprak boyutlarında azalır; bu durum Şekil 6.20a’da görülebilir. Bölüm 6.4.6’da benzer bir durum görmüştük, ancak aynı açıklama burada geçerli değildir.

Eğer neden daha fazla vektör komutu nedeniyle CPU’nun frekans düşürmesi olsaydı, aslında CPU daha iyi kullanılmış olurdu çünkü vektör komutları komut başına daha fazla iş yapmaktadır. Daha iyi bir açıklama, hem birebir eşleme orta durdurmasının hem de birebir eşleme rotasyonunun skaler kodda SIMD koda göre daha iyi çalışması olabilir; ayrıca bu teknikler büyük yaprak boyutlarında giderek daha güçlü hâle gelir. Birebir eşleme orta durdurması için orijinal uygulamada gerekli olmayan ek işlemler yapmak zorundayız (bkz. Bölüm 5.4.3). Birebir eşleme rotasyonu orta durdurması da aynı derecede etkili değildir ve en az bir SIMD şeridi çakışma bulamamışsa tüm vektörün işlenmesi tamamlanmak zorundadır (bkz. Bölüm 5.5.3).

6.6.2 Bellek Tüketimi

Birebir eşleme rotasyonu olan ve olmayan RecSplit’in bellek tüketimi Şekil 6.22’de gösterilmektedir. SIMD ve GPU uygulamaları, sıralı RecSplit’in birebir eşleme rotasyonu olan veya olmayan ilgili sürümüyle neredeyse aynı bellek tüketimine sahiptir. Bir milyon anahtar için fark her iki yönde de anahtar başına 0.002 bitten daha azdır ve bir milyar anahtar için neredeyse yok denecek kadar küçüktür. Bu da nihai MPHF’deki farklılıkların, özellikle 32 bit hash fonksiyonunun kullanımının, bellek gereksinimleri üzerinde anlamlı bir etkisi olmadığını göstermektedir.

Beklendiği gibi, kova ve yaprak boyutları büyüdükçe bellek tüketimi azalır. Küçük kovalar için Double Elias-Fano gösterimi çok fazla yer kaplar; bu nedenle toplam bellek tüketimi anahtar başına 2.6 ile 3.0 bit arasındadır. Ancak kova boyutu 50 için bu değer Rice Bit Vector’un bellek tüketimine kıyasla zaten oldukça küçüktür. Toplam bellek tüketimi anahtar başına 1.7 ile 2.2 bit arasındadır. Kova boyutunun 2000’e çıkarılması yalnızca kova başına yaklaşık 0.1 bit tasarruf sağlar. Bunun bedeli ise daha sonra göreceğimiz gibi çok daha yavaş sorgulardır. Yaprak boyutunun artırılması daha büyük bir etki sağlar. Elbette bu daha uzun oluşturma süresine yol açar, ancak sorgu süreleri de iyileşir.

Bijeksiyon rotasyonu kullanmak, yaprak boyutu 5 için anahtar başına alan tüketimini yaklaşık 0.05 bit artırır; ancak yaprak boyutları büyüdükçe fark küçülür ve oldukça büyük yaprak boyutları için önemsiz hale gelir. Bu davranışı anlamak için Bölüm 5.5.1’deki Teorem 5.1’e tekrar bakalım. Bu teorem bize, boyutu m olan bir yaprak verildiğinde ortalama olarak m kat daha az hash fonksiyonunun denenmesi gerektiğini söyler. Doğru rotasyonu saklayabilmek için yalnızca her m-inci hash fonksiyonu denenir. Bu da Rice Bit Vector içinde saklanan sayının ortalama olarak aynı olduğu anlamına gelir; yani alan tüketimi aynı olmalıdır.

Ancak Teorem 5.1’i kanıtlamak için bazı varsayımlar yaptık. Eğer bu varsayımlar doğru değilse, deneme sayısının azaltıldığı katsayı m’den daha küçük olur. Biz hâlâ yalnızca her m-inci hash fonksiyonunu denediğimiz için alan tüketimi, bijeksiyon rotasyonu kullanılmayan duruma göre daha büyük olur. Daha büyük yaprak boyutları için varsayımlar yaklaşık olarak sağlanır ve sonuç olarak azaltma katsayısı yaklaşık m olur. Örneğin büyük m için büyük sayılar yasasına göre |A| ≈ |B| olur. Benzer şekilde, a’nın farklı rotasyonlarının sayısı da m büyüdükçe ortalama olarak m’e daha çok yaklaşır. Bu durum teoremin varsayımlarını tam olarak karşılamak için yeterli değildir, ancak |A| ile |B| birbirine ne kadar yakınsa ve a’nın farklı rotasyonlarının sayısı m’e ne kadar yakınsa, hesaplamalar gerçeğe o kadar yaklaşır. Sonuç olarak, bijeksiyon rotasyonu kullanmak ile kullanmamak arasındaki fark, yaprak boyutları büyüdükçe azalır.

Grafiklerin aşırı kalabalık olmasını önlemek için sorgu zamanı grafikleri ikiye ayrılmıştır: yalnızca orijinal uygulamaların sorgu zamanını içeren grafikler (Şekil 6.23) ve diğer uygulamaların orijinal uygulamalara göre hızlanmalarını içeren grafikler (Şekil 6.24). Beklendiği gibi sorgu süreleri genel olarak daha büyük bucket boyutları için artar, ancak daha büyük yaprak boyutları için azalır. Bunun nedeni, sorgu süresinin temelde bölme ağaçlarının yüksekliğine bağlı olmasıdır; bucket büyüdükçe yükseklik artar, ancak yaprak boyutları büyük olduğunda toplulaştırma seviyelerindeki daha yüksek dallanma dereceleri nedeniyle yükseklik azalır.

Bir milyar anahtar için sorgu süreleri, bir milyon anahtara kıyasla belirgin biçimde daha büyüktür. Bunun nedeni algoritmik değildir; sorgu zamanı O(1)’dir, fakat tamamen önbellekle ilgilidir. Bucket boyutu 5 ve yaprak boyutu 5 için bile, bir milyon anahtarın MPHF’si 3 MB’tan daha az yer kaplar (bkz. Şekil 6.22) ve bu kolayca L3 önbelleğe sığar. Bir milyar anahtar için alan tüketimi üç büyüklük mertebesi daha fazladır. Önbellekleme ayrıca Şekil 6.23b’deki ilginç bir anomaliyi de açıklayabilir. Bir milyar anahtar için sorgu süreleri bucket boyutu 500 olduğunda, bucket boyutu 50’ye göre daha küçüktür. Bunun nedeni muhtemelen Double Elias-Fano gösteriminin bucket boyutu 500 için daha küçük olması ve dolayısıyla daha büyük bir kısmının önbelleğe sığmasıdır. Örneğin Bölüm 4.5.2’deki formüller kullanıldığında, jump dizisi yaklaşık 266 kB gerektirir ve L2 önbelleğe sığar; üst bit dizileri ise birlikte en fazla 12 MB yer kaplar ve bu nedenle L3 önbelleğe sığar. Bucket boyutu 50 için her ikisi de on kat daha büyüktür.

Bijeksiyon rotasyonu kullanıldığında sorgu süreleri birkaç yüzde daha büyüktür. Bu beklenen bir durumdur çünkü daha fazla işlem yapılması gerekir. Öncelikle bulunan yaprağın dolu olup olmadığını kontrol etmek için ek bir durum ayrımı gerekir (yani m = ℓ), çünkü yalnızca dolu yapraklar bijeksiyon rotasyonu kullanır. Eğer doluysa, rotasyonu hesaplamak için bir modulo işlemi kullanılır. Anahtarın döndürülmüş olan B kümesinde bulunduğu durumda (bkz. Bölüm 5.5), rotasyonu uygulamak gerekir ve bu da başka bir modulo işlemi gerektirir. Neyse ki her iki durumda da modül compile-time sabiti olan ℓ’dir. Bu nedenle derleyici, Bölüm 5.6.1’de olduğu gibi pahalı modulo işlemlerinden kaçınabilir. En basit durumda ℓ iki’nin kuvvetidir. Bu durumda modulo işlemi tek bir ucuz AND komutuyla değiştirilebilir. Şekil 6.23’teki iki uygulama arasındaki farkın ℓ = 8 ve ℓ = 16 için daha küçük olmasının nedeni budur.

Şekil 6.24’e bakıldığında, SIMD ve GPU uygulamalarının genel olarak ne daha hızlı ne de daha yavaş MPHF’ler ürettiği görülür. Çoğu durumda fark %2’den azdır. Ancak bir milyon anahtar ve bucket boyutu 5 için hızlanma %8’e kadar çıkabilir. Bunun nedeni başlangıç tohumlarının derleme zamanı sabitleri olması olabilir (bkz. Bölüm 5.2), ancak bunun gerçekten bu kadar büyük farkları açıklayıp açıklayamayacağı net değildir. En azından toplam iş miktarı daha küçük olduğu için bucket boyutu 5 için etkinin daha büyük olması makuldür.

İlginç bir şekilde, bir milyar anahtar için grafik tersine döner. GPU uygulaması, orijinal uygulamaya göre %11’e kadar daha yavaş bir MPHF üretir. GPU uygulamasının, bu durumda çok daha hızlı olan SIMD uygulamasıyla tamamen aynı MPHF’yi ürettiği göz önüne alındığında, bu fark gerçek bir sonuç farkından ziyade ölçüm yöntemiyle daha iyi açıklanabilir. Sorgular, MPHF oluşturulduktan hemen sonra zamanlanır. Belki GPU’nun saat frekansında bir fark vardır. Ne yazık ki şu anda yalnızca tahmin yürütebiliriz.

Kullanıcı sorgu zamanını önemsemiyorsa, Şekil 6.25 bize çok kompakt MPHF’ler için bijeksiyon rotasyonlu GPURecSplit’in en iyi seçim olduğunu gösterir; buna karşılık anahtar başına daha fazla bit maliyetiyle çok hızlı oluşturma için bijeksiyon rotasyonlu SIMDRecSplit daha uygundur. Orijinal uygulama hiçbir zaman kullanışlı değildir çünkü SIMD uygulaması tarafından tamamen geride bırakılmıştır. Bir milyar anahtar için, bijeksiyon rotasyonlu GPURecSplit, bucket boyutu 2000 ve yaprak boyutu 17 ile neredeyse her şeyi geride bırakır. Yalnızca SIMD uygulaması MPHF’yi biraz daha hızlı oluşturabilir, ancak bunun karşılığında önemli ölçüde daha fazla alan kullanır. Şekil 6.25 ayrıca bijeksiyon rotasyonunun gerçekten faydalı olduğunu da gösterir; yani biraz daha yüksek alan tüketimi, parametreleri ayarlayarak telafi edilebilir ve böylece hem daha hızlı oluşturma hem de daha kompakt bir MPHF elde edilebilir.

Kullanıcı yalnızca sorgu ve oluşturma sürelerini önemsiyorsa, Şekil 6.26 SIMDRecSplit’in tercih edilen seçenek olduğunu açıkça gösterir. Bu beklenen bir durumdur çünkü genellikle orijinal uygulamadan çok daha hızlıdır ve GPURecSplit hızlı sorgular için gerekli olan küçük bucket boyutlarında yavaştır. Bijeksiyon rotasyonu SIMD uygulaması için biraz daha iyi görünmektedir, ancak diğer uygulamalar için durum böyle değildir.

Tamlık açısından, sorgu zamanı ile alan tüketimi arasındaki Pareto sınırlarını Şekil 6.27’de gösteriyoruz. Uygulamalar arasında büyük farklar yoktur çünkü uygulamalarımızın amacı, sorgu zamanı ve alan tüketimini mümkün olduğunca korurken oluşturma süresini iyileştirmektir. Bununla birlikte, oluşturma süresi önemsizse bijeksiyon rotasyonu ters etki yapar; çünkü alan tüketimini ve sorgu zamanını biraz artırır.

Bildiğimiz kadarıyla RecSplit uygulamalarımız, pratik oluşturma ve sorgu süreleriyle çok alan verimli MPHF’ler (anahtar başına 2 bitten az) üretmek için en iyi yöntemlerdir. Günümüzde makul oluşturma süresi ve alan tüketimiyle çok hızlı sorgular için en iyi yöntem PTHash [76, 75]’tir; bkz. Bölüm 3.4. PTHash’i, yazarların makalesinde kullanılan parametrelerle test ettik [75]. Tablo 6.2’de görüldüğü gibi, bucket boyutu 7 ve yaprak boyutu 11 olan SIMDRecSplit, PTHash’ten daha iyi oluşturma süresi ve alan tüketimine sahiptir. Ancak PTHash’in sorguları 2.6×’ya kadar daha hızlıdır. Hiçbir RecSplit uygulaması PTHash’in sorgu sürelerine yaklaşamaz. Yaprak boyutu daha da artırılsa bile yalnızca çok küçük iyileşmeler ölçülebilir; çünkü b = 7 ve ℓ = 11 için bölme ağaçlarının çoğu yalnızca tek bir yapraktan oluşur.

6.6.3 Sorgu Süresi

6.6 Orijinal RecSplit Uygulaması ile Karşılaştırma

Şekil 6.23: Farklı bucket ve yaprak boyutları için tüm RecSplit uygulamalarımızın sorgu zamanı. Daha iyi görselleştirme için yalnızca orijinal uygulamalar gösterilmiştir.

6.6.4 Pareto Sınırları

Şekil 6.24: Tüm RecSplit uygulamalarımızın, orijinal uygulamaya göre sorgu zamanı hızlanması. Bijeksiyon rotasyonlu hızlanmalar, bijeksiyon rotasyonlu orijinal uygulamaya göre; bijeksiyon rotasyonu olmadan elde edilen hızlanmalar ise bijeksiyon rotasyonu olmayan orijinal uygulamaya göredir.

6.7 PTHash ile Karşılaştırma

Şekil 6.25: Farklı uygulamalar için Pareto sınırları (oluşturma süresi ile alan tüketimi).

Şekil 6.26: Farklı uygulamalar için Pareto sınırları (oluşturma süresi ile sorgu zamanı).

Şekil 6.27: Farklı uygulamalar için Pareto sınırları (sorgu zamanı ile alan tüketimi).

Tablo 6.2: Dahili bellekli PTHash ile karşılaştırma

SIMDRecSplit ve PTHash her ikisi de 16 iş parçacığı kullanır. SIMDRecSplit için bucket boyutu b = 7 ve yaprak boyutu ℓ = 11’dir. Bijeksiyon rotasyonu kullanılmamıştır. PTHash yazarlarının bir makalesinde olduğu gibi [75], parantez içinde belirtilen kodlayıcıyla α = 0.94 ve c = 7 kullanılır; ayrıntılar için bkz. [76].

Yöntem — 1 milyon anahtar
SIMDRecSplit — Oluşturma: 46 ns/anahtar, Alan: 2.39 bit/anahtar, Sorgu: 29 ns
PTHash (D-D) — Oluşturma: 102 ns/anahtar, Alan: 3.48 bit/anahtar, Sorgu: 12 ns
PTHash (PC) — Oluşturma: 95 ns/anahtar, Alan: 3.11 bit/anahtar, Sorgu: 13 ns
PTHash (EF) — Oluşturma: 101 ns/anahtar, Alan: 2.70 bit/anahtar, Sorgu: 21 ns

10 milyon anahtar
SIMDRecSplit — Oluşturma: 52 ns/anahtar, Alan: 2.39 bit/anahtar, Sorgu: 37 ns
PTHash (D-D) — Oluşturma: 98 ns/anahtar, Alan: 3.34 bit/anahtar, Sorgu: 14 ns
PTHash (PC) — Oluşturma: 99 ns/anahtar, Alan: 2.91 bit/anahtar, Sorgu: 16 ns
PTHash (EF) — Oluşturma: 99 ns/anahtar, Alan: 2.54 bit/anahtar, Sorgu: 27 ns

100 milyon anahtar
SIMDRecSplit — Oluşturma: 83 ns/anahtar, Alan: 2.39 bit/anahtar, Sorgu: 73 ns
PTHash (D-D) — Oluşturma: 112 ns/anahtar, Alan: 3.23 bit/anahtar, Sorgu: 26 ns
PTHash (PC) — Oluşturma: 110 ns/anahtar, Alan: 2.76 bit/anahtar, Sorgu: 29 ns
PTHash (EF) — Oluşturma: 108 ns/anahtar, Alan: 2.45 bit/anahtar, Sorgu: 45 ns

7. Sonuç

Bu tezde minimal perfect hash functions (MPHF’ler) daha hızlı oluşturmak için yeni teknikler sunuyoruz. Özellikle RecSplit MPHF’nin [46] çok iş parçacıklı işlem, SIMD ve GPU kullanan yeni uygulamalarını sunuyoruz. Ayrıca m boyutundaki küçük anahtar kümeleri üzerinde neredeyse optimal alan tüketimiyle ve klasik kaba kuvvet yaklaşımına göre m katına kadar daha hızlı oluşturma sağlayan bijection rotation adlı yeni bir teknik öneriyoruz.

Bijeksiyon rotasyonu kullanarak, 8 çekirdekli bir CPU üzerindeki SIMD uygulamamız için 333×’e kadar ve GPU uygulamamız için 1873×’e kadar hızlanma elde ediyoruz; bu değerler Sux kütüphanesindeki [13] orijinal sıralı uygulamayla karşılaştırılmıştır. Bu sayede örneğin anahtar başına 1.56 bit kullanan bir MPHF’yi anahtar başına 1.5 µs’ten daha kısa sürede oluşturmak mümkün hale gelir.

Çalışmamızı veya genel olarak RecSplit’i geliştirmek için birçok yol vardır. Bu bölümde olası gelecek çalışmalar için bazı fikirler öneriyoruz.

Bölüm 5.5’te bijeksiyon rotasyonunu tanıttık ve Bölüm 5.5.1’de temel bir analiz sunduk. Gelecekte, özellikle her zaman doğru olmayan varsayımları kullanmadan ortalama kazancı inceleyerek bijeksiyon rotasyonunu daha kapsamlı analiz etmek ilginç olacaktır. Bu analize dayanarak, toplulaştırma seviyelerindeki dallanma derecelerini uyarlamak uygun olacaktır. Dallanma dereceleri, orijinal RecSplit makalesinde [46], her iki toplulaştırma seviyesindeki beklenen iş miktarının yaprak seviyesindeki beklenen iş miktarına yaklaşık eşit olması için seçilmiştir. Bijeksiyon rotasyonu ile yaprak seviyesindeki beklenen iş miktarı azalır. Bu nedenle dallanma derecelerinin de azaltılması gerekir. Bunu henüz yapmadık; bu nedenle bijeksiyon rotasyonu şu anda en çok yaklaşık 50 bucket boyutu için faydalıdır.

Bölüm 3.5’te SAT tabanlı bir MPHF’den [81] bahsettik. Yazarlar iki teknik önermiştir: biri pratik sürede anahtar başına yaklaşık 1.83 bit elde eder, diğeri ise neredeyse optimaldir fakat yavaştır ve yalnızca en fazla yaklaşık 40 anahtar içeren küçük girdiler için uygulanabilir. Gelecekteki çalışmalar bu ikinci tekniği RecSplit içindeki bijeksiyonları hesaplamak için kullanmayı deneyebilir. Belki özellikle büyük yapraklar için daha hızlıdır. Eğer gerçekten daha hızlıysa, SAT tabanlı tekniklerin bölmeleri arama sürecini hızlandırmak için de kullanılıp kullanılamayacağı incelenebilir.

Bölüm 6.5.6’da GPURecSplit için birden fazla GPU kullanımını tartıştık. RecSplit’in yazarları RecSplit’in dağıtık hesaplamadan (örneğin MapReduce [42]) ve harici depolamadan kolayca yararlanabileceğini zaten belirtmiştir. Harici depolama, harici bir sıralama algoritması kullanılarak gerçekleştirilebilir [43]; geri kalan adımların ana bellekte aynı anda yalnızca bir bucket’a ihtiyacı vardır. Bu, birkaç milyar anahtarın çok ötesine iyi ölçeklenebilen RecSplit uygulamalarına olanak tanır.

Ancak giriş anahtarlarının sayısı arttıkça, başlangıç hash fonksiyonunda çakışma oluşma riski de artar (bkz. Bölüm 4.1). Eğer bir çakışma oluşursa RecSplit bir MPHF belirleyemez (uygulama sonsuz döngüye girer). Çakışma olasılığını azaltmak için 128 bitlik bir hash fonksiyonu kullanılır. Ne yazık ki her bit kullanılmaz. 128 bitlik anahtarın en az anlamlı 64 biti bucket içindeki bölmeleri ve bijeksiyonları bulmak için kullanılır, ancak en anlamlı 64 bit yalnızca anahtarın bucket’ını hesaplamak için kullanılır. Sadece ⌈n / b⌉ adet bucket bulunduğundan, çıkarılan bilgi yalnızca log₂⌈n / b⌉ bit içerir. Bucket sayısı iki’nin kuvveti olduğunda bu durum açıktır: bucket atama fonksiyonu (bkz. Bölüm 4.2) yalnızca anahtarın en anlamlı log₂⌈n / b⌉ bitlerini alır.

Sonuç olarak RecSplit, 128 bitlik anahtarlardan beklenen çakışma direncine sahip değildir. Örneğin şu durumu düşünelim:

n = ⌈1.18 √2⁶⁴⌉ ≈ 5 milyar anahtar

ve bucket boyutu b = 2000. Doğum günü paradoksuna göre [65], anahtarların en az anlamlı 64 bitinde en az bir çakışma olma olasılığı %50’den fazladır. 2.5 milyon bucket vardır ve iki çakışan anahtar aynı bucket’a düşerse oluşturma başarısız olur. Buna göre başarısızlık olasılığı en az

0.5 × (1 / 2,500,000) = 1 / 5,000,000

dür.

5 milyonda 1 olasılığın kabul edilebilir bir risk olup olmadığı okuyucuya bağlıdır. Elbette bu durum bağlama da bağlıdır. Oluşturma işleminin bir insan gözetiminde bir kez çalıştırılması ile milyonlarca kullanıcı tarafından kullanılan bir tüketici uygulamasında kullanılması durumlarında değerlendirme farklı olacaktır.

Bu sorunun giriş boyutu üzerinde pratik bir sınıra yol açtığını belirtmek önemlidir. Yaklaşık 13 katrilyon anahtar için (13 × 10¹⁵ ≈ 1.44 × 2⁵³, yani 208 petabayt veri) başarısızlık olasılığı %50’den fazladır. Doğum günü paradoksuna göre bu, tüm 128 bit kullanılsaydı aynı sınırı sağlayacak olan 1.18 √2¹²⁸ anahtara göre 1674 kat daha küçüktür.

Basit bir çözüm, her kovada çakışma olup olmadığını kontrol etmektir. Herhangi bir kovada çakışma varsa, başlangıç karma fonksiyonu için başka bir seed kullanılır ve işlem tekrar denenir. Başarısızlık olasılığı çok büyük değilse bu makul bir yaklaşımdır. Başka bir çözüm ise bölme ağaçlarının kurulumu için tüm 128‑bit anahtarları kullanmaktır. Bu şekilde RecSplit, 128‑bit anahtarlardan beklenen çakışma direncine sahip olur; ancak bunun bedeli önemli ölçüde artan kurulum süresidir (muhtemelen en az 2 kat). RecSplit’in ölçeklenebilir ve pratik bir uygulaması için bu çözümlerden birinin uygulanması gerekir.

RecSplit’in yazarları, RecSplit’in minimal olmayan perfect hash fonksiyonlarına genelleştirilebileceğini belirtir; yani kodomain [n] değil, m > n olacak şekilde [m] olur ve perfect hash fonksiyonunun yalnızca bijektif olması değil, enjekte edici olması yeterlidir. Bu tür perfect hash fonksiyonları MPHFs’lerden bile daha kompakt olabilir. Benzer şekilde RecSplit, alan tasarrufu sağlamak amacıyla k-perfect hashing’e de genelleştirilebilir; burada her hash değeri için en fazla k anahtara izin verilir. Bu yaklaşım bu tezin yazarı tarafından uygulanmıştır, ancak sonuç (henüz) yayımlanmamıştır. RecSplit’in gelecekte üretime hazır bir uygulaması, her iki genellemeyi de sunabilir ve parametrelere (kova ve yaprak boyutu) ile uygun bir GPU’nun varlığına bağlı olarak SIMD veya GPU uygulamasının kullanılmasına otomatik olarak karar verebilir.

7.1.3 Ölçeklenebilirlik

Çözümler

7.1.4 Genellemeler

Kaynakça

[1] BwUniCluster 2.0 Donanım ve Mimari – bwUniCluster Bileşenleri. https://wiki.bwhpc.de/e/BwUniCluster_2.0_Hardware_and.Architecture#Components_of_bwUniCluster. Erişim: 11 Eylül 2022.

[2] Clang: LLVM için C dil ailesi ön ucu. https://clang.llvm.org/. Erişim: 10 Eylül 2022.

[3] CUDA C++ Programlama Rehberi. https://docs.nvidia.com/cuda/cuda-c-programming-guide/index.html. Erişim: 9 Ağustos 2022.

[4] CUDA Toolkit Dokümantasyonu – Tamsayı Intrinsics – Funnel Shift. https://docs.nvidia.com/cuda/cuda-math-api/group__CUDA__MATH__INTRINSIC__INT.html#group__CUDA__MATH__INTRINSIC__INT_1g6afcc1126ca2bf68f74c34812cbde57d. Erişim: 8 Ağustos 2022.

[5] Intel Core i7-11700 İşlemcisi. https://ark.intel.com/content/www/us/en/ark/products/212279/intel-core-i711700-processor-16m-cache-up-to-4-90-ghz.html. Erişim: 8 Eylül 2022.

[6] Intel Core i7-7700 İşlemcisi. https://ark.intel.com/content/www/us/en/ark/products/97128/intel-core-i77700-processor-8m-cache-up-to-4-20-ghz.html. Erişim: 10 Eylül 2022.

[7] Intel Xeon Gold 6230 İşlemcisi. https://ark.intel.com/content/www/us/en/ark/products/192437/intel-xeon-gold-6230-processor-27-5m-cache-2-10-ghz.html. Erişim: 11 Eylül 2022.

[8] MurmurHash3 Github. https://github.com/aappleby/smhasher/blob/master/src/MurmurHash3.cpp. Erişim: 18 Temmuz 2022.

[9] Nvidia Developer Blog – Cooperative Groups: Esnek CUDA İş Parçacığı Programlama. https://developer.nvidia.com/blog/cooperative-groups/. Erişim: 8 Ağustos 2022.

[10] Nvidia Developer Blog – CUDA Pro İpucu: Warp-Toplanmış Atomikler ile Optimize Edilmiş Filtreleme. https://developer.nvidia.com/blog/cuda-pro-tip-optimized-filtering-warp-aggregated-atomics/. Erişim: 8 Ağustos 2022.

[11] Nvidia Developer Blog – CUDA Warp-Seviyesi İlkel İşlemlerinin Kullanımı. https://developer.nvidia.com/blog/using-cuda-warp-level-primitives/. Erişim: 8 Ağustos 2022.

[12] Nvidia Developer Forums – 64 Bit Tamsayı Performansı Hakkında Soru. https://forums.developer.nvidia.com/t/question-about-64-bit-integer-performance/64147. Erişim: 18 Ağustos 2022.

[13] Sux Github. https://github.com/vigna/sux. Erişim: 11 Temmuz 2022.

[14] Intel Advanced Vector Extensions Programlama Başvuru Kılavuzu. https://www.intel.com/content/dam/develop/external/us/en/documents/36945, 2011. Erişim: 16 Ağustos 2022.

[15] Intel AVX-512 Talimatları. https://www.intel.com/content/www/us/en/developer/articles/technical/intel-avx-512-instructions.html, 2017. Erişim: 16 Ağustos 2022.

[16] Nvidia Tesla V100 GPU Mimarisi. https://images.nvidia.com/content/volta-architecture/pdf/volta-architecture-whitepaper.pdf, 2017. Erişim: 11 Eylül 2022.

[17] Nvidia Ampere GA102 GPU Mimarisi. https://www.nvidia.com/content/PDF/nvidia-ampere-ga-102-gpu-architecture-whitepaper-v2.pdf, 2020. Erişim: 16 Ağustos 2022.

[18] cppreference.com – std::lock_guard. https://en.cppreference.com/w/cpp/thread/lock_guard, 2021. Erişim: 19 Ağustos 2022.

[19] Linux kılavuz sayfası – export(1p). https://man7.org/linux/man-pages/man1/export.1p.html, 2021. Erişim: 19 Ağustos 2022.

[20] Linux kılavuz sayfası – lscpu(1). https://man7.org/linux/man-pages/man1/lscpu.1.html, 2021. Erişim: 19 Ağustos 2022.

[21] Intel 64 ve IA-32 Mimarileri Yazılım Geliştirici Kılavuzları. https://www.intel.com/content/www/us/en/developer/articles/technical/intel-sdm.html, 2022. Erişim: 18 Ağustos 2022.

[22] Intel Intrinsics Rehberi. https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html, 2022. Erişim: 18 Ağustos 2022.

[23] Nvidia Nsight Systems. https://developer.nvidia.com/nsight-systems, 2022. Erişim: 19 Ağustos 2022.

[24] Agner Fog. Komut tabloları – Intel, AMD ve VIA CPU’ları için komut gecikmeleri, verim oranları ve mikro‑işlem ayrıntılarının listeleri. https://www.agner.org/optimize/instruction_tables.pdf. Erişim: 18 Ağustos 2022.

[25] Agner Fog. C++ içinde yazılım optimizasyonu – Windows, Linux ve Mac platformları için bir optimizasyon rehberi. https://www.agner.org/optimize/optimizing_cpp.pdf. Erişim: 16 Ağustos 2022.

[26] Agner Fog. Vector Class Library. https://github.com/vectorclass/version2. Erişim: 11 Temmuz 2022.

[27] Agner Fog. Vector Class Library Kılavuzu. https://www.agner.org/optimize/vcl_manual.pdf. Erişim: 11 Temmuz 2022.

[28] Jean-Philippe Aumasson ve Daniel J. Bernstein. Siphash: kısa girdiler için hızlı bir PRF. Cryptology ePrint Archive, Makale 2012/351, 2012. https://eprint.iacr.org/2012/351.

[29] Djamal Belazzougui, Paolo Boldi, Giuseppe Ottaviano, Rossano Venturini ve Sebastiano Vigna. Rastgele hipergrafların cache‑oblivious soyulması. 2014 Data Compression Conference içinde, sayfa 352–361, 2014.

[30] Djamal Belazzougui, Paolo Boldi, Rasmus Pagh ve Sebastiano Vigna. Az alan kullanarak hızlı önek araması ve uygulamaları. Mark de Berg ve Ulrich Meyer (editörler), Algorithms – ESA 2010 içinde, sayfa 427–438, Berlin, Heidelberg, 2010. Springer.

[31] Djamal Belazzougui, Fabiano C. Botelho ve Martin Dietzfelbinger. Hash, yer değiştirme ve sıkıştırma. Amos Fiat ve Peter Sanders (editörler), Algorithms – ESA 2009 içinde, sayfa 682–693, Berlin, Heidelberg, 2009. Springer.

[32] Djamal Belazzougui ve Gonzalo Navarro. Alfabe bağımsız sıkıştırılmış metin indeksleme. ACM Transactions on Algorithms, 10(4), Ağustos 2014.

[33] Jules Bertrand, Fanny Dufossé, Somesh Singh ve Bora Uçar. Hiperkenar sorguları için algoritmalar ve veri yapıları. Araştırma Raporu RR-9390, Inria Grenoble Rhône-Alpes, 2022. Nisan 2022’de gözden geçirilmiş sürüm.

[34] Burton H. Bloom. Kabul edilebilir hatalarla hash kodlamasında alan/zaman ödünleşimi. Communications of the ACM, 13(7):422–426, 1970.

[35] Fabiano C. Botelho, Rasmus Pagh ve Nivio Ziviani. Neredeyse optimal alanda pratik perfect hashing. Information Systems, 38(1):108–131, Mart 2013.

[36] Larry Carter, Robert Floyd, John Gill, George Markowsky ve Mark Wegman. Tam ve yaklaşık üyelik test ediciler. Proceedings of the Tenth Annual ACM Symposium on Theory of Computing (STOC ’78) içinde, sayfa 59–65, 1978.

[37] Chin-Chen Chang ve Chih-Yang Lin. Birliktelik kurallarının çıkarılması için perfect hashing şemaları. The Computer Journal, 48(2):168–179, 2005.

[38] Bernard Chazelle, Joe Kilian, Ronitt Rubinfeld ve Ayellet Tal. Bloomier filtresi: statik destek arama tabloları için verimli bir veri yapısı. Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’04) içinde, sayfa 30–39, 2004.

[39] Chuang-Kai Chiou ve Judy C. R. Tseng. Minimal perfect hashing ve budama temelli artımlı birliktelik kuralı çıkarma algoritması. Hua Wang ve diğerleri (editörler), Web Technologies and Applications içinde, sayfa 106–113, Berlin, Heidelberg, 2012. Springer.

[40] Victoria G. Crawford, Alan Kuhnle, Christina Boucher, Rayan Chikhi ve Travis Gagie. Pratik dinamik de Bruijn grafikleri. Bioinformatics, 34(24):4189–4195, Haziran 2018.

[41] David Strafford. David Strafford Blogspot. http://zimbry.blogspot.com/2011/09/better-bit-mixing-improving-on.html. Erişim: 18 Temmuz 2022.

[42] Jeffrey Dean ve Sanjay Ghemawat. MapReduce: büyük kümelerde basitleştirilmiş veri işleme. Communications of the ACM, 51(1):107–113, Ocak 2008.

[43] Roman Dementiev ve Peter Sanders. Asenkron paralel disk sıralama. Proceedings of the Fifteenth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA ’03) içinde, sayfa 138–148, 2003.

[45] Peter Elias. Statik dosyaların içerik ve adres ile verimli depolanması ve erişimi. Journal of the ACM, 21(2):246–260, Nisan 1974.

  1. Emmanuel Esposito, Thomas Mueller Graf ve Sebastiano Vigna. RecSplit: özyinelemeli bölme yoluyla minimal perfect hashing. Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX) içinde, sayfa 175–185, 2020.

  2. Robert M. Fano. Bir İlişkisel Belleğin Gerçekleştirilmesi İçin Gereken Bit Sayısı Üzerine. Massachusetts Institute of Technology, Project MAC, 1971.

  3. Michael J. Flynn. Bazı bilgisayar organizasyonları ve etkinlikleri. IEEE Transactions on Computers, C-21(9):948–960, 1972.

  4. Catherine Forbes, Merran Evans, Nicholas Hastings ve Brian Peacock. Statistical Distributions, Dördüncü Baskı. John Wiley & Sons, Ltd, 2010.

  5. Edward A. Fox, Qi Fan Chen ve Lenwood S. Heath. Minimal perfect hash fonksiyonlarının kurulumu için daha hızlı bir algoritma. Proceedings of the 15th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR ’92) içinde, sayfa 266–273, New York, NY, ABD, 1992. Association for Computing Machinery.

  6. Michael L. Fredman, János Komlós ve Endre Szemerédi. O(1) en kötü durum erişim süresine sahip seyrek bir tablonun depolanması. Journal of the ACM, 31(3):538–544, Haziran 1984.

  7. Michael L. Fredman ve Dan E. Willard. Fusion ağaçları ile bilgi kuramsal sınırı aşmak. Journal of Computer and System Sciences, 47(3):424–436, 1993.

  8. Kimmo Fredriksson ve Fedor Nikitin. Rastgele erişimi ve hızlı dize eşleştirmeyi destekleyen basit bir sıkıştırma kodu. Camil Demetrescu (editör), Experimental Algorithms içinde, sayfa 203–216, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg.

  9. Marco Genuzio, Giuseppe Ottaviano ve Sebastiano Vigna. (Minimal perfect hash) fonksiyonlarının hızlı ve ölçeklenebilir kurulumu. Andrew V. Goldberg ve Alexander S. Kulikov (editörler), Experimental Algorithms içinde, sayfa 339–352, Cham, 2016. Springer International Publishing.

  10. GNU Project. GCC, GNU Derleyici Koleksiyonu. https://gcc.gnu.org/. Erişim: 8 Eylül 2022.

  11. GNU Project. libstdc++ Introsort Uygulaması. https://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-4.4/a01347.html#l02245. Erişim: 3 Haziran 2022.

  12. S. Golomb. Run-length kodlamaları (yazışma). IEEE Transactions on Information Theory, 12(3):399–401, 1966.

  13. Thomas Mueller Graf ve Daniel Lemire. Xor filtreleri: bloom ve cuckoo filtrelerinden daha hızlı ve daha küçük. ACM Journal of Experimental Algorithmics, 25, Mart 2020.

  14. Torbjörn Granlund ve Peter L. Montgomery. Çarpma kullanarak sabit tamsayılara bölme. SIGPLAN Notices, 29(6):61–72, Haziran 1994.

  15. Bob Jenkins. SpookyHash: 128‑bit kriptografik olmayan bir hash. https://burtleburtle.net/bob/hash/spooky.html, 2012. Erişim: 22 Ağustos 2022.

  16. Aaron B. Kiely. Rice kodlamasında Golomb parametresinin seçimi. Interplanetary Network Progress Report, 42-159:1–18, 2004.

  17. Anthony LaMarca ve Richard E. Ladner. Önbelleklerin sıralama performansı üzerindeki etkisi. Journal of Algorithms, 31(1):66–104, 1999.

  18. Sylvain Lefebvre ve Hugues Hoppe. Perfect mekânsal hashing. ACM Transactions on Graphics, 25(3):579–588, Temmuz 2006.

  19. Daniel Lemire. Bir aralıkta hızlı rastgele tamsayı üretimi. ACM Transactions on Modeling and Computer Simulation, 29(1), Ocak 2019.

  20. Arjen K. Lenstra. Doğum günü paradoksu. Encyclopedia of Cryptography and Security içinde, sayfa 147–148. Springer US, Boston, MA, 2011.

  21. Antoine Limasset, Guillaume Rizk, Rayan Chikhi ve Pierre Peterlongo. Çok büyük anahtar kümeleri için hızlı ve ölçeklenebilir minimal perfect hashing. Costas S. Iliopoulos, Solon P. Pissis, Simon J. Puglisi ve Rajeev Raman (editörler), 16th International Symposium on Experimental Algorithms (SEA 2017) içinde, cilt 75, Leibniz International Proceedings in Informatics (LIPIcs), sayfa 25:1–25:16, Dagstuhl, Almanya, 2017. Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik.

  22. Yi Lu, Balaji Prabhakar ve Flavio Bonomi. Ağ uygulamaları için perfect hashing. 2006 IEEE International Symposium on Information Theory içinde, sayfa 2774–2778, 2006.

  23. B. S. Majewski, N. C. Wormald, G. Havas ve Z. J. Czech. Bir perfect hashing yöntemleri ailesi. The Computer Journal, 39(6):547–554, Ocak 1996.

  24. Ingo Müller, Peter Sanders, Robert Schulze ve Wei Zhou. Parmak izi kullanarak retrieval ve perfect hashing. Proceedings of the 13th International Symposium on Experimental Algorithms içinde, cilt 8504, sayfa 138–149, Berlin, Heidelberg, 2014. Springer-Verlag.

  25. David R. Musser. İçgözlemsel sıralama ve seçim algoritmaları. Software: Practice and Experience, 27(8):983–993, 1997.

  26. Nvidia. CUDA Geliştirici Web Sitesi. https://developer.nvidia.com/cuda-zone. Erişim: 11 Temmuz 2022.

  27. Muhammad Osama, Anton Wijs ve Armin Biere. GPU hızlandırmalı inprocessing ile SAT çözümü. Jan Friso Groote ve Kim Guldstrand Larsen (editörler), Tools and Algorithms for the Construction and Analysis of Systems içinde, sayfa 133–151, Cham, 2021. Springer International Publishing.

  28. Rasmus Pagh. Hash and displace: minimal perfect hash fonksiyonlarının verimli değerlendirilmesi. Frank Dehne, Jörg-Rüdiger Sack, Arvind Gupta ve Roberto Tamassia (editörler), Algorithms and Data Structures içinde, sayfa 49–54, Berlin, Heidelberg, 1999. Springer Berlin Heidelberg.

  29. Alessandro Dal Palù, Agostino Dovier, Andrea Formisano ve Enrico Pontelli. CUD@SAT: GPU’lar üzerinde SAT çözümü. Journal of Experimental & Theoretical Artificial Intelligence, 27(3):293–316, 2015.

  30. Giulio Ermanno Pibiri ve Roberto Trani. PTHash ile minimal perfect hash fonksiyonlarının paralel ve harici bellek kullanılarak kurulumu. CoRR, abs/2106.02350, 2021.

  31. Giulio Ermanno Pibiri ve Roberto Trani. PTHash: FCH minimal perfect hashing yaklaşımının yeniden incelenmesi. Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR ’21) içinde, sayfa 1339–1348, New York, NY, ABD, 2021. Association for Computing Machinery.

  32. Giulio Ermanno Pibiri ve Rossano Venturini. Devasa n-gram veri kümeleri için verimli veri yapıları. Bilgi Erişiminde Araştırma ve Geliştirme Üzerine 40. Uluslararası ACM SIGIR Konferansı Bildirileri (SIGIR ’17) içinde, sayfalar 615–624, New York, NY, ABD, 2017. Association for Computing Machinery.

Kaynakça

  1. R. Rice ve J. Plaunt. Uzay aracı televizyon verilerinin verimli sıkıştırılması için uyarlanabilir değişken uzunluklu kodlama. IEEE Transactions on Communication Technology, 19(6):889–897, 1971.

  2. D. Salomon, G. Motta ve D. Bryant. Veri Sıkıştırma: Eksiksiz Başvuru Kaynağı. Molecular Biology Intelligence Unit. Springer London, 2007.

  3. Harold H. Seward. Elektronik dijital bilgisayarların iş operasyonlarına uygulanmasında bilginin sıralanması. Yüksek lisans tezi, Massachusetts Institute of Technology, 1954.

  4. Sean Weaver ve Marijn Heule. SAT teknolojisini kullanarak minimal mükemmel karma fonksiyonlarının oluşturulması. AAAI Yapay Zekâ Konferansı Bildirileri, 34(02):1668–1675, Nisan 2020.