Optimal and near-optimal algorithms for k-item broadcast

Since many distributed-memory machines rely only on point-to-point communic ation between processors, various broadcast operations must be created usin g this type of primitive. In this paper we consider the fundamental problem of broadcasting k-items from one processor to all the remaining processors on a parallel machine. Using point-to-point communication and the LogP mod el, we design an algorithm for k-item broadcast whose running time is withi n an additive constant of the lower bound. We also present an optimal algor ithm for k-item broadcast on a variant of LogP. (C) 1999 Academic Press.