Optimal ikili arama ağaçlarının paralel oluşturulması
Parallel construction of optimal binary search trees
- Tez No: 352112
- Danışmanlar: YRD. DOÇ. DR. DENİZ DAL
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: OpenMP, MPI, Paralel Hesaplama, Optimal İkili Arama Ağacı, OpenMP, MPI, Parallel Computing, Optimal Binary Search Tree
- Yıl: 2014
- Dil: Türkçe
- Üniversite: Atatürk Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- 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
- 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
2009
HukukGalatasaray ÜniversitesiKamu Hukuku Ana Bilim Dalı
PROF. DR. JEAN MARC SOREL
PROF. DR. HALİL ERCÜMENT ERDEM
- 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
2001
Jeodezi ve Fotogrametriİstanbul Teknik ÜniversitesiJeodezi ve Fotogrametri Mühendisliği Ana Bilim Dalı
DOÇ.DR. FİLİZ SUNAR ERBEK
- 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
1998
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
DOÇ. DR. ERTUĞRUL ÇELEBİ
- Yapay sinir ağlarında öğrenme algoritmalarının analizi
Analysis of learning algorithms in neural networks
SEVİNÇ BAKLAVACI
Yüksek Lisans
Türkçe
1994
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiDOÇ.DR. LEYLA GÖREN
- 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
2014
Endüstri ve Endüstri MühendisliğiUludağ ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. ERDAL EMEL