Minimizing communication latencies in conjugate gradient type parallel herative solvers
Eşlenik gradyan tipi paralel özyineli çözücülerde iletişim gecikme sürelerinin en aza indirgenmesi
- Tez No: 112581
- 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: seyrek matrisler, paralel özyineli çözücüler, paralel matris- vektör çarpımı, haberleşme en aza indirme, hiperçizge bölümleme, sparse matrices, parallel iterative solvers, parallel matrix-vector mul tiplication, communication minimization, hypergraph partitioning
- Yıl: 2001
- 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ı: 66
Özet
ÖZET EŞLENİK GRADYAN TİPİ PARALEL ÖZYİNELİ ÇÖZÜCÜLERDE İLETİŞİM GECİKME SÜRELERİNİN EN AZA İNDİRGENMESİ M. Mustafa Özdal Bilgisayar Mühendisliği, Yüksek Lisans Tez Yöneticisi: Prof. Dr. Cevdet Aykanat Temmuz, 2001 Eşlenik Gradyan (EG) tipi özyineli çözücüler büyük, seyrek, doğrusal denklem sistemlerinin çözümlerinde sıkça kullanılmaktadırlar. Genelde, her özyinelemede uygulanan temel işlemler, seyrek matris vektör çarpımları (SyMxV) ve vektör iç çarpımlarıdır. Paralel EG algoritmalarında, SyMxV işlemleri noktadan nok taya tipinde iletişim gerektirirken, iç çarpım işlemleri herkesten herkese yayım (HHY) tipinde iletişim gerektirmektedirler. Bu tezde, noktadan noktaya iletişim işlemlerinin HHY işlemlerinin içine gömüldüğü yeni bir iletişim metodu öner ilmektedir. Buradaki amaç, her bir işlemci tarafından gönderilen mesaj sayısının en aza indirgenmesi ve böylece paralel EG algoritmasındaki iletişim gecikme sürelerinin azaltılmasıdır. Diğer yandan, böyle bir metodun iletişim hacmini arttırma gibi bir dezavantajı vardır. Bu yüzden, iletişim hacmindeki ek yükleri en aza indirgemek için bir yöntem maliyet modeli ile birlikte sunulmaktadır. Öner ilen yöntemlerin pratikteki geçerliliklerini gözlemlemek için deneyler yapılmıştır. Özellikle mesaj başlama maliyetlerinin toplam iletişim zamanlarında baskın olduğu durumlarda, işlemci zamanlarında bir azalma gözlemlenmiştir.
Özet (Çeviri)
ABSTRACT MINIMIZING COMMUNICATION LATENCIES IN CONJUGATE GRADIENT TYPE PARALLEL ITERATIVE SOLVERS M. Mustafa Özdal MS in Computer Engineering Supervisor: Prof. Cevdet Aykanat July, 2001 Conjugate Gradient (CG) type iterative solvers are widely used for the solu tion of large, sparse, linear system of equations on multicomputers. Typically, the basic operations performed at each iteration are sparse matrix vector multiplica tions (SpMxV), and inner product computations. In the parallel CG algorithm, SpMxV operations require point-to-point type communications, whereas inner product computations require all-to-all broadcast (AABC) type communications. In this thesis, we propose a novel communication scheme in which the point-to- point communications are embedded into the AABC operations. The purpose here is to minimize the number messages sent by each processor, so that the com munication latencies of a parallel CG program are minimized. However, such a scheme has the disadvantage that the communication volume requirements might increase. For this reason, a cost model and a methodology to minimize the over head in communication volume is given. Some experiments have been performed to test the practical validity of the proposed scheme. It is observed that the execution times for communication operations decrease in this scheme, especially for the configurations in which the message start-up costs dominate the total communication times.
Benzer Tezler
- Minimizing communication through computational redundancy in parallel iterative solvers
Paralel yinelemeli çözümleyicilerde fazla hesaplama ile haberleşme azaltımı
FAHREDDİN ŞÜKRÜ TORUN
Yüksek Lisans
İngilizce
2011
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Bölümü
PROF. DR. CEVDET AYKANAT
- Hypergraph models for sparse matrix partitioning and reordering
Seyrek matris bölümleme ve yeniden-düzenleme için hiperçizge modelleri
ÜMİT VEYSEL ÇATALYÜREK
Doktora
İngilizce
1999
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Yazılımı Ana Bilim Dalı
DOÇ. DR. CEVDET AYKANAT
- Mağaza imajı ve özel marka imajı ile önceki deneyimin özel markalarda algılanan risk ve satın alma niyetine etkisi: Türkiye - Azerbaycan kıyaslaması
Store image and private label image with prior experience impact on the private label's perceived risk and purchase intention: Turkey-Azerbaijan comparison
EMİL AGHARZAYEV
Yüksek Lisans
Türkçe
2019
İşletmeMarmara Üniversitesiİşletme Ana Bilim Dalı
DR. ÖĞR. ÜYESİ NURETTİN OZAN BAKIR
- Hypergraph models for parallel sparse matrix-matrix multiplication
Paralel seyrek matris-matris çarpımı için hiperçizge modelleri
KADİR AKBUDAK
Doktora
İngilizce
2015
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. CEVDET AYKANAT
- Energy and buffer aware application mapping for networks on chip
Yonga üzeri ağlar için enerji ve arabelleğe duyarlı uygulama eşleştirme
COŞKUN ÇELİK
Doktora
İngilizce
2013
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
DOÇ. DR. CÜNEYT F. BAZLAMAÇCI