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ı, Bilgisayarlar, Sorting, parallel sorting, algorithms, multivvay-merge sorting, sorting in clusters. IV, Computers, Ordering
- 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ı: Belirtilmemiş.
Ö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
- İklim değişikliğine mekansal uyumda toprak ekosistem servislerinin rolü: Nilüfer çayı havzası
The role of soil ecosystem services in spatial adaptation to climate change: Nilüfer stream basin
MERVE YILMAZ MUTLU
Yüksek Lisans
Türkçe
2023
Şehircilik ve Bölge Planlamaİstanbul Teknik ÜniversitesiŞehir ve Bölge Planlama Ana Bilim Dalı
PROF. DR. AZİME TEZER
- Dünyada ve osmanlı imparatorluğu'nda meteorolojinin kurumsallaşması: amelî ve tatbîkî meteoroloji üzerine bir inceleme
The institutionalization of meteorology in the world and the ottoman empire: an analysis of amelî ve tatbîkî meteoroloji
KARDELEN ALTINAY
Yüksek Lisans
Türkçe
2025
Tarihİstanbul Teknik ÜniversitesiBilim ve Teknoloji Tarihi Ana Bilim Dalı
DOÇ. DR. HASAN KARATAŞ
- Sedad Hakkı Eldem'in çeşitlenen mimarlığını yumak metaforu bağlamında okumak: Alternatif bir anlatının ilk sarmalları
Reading Sedad Hakkı Eldem's diversified architectural productions in the context of the skein metaphor: Initial windings of an alternative narrative
ÖMER FARUK TEKİN
Doktora
Türkçe
2024
Mimarlıkİstanbul Teknik ÜniversitesiMimarlık Ana Bilim Dalı
PROF. DR. MEHMET MURAT GÜL
- Dinamik ortamlar için istatiksel metotlar kullanan çoklu evrimsel algoritmalar
Multiploid evolutionary algorithms with statistical methods for dynamic environments
EMRULLAH GAZİOĞLU
Doktora
Türkçe
2022
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. AYŞE ŞİMA UYAR
- Genom boyu taramaları ve moleküler genetik yaklaşımlarıyla Escherichia coli bakterisinde bor toleransı ile ilgili genlerin araştırılması
Investigation of genes related to boron tolerance in Escherichia coli using genome-wide screening and molecular genetic approaches
MERVE SEZER