Abstract
The paper considers the well-known problem of LU decomposition to study a method to derive data distributions for parallel computers with a distributed memory organization. The importance of the paper lies not so much in the special application but with the principle that the problem of finding an optimal data distribution is formulated as an optimization problem. This is possible by using a parameterized data distribution and a rigorous performance prediction technique that allows us to derive runtime formulas containing the parameters of the data distribution. The parameters are determined in such a way that the total runtime is minimized, thus also minimizing the communication overhead and the load imbalance penalty.
both authors are supported by DFG
Chapter PDF
Similar content being viewed by others
References
D.P. Bertsekas and J.N. Tsitsiklis. Parallel and Distributed Computing. Prentice Hall, New York, NY, 1988.
A. Dierstein, R. Hayer, and T. Rauber. A Branch-and-Bound Algorithm for Array Distributions. In 2nd Euromicro Workshop on Parallel and Distributed Processing, pages 528–535, 1994.
G.C. Fox, R.D. Williams, and P.C. Messias. Parallel Computing Works! Morgan Kaufmann Publishers, 1994.
S.L. Johnsson and C.T. Ho. Optimum Broadcasting and Personalized Communication in Hypercubes. IEEE Transactions on Computers, 38(9:1249–1268, 1989.
T. Rauber and G. Rünger. Performance Predictions for Parallel Diagonal-Implicitly Iterated Runge-Kutta Methods. In 9th Workshop on Parallel and Distributed Simulation, Lake Placid, USA, 1995.
T. Rauber, G. Rünger, and R. Wilhelm. An Application Specific Parallel Programming Paradigm. In International Conference on High-Performance Computing and Networking, 1995.
E.F. van de Velde. Data redistribution and concurrency. Parallel Computing, 16:125–138, 1990.
E.F. van de Velde. Concurrent Scientific Computing. Springer, 1994.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Rauber, T., Rünger, G. (1995). Optimal data distributions for LU decomposition. In: Haridi, S., Ali, K., Magnusson, P. (eds) EURO-PAR '95 Parallel Processing. Euro-Par 1995. Lecture Notes in Computer Science, vol 966. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0020480
Download citation
DOI: https://doi.org/10.1007/BFb0020480
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60247-7
Online ISBN: 978-3-540-44769-6
eBook Packages: Springer Book Archive