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