# Optimal Broadcast in a Distributed Memory Model of Parallel Computation

### Ramesh Subramonian and Narayan Venkatasubramanyan

###
EECS Department

University of California, Berkeley

Technical Report No. UCB/CSD-93-731

March 1993

### http://www.eecs.berkeley.edu/Pubs/TechRpts/1993/CSD-93-731.pdf

A commonly arising problem in many parallel algorithms is broadcast. Many multi-processors do not have dedicated hardware for this purpose. Therefore, a broadcast must be effected by point-to-point message passing. In this paper, we address the problem of effecting broadcast by point-to-point message transmission, where a source processor has many messages which it wishes to disseminate to
*P*-1 other processors. In a step, a processor can send at most one item from among those in its possession and receive at most one item. An item is received at most
*L* steps after it is sent. The goal is to find a schedule that achieves the broadcast in minimum time.

We improve on previous results by (i) providing an integer programming formulation whose optimal solution represents an optimal *k*-broadcast schedule, without making any assumptions about *L* or *P*; and (ii) developing a simpler but marginally sub-optimal solution which also makes no assumptions about *L* or *P*. In addition, we (i) refine the LogP model to capture network behaviour more precisely; and (ii) provide a bound on the performance degradation when the latency is allowed to vary.

BibTeX citation:

@techreport{Subramonian:CSD-93-731, Author = {Subramonian, Ramesh and Venkatasubramanyan, Narayan}, Title = {Optimal Broadcast in a Distributed Memory Model of Parallel Computation}, Institution = {EECS Department, University of California, Berkeley}, Year = {1993}, Month = {Mar}, URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/1993/6019.html}, Number = {UCB/CSD-93-731}, Abstract = {A commonly arising problem in many parallel algorithms is broadcast. Many multi-processors do not have dedicated hardware for this purpose. Therefore, a broadcast must be effected by point-to-point message passing. In this paper, we address the problem of effecting broadcast by point-to-point message transmission, where a source processor has many messages which it wishes to disseminate to <i>P</i>-1 other processors. In a step, a processor can send at most one item from among those in its possession and receive at most one item. An item is received at most <i>L</i> steps after it is sent. The goal is to find a schedule that achieves the broadcast in minimum time. <p>We improve on previous results by (i) providing an integer programming formulation whose optimal solution represents an optimal <i>k</i>-broadcast schedule, without making any assumptions about <i>L</i> or <i>P</i>; and (ii) developing a simpler but marginally sub-optimal solution which also makes no assumptions about <i>L</i> or <i>P</i>. In addition, we (i) refine the LogP model to capture network behaviour more precisely; and (ii) provide a bound on the performance degradation when the latency is allowed to vary.} }

EndNote citation:

%0 Report %A Subramonian, Ramesh %A Venkatasubramanyan, Narayan %T Optimal Broadcast in a Distributed Memory Model of Parallel Computation %I EECS Department, University of California, Berkeley %D 1993 %@ UCB/CSD-93-731 %U http://www.eecs.berkeley.edu/Pubs/TechRpts/1993/6019.html %F Subramonian:CSD-93-731