Determining optimal and efficient communication schedules for parallel algorithms

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)39-44
Number of pages6
JournalInternational Journal of Parallel and Distributed Systems and Networks
Issue number1
StatePublished - Dec 1 2000
Externally publishedYes

ASJC Scopus subject areas

  • Hardware and Architecture


Dive into the research topics of 'Determining optimal and efficient communication schedules for parallel algorithms'. Together they form a unique fingerprint.

Cite this