← perfect_hashing/
[27] 2022 #BE6

An Efficient Parallel Implementation of a Perfect Hashing Method for Hypergraphs

Singh, Ucar

HiperGrafikler için Mükemmel Bir Hashleme Yönteminin Verimli Paralel Gerçekleştirilmesi

Atıf

Somesh Singh, Bora Uçar. HiperGrafikler için Mükemmel Bir Hashleme Yönteminin Verimli Paralel Gerçekleştirilmesi. GrAPL 2022 - Graphs, Architectures, Programming, and Learning Çalıştayı, IEEE, Mayıs 2022, Lyon, Fransa. ss. 265–274. hal-03612360

https://inria.hal.science/hal-03612360

Somesh Singh, Bora Uçar

HAL Kimliği: hal-03612360
Gönderim tarihi: 17 Mar 2022

HiperGrafikler için Mükemmel Bir Hashleme Yönteminin Verimli Paralel Gerçekleştirilmesi

Somesh Singh
INRIA ve LIP (CNRS – Université de Lyon – INRIA – ENS Lyon), Fransa
somesh.singh@ens-lyon.fr

Özet

Verilen bir graf veya hipergraf içinde bir kenarın varlığını sorgulamak birçok algoritmada temel bir yapı taşıdır. Bu amaçla hashleme tabanlı yöntemler kullanılabilir; burada verilen kenarlar bir ön işleme adımında bir hash tablosunda saklanır ve daha sonra sorgular arama işlemleri kullanılarak yanıtlanır. Genel hashleme yöntemleri ortalama durumda hızlı arama sürelerine sahip olsa da, en kötü durumdaki çalışma süresi çok daha yüksektir. Mükemmel hashleme yöntemleri, saklanacak öğelerin tamamının önceden mevcut olduğu gerçeğinden yararlanır ve verilen girdi için çakışmasız bir hash fonksiyonu oluşturur; böylece en kötü durumda bile optimal arama süresi elde edilir.

Yakın zamanda önerilmiş hipergraflar için bir mükemmel hashleme yönteminin paylaşımlı bellekli paralel bir gerçekleştirilmesini inceliyoruz. Ortaya çıkan paralel algoritmaları mevcut en ileri yöntemlerle deneysel olarak karşılaştırıyor ve gerçek hayattaki seyrek tensörlere karşılık gelen bir hipergraf kümesi üzerinde daha iyi çalışma süresi ve ölçeklenebilirlik gösteriyoruz.

Verilen bir graf veya hipergraf içinde kenarların varlığıyla ilgili sorgulara cevap verecek veri yapıları oluşturmak için paralel algoritmaları inceliyoruz. Daha açık ifade etmek gerekirse, tepe kümesi V ve hiperkenar kümesi E olan bir hipergraf H = (V, E) verildiğinde, bir sorgu V tepe kümesinin bir alt kümesi q'dan oluşur ve q'nun E içinde bir hiperkenar olup olmadığını sorar. Çalışmamız, tepe kümesinin d ayrık kümenin birleşimi olduğu d-uniform, d-parçalı hipergraflara odaklanmaktadır; V = ⋃_{i=1}^d V(i) ve her hiperkenar V(i) kümesinin her birinden tam olarak bir tepe içerir. Özel bir durum d = 2'dir ve bu durum iki parçalı graflarla ilgilidir.

İki parçalı grafların doğal olarak matrisleri modellemesine benzer şekilde, d-uniform ve d-parçalı hipergraflar d boyutlu tensörleri (veya çok boyutlu dizileri) modellemektedir.

Bora Uçar
CNRS ve LIP (CNRS – Université de Lyon – INRIA – ENS Lyon), Fransa
bora.ucar@ens-lyon.fr

s1 × ... × sd boyutlarında d boyutlu bir T tensörü olsun. T içindeki her sıfır olmayan giriş, [i1, ..., id] biçiminde d indeksli sıralı bir küme veya bir d-ikilisi ile adreslenir; burada j = 1, ..., d için ij ∈ {1, ..., sj}. T ile ilişkili d-uniform, d-parçalı hipergraf H = (V, E) şu şekilde tanımlanabilir.

Tepe kümesi

V = ⋃_{i=1}^d V(i)

şeklindedir; burada

V(i) = {v(i)1, ..., v(i){s_i}}.

Hiperkenar kümesi E, her sıfır olmayan T[i1, ..., id] için

h = [v(1){i1}, ..., v(d){id}]

biçiminde bir hiperkenar içerir. Bu eşleştirme göz önüne alındığında, amacımız verilen bir matris veya tensörde belirli bir konumun sıfır olmayan bir değer içerip içermediğini soran sorgulara cevap verecek verimli paralel algoritmalar geliştirmektir.

Belirli bir kullanım durumu, Kolda ve Hong [10] tarafından yakın zamanda önerilen bir tensör ayrıştırma yönteminde ortaya çıkmaktadır. Bu çalışmada, verilen bir tensörün sıfır ve sıfır olmayan elemanlarının örneklenmesi gereken seyrek bir tensör ayrıştırma algoritması geliştirilmiştir. Sıfırların örneklenmesi için rastgele bir indeks kümesi oluşturulur ve verilen tensördeki bu konumların sıfır olup olmadığı kontrol edilir. Verilen seyrek tensörün bir hipergraf olarak modellenmesi, böylece ele aldığımız probleme yol açmaktadır.

Daha genel bir bağlamda, kenar sorgularına hızlı yanıt veren bir veri yapısı, verilen bir tepe kümesinin bir clique oluşturup oluşturmadığını veya yeterince yoğun bir tepe kümesi olup olmadığını tespit etmek için kullanılabilir. Bu işlem, tepe kümesinin büyüklüğünün karesiyle orantılı bir sürede gerçekleştirilir ve kümedeki tepelerin derece toplamından bağımsızdır; oysa bu toplam çok daha büyük olabilir.

Bahsedilen senaryolardaki bir sorgu d indeks içerir. Bir sorgu indeksleri okunmadan yanıtlanamayacağı için, bir yanıt yalnızca Ω(d) zamanda verilebilir. Bu nedenle bir sorguya yanıt veren verimli bir veri yapısı Θ(d) zaman almalıdır. Eğer d'yi sabit kabul edersek, bir sorgu sabit zamanda yanıtlanmalıdır.

Sorguları yanıtlamak için klasik hashleme yöntemleri kullanılabilir. Ortalama durumda sorgu yanıt süresi O(d) olacak olsa da, en kötü durum çok daha yüksektir. Hipergrafın (veya tensörün) sorgular yanıtlanmadan önce ön işleme tabi tutulabildiği ve değişmediği durumlarda daha iyi sonuçlar elde edilebilir. Mükemmel hashleme yöntemleri, belirli bir statik öğe kümesi için çalışır ve verilen küme üzerinde kullanıldığında çakışma olmayacak şekilde bir hash fonksiyonu bulur. Böylece bu yöntemler en kötü durumda Θ(d) sorgu süresi sağlar.

FKSLean olarak adlandırılan bir mükemmel hashleme yöntemi, ele alınan problem için yakın zamanda Bertrand ve arkadaşları [2] tarafından geliştirilmiştir. Biz, paylaşımlı bellekli paralel sistemlerde FKSLean veri yapılarının oluşturulmasında kullanılan yöntemlerin verimli bir paralelleştirmesi olan PARFKSLEAN'ı öneriyoruz.

Makalenin geri kalanı şu şekilde düzenlenmiştir. FKSLean yöntemini paralelleştirdiğimiz için, bir sonraki bölümde bunun ayrıntılı bir özetini sunuyoruz. Aynı bölümde mükemmel hashleme üzerine bazı güncel çalışmaları da kısaca inceliyoruz. Bölüm III'te paralel gerçekleştirmemiz olan PARFKSLEAN'ı açıklıyoruz. Bölüm IV'te PARFKSLEAN'ı büyük problem örneklerinden oluşan bir küme üzerinde değerlendiriyor ve mevcut en ileri yöntemlerle karşılaştırıyoruz. Bölüm V'te ise makaleyi bir özet ve planlanan araştırmalarla sonlandırıyoruz.

I. GİRİŞ

II. ARKA PLAN

Bir d-parçalı d-uniform hipergraf H = (V, E) içinde hiperkenar kümesi E, d-ikili öğelerden oluşur. Bu hipergraflar iki parçalı grafların genelleştirilmiş biçimleridir ve seyrek tensörleri ile matrisleri modellemek için kullanılır.

Makale boyunca n hiperkenar sayısını, p ise n'den büyük bir asal sayıyı göstermektedir. Genelliği bozmadan i = 1, ..., d için n ≥ |V(i)| olduğunu varsayıyoruz; aksi halde hiçbir hiperkenarda yer almayan tepeler bulunur.

xi'nin 0 ile p − 1 arasında olduğu [x0, ..., x_{d−1}] biçimindeki tüm d-ikili öğelerin evreni U ile gösterilir. Başka bir deyişle:

U = {0, ..., p − 1}^d

burada E ⊆ U'dur. Her sorgu U evreninin bir elemanı olacaktır.

A. FKSLean'in Özeti

FKSLean yöntemi [2], verilen statik hiperkenar kümesi için mükemmel hashleme elde etmek amacıyla iki seviyeli bir yapı kullanır. Bu yöntem, iyi bilinen bir yaklaşımın [7] uyarlanmış hâlidir ve hipergrafları verimli şekilde işler.

Birinci seviye bir hash fonksiyonu, verilen hiperkenarları kovalar (bucket) hâlinde ayırmak için kullanılır. Daha sonra her kova için o kovaya eşlenen hiperkenarlar üzerinde mükemmel bir hashleme bulunur ve hiperkenarlar veya hiperkenarlara ait başvurular bu kovaya ait bir alanda saklanır.

x ve y evren U'nun iki elemanı olsun. d-ikili x ve y'ye karşılık gelen vektörlerin iç çarpımını göstermek için

x^T y := ∑_{i=1}^d x_i y_i

ifadesini kullanıyoruz.

FKSLean yönteminde birinci seviye için k ∈ U seçilir ve hash fonksiyonu

h : U → {0, ..., n − 1}

şu şekilde tanımlanır:

h(k, x, p, n) := (k^T x mod p) mod n.

Daha sonra her hiperkenar x ∈ E, şu şekilde tanımlanan B_i kovasına atanır:

i := h(x, k, p, n).

b_i, E içinden B_i'ye eşlenen hiperkenar sayısını göstersin. B_i kovasına eşlenen hiperkenar referanslarını depolamak için B_i ile ilişkili 2b_i² büyüklüğünde bir alan ayrılır; bu alanda her hiperkenar benzersiz bir konumda saklanır.

Bu durum, her kova B_i için k_i ∈ U seçilerek sağlanır; öyle ki

h(k_i, x, p, 2b_i²) := (k_i^T x mod p) mod 2b_i²

fonksiyonu, birinci seviye hash fonksiyonu tarafından B_i'ye eşlenen tüm x değerleri için bir enjeksiyon olur. Başka bir ifadeyle, B_i içindeki her hiperkenar x, h(k_i, x, p, 2b_i²) ile {0, ..., 2b_i² − 1} aralığında benzersiz bir sayıya eşlenir.

Daha sonra x'e ait bir referans, B_i ile ilişkili depolama alanında h(k_i, x, p, 2b_i²) konumuna yerleştirilir. B_i kovasında b_i adet hiperkenar bulunduğu için depolama alanının yalnızca 1/(2b_i) oranındaki kısmı hiperkenar referansları içerir; diğer girişler boştur.

Bu yapı verildiğinde, bir hiperkenar q'nun hiperkenar kümesi E içinde olup olmadığını test etmek iki adımda yapılabilir:

  1. Kova numarasını hesapla: i = h(k, q, p, n).
  2. B_i kovasının depolama alanındaki h(k_i, q, p, 2b_i²) konumunu kontrol et.

Eğer o konumda herhangi bir referans saklanmıyorsa, q E içinde değildir. Aksi durumda, o konumda referansı saklanan hiperkenar q ile karşılaştırılır ve sonuç döndürülür.

FKSLean, her kova B_i'nin k_i olarak kullanabileceği d-ikili öğeleri içeren bir K kümesi tutar. Amaç yalnızca az sayıda farklı d-ikili saklamak ve bunları farklı kovalar arasında ikinci seviye hash fonksiyonları için yeniden kullanmaktır. Böylece bir kova, tam bir d-ikili saklamak yerine K içindeki bir d-ikilisinin kimliğini saklar.

Orijinal kaynak [7], beklenti açısından yapının O(dn) zamanda kurulabileceğini garanti eder. FKSLean'e özgü bir diğer teorik sonuç, beklenti açısından K içinde O(log n) farklı d-ikili bulunmasının her kovaya uygun bir hash fonksiyonu sağlamak için yeterli olduğudur.

Yukarıda tartışıldığı gibi, FKSLean kovalar için toplamda O(n) depolama alanı ve K için ek olarak O(d log n) alan kullanır. Teorik sonuçlar ve pratik deneyler [2], bu sınırların sabit katsayılarının küçük olduğunu göstermektedir. Uygulamada 5n'den az depolama alanı ve K içinde 0.5 log₂ n'den az d-ikili yeterli olmaktadır.

B. Diğer Güncel Çalışmalar

Statik kümeler için mükemmel hash fonksiyonlarına odaklanan başka güncel çalışmalar da vardır. Bunlar arasında en yenileri PTHash [14], RecSplit [6] ve BBHash [12]'dir. Hem PTHash hem de BBHash, kurulum aşamalarının paralel gerçekleştirmelerine sahiptir.

Mevcut PTHash uygulaması [15], PTHash'i BBHash ile karşılaştırmakta ve PTHash ile daha iyi sonuçlar elde edildiğini bildirmektedir; bu nedenle mevcut en ileri yöntemi temsil etmektedir. Bu yüzden deneylerimizde PTHash kullanıyoruz.

PTHash ve yukarıda atıf verilen diğer güncel mükemmel hash fonksiyonları, statik kümeler için minimal mükemmel hash fonksiyonları oluşturur. Bu fonksiyonlar, verilen n elemanlı bir kümedeki her elemanı çakışma olmadan {0, ..., n − 1} negatif olmayan tamsayılarına eşler. Bu nedenle hedef problemde kullanılabilirler.

Bu yaklaşımda hiperkenarlar işlenerek hiperkenar kümesini {0, ..., n − 1} aralığına birebir eşleyen minimal mükemmel bir hash fonksiyonu f bulunur. Daha sonra n boyutunda bir dizi ayrılır ve bir hiperkenar e'nin kimliği bu dizinin f(e) konumunda saklanır (indeksler sıfırdan başlar).

Verilen bir hiperkenar q'nun orijinal kümede olup olmadığını kontrol etmek için f(q) konumunda saklanan hiperkenar e'nin kimliği alınır ve q ile e karşılaştırılır.

PTHash, FKSLean, RecSplit ve BBHash içinde uygulanan güncel kurulum algoritmaları oldukça verimlidir ve sorgular için en kötü durumda Θ(d) zaman sağlar. Bunlar arasında yalnızca FKSLean hiperkenarları doğal biçimde destekler; diğerleri için giriş hiperkenarlarının önce 64 veya 128 bit anahtarlara eşlenmesi gerekir.

Şekil 1, FKSLean [2] veri yapısını göstermektedir. Şekilde görüldüğü gibi birinci seviye hash fonksiyonu için kullanılan bir d-ikili k, d-ikili öğelerden oluşan bir K kümesi ve her kova için bir depolama alanı bulunmaktadır.

Her bir kova (B_i) için, birinci seviye hash fonksiyonu tarafından (B_i)'ye eşlenen hiperkenar sayısı (b_i)'nin bilinmesi gerekir. Buna göre:

FKSLean'in etkinliği üç teorik sonuca dayanmaktadır [2]. Birincisi, rastgele seçilen bir (k ∈ U) için (\sum b_i^2 < 7n) olma olasılığı 1/2'den büyüktür. Bu sonuç sayesinde, beklenti açısından birkaç denemede (\sum b_i^2 < 7n) sağlayan bir (k) bulunabilir. Böyle bir (k), kovalar için toplamda (O(n)) depolama alanı garantiler.

İkinci teorik sonuç, rastgele seçilen bir (k_i ∈ U) için (k_i)'nin (B_i) içindeki hiperkenarlar için (h(k_i, x, p, 2b_i^2)) biçiminde mükemmel bir hashleme tanımlama olasılığının 1/2'den büyük olduğudur. Bu da beklenti açısından böyle bir (k_i)'nin sabit sayıda denemede bulunabileceğini gösterir.

PTHash'in orijinal uygulaması [14] minimal mükemmel hash fonksiyonları oluştururken, daha yeni sürüm [15] minimal olmayan hash fonksiyonları da kurmaktadır. Minimal olma kısıtının gevşetilmesi daha hızlı kurulum süresi sağlar. Deneylerimiz bu yeni uygulamayı [15] kullanmaktadır.

Hiperkenar sorgularını yanıtlamak için iki alternatif yaklaşım daha düşünülebilir.

Birincisi, yaklaşık küme üyeliği testleri için tasarlanmış Bloom filtreleri [3] ve bunların varyantlarını kullanmaktır. Bellek ve çalışma süresi açısından verimli Bloom filtre varyantları tasarlamak oldukça aktif bir araştırma alanıdır [4], [8], [18]. Genel olarak bu filtrelerin küçük bir yanlış pozitif olasılığı vardır. Bu nedenle hedef uygulama bağlamlarında bir Bloom filtre varyantı kullanmak, filtrenin döndürdüğü her pozitif yanıtı doğrulamak için başka bir veri yapısının da kurulmasını gerektirir. Bu durum sorgu yanıt süresini azaltabilir, ancak iki veri yapısının kurulması için ek maliyet gerektirir.

İkinci alternatif ise Cuckoo hashing [13] ve varyantlarını kullanmaktır. Bunlar en kötü durumda (O(1)) arama süresine sahip mükemmel hashleme yaklaşımlarıdır; bizim durumumuzda bu süre (O(d))'dir. Ancak kurulum süreci çok daha karmaşıktır. Bizim durumumuzda saklanacak öğeler başlangıçta hazır olduğundan, bir Cuckoo hash tablosu kurmak; öğeler ile bellek yuvaları arasında rastgele bir iki parçalı graf oluşturmak ve öğelerin yuvalarla mükemmel eşleşmesini test etmek anlamına gelir. Eşleştirme için verimli algoritmalar bulunsa da [1], [5], uygun hash fonksiyonlarını bulmak, iki parçalı grafı örtük veya açık biçimde kurmak ve maksimum kardinaliteli eşleşmeleri paralel olarak bulmak, paralelleştirdiğimiz algoritmalara kıyasla çok daha karmaşık olacaktır.

PARFKSLEAN, FKSLean'in kurulum aşamasının paralel bir sürümünü gerçekleştirir. Verimli bellek erişimi sağlamak için kovalarla ilişkili depolama alanı bitişik bir dizi olarak tutulur. Bu da kovaları ve onlarla ilişkili depolama alanını temsil etmek için iyi bilinen compressed sparse row (CSR) biçimine benzer bir veri yapısı kullanmamıza yol açar.

Şekil 1'de fksStorage bitişik bir dizidir ve kovalarla ilişkili depolama alanlarını ardışık şekilde tutar; fksOffset ise fksStorage içindeki her kovanın başlangıç adresini içerir. Bu dizileri verimli biçimde oluşturabilmek için ara bir adımda CSR biçiminde başka bir matris oluşturulur. Başka bir deyişle, PARFKSLEAN tarafından gerçekleştirilen çalışmanın büyük bir kısmı art arda iki matrisin oluşturulması olarak ifade edilir.

Bunlardan ilki (n \times n) boyutunda bir matristir ve her sütuna rastgele tek bir sıfır olmayan değer yerleştirilerek sütun bazında oluşturulur (birinci seviye hash fonksiyonu). Bu matrisin CSR gösterimi, her kova için bir hiperkenar listesi oluşturmak amacıyla hazırlanır.

İkinci matrisin boyutu (n \times S)’dir; burada (S), fksStorage dizisinin boyutudur. Bu ikinci matrisin satır işaretçileri, birincinin satır işaretçileri kullanılarak kurulur. Sütun indeksleri, ikinci seviye karma fonksiyonundaki anahtarlardır; kovaların başlangıcına göre kaydırılmıştır ve saklanmaz. Bunun yerine, hiperkenar kimlikleri sıfırlarla birlikte saklanır—bu nedenle depolama yapısı CSR benzeridir.

Yapım üç aşamada gerçekleştirilir.

  1. Birinci aşama: Bir asal sayı seçilir. Çoğu pratik durumda, (n < 2^{31} - 1) olduğunda, (p) olarak Mersenne asal sayısı (2^{31} - 1) seçilebilir. Eğer (n \ge 2^{31} - 1) ise daha büyük bir asal bulunabilir. Bertrand önermesine göre [9, s. 455], (n > 1) için her zaman (n) ile (2n) arasında bir asal sayı vardır; dolayısıyla (p) değerini bulmak için en fazla (n) sayı test edilmesi gerekir.

  2. İkinci aşama: Birinci seviye karma için uygun bir k bulur ve bir sonraki aşama için veri yapılarını hazırlar.

  3. Üçüncü aşama: İkinci seviye karmayı gerçekleştirir ve Şekil 1’deki veri yapısını son hâline getirir.

Buradaki temel amaç, fksStorage boyutu üzerinde bir üst sınır sağlayan bir k bulmaktır. Daha önce [2] rapor edildiği üzere, rastgele seçilen herhangi bir k, (\sum b_i^2 < 7n) sınırını 1/2’den çok daha yüksek bir olasılıkla sağlar. Bu düşünceden hareketle PARFKSLEAN, rastgele seçilen bir k için kovalar oluşturulurken fksStorage boyutunu hesaplar. Bu yaklaşım, bu aşamada birinci seviye karmanın verimli biçimde gerçekleştirilmesini sağlar ve sonraki aşamada ikinci seviye karma için kaba taneli paralelliğe imkân verir.

Bu aşamada:

Genel hesaplama üç süper-adımda gerçekleştirilir.

A. fksOffset Kurulumu

III. PARALEL OLUŞTURMA

1) Kovalamaya Ayırma (Bucketing)

PARFKSLEAN, her hiperkenar (e) için (h(k, e, p, n)) değerini paralel olarak hesaplar ve bunları bucket_ids adlı bir dizide saklar. Bu hesaplamalar birbirinden bağımsız olduğundan, bucket_ids tamamen paralel şekilde doldurulabilir.

Bu adım, OpenMP’nin parallel for yapısı kullanılarak statik zamanlama ve (\lceil n/T \rceil) sabit parça boyutu ile paralelleştirilir; burada T iş parçacığı sayısıdır. Bu yaklaşım iyi bir yük dengesi sağlar.

2) Kovalar için hiperkenar listelerinin oluşturulması

Sonraki adımda, kovaların hiperkenar listeleri CSR biçiminde items ve offset dizileri kullanılarak oluşturulur.

items ve offset dizilerinin her ikisi de (O(n)) alan karmaşıklığına sahiptir. Bu iki dizi, PARFKSLEAN’in nihai veri yapısının parçası değildir; sonraki aşamada verimli paralelleştirme sağlamak amacıyla oluşturulurlar.

PARFKSLEAN, offset dizisini bucket_ids dizisi kullanılarak paralel bir histogram hesaplaması ve ardından bir prefix-sum işlemi ile oluşturur. Paralel histogram hesaplamasında hiperkenarlar iş parçacıkları arasında eşit biçimde dağıtılır. Bir iş parçacığı kendisine ait hiperkenarları ziyaret eder ve bir hiperkenar (e) için offset[bucket_ids[e]] değerini atomik olarak artırır (atomik toplama kullanılır). Histogram hesaplaması (O(n)) adet atomik işlem gerektirir.

Ardından offset üzerinde prefix-sum işlemi, iyi bilinen iki geçişli bir algoritma kullanılarak hesaplanır. Bu algoritmada:

offset hesaplandıktan sonra PARFKSLEAN, items dizisini paralel olarak oluşturur. Her iş parçacığına (\lceil n/T \rceil) hiperkenar atanır. Bir iş parçacığı kendi hiperkenarlarını tek tek işler. İşlenen her hiperkenar (e) için, iş parçacığı offset[bucket_ids[e]] değerini atomik olarak azaltarak bir ofset değeri elde eder ve (e)’nin kimliğini items dizisinde karşılık gelen konuma yazar. Bu işlem (O(n)) adet atomik işlem gerektirir.

3) Depolama alanının hazırlanması

Bu aşamadaki üçüncü süper-adım, ikinci seviye karmada verimlilik sağlamak amacıyla Şekil 1’de gösterilen fksOffset dizisini hazırlamaktır. Şu gözlemden hareketle:

[ b_i = offset[i + 1] - offset[i] ]

dizi paralel olarak şu şekilde başlatılır:

[ fksOffset[i] = \begin{cases} b_i & \text{eğer } b_i \in {0,1} \ 1 + 2b_i^2 & \text{aksi halde} \end{cases} ]

Her iş parçacığına (\lceil n/T \rceil) kova atayan statik bir zamanlama, bu başlatma sırasında iyi bir yük dengesi sağlar. Ardından offset için daha önce tartışıldığı gibi fksOffset üzerinde paralel bir prefix-sum işlemi gerçekleştirilir. Sonunda fksStorage’ın toplam boyutu fksOffset[n] konumunda elde edilir ve bellek sınırlarının karşılanıp karşılanmadığını kontrol etmek için kullanılabilir.

B. fksStorage’ın Oluşturulması

Bu aşamada PARFKSLEAN önce fksStorage için bellek ayırır. Ardından Şekil 1’deki K anahtar havuzu doldurulur. K içine (2 \log_2 n) adet anahtar konur; bu sayı küçüktür ve paralelleştirme gerektirmez. Bu kadar anahtar, her kovaya uygun bir karma fonksiyonu sağlamak için yeterlidir. Nadir durumlarda bu anahtarlar yetersiz kalırsa, ek anahtarlar üretilebilir ve K’ye eklenebilir.

Ardından PARFKSLEAN, her kova için mükemmel karma bulmak amacıyla kovaları iş parçacıklarına atamaya dayanan kaba taneli bir paralelleştirme yaklaşımı izler. Önceki aşamada yapılan çalışmalar sayesinde offset, items ve fksOffset dizileri hazırdır ve tüm hesaplama son derece kolay paralelleştirilebilir.

Bir kova boşsa yapılacak bir işlem yoktur. Eğer bir kovada yalnızca tek bir hiperkenar varsa, o hiperkenarın kimliği fksStorage içinde saklanır. Birden fazla hiperkenar içeren bir (B_i) kovası için, mükemmel bir karma bulmak amacıyla K’den alınan d-lüler tek tek test edilir.

Bu amaçla, (B_i)’nin hiperkenar listesinde bulunan her hiperkenar (e), test edilen bir (k_i) için aşağıdaki konuma yerleştirilir:

[ h(k_i, e, p, 2b_i^2) + fksOffset[i] ]

Bu işlem, tüm (e) değerleri işlenene kadar (bu durumda (k_i) mükemmel bir karmayı tanımlar) veya bir çakışma oluşana kadar (bu durumda başka bir d-lü denenir) sürer.

Kova başına yapılan iş miktarı eşit değildir. Olası iş yükü dengesizliğini önlemek için PARFKSLEAN dinamik bir zamanlayıcı kullanır. Kovalar üzerindeki döngü, OpenMP’nin parallel for yapısı kullanılarak T iş parçacığı arasında dinamik zamanlama ve (\lceil n/(2T) \rceil) parça boyutu ile paralelleştirilir. Kova sayısı iş parçacığı sayısından çok daha fazla olduğundan, bu paralelleştirme şemasının iyi bir yük dengesi sağlaması beklenir.

IV. DENEYLER

A. Kurulum

Tüm deneyler, 64 çekirdeğe sahip (iki soket, her biri 32 çekirdek) Intel Xeon Gold 5218 CPU üzerinde gerçekleştirilmiştir. İşlemci 2.3 GHz saat hızına, 22 MB L3 önbelleğe ve 384 GB DDR4-2667 belleğe sahiptir ve Debian GNU/Linux 10 (64 bit) çalıştırmaktadır.

Tüm kodlar C++ ile yazılmıştır ve GCC 8.3.0 kullanılarak -O3 ve -march=native optimizasyon bayraklarıyla derlenmiştir. Paralelleştirme için OpenMP kullanılmıştır. PARFKSLEAN içindeki tüm mod n ve mod p işlemleri için sırasıyla fastmod library [11] ve Mersenne asal sayıları ile hızlı modulo işlemleri [17] kullanılmıştır; mod 2b_i^2 işlemleri ise C++’ta standart modulo operatörü % ile gerçekleştirilmiştir.

Ayrıca, bütünlüğü sağlamak amacıyla her iki aracın sorgu yanıt süresini de kısaca inceliyoruz. PARFKSLEAN ve PTHash’ın oluşturma ve sorgu aşamalarındaki yürütme sürelerini 10 bağımsız çalıştırmanın ortalaması olarak raporluyoruz.

PTHash uygulaması 64-bit öğeler üzerinde çalışır ve arayüz, diğer giriş türlerinin universe reduction [17] adı verilen bir teknik kullanılarak 64-bit anahtarlara dönüştürülmesini önerir. Bu dönüşümü çevrimdışı gerçekleştiriyoruz ve dönüşüm sürelerini PTHash varyantlarının oluşturma aşamasına dahil etmiyoruz.

Girdi Tensörleri

PARFKSLEAN performansını değerlendirmek için gerçek dünya uygulamalarından türetilmiş on adet seyrek tensör üzerinde deneyler sunuyoruz. Tüm tensörler FROSTT [16] içinde bulunmaktadır ve Tablo I’de sıfır olmayan eleman sayısına göre artan sırayla açıklanmıştır. Ayrıca bu tensörlere verilen sıraya göre T-1 ile T-10 arasında referans veriyoruz.

Karşılaştırmalar

Önerilen PARFKSLEAN yöntemini, PTHash’ın en güncel uygulamasıyla (sürüm 1.0.1, https://github.com/jermp/pthash/) karşılaştırıyoruz.

PTHash’ı, orijinal kaynakta [15] önerildiği şekilde üç farklı parametre ayarıyla çalıştırıyoruz:

PTHash’ın oluşturma aşaması paraleldir, ancak sorgu aşaması değildir. Sorgu aşamasını paralelleştirmek için hem PARFKSLEAN hem de PTHash’ta aynı döngü-paralelliği yaklaşımını izledik; her sorgu bir iş parçacığına atanır. OpenMP’nin paralel for döngüleri için statik zamanlama kullanılmıştır.

Bu nedenle temel olarak PARFKSLEAN ve PTHash’ın oluşturma aşamasındaki çalışma süresi ve ölçeklenebilirliğini inceliyoruz.

B. Oluşturma Aşamasının Analizi

Şekil 2, {2, 4, 8, 16, 32, 64} olmak üzere altı farklı iş parçacığı yapılandırması için oluşturma aşamasında PARFKSLEAN ve PTHash’ın çalışma sürelerinin karşılaştırmasını sunar.

Her bir grafikte oluşturma süresi, her tensör için PARFKSLEAN’ın oluşturma süresine göre normalize edilmiştir. Dolayısıyla her girdi için PARFKSLEAN’a karşılık gelen sütun birim yüksekliğe sahiptir. PARFKSLEAN’ın çalışma süresi saniye cinsinden, her tensör için PARFKSLEAN sütununun üzerinde belirtilmiştir.

Bu tartışmanın ışığında, PARFKSLEAN’ın oluşturma aşamasının en hızlı PTHash varyantından bile her zaman daha hızlı olduğu sonucuna varıyoruz.

Şekil 3, nell-2, flickr-4d, delicious-4d ve nell-1 veri kümelerinde PARFKSLEAN ve PTHash varyantlarının oluşturma aşamasındaki paralel ölçeklenmesini göstermektedir. Veri kümesindeki sıfır olmayan eleman sayıları farklı olan en büyük dört tensörü seçtik.

Şekilde PARFKSLEAN ve PTHash varyantlarının hızlanma değerleri, kendi iki iş parçacıklı çalışma sürelerine göre ölçülmüştür. Bu karşılaştırma PARFKSLEAN’ın paralelleştirme yaklaşımının etkinliğini ortaya koymaktadır. Tüm test edilen durumlarda PARFKSLEAN’ın PTHash’tan daha iyi ölçeklendiğini gözlemliyoruz.

daki her tensör için. Üç PTHash varyantına karşılık gelen sütunlarda, eğer sütun yüksekliği bir birimden büyükse, sütun ne kadar yüksekse PARFKSLEAN’a göre o kadar yavaştır.

Şekil 2a–2f’te görüldüğü üzere, PARFKSLEAN’ın oluşturma aşaması PTHash’ın üç varyantının da her zaman önündedir. İş parçacığı sayısı arttıkça PARFKSLEAN’ın PTHash’a göre göreli performansı tüm girdi tensörlerinde iyileşmektedir; bu durum daha yüksek iş parçacığı sayılarında PTHash varyantlarına karşılık gelen daha yüksek sütunlarla açıkça görülmektedir. PARFKSLEAN, oluşturma aşamasında PTHash’ın en iyi performans gösteren varyantından 5.6 kata kadar daha hızlıdır; en yüksek hızlanma PTHash-PC’ye göre elde edilmiştir.

Şekil 2 (devam)

16, 32 ve 64 iş parçacığı ile PARFKSLEAN ve PTHash’ın oluşturma süreleri. Y ekseni, PARFKSLEAN’a göre normalize edilmiş oluşturma süresini göstermektedir. PARFKSLEAN’ın mutlak oluşturma süresi (saniye cinsinden) her tensör için kendi sütununun üzerinde verilmiştir.

(d) # iş parçacığı = 16

Algoritmalar:

Tensörler:

(e) # iş parçacığı = 32

Algoritmalar:

Tensörler:

(f) # iş parçacığı = 64

Algoritmalar:

Tensörler:

PARFKSLEAN’ın 2 iş parçacığıyla elde edilen oluşturma süresi, 1 iş parçacığıyla elde edilene göre 1.9 kat daha hızlıdır—bu durum Tablo II ile Şekil 2a’daki mutlak çalışma sürelerinin karşılaştırılmasıyla görülmektedir. Tabloda FKSLean’ın ortalama olarak 1 iş parçacığıyla çalıştırılan PARFKSLEAN’dan 2.66 kat daha hızlı olduğunu görüyoruz. Dolayısıyla oluşturma aşamasında FKSLean, 2 iş parçacığıyla çalıştırılan PARFKSLEAN’dan tüm girdiler için daha hızlıdır; ortalama olarak 1.37 kat daha hızlıdır. Bunun nedeni, Bölüm III’te tartışıldığı gibi, PARFKSLEAN’ın paralelleştirme amacıyla FKSLean’dan daha fazla iş yapmasıdır. Ayrıca paralelleştirmeye bağlı ek yükler de vardır.

Bununla birlikte, dört ve daha fazla iş parçacığında paralelleştirmenin sağladığı faydalar ek iş yükü ve diğer ek maliyetlerden daha ağır basmaktadır. PARFKSLEAN için hızlanma değeri iş parçacığı sayısı arttıkça sürekli artmaktadır. 64 iş parçacığında, 2 iş parçacığına göre hızlanma değeri dört tensörün tamamında 17’nin üzerindedir. PARFKSLEAN’ın hızlanma eğrileri farklı tensörlerde benzerlik göstermektedir; bu durum PARFKSLEAN’ın sağlam olduğunu ve girdiye aşırı duyarlı olmadığını göstermektedir. Öte yandan PTHash varyantlarının hızlanması tüm girdilerde 32 iş parçacığından sonra neredeyse plato yapmaktadır.

Ölçeklenebilirlik Çalışması

Şimdi PARFKSLEAN’ın optimize edilmiş sıralı bir uygulama olan FKSLean’a göre ölçeklenebilirliğini yorumluyoruz. Tablo II, daha önce bahsedilen dört büyük tensör için FKSLean ve tek iş parçacıklı PARFKSLEAN’ın oluşturma sürelerini göstermektedir.

Şekil 3

Dört büyük tensör üzerinde PARFKSLEAN ve PTHash’ın oluşturma aşamasının ölçeklenebilirliği.

Veri kümeleri:

Algoritmalar:

İş parçacığı sayıları:

Tablo II

FKSLean ve PARFKSLEAN’ın 1 iş parçacığı ile oluşturma süreleri (saniye).

Bu ayarda PARFKSLEAN, FKSLean’a göre her zaman hızlanma elde eder. Tüm iş parçacığı ayarlarında (4 ve üzeri) ölçeklenebilirlik, Şekil 2’deki çalışma sürelerinin Tablo II’deki FKSLean süreleriyle karşılaştırılmasıyla görülebilir. Özellikle 64 iş parçacığında PARFKSLEAN, T-5, T-7, T-9 ve T-10 tensörleri için FKSLean’a göre ortalama 12.94 kat hızlanma elde etmektedir.

Şekil 2, Şekil 3 ve Tablo II için yapılan gözlemleri birleştirdiğimizde, PARFKSLEAN’ın oluşturma aşamasının iyi ölçeklendiği ve dört veya daha fazla iş parçacığında FKSLean’a göre hızlanma sağladığı sonucuna varıyoruz. Ayrıca paralel ölçeklenmesi PTHash’tan daha iyidir.

C. Sorgu Yanıt Süresinin Analizi

Sorguların sorgu aşamasının başında mevcut olduğunu varsayıyoruz. Sorgu işleme kaba taneli bir strateji kullanılarak paralelleştirilmiştir. Her sorgu bir iş parçacığına atanır. Tüm sorgular paralel olarak bağımsız biçimde işlenir. Tek bir sorgunun işlenmesi içinde paralellik yoktur.

Tablo III, daha önce belirtilen dört büyük tensör için 10^7 sorguya yanıt verirken PARFKSLEAN ve PTHash varyantlarının sorgu aşamasındaki çalışma sürelerini karşılaştırmaktadır. Bu tabloda görüldüğü üzere PARFKSLEAN, tüm iş parçacığı yapılandırmalarında ve tüm girdiler için, 64 iş parçacıklı nell-1 durumu hariç (bu durumda iki araç da aynı yanıt süresine sahiptir), PTHash’ın en iyi performans gösteren varyantı kadar hızlı veya ondan daha hızlıdır.

PARFKSLEAN, flickr-4d üzerinde 4 iş parçacığı ile PTHash-DD'ye kıyasla en fazla 1.94 hızlanma elde eder. Dolayısıyla PARFKSLEAN, sorguları yanıtlamak açısından genel olarak en hızlı PTHash varyantından daha hızlıdır. Her iki durumda da her sorgu tek bir iş parçacığı tarafından yanıtlandığından, fark ilgili algoritmaların özgün performansından kaynaklanmaktadır.

KAYNAKLAR

  1. A. Azad, A. Buluç, and A. Pothen, “Computing maximum cardinality matchings in parallel on bipartite graphs via tree-grafting,” IEEE Transactions on Parallel and Distributed Systems, cilt 28, no. 1, ss. 44–59, 2017.

  2. J. Bertrand, F. Dufossé, and B. Uçar, “Algorithms and data structures for hyperedge queries,” Inria Grenoble Rhône-Alpes, Research Report RR-9390, Şub. 2021.

  3. B. H. Bloom, “Space/time trade-offs in hash coding with allowable errors,” Communications of the ACM, cilt 13, no. 7, ss. 422–426, 1970.

  4. P. C. Dillinger, L. Hübscle-Schneider, P. Sanders, and S. Walzer, “Fast succinct retrieval and approximate membership using ribbon,” arXiv:2109.01892, 2021.

  5. F. Dufossé, K. Kaya, and B. Uçar, “Two approximation algorithms for bipartite matching on multicore architectures,” Journal of Parallel and Distributed Computing, cilt 85, ss. 62–78, 2015.

  6. E. Esposito, T. Mueller Graf, and S. Vigna, “RecSplit: Minimal perfect hashing via recursive splitting,” in Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX). SIAM, 2020, ss. 175–185.

  7. M. L. Fredman, J. Komlós, and E. Szemerédi, “Storing a sparse table with O(1) worst case access time,” J. ACM, cilt 31, no. 3, ss. 538–544, 1984.

  8. T. M. Graf and D. Lemire, “Binary fuse filters: Fast and smaller than xor filters,” arXiv:2201.01174, 2022.

  9. G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 6. baskı. Oxford Univ. Press, 2008.

  10. T. G. Kolda and D. Hong, “Stochastic gradients for large-scale tensor decomposition,” SIAM Journal on Mathematics of Data Science, cilt 2, no. 4, ss. 1066–1095, 2020.

  11. D. Lemire, O. Kaser, and N. Kurz, “Faster remainder by direct computation: Applications to compilers and software libraries,” Software: Practice and Experience, no. 6, ss. 953–970, 2019.

  12. A. Limasset, G. Rizk, R. Chikhi, and P. Peterlongo, “Fast and Scalable Minimal Perfect Hashing for Massive Key Sets,” in 16th International Symposium on Experimental Algorithms (SEA), 2017, ss. 25:1–25:16.

  13. R. Pagh and F. F. Rodler, “Cuckoo hashing,” in Algorithms — ESA 2001, F. M. auf der Heide, Ed. Springer Berlin Heidelberg, 2001, ss. 121–133.

  14. G. E. Pibiri and R. Trani, “PTHash: Revisiting FCH minimal perfect hashing,” in 44th SIGIR International Conference on Research and Development in Information Retrieval. ACM, 2021, ss. 1339–1348.

  15. G. E. Pibiri and R. Trani, “Parallel and external-memory construction of minimal perfect hash functions with PTHash,” arXiv:2106.02350, 2021.

  16. S. Smith, J. W. Choi, J. Li, R. Vuduc, J. Park, X. Liu, and G. Karypis, “FROSTT: The formidable repository of open sparse tensors and tools,” http://frostt.io/, 2017.

  17. M. Thorup, “High speed hashing for integers and strings,” arXiv:1504.06804, 2015.

  18. S. Walzer, “Peeling close to the orientability threshold—spatial coupling in hashing-based data structures,” in Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2021, ss. 2194–2211.

Bu makale, yakın zamanda geliştirilmiş bir mükemmel karma yönteminin verimli bir paylaşımlı bellek paralel gerçekleştirimini önermektedir. Bu yöntem, verilen bir hiperçizgede hiperkenarların varlığını verimli biçimde sorgulamak için kullanılmaktadır. Başka bir ifadeyle, yöntem seyrek bir matrisin veya bir tensörün sıfır olmayan elemanlarını sorgulamak amacıyla tasarlanmıştır.

Deneyler büyük seyrek tensörler üzerinde gerçekleştirilmiş ve başka bir son teknoloji mükemmel karma yöntemine kıyasla daha iyi çalışma süresi ve ölçeklenebilirlik gösterilmiştir.

Makalenin odağı d-uniform, d-partite hiperçizgeler üzerindedir. Neyse ki yöntem, keyfi hiperçizgelere kolayca genişletilebilir. İkinci seviye karma fonksiyonlarının saklanmasında çok fazla alan israf edilmemesine dikkat edilmelidir.

Bir diğer genelleştirme, hiperkenarların eklenebildiği veya silinebildiği dinamik ortamlarla ilgilidir; bu genelleştirme çeşitli ortamlarda uygulama alanı bulabilir. Yukarıdaki iki nokta gelecekte yapılacak çalışmaların konusunu oluşturmaktadır.