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.