𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Parallelization Techniques for Sparse Matrix Applications

✍ Scribed by Manuel Ujaldón; Emilio L. Zapata; Shamik D. Sharma; Joel Saltz

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
390 KB
Volume
38
Category
Article
ISSN
0743-7315

No coin nor oath required. For personal study only.

✦ Synopsis

Sparse matrix problems are difficult to parallelize efficiently on distributed memory machines since data is often accessed indirectly. Inspector-executor strategies, which are typically used to parallelize loops with indirect references, incur substantial runtime preprocessing overheads when references with multiple levels of indirection are encountered-a frequent occurrence in sparse matrix algorithms. The sparse-array rolling (SAR) technique, introduced in [M. Ujaldo ´n and E. L. Zapata, Proc. 9th ACM Int'l. Conf. on Supercomputing, Barcelona, July 1995, pp. 117-126], significantly reduces these preprocessing overheads. This paper outlines the SAR approach and describes its runtime support accompanied by a detailed performance evaluation. The results demonstrate that SAR yields significant reduction in preprocessing overheads compared to standard inspector-executor techniques.

📜 SIMILAR VOLUMES

Parallel sparse matrix vector multiply s
Parallel sparse matrix vector multiply software for matrices with data locality
✍ TUMINARO, RAY S.; SHADID, JOHN N.; HUTCHINSON, SCOTT A. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 339 KB

In this paper we describe general software utilities for performing unstructured sparse matrixvector multiplications on distributed-memory message-passing computers. The matrix-vector multiply comprises an important kernel in the solution of large sparse linear systems by iterative methods. Our focu

A sparse matrix technique for the analys
A sparse matrix technique for the analysis of linear antennas
✍ Y. Liu; K. Lan; K. K. Mei 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 109 KB 👁 2 views

Bar-Chaim, and I. Urym, Designing high dynamic range fibre-optic links: A comparison between directly-modulated Fabry-Perot and distributed-feedback laser Ž .

Matrix stretching for sparse least squar
Matrix stretching for sparse least squares problems
✍ Mikael Adlers; Åke Björck 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 91 KB

For linear least squares problems min x Ax -b 2 , where A is sparse except for a few dense rows, a straightforward application of Cholesky or QR factorization will lead to catastrophic fill in the factor R. We consider handling such problems by a matrix stretching technique, where the dense rows ar