Implementation and evaluation of a communication intensive application on the EARTH multithreaded system

• Published in: Concurrency and computation 2002-03, Vol.14 (3), p.183-201
• Main Authors: Theobald, Kevin B., Kumar, Rishi, Agrawal, Gagan, Heber, Gerd, Thulasiram, Ruppa K., Gao, Guang R.
• Format: Article
• Language: English
• Subjects: conjugate gradient; EARTH; multithreading; parallel computing; sparse matrices
• ISSN: 1532-0626; 1532-0634
• DOI: 10.1002/cpe.604

This paper reports a study of sparse Matrix Vector Multiplication (MVM) on a parallel computing platform based on a fine‐grained multithreaded program execution model. Such sparse MVM computations, when parallelized without performing graph partitioning, suffers a very high communication to computation ratio, and is well known to have a very limited scalability on traditional distributed‐memory machines. The particular multithreaded system we use is the Efficient Architecture for Running THreads (EARTH) model, which can be implemented from off‐the‐shelf processors. With the Class B input sparse matrix from the NAS CG benchmark (75 000 rows), we attain an absolute speedup of 90 on 120 nodes of a distributed memory configuration. This is achieved without using inspector/executor or graph partitioning, or any communication minimization phase, which means that similar results can be expected for adaptive problems as well. High scalability is achieved because of a number of characteristics of the EARTH architecture: local synchronizations, low communication overheads, ability to overlap communication and computation, and low context‐switching costs. Copyright © 2002 John Wiley & Sons, Ltd.