Parallel algorithms for the solution of large sparse linear inequality systems on distributed memory architectures
Dağıtık bellek mimarilerinde büyük seyrek lineer eşitsizlik sistemlerinin çözümü için paralel algoritmalar
- Tez No: 79352
- Danışmanlar: DOÇ. DR. PINAR Ç. MUSTAFA
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Bellek, Dağıtık sistemler, Paralel algoritmalar, linear feasibility, block projections, surrogate constraints method, load balancing, hypergraph partitioning model, image recovery, image restora tion, image reconstruction from projections, parallel algorithms. m, Memory, Distributed systems, Parallel algorithms
- Yıl: 1998
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
ÖZET DAĞITIK BELLEK MİMARİLERİNDE BÜYÜK SEYREK LİNEER EŞİTSİZLİK SİSTEMLERİNİN ÇÖZÜMÜ İÇİN PARALLEL ALGORİTMALAR Esma Turna Bilgisayar ve Enformatik Mühendisliği Bölümü Yüksek Lisans Tez Yöneticisi: Doç. Mustafa Ç. Pınar Ağustos, 1998 Bu tezde birçok parallel algoritma önerilmiş ve bu algoritmalardan büyük seyrek lineer eşitsizlik sistemlerinin çözümü için yaralanılmıştır. Parallelleştirme şemala rı, aracı kısıtlar yöntemi için önerilmiş olan orta ölçekli parallel formülasyondan yararlanılarak geliştirilmiştir. Sözü edilen şemalar bir boyutlu ve iki boyutlu parçalama esasına dayalıdır. Bununla birlikte, bir boyutlu parçalama şemasında iletişim gereksiniminin azaltılması için hiperçizge parçalama yöntemini kullanan üçüncü bir paralleleştirme şeması önerilmiştir. Hiperçizge modelinden yarar lanılarak iletişim gereksiniminin düzenlenmesi genel ve bölgesel iletişim şemaları vasıtasıyla sağlanmıştır. Aynı zamanda, düzgün satırsal bölümlü ve kartezyen parçalama yöntemlerinin etkin biçimde kullanılabilmesi için parça yükleme yakla şımına dayalı yeni algoritmalar araştırılmıştır. Görüntü düzeltme problemi genel bir kapsamda lineer eşitsizlik sistemi olarak formüle edilmiştir. Geliştirilen par allel algoritmalarla görüntüleme araçlarının yanlış odaklaması, atmosferdeki dal galanmalar ve benzeri sebeplerden noktasal dağılım fonksiyonlarıyla bulanıklaşmış görüntülerin restorasyonu sağlanmıştır. Anahtar kelimeler, lineer fizibilite, blok projeksyonlar, aracı kısıtlar yöntemi, yük denkliği, hiperçizge parçalama modeli, görüntü düzeltme, görüntü restorasy onu, projeksiyon yöntemiyle görüntü yapılandırılması, parallel algoritmalar. iv
Özet (Çeviri)
ABSTRACT PARALLEL ALGORITHMS FOR THE SOLUTION OF LARGE SPARSE INEQUALITY SYSTEMS ON DISTRIBUTED MEMORY ARCHITECTURES Esma Turna M.S. in Computer Engineering and Information Science Supervisor: Assoc. Prof. Mustafa Ç. Pmar August, 1998 In this thesis, several parallel algorithms are proposed and utilized for the so lution of large sparse linear inequality systems. The parallelization schemes are developed from the coarse-grain parallel formulation of the surrogate constraint method, based on the partitioning strategy: ID partitioning and 2D partition ing. Furthermore, a third parallelization scheme is developed for the explicit minimization of the communication overhead in ID partitioning, by using hyper- graph partitioning. Utilizing the hypergraph model, the communication overhead is maintained via a global communication scheme and a local communication scheme. In addition, new algorithms that use the bin packing heuristic are inves tigated for efficient load balancing in uniform rowwise stripped and checkerboard partitioning. A general class of image recovery problems is formulated as a linear inequality system. The restoration of images blurred by so called point spread functions arising from effects such as misfocus of the photographic device, at mospheric turbulence, etc. is successfully provided with the developed parallel algorithms.
Benzer Tezler
- Bir çokluişlemci sisteminde paralel değerlendirme programları
Başlık çevirisi yok
MUSTAF MURAT İNCEOĞLU
Doktora
Türkçe
1997
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolEge ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. SİNAN YILMAZ
- Parallelization of an interior point algorithm for linear programming
Bir iç nokta doğrusal programlama algoritmasının paralelleştirilmesi
HÜSEYİN SİMİTÇİ
Yüksek Lisans
İngilizce
1995
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. CEVDET AYKANAT
- Tomografik görüntü oluşturulmasında doğrudan fourier yöntemine yeni bir yaklaşım
A Novel approach to direct fourier transform technique in tomographic image reconstruction
A.FİLİZ BAYTAŞ
Doktora
Türkçe
1994
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiNükleer Mühendislik Ana Bilim Dalı
PROF. DR. MELİH GEÇKİNLİ
- Yüzey kurma probleminin transputer tabanlı sistemlerde paralel çözümü
Başlık çevirisi yok
ZİYA MERT GÜRAY
Yüksek Lisans
Türkçe
1998
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. COŞKUN SÖNMEZ
- Parallelization of the fast multipole solution of the electromanyetic scattering problem
Elektromanyetik saçılım probleminin hızlı multipole çözümü paralelleştirme
ALİ AYUB KALUFYA
Yüksek Lisans
İngilizce
1997
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. CEVDET AYKANAT