Minimizing communication latencies in conjugate gradient type parallel herative solvers

Abstract

Ö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. Anahtar sözcükler: seyrek matrisler, paralel özyineli çözücüler, paralel matris- vektör çarpımı, haberleşme en aza indirme, hiperçizge bölümleme.

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. Keywords: sparse matrices, parallel iterative solvers, parallel matrix-vector mul tiplication, communication minimization, hypergraph partitioning.