Paralel matris işlemleri kütüphanesinin çizge bölümlemeye dayalı olarak gerçeklenmesi
Parallel matrix library using graph partitioning
- Tez No: 120229
- Danışmanlar: PROF.DR. TURHAN TUNALI
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Çizge bölümleme, paralel programlama, dağıtık sistemler, matris işlemleri, Grafik bölümleme, Graph Partitioning, parallel programming, distributed systems, matrix operations, Parallel programs
- Yıl: 2002
- Dil: Türkçe
- Üniversite: Ege Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Uluslararası Bilgisayar Ana Bilim Dalı (disiplinlerarası)
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
ÖZET PARALEL MATRİS İŞLEMLERİ KÜTÜPHANESİNİN ÇİZGE BÖLÜMLEMEYE DAYALI OLARAK GERÇEKLENMESİ ALP, Ali Yüksek Lisans Tezi, Uluslararası Bilgisayar Enstitüsü Tez Yöneticisi: Prof.Dr. Kayhan ERCİYEŞ Ağustos, 2002, 107 sayfa Bu tezde çizge bölümleme metodları kullanılarak dinamik paralel matris işlemleri kütüphanesi gerçekleştirilmiş ve çizge bölümleme için yeni yöntemler önerilmiştir. Çizge bölümleme problemini çözmek için geliştirilen seri ve paralel algoritmaların coğrafi bilgi sistemleri, bilimsel hesaplamalar, iş paylaşımı vb. gibi bir çok alanda uygulamaları vardır. Bu tezde sunulan çizge bölümleme algoritması diğer yöntemlerde olduğu gibi kabalaştırma, parçalama ve ayrıştırma aşamalarını içermektedir. Eski metodlardan farklı olarak önerilen yöntemde ilk olarak birbirlerinden belirli uzaklıkta olan sabit düğümler seçilir ve bunlar kabalaştırma aşamasında kendilerine komşu olan uygun düğümler ile kümelenir. Yeni yöntem ile elde edilen sonuçlar diğer metodların sonuçları ile karşılaştırıldığında, yeni yöntemin çok daha dengeli, eşit büyüklükteVI çizge bölümleri oluşturduğu görülmüştür. Bu tezde ayrıca, önerilen merkezi düğüm algoritması paralel hale getirilmiş ve iş istasyonları grubu kullanılarak uygulaması yapılmıştır. Elde edilen sonuçlar paralel algoritmanın seri algoritmaya göre daha iyi çalışma zamanına sahip olduğunu göstermiştir. Basit paralel matris işlemlerini gerçekleştiren çok sayıda paralel matris kütüphanesi bulunmasına karşın, bu tezde gerçekleştirilen kütüphanede kullanıcılar, matris boyutunu, yapılacak matris işlemini ve bu işlemde kullanılacak olan çizge bölümleme yöntemini seçebildiği için kütüphane dinamik bir yapıya sahiptir. Seri çalışma zamanı oldukça yüksek olan matris çarpımı, kofaktör ve adjoint matrisinin bulunması, ters matrisin hesaplanması işlemleri paralel matris kütüphanesinde gerçekleştirildiğinde seri sürenin altına inildiği ve yüksek speed-up değerlerinin elde edildiği görülmüştür. Ancak, matris toplama, çıkarma, matris determinantının ve kronecker çarpımının hesaplanması gibi kısa seri çalışma zamanlarına sahip işlemlerde seri sürenin altına inilemememiştir. Elde edilen sonuçlar, bu işlemlerin paralelleştirilmeye uygun olmadığını göstermiştir.
Özet (Çeviri)
VII ABSTRACT PARALLEL MATRIX LIBRARY USING GRAPH PARTITIONING ALP, Ali Msc in International Computing Institute Supervisor: Prof.Dr. Kayhan HRCİYEŞ August, 2002, 1 07 pages In this thesis, a dynamic parallel matrix library using graph partitioning is. realized and new methods are developed for the graph partitioning. Serial and parallel algorithms for the graph partitioning problem that has extensive applications in many areas, including scientific computing, task scheduling and geographical information systems have been presented The presented algorithm has coarsening, partitioning and uncoarsening phases like other partitioning methods. But, fixed nodes which have a specified distance to each others have been chosen and they have been coarsened with their neighbor nodes in the coarsening phase. Much better balanced partitions have been obtained in the new method than in other algorithms. Also, a parallel method for the centered node matching(CM) algorithm has been developed. It is shown that parallel CM has better runtimes than the serial one.VIII Although there are many parallel matrix libraries which implement basic parallel matrix operations, the library implemented in this thesis differs from them because of its dynamic structure. In this dynamic parallel matrix library, user can choose the matrix size, matrix operation and the graph partitioning method. Some matrix operations such as multiplication, calculation of the inverse, cofactor and adjoint matrixes have long serial run time. Fortunately, in the paralel matrix library, these operations have shorter parallel runtimes than the serial times and high speed-up values, good efficiencies. However, because of the very short serial run times of some matrix operations such as matrix addition/subtraction, calculation of the Kronecker Product and the determinant of a matrix, library has obtained longer parallel am times and bad speed-up values for this operations. Therefore, it is seen that addition/subtraction, Kronecker Product and determinant operations is not suitable for parallelization.
Benzer Tezler
- Çamaşır makinelerinde kullanılan plastik kasnakların seri üretim otomasyon sistemi tasarım doğrulama analizi
Mass production automation system design verification analysis of plastic pulley used in washing machine
HİLAL YILDIZ
Yüksek Lisans
Türkçe
2024
Mekatronik Mühendisliğiİstanbul Teknik ÜniversitesiMekatronik Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ SIDDIK MURAT YEŞİLOĞLU
- Designing a fast direct sparse matrix solver for multi-core distributed systems
Çok çekirdekli dağıtık sistemler için hızlı doğrudan seyrek matris çözücü tasarlanması
MEHMET TUNÇEL
Yüksek Lisans
İngilizce
2013
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiHesaplamalı Bilim ve Mühendislik Ana Bilim Dalı (disiplinlerarası)
PROF. DR. MUSTAFA SERDAR ÇELEBİ
- Python ve Julia programlarının doğrusal olmayan deprem analizleri ve paralel programlamaya uygunluklarının araştırılması
Applicability of Python and Julia languages to nonlinear seismic analysis of structures and parallel programing
BARIŞ KASAPOĞLU
Yüksek Lisans
Türkçe
2017
İnşaat Mühendisliğiİstanbul Teknik Üniversitesiİnşaat Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. BARIŞ ERKUŞ
- Genel korunum denklemini sonlu hacimler metodu ile modelleyen ve heterojen hesaplama teknolojisini destekleyen yazılımın geliştirilmesi
Development of a software modeling the general transport equation with finite volume method and supporting heterogeneous computing technology
BARIŞ CUMHUR
Yüksek Lisans
Türkçe
2020
Makine MühendisliğiKocaeli ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
PROF. DR. HASAN KARABAY
- Data vectorization in blockchain smart contracts
Blokzincir akıllı sözleşmelerde veri vektörleştirme
ÇAĞLA ÖZATAR
Yüksek Lisans
İngilizce
2026
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolGebze Teknik ÜniversitesiMatematik Ana Bilim Dalı
DOÇ. DR. SELÇUK TOPAL