AbstractWe consider Multimessage Multicasting over the n processor complete (or fully connected) static network (MMC}). We present a fast approximation algorithm with an improved approximation bound for problem instances with small fan-out (maximum number of processors receiving any given message), but arbitrary degree d, where d is the maximum number of messages that each processor may send or receive. These problem instances are the ones that arise in practice, since the fan-out restriction is imposed by the applications and the number of processors available in commercial systems.
Our algorithm is centralized and requires all the communication information ahead of time. Applications where this information is available include iterative algorithms for solving linear equations and most dynamic programming procedures. The Meiko CS-2 machine as well as other computer systems whose processors communicate via dynamic networks will also benefit from our results at the expense of doubling the number of communication phases.
Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; C.1.4 [Processor Architectures]: ; G.2.2 [Discrete Mathematics]: Graph Theory; C.2.1 [Computer-Communication Networks]: Network Architecture and Design; G.1.3 [Numerical Analysis]: Numerical Linear Algebra
Additional Key Words and Phrases: approximation algorithms, multimessage multicasting, dynamic networks, parallel iterative methods, generalized edge coloring
Selected references
- Hyeong-Ah Choi and S. Louis Hakimi. Data transfers in networks. Algorithmica, 3:223-245, 1988.
- E. G. Coffman, Jr., M. R. Garey, D. S. Johnson, and A. S. Lapaugh. Scheduling file transfers. SIAM Journal on Computing, 14(3):743-780, August 1985.
- Leslie Ann Goldberg, Mark Jerrum, Tom Leighton, and Satish Rao. Doubly logarithmic communication algorithms for optical-communication parallel computers. SIAM Journal on Computing, 26(4):1100-1119, August 1997.
- Teofilo Gonzalez and Sartaj Sahni. Open shop scheduling to minimize finish time. Journal of the ACM, 23(4):665-679, October 1976.
- Jennifer Whitehead. The complexity of file transfer scheduling with forwarding. SIAM Journal on Computing, 19(2):222-245, April 1990.