Implementation and evaluation of a communication intensive application on the EARTH multithreaded system
Kevin B. Theobald, Rishi Kumar, Gagan Agrawal, Gerd Heber, Ruppa K. Thulasiram, Guang R. Gao · Concurrency and Computation Practice and Experience · 2002
Abstract 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.