Abstract
We consider a certain class of parallel program segments in which the order of messages sent affects the completion time. We give characterization of these parallel program segments and propose a solution to minimize the completion time. With a sample parallel program, we experimentally evaluate the effect of the solution on a PC cluster.
This work is partially supported by the Scientific and Technical Research Council of Turkey (TUBITAK) under grant 103E028.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Burns, G., Daoud, R., Vaigl, J.: LAM: an open cluster environment for MPI. In: Ross, J.W. (ed.) Proceedings of Supercomputing Symposium 1994, University of Toronto, pp. 379–386 (1994)
Ca̧talyürek, Ü.V., Aykanat, C.: Hypergraph-partitioning based decomposition for parallel sparse-matrix vector multiplication. IEEE Transactions on Parallel and Distributed Systems 10(7), 673–693 (1999)
Ca̧talyürek, Ü.V., Aykanat, C.: A fine-grain hypergraph model for 2d decomposition of sparse matrices. In: Proceedings of International Parallel and Distributed Processing Symposium (IPDPS) (April 2001)
Ca̧talyürek, Ü.V., Aykanat, C.: A hypergraph-partitioning approach for coarsegrain decomposition. In: Proceedings of Scientific Computing 2001 (SC 2001), Denver, Colorado, November 2001, pp. 10–16 (2001)
Dongarra, J.J., Dunigan, T.H.: Message-passing performance of various computers. Concurrency—Practice and Experience 9(10), 915–926 (1997)
Gropp, W., Lusk, E.: Reproducible measurements of mpi performance characteristics. Tech. Rept. ANL/MCS-P755-0699, Argonne National Lab. (June 1999)
Hendrickson, B., Kolda, T.G.: Graph partitioning models for parallel computing. Parallel Computing 26, 1519–1534 (2000)
Hendrickson, B., Kolda, T.G.: Partitioning rectangular and structurally unsymmetric sparse matrices for parallel processing. SIAM J. Sci. Comput. 21(6), 2048–2072 (2000)
Sterling, T., Savarese, D., Becker, D.J., Dorband, J.E., Ranaweke, U.A., Packer, C.V.: BEOWULF: A parallel workstation for scientific computation. In: Proceedings of the 24th International Conference on Parallel Processing (1995)
Uçar, B., Aykanat, C.: Minimizing communication cost in fine-grain partitioning of sparse matrices. In: Yazıcı, A., Sȩner, C. (eds.) Proc. ISCISXVIII-18th Int. Symp. on Computer and Information Sciences, Antalya, Turkey (November 2003)
Uçar, B., Aykanat, C.: Encapsulating multiple communication-cost metrics in partitioning sparse rectangular matrices for parallel matrix-vector multiplies. SIAM J. Sci. Comput. 25(6), 1837–1859 (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Uçar, B., Aykanat, C. (2004). A Message Ordering Problem in Parallel Programs. In: Kranzlmüller, D., Kacsuk, P., Dongarra, J. (eds) Recent Advances in Parallel Virtual Machine and Message Passing Interface. EuroPVM/MPI 2004. Lecture Notes in Computer Science, vol 3241. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30218-6_23
Download citation
DOI: https://doi.org/10.1007/978-3-540-30218-6_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-23163-9
Online ISBN: 978-3-540-30218-6
eBook Packages: Springer Book Archive