A Simple Work-Optimal Broadcast Algorithm for Message-Passing Parallel Systems

摘要

In this note we give a simple bandwidth- and latency optimal algorithm for the problem of broadcasting m units of data from a distinguished root processor to all p - 1 other processors in one-ported (hypercubic) message-passing systems. Assuming linear, uniform communication cost, the time for the broadcast to complete is O(m+log_2 p), more precisely no processor is involved in more than [log_2 p] communication operations (send, receive, and send-receive), and for any constant message size threshold b each processor (except the root) sends at most m - b′ + ([log_2 p] - l)b′ units of data, where b′ is determined by the smallest l ≤ [log_2 p] such that b′ = m/2~l ≤ b (the root sends 2m - b′ + ([log_2 p] - l)b′ units of data). Non-root processors receive m units of data. Building on known ideas, the salient features of the algorithm presented here is its simplicity of implementation, and smooth transition from latency to bandwidth dominated performance as data size m increases. The implementation performs very well in practice.