Ramesh Subramonian and Narayan Venkatasubramanyan

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-93-731
March 1993

http://www2.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://www2.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://www2.eecs.berkeley.edu/Pubs/TechRpts/1993/6019.html
%F Subramonian:CSD-93-731