Geri Dön

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

  1. Tez No: 112581
  2. Yazar: M. MUSTAFA ÖZDAL
  3. Danışmanlar: PROF. DR. CEVDET AYKANAT
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. 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
  7. Yıl: 2001
  8. Dil: İngilizce
  9. Üniversite: İhsan Doğramacı Bilkent Üniversitesi
  10. Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. 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

  1. 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

    İngilizce

    2011

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent Üniversitesi

    Bilgisayar Mühendisliği Bölümü

    PROF. DR. CEVDET AYKANAT

  2. 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

    İngilizce

    1999

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent Üniversitesi

    Bilgisayar Yazılımı Ana Bilim Dalı

    DOÇ. DR. CEVDET AYKANAT

  3. 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

    Türkçe

    2019

    İşletmeMarmara Üniversitesi

    İşletme Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ NURETTİN OZAN BAKIR

  4. Hypergraph models for parallel sparse matrix-matrix multiplication

    Paralel seyrek matris-matris çarpımı için hiperçizge modelleri

    KADİR AKBUDAK

    Doktora

    İngilizce

    İngilizce

    2015

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. CEVDET AYKANAT

  5. 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

    İngilizce

    2013

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik Üniversitesi

    Elektrik-Elektronik Mühendisliği Ana Bilim Dalı

    DOÇ. DR. CÜNEYT F. BAZLAMAÇCI