Details:
| Title | Multiprocessor runtime support for fine-grained, irregular DAGs | | Author(s) | E. A. Brewer, F. T. Chong, J. Saltz, S. D. Sharma | | Type | Article in Journal | | Abstract | We examine multiprocessor runtime support for fine-grained, irregular directed acyclic graphs (DAGs) such as those that arise from sparse-matrix triangular solves. We conduct our experiments on the CM-5, whose lower latencies and active-message support allow us to achieve unprecedented speedups for a general multiprocessor. Where as previous implementations have maximum speedups of less than 4 on even simple banded matrices, we are able to obtain scalable performance on extremely small and irregular problems. On a matrix with only 5300 rows, we are able to achieve scalable performance with a speedup of 34 for 128 processors, resulting in an absolute performance of over 33 million double-precision floating point operations per second.
We achieve these speedups with non-matrix-specific methods which are applicable to any DAG. We compare a range of run-time preprocessed and dynamic approaches on matrices from the Harwell-Boeing benchmark set. Although precomputed data distributi... |
| Language | English | | Journal | Parallel Processing Letters | | Volume | 5 | | Number | 4 | | Pages | 671-683 | | Year | 1995 | | Edition | 0 | | Translation |
No | | Refereed |
No |
|
