Interprocessor Communication with Limited Memory
|
Abstract—Many parallel applications require periodic redistribution of workloads and associated data. In a distributed memory computer, this redistribution can be difficult if limited memory is available for receiving messages. We propose a model for optimizing the exchange of messages under such circumstances which we call the minimum phase remapping problem. We first show that the problem is NP-Complete, and then analyze several methodologies for addressing it. First, we show how the problem can be phrased as an instance of multicommodity flow. Next, we study a continuous approximation to the problem. We show that this continuous approximation has a solution which requires at most two more phases than the optimal discrete solution, but the question of how to consistently obtain a good discrete solution from the continuous problem remains open. We also devise a simple and practical approximation algorithm for the problem with a bound of 1.5 times the optimal number of phases. We also present an empirical study of variations of our algorithms which indicate that our approaches are quite practical.
[1] 606 G. Cybenko, Dynamic Load Balancing for Distributed Memory Multiprocessors J. Parallel Distributed Computing, vol. 7, pp. 279-301, 1989.
[2] B. Hendrickson and K. Devine, Dynamic Load Balancing in Computational Mechanics Computer Methods in Applied Mechanics and Eng., vol. 184, nos. 2-4, pp. 485-500, 2000.
[3] K.D. Devine, B. Hendrickson, E.G. Boman, M.M. St. John, and C. Vaughan, Zoltan: A Dynamic Load-Balancing Library for Parallel Applications User's Guide Technical Report SAND99-1377, Sandia Nat'l Laboratories, Albuquerque, New Mexico,http://www.cs.sandia.govZoltan/, 1999.
[4] A. Pinar and B. Hendrickson, Interprocessor Communication with Memory Constraints Proc. 12th ACM Symp. Parallel Algorithms and Architectures, pp. 39-45, July 2000.
[5] A. Pinar and B. Hendrickson, Communication Support for Adaptive Computation Proc. 10th SIAM Conf. Parallel Processing for Scientific Computing, Mar. 2001.
[6] R. Cypher and S. Konstantinidou, Bounds on the Efficiency of Message-Passing Protocols for Parallel Computers SIAM J. Computing, vol. 25, no. 5, pp. 1082-1104, 1996.
[7] J. Hall, J. Hartline, A. Karlin, J. Saia, and J. Wilkes, On Algorithms for Efficient Data Migration Proc. Symp. Discrete Algorithms, 2001.
[8] R.M. Karp, Reducibility among Combinatorial Problems Complexity of Computer Computations, R.E. Miller and J.W. Thatcher, eds., pp. 85-103, New York: Plenum Press, 1972.
[9] R.K. Ahuja, R.L. Magnanti, and J.B. Orlin, Network Flows: Theory, Algorithms and Applications. Englewood Cliffs, N.J.: Prentice Hall, 1993.
[10] A. Pinar and B. Hendrickson, Partitioning for Complex Objectives Proc. 15th Int'l Parallel and Distributed Processing Symp., 2001.
Index Terms:
Interprocessor communication, dynamic load balancing, data migration, scheduling, NP-completeness, approximation algorithms.
Citation:
Ali Pinar, Bruce Hendrickson, "Interprocessor Communication with Limited Memory," IEEE Transactions on Parallel and Distributed Systems, vol. 15, no. 7, pp. 606-616, July 2004, doi:10.1109/TPDS.2004.22
PURCHASE ARTICLE: $19
IEEE Xplore Subscribers
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb