Optimal Partitioning of Random Programs Across Two Processors

Research output: Contribution to journalComment/debate

Abstract

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
Volume15
Issue number2
DOIs
StatePublished - Feb 1989
Externally publishedYes

Fingerprint

Random variables

ASJC Scopus subject areas

  • Software

Cite this

Optimal Partitioning of Random Programs Across Two Processors. / Nicol, David M.

In: IEEE Transactions on Software Engineering, Vol. 15, No. 2, 02.1989, p. 134-141.

Research output: Contribution to journalComment/debate

@article{6ce2bfcc672044f1b3b9e8e63792e7a2,
title = "Optimal Partitioning of Random Programs Across Two Processors",
abstract = "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.",
author = "Nicol, {David M.}",
year = "1989",
month = "2",
doi = "10.1109/32.21740",
language = "English (US)",
volume = "15",
pages = "134--141",
journal = "IEEE Transactions on Software Engineering",
issn = "0098-5589",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "2",

}

TY - JOUR

T1 - Optimal Partitioning of Random Programs Across Two Processors

AU - Nicol, David M.

PY - 1989/2

Y1 - 1989/2

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0024611250&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0024611250&partnerID=8YFLogxK

U2 - 10.1109/32.21740

DO - 10.1109/32.21740

M3 - Comment/debate

AN - SCOPUS:0024611250

VL - 15

SP - 134

EP - 141

JO - IEEE Transactions on Software Engineering

JF - IEEE Transactions on Software Engineering

SN - 0098-5589

IS - 2

ER -