Ramesh Subramonian and Narayan Venkatasubramanyan

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-93-731

, 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 <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.

---

BibTeX citation:

@techreport{Subramonian:CSD-93-731,
    Author= {Subramonian, Ramesh and Venkatasubramanyan, Narayan},
    Title= {Optimal Broadcast in a Distributed Memory Model of Parallel Computation},
    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