Report ID
1996-15
Report Authors
Teofilo F. Gonzalez
Report Date
Abstract
We consider Multimessage Multicasting over the $n$ processor complete (or fullyconnected) static network ($MM_{C}$). First we present a linear time algorithmthat constructs for every degree $d$ problem instance a communication schedulewith total communication time at most $d^2$, where $d$ is the maximum number ofmessages that each processor may send (receive). Then we present degree $d$problem instances such that all their communication schedules have totalcommunication time at least $d^2$. We observe that our lower bound applieswhen the fan-out (maximum number of processors receiving any given message) ishuge, and thus the number of processors is also huge. Since this environmentis not likely to arise in the near future, we turn our attention to the studyof important subproblems that are likely to arise in practice. We show thatwhen each message has fan-out $k=1$ the $MM_C$ problem corresponds to theMakespan Openshop Preemptive Scheduling problem which can be solved inpolynomial time, and show that for $k \\ge 2$ our problem is NP-complete. Wepresent an algorithm to generate a communication schedule with totalcommunication time $2d-1$ for any degree $d$ problem instance with fan-out$k=2$. Our main result is an $O(q \\cdot d \\cdot e)$ time algorithm, where $e\\le nkd$ (the input length), with an approximation bound of $qd +k^{\\frac{1}{q}}(d-1)$, for any integer $q$ such that $k > q >= 2$.Our algorithms are centralized and require all the communication informationahead of time. Applications where all of this information is readily availableinclude iterative algorithms for solving linear equations, and most dynamicprogramming procedures. The Meiko CS-2 machine and in general computer systemswith processors communicating via dynamic permutation networks whose basicswitches can act as data replicators (e.g., $n$ by $n$ Benes network with 2 by2 switches that can also act as data replicators) will also benefit from ourresults at the expense of doubling the number of communication phases.
Document
1996-15.ps195.81 KB