01766439

j

01766439 Theobald, Kevin B. Kumar, Rishi Agrawal, Gagan Heber, Gerd Thulasiram, Ruppa K. Gao, Guang R. Implementation and evaluation of a communication intensive application on the EARTH multithreaded system. Concurrency and Computation: Practice \& Experience 14, No.3, 183-201 (2002). 2002 John Wiley \& Sons, Ltd., Chichester EN C.m matrix vector multiplication

doi:10.1002/cpe.604

Summary: 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.