Adaptation of multiway-merge sorting algorithm to MIMD architectures with an experimental study
Çok yönlü paralel birleştirme sıralama algoritmasının deneysel çalışmaları ile birlikte çoklu komut çoklu data mimarilerine uyarlanması
- Tez No: 129186
- Danışmanlar: PROF. DR. CEVDET AYKANAT
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Sıralama, paralel sıralama, algoritmalar, çokyönlü-birleştirme sıralaması, bilgisayar kümelerinde sıralama. vı, Sorting, parallel sorting, algorithms, multivvay-merge sorting, sorting in clusters. IV
- Yıl: 2002
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 96
Özet
ÖZET ÇOK YÖNLÜ PARALEL BİRLEŞTİRME SIRALAMA ALGORİTMASININ DENEYSEL ÇALIŞMALARI İLE BİRLİKTE ÇOKLU KOMUT ÇOKLU DATA MİMARİLERİNE UYARLANMASI Levent Cantürk Bilgisayar Mühendisliği, Yüksek Lisans Tez Yöneticisi: Prof. Dr. Cevdet Aykanat Nisan, 2002 Elemanları sıralama problemi, hesaplamalarda muhtemelen üzerinde en çok çalışmış olan problemlerin başında gelmektedir. Bu konuda oldukça fazla optimum algoritmalar geliştirilmiştir. Bu algoritmalar birçok paralel model üzerinde denendi. Bunlar arasında tabi ki çoklu komut çoklu data (ÇKÇD) mimarileri için önerilen ve oldukça iyi çalışan algoritmalar da yer aldı. Bu çalışmamızda biz de, esasen ürün ağları için tasarlanmış çok yönlü birleştirme paralel sıralama algoritmasını ÇKÇD mimarilerine uygun hale getirdik. Çalışmamız, iş yükünün parallel makinalara dengeli dağıtılması, bilgisayarlar arasındaki iletişim yükünün azaltılması ve kendine has performans özellikleriyle oldukça başarılı bir uyarlamadır. Çok yönlü birleştirme sıralama algoritması, sıralanacak eleman sayısından bağımsız olarak sadece iki kere bütün bilgisayarlardan bütün bilgisayarlara kişisel iletişim ve iki kere de bilgisayardan bilgisayara iletişime ihtiyaç duymaktadır. Ek olarak, bu algoritma en kötü olasılıkla 2N/P kadar lokal belleğe ihtiyaç duymaktadır. Burada N sıralanacak eleman sayısını, P ise sıralamada kullanılacak işlemci sayısını temsil etmektedir. Algoritmayı Bilkent Üniversitesi Bilgisayar Mühendisliğinde kurulmuş olan dağıtık bellekli bilgisayar kümesi üzerinde programlayarak test ettik. Sonuçlan karşılaştırma açısından bir tane örneklemeye dayalı paralel sıralama algoritmalarından (PSRS) birtane de paralel hızlısıralama algoritması örneğini (Hyperquicksort) aynı sistem ü/erinde geliştirdik. Deneylerimizde girdi verilerinin dağılımlarına dayanan üç farklı kalite testi“uniformly”,“Gaussian”ve“Zero”olmak üzere uyguladık. Çok yönlü birleştirme algoritması diğer iki algoritmaya göre daha iyi sonuçlar elde etmemesine rağmen,“Zero”kalite testinde olduğu gibi bazı durumlarda da diyer aluoritmaları geçmiştir. Deneylerin sonuçları raporda detaylı olarak sunulmuştur. Çok yönlü birleştirme algoritması en iyi sıralama algoritması olmamasına rağmen, bir çok ÇKÇD mimarisindeki bilgisayarda çalışabilecek ve kabul edilebilir performans verebilecek bir algoritmadır.
Özet (Çeviri)
ABSTRACT ADAPTATION OF MULTIWAY-MERGE SORTING ALGORITHM TO MIMD ARCHITECTURES WITH AN EXPERIMENTAL STUDY Levent Cantürk M.S. in Computer Engineering Supervisor: Prof. Dr. Cevdet Aykanat April, 2002 Sorting is perhaps one of the most widely studied problems of computing. Numerous asymptotically optimal sequential algorithms have been discovered. Asymptotically optimal algorithms have been presented for varying parallel models as well. Parallel sorting algorithms have already been proposed for a variety of multiple instruction, multiple data streams (MIMD) architectures. In this thesis, we adapt the multiway- merge sorting algorithm that is originally designed for product networks, to MIMD architectures. It has good load balancing properties, modest communication needs and well performance. The multiway-merge sort algorithm requires only two all-to-all personalized communication (AAPC) and two one-to-one communications independent from the input size. In addition to evenly distributed load balancing, the algorithm requires only size of 2N/P local memory for each processor in the worst case, where N is the number of items to be sorted and P is the number of processors. We have implemented the algorithm on the PC Cluster that is established at Computer Engineering Department of Bilkent University. To compare the results we have implemented a sample sort algorithm (PSRS Parallel Sorting by Regular Sampling) by X. Liu et all and a parallel quicksort algorithm (HyperQuickSort) on the same cluster. In the experimental studies we have used three different benchmarks namely Uniformly, Gaussian, and Zero distributed inputs. Although the multiway- merge algorithm did not achieve better results than the other two, which are 't theoretically cost optimal algorithms, there are some cases that the multiway-merge algorithm outperforms the other two like in Zero distributed input. The results of the inexperiments are reported in detail. The multivvay-merge sort algorithm is not necessarily the best parallel sorting algorithm, but it is expected to achieve acceptable performance on a wide spectrum of MIMD architectures.
Benzer Tezler
- Çokyönlü dizilerin yüksek boyutlu model gösterilim ve/veya ağırlıklı indirgeyimcil ayrıştırım tabanlı anlatımları ve uygulamaları
Weighted reductive and hdmr based decompositions of multiway arrays and it?s application
LETİSYA DİVANYAN
Yüksek Lisans
Türkçe
2012
Mühendislik Bilimleriİstanbul Teknik ÜniversitesiHesaplamalı Bilimler ve Mühendislik Ana Bilim Dalı
PROF. DR. METİN DEMRİALP
- Life cycle assessment of glassware products
Cam ürünler için yaşam döngüsü değerlendirmesi
ASLI ALKAN
Yüksek Lisans
İngilizce
2004
Çevre MühendisliğiBoğaziçi ÜniversitesiÇevre Mühendisliği Ana Bilim Dalı
PROF. DR. NİLGÜN KIRAN CILIZ
- Kırsal kalkınma planlaması; Bursa ili Keles ilçesi örneği
Rural development planning; a case of Keles county, Bursa
İ. BÜLENT GÜRBÜZ
- Kariyer planlamasının problem çözme becerileri ve yanal düşünme eğilimleri üzerindeki etkisinin incelenmesi: Spor Bilimleri Fakültesi öğrencileri üzerine bir araştırma
Examining the effect of career planning on problem solving skills and lateral thinking tendencies: A study on Sport Sciences Faculty students
MUSTAFA TAZE
Doktora
Türkçe
2024
SporMuş Alparslan ÜniversitesiBeden Eğitimi ve Spor Ana Bilim Dalı
DR. ÖĞR. ÜYESİ METİN KARAYOL
- Fraktal geometri konusunun ortaöğretim programına uygulanması
Adaptation of the subject of fractal geometry into the program of lise
COŞKUN ÜSTÜN
Yüksek Lisans
Türkçe
1999
Eğitim ve ÖğretimKaradeniz Teknik ÜniversitesiFen Bilimleri Eğitimi Ana Bilim Dalı
DOÇ. DR. ADNAN BAKİ