Multimessage Multicasting with Forwarding

We consider Multimessage Multicasting over the $n$ processor complete (or fullyconnected) static network ($MM_{C}$) with Forwarding. We present an efficientalgorithm that constructs for every degree $d$ problem instance a communicationschedule with total communication time at most $2d$, where $d$ is the maximumnumber of messages that each processor may send (receive). Our algorithmconsists of two phases. In the first phase a set of communications arescheduled to be carried out in $d$ time periods, and when these communicationsare performed the remaining problem becomes a multimessage unicasting problemof degree $d$. In the second phase we generate a communication schedule forthis problem by reducing it to the Makespan Openshop Preemptive Schedulingproblem which can be solved in polynomial time. The solution is theconcatenation of the communication schedules for these two phases.Our centralized algorithms require all the communication information ahead oftime. Applications where all of this information is readily 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 since the same schedules can be used for these systems.