Geri Dön

Optimal ikili arama ağaçlarının paralel oluşturulması

Parallel construction of optimal binary search trees

  1. Tez No: 352112
  2. Yazar: KAVEH FEYZİ
  3. Danışmanlar: YRD. DOÇ. DR. DENİZ DAL
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: OpenMP, MPI, Paralel Hesaplama, Optimal İkili Arama Ağacı, OpenMP, MPI, Parallel Computing, Optimal Binary Search Tree
  7. Yıl: 2014
  8. Dil: Türkçe
  9. Üniversite: Atatürk Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 106

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

Özet (Çeviri)

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.

Benzer Tezler

  1. Contribution a la recherche d'un cadre juridique pour un droit international de laconcurrence plus efficace

    Daha etkin bir uluslararası rekabet için hukuki çerçeve arayışı

    ALİ CENK KESKİN

    Doktora

    Fransızca

    Fransızca

    2009

    HukukGalatasaray Üniversitesi

    Kamu Hukuku Ana Bilim Dalı

    PROF. DR. JEAN MARC SOREL

    PROF. DR. HALİL ERCÜMENT ERDEM

  2. Uydu görüntü verisinin yapay sinir ağları ile sınıflandırılması

    Classification of satellite imagery data with artificial neural networks

    COŞKUN ÖZKAN

    Doktora

    Türkçe

    Türkçe

    2001

    Jeodezi ve Fotogrametriİstanbul Teknik Üniversitesi

    Jeodezi ve Fotogrametri Mühendisliği Ana Bilim Dalı

    DOÇ.DR. FİLİZ SUNAR ERBEK

  3. Markov random fields and a multiscale implementation of markov random fields on Bayesian image segmentation

    Başlık çevirisi yok

    UĞUR SIVAKÇI

    Yüksek Lisans

    İngilizce

    İngilizce

    1998

    Elektrik ve Elektronik Mühendisliğiİstanbul Teknik Üniversitesi

    Elektrik-Elektronik Mühendisliği Ana Bilim Dalı

    DOÇ. DR. ERTUĞRUL ÇELEBİ

  4. Yapay sinir ağlarında öğrenme algoritmalarının analizi

    Analysis of learning algorithms in neural networks

    SEVİNÇ BAKLAVACI

  5. Elektromanyetik algoritmanın karşılaştırmalı analizi ve geliştirilmesi

    Comparative analysis and improvement of electromagnetism-like algorithm

    ALKIN YURTKURAN

    Doktora

    Türkçe

    Türkçe

    2014

    Endüstri ve Endüstri MühendisliğiUludağ Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    PROF. DR. ERDAL EMEL