Abstract
Improved Approximation Algorithms for Multimessage Multicasting
by: Teofilo F. Gonzalez
Abstract:
We consider Multimessage Multicasting over the $n$ processor complete (or fullyconnected) static network ($MM_{C}$). We present several fast approximationalgorithms with improved approximation bounds for problem instances with smallfan-out (maximum number of processors receiving any given message), butarbitrary degree $d$, where $d$ is the maximum number of messages that eachprocessor may send (receive). These problem instances are the ones that arisein practice, since the fan-out restriction is imposed by the applications andthe number of processors available in commercial systems.Our algorithms are centralized and require all the communication informationahead of time. Applications where this information is available includeiterative algorithms for solving linear equations and most dynamic programmingprocedures. The Meiko CS-2 machine and in general computer systems withprocessors communicating via dynamic permutation networks whose basic switchescan act as data replicators (e.g., $n$ by $n$ Benes network with 2 by 2switches that can also act as data replicators) will also benefit from ourresults at the expense of doubling the number of communication phases.
Keywords:
Approximation Algorithms, Multimessage Multicasting, ParallelIterative Methods, Communication Schedules
Date:
July 1996
Document: 1996-16
