Optimal Partitioning of Random Programs Across Two Processors

Research output: Contribution to journalComment/debatepeer-review


Recent work by Indurkhya et al., discusses the optimal partitioning of random distributed programs. They conclude that the optimal partitioning of a homogeneous random program over a homogeneous distributed system either assigns all modules to a single processor, or distributes the modules as evenly as possible among all processors. Their analysis rests heavily on the approximation that equates the expected maximum of a set of independent random variables with the set's maximum expectation. In this paper we strengthen their results by providing an approximation-free proof of this result for two processors under general conditions on the module execution time distribution. However, we show that additional rigor leads to a different characterization of the optimality points. We also show that under a rigorous analysis one is led to different conclusions in the general p-processor case than those reached using Indurkhya et al.'s approximation.

Original languageEnglish (US)
Pages (from-to)134-141
Number of pages8
JournalIEEE Transactions on Software Engineering
Issue number2
StatePublished - Feb 1989
Externally publishedYes

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Optimal Partitioning of Random Programs Across Two Processors'. Together they form a unique fingerprint.

Cite this