Optimal İkili Arama Ağaçlarının Paralel Oluşturulması

---

Tezin Türü: Yüksek Lisans

Tezin Yürütüldüğü Kurum: Atatürk Üniversitesi, Mühendislik Fakültesi, Bilgisayar Mühendisliği, Türkiye

Tezin Onay Tarihi: 2014

Tezin Dili: Türkçe

Öğrenci: Kaveh Feyzi

Danışman: Deniz Dal

Açık Arşiv Koleksiyonu: AVESİS Açık Erişim Koleksiyonu

Özet:

Bu yüksek lisans tezinde optimal ikili arama ağaçlarının paralel oluşturulması üzerinde çalışılmıştır. Optimal ikili arama ağacı, düğümleri arama maliyeti minimum olacak şekilde düzenlenmiş bir ikili arama ağacıdır. İkili arama ağaçlarında her bir düğümün solundaki tüm düğümler kendisinden küçük, sağındakiler ise kendisinden büyüktür. Optimal ikili arama ağaçlarında paralel hesaplamaya ihtiyaç duyulmasının nedeni, verilerin miktarı arttıkça işlem süresinin aşırı derecede uzamasıdır. Paralel hesaplamadaki düşünce, bir işin farklı kısımlarının eş zamanlı yürütülerek işin daha kısa sürede bitirilmesini sağlamaktır. Bu çalışmada bu doğrultuda iki yazılım örneği hazırlanmıştır. Bunların ikisinde de var olan veri dosyalarından birisini seçme veya rastgele veri içeren yeni bir dosya üretme seçeneği sunan bir kod ile açılış yapılmıştır. Yazılım örneklerinin ilkinin devamında paylaşımlı bellek mimarisi ve OpenMP kullanılarak paralel optimal ikili arama ağaçları oluşturulmuştur. İkincisinin devamında ise MPI kütüphanesi ve OpenMP ile hibrid mimari kullanılarak paralel optimal ikili arama ağaçları oluşturulmuştur. Her iki yazılım örneğinde de programlama dili olarak C++ kullanılmıştır. Çalışmanın sonunda her iki yazılım örneğinin performansları karşılaştırılmıştır ve seri versiyona kıyasla oldukça iyi sonuçlara ulaşılmıştır. Anahtar Kelimeler: OpenMP, MPI, Paralel Hesaplama, Optimal İkili Arama Ağacı.