Determining optimal and efficient communication schedules for parallel algorithms

In this paper we consider the problem of assigning communication schedules for parallel algorithms that result in efficient and/or optimal running times. In order to determine running time, three items must be taken into consideration: 1) local computational tasks, 2) initial data layout, and 3) the communication schedule. We show that even when the local computational tasks and initial data layout are provided, and the local computational tasks are ordered for every processor, the problem of determining the communication schedule that will result in an optimal parallel algorithm, in general, is NP-complete. We also show that it is still an NP-complete problem to determine a schedule that results in a parallel running time within an additive constant of optimal. In fact, we show that determining a communication schedule that will-result in a running time within a multiplicative factor of 3/2 is NP-complete. However, we will present a polynomial time algorithm that will produce a communication schedule, which will result in a parallel running time within, at most, twice the optimal time. In order for our results to be applicable to a wide-array of machines, we work within the well-known LogP model of parallel computation.