Optimal ikili arama ağaçlarının paralel oluşturulması
Parallel construction of optimal binary search trees
Yazar: KAVEH FEYZİ
Danışman: YRD. DOÇ. DR. DENİZ DAL
Atatürk Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Yüksek Lisans, 2014
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control

Ö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ı.

Abstract:
In this master's thesis, parallel construction of optimal binary search trees has been studied. An optimal binary search tree is a binary search tree where the nodes are arranged in such a way that the tree cost is minimum. In binary search trees, the left subtree of a node contains nodes whose key values are less than the node's key; similarly the right subtree of the very same node contains nodes whose key values are greater than the node's key. Due to the excessive processing time for the ever increasing number of data, we need parallel processing for constructing optimal binary search trees. The idea of parallel processing is to simultaneously execute the different parts of a task and finish it in less time.
In this regard, two software have been written. In both of these implementations, a user can first either select one of the available input files for processing or create a new input file with random keys. During the following stage, the first software model employs a shared memory architecture with OpenMP whereas the second model chooses a hybrid approach using both OpenMP and MPI for constructing optimal binary search trees in parallel. Both software uses c++ as the programing language. In the end, their performance is compared with respect to the serial implementation and promising results are obtained.
 
Keywords: OpenMP, MPI, Parallel Computing, Optimal Binary Search Tree