Minimizing Communication Latencies in Conjugate Gradient Type Parallel Iterative Solvers

Abstract

Conjugate Gradient (CG) type iterative solvers are widely used for the solu- tion of large, sparse, linear system of equations on multicom puters. 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 in to 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 CcG program are minimized. However, such a scheme has the disad van tage 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.

Alternate abstract:

Eşlenik Gradyan (EG) tipi özyineli çözücüler büyük, seyrek, doğrusal denklem sistemlerinin çozümlerinde sıkça kullanılmaktadırlar. Genelde, her özyinelemede uy gulanan temel işlemler, seyrek matris vektör çarpımları (Sy Mx V) 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 herke se yayım (HHY) tipinde iletişim gerek tirmektedirler. 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şlem ci 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 sunulmaktadir. Öner- ilen yöntemlerin pratikteki geçerlilik lerini gözlemlemek için deneyler yapılmıştır. Özellikle mesaj başlama maliyetlerin in toplam iletişim zamanlarinda baskın olduğu durumlarda, işlemci zamanlarında bir azalma gözlemlenmiştir.