On distributed memory parallel randomized Kaczmarz for sparse system of equations
Seyrek denklem sistemleri için dağıtık bellek paralel rastgele Kaczmarz üzerine
- Tez No: 897486
- Danışmanlar: PROF. DR. MURAT MANGUOĞLU
- Tez Türü: Doktora
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2024
- Dil: İngilizce
- Üniversite: Orta Doğu Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Bilgisayar Mühendisliği Bilim Dalı
- Sayfa Sayısı: 220
Özet
Bilim ve mühendislik problemlerinin doğrusal denklemler sistemi olarak modellenmesi yaygındır. Kaczmarz algoritması, çeşitli uygulama alanlarından türetilen bu tür denklemleri çözmek için yinelemeli izdüşümlere dayalı bir satır eylem yöntemidir. Her Kaczmarz yinelemesi bir öncekine bağlı olduğundan, rastgele Kaczmarz da dahil olmak üzere çeşitli satır seçme stratejileri ortaya çıkmıştır. Aynı bağımlılık, Kaczmarzın paralel olarak uygulanmasını da zorlaştırır. Kaczmarz yinelemelerinin doğası gereği, sık sık iletişim kurulması gerekir ve bu da önemli bir ek yüke neden olur. Bu çalışmada, dağıtık bellek mimarileri için seyrek sistemleri çözmek amacıyla iki farklı yöntem önerilmektedir: İlk yöntem, paralel DS çarpanlara ayırma ile oluşturulan daha küçük indirgenmiş sistem için çözücü olarak ardışık rastgele Kaczmarz kullanan hibrit bir yaklaşımdır. İkincisi ise iletişim yükünü azaltmak için bir paralel rastgele Kaczmarz yöntemidir. Sistemi, farklı bloklarda yürütülen Kaczmarz yinelemeleri arasındaki bağımlılığı azaltmak için bölümlere ayırır. İşlemler arasındaki iletişimi paylaşılan sıfır olmayan indislerle sınırlandırarak iletişim yükünde ek bir azalma sağlanır. Deneyler, bu yöntemlerin iletişim yükü ve performans üzerindeki etkilerini karşılaştırmak için çeşitli alanlardaki problemler kullanılarak gerçekleştirilmiştir. Son olarak, önerilen paralel rastgele Kaczmarz yönteminin daha büyük problemler üzerindeki paralel hızlandırmaları sunulmuştur.
Özet (Çeviri)
It is common for science and engineering problems to be modeled as system of linear equations. Kaczmarz algorithm is a row action method based on iterative projections for solving such equations derived from various application domains. Since each Kaczmarz iteration is dependent on the previous one, several row selection strategies have emerged including the randomized Kaczmarz. Same dependency also makes the parallel implementation of Kaczmarz challenging. Because of the nature of Kaczmarz iterations, it is required to communicate frequently which results in a substantial overhead. In this study, two different methods to solve sparse systems are proposed for distributed memory architectures: The first method is a hybrid approach that uses sequential randomized Kaczmarz as the solver for the smaller reduced system constructed with parallel DS factorization. The second one is a parallel randomized Kaczmarz method to reduce the communication overhead. It partitions the system to decrease the dependency between Kaczmarz iterations executed on different blocks. Additional decrease on the communication overhead is ensured by limiting the communication between processes to the shared nonzero indices. The experiments are performed on problems from various domains to compare the effects of those methods on the communication overhead and performance. Finally, parallel speedups of the proposed parallel randomized Kaczmarz method on larger problems are presented.
Benzer Tezler
- Partitioning models for scaling distributed graph computations
Dağıtık çizge hesaplamalarının ölçeklendirilmesi için bölümleme yöntemleri
GÜNDÜZ VEHBİ DEMİRCİ
Doktora
İngilizce
2019
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. CEVDET AYKANAT
- Yusufçuk optimizasyon algoritmasının dağıtık ve paylaşımlı bellek mimarileri üzerinde paralelizasyonu
Parallelization of Dragonfly optimization algorithm on distributed and shared memory architects
RAMAZAN POLAT
Yüksek Lisans
Türkçe
2019
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolMersin ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. ALİ AKDAĞLI
- Spatial subdivision for parallel ray casting/tracing
Paralel ışın düşürme/izleme için uzaysal bölümleme
VEYSİ İŞLER
Doktora
İngilizce
1995
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiPROF.DR. BÜLENT ÖZGÜÇ
- Parallel sequence mining on distributed memory systems
Dağıtık bellekli sistemlerde paralel dizi madenciliği
EMBİYA KARAPINAR
Yüksek Lisans
İngilizce
2001
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. ATİLLA GÜRSOY
- Coloring for distributed-memory-parallel gauss-seidel algorithm
Dağıtık-bellek-paralel gauss-seıdel algoritması için renklendirme
ONUR KOÇAK
Yüksek Lisans
İngilizce
2019
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. CEVDET AYKANAT