Load balancing of complex stochastic tasks using stochastic majorization

David Malcolm Nicol, Rahul Simila, Don Towsley

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We consider the static load balancing problem of assigning several large tasks to a (smaller) system of homogeneous processors, where a task's structure is modeled as a branching process, and all tasks are assumed to have stochastically identical behavior. We show how the theory of majorization can be used to obtain a partial order among possible task assignments. The power of this approach may be summarized as follows: a simple comparison between assignments creates an ordering between them that holds for a variety of objective functions as well as for several statistics such as the mean and variance. This partial ordering is particularly useful when heterogeneous constraints are placed on the numbers of tasks that one may assign to the processors. Our results show that if the vector of numbers of tasks assigned to each processor under one mapping is majorized by that of another mapping, then the former mapping is better than the latter with respect to a large number objective functions. In particular, we show how measurements of finishing time, resource utilization, and reliability are all captured by the theory.

Original languageEnglish (US)
Title of host publicationProceedings - IEEE INFOCOM
PublisherPubl by IEEE
Pages1306-1313
Number of pages8
Volume3
ISBN (Print)0818635800
StatePublished - 1993
Externally publishedYes
EventProceedings of the 12th Annual Joint Conference of the IEEE Computer and Communications Societies - IEEE INFOCOM '93 - San Francisco, CA, USA
Duration: Mar 30 1993Apr 1 1993

Other

OtherProceedings of the 12th Annual Joint Conference of the IEEE Computer and Communications Societies - IEEE INFOCOM '93
CitySan Francisco, CA, USA
Period3/30/934/1/93

ASJC Scopus subject areas

  • Hardware and Architecture
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Load balancing of complex stochastic tasks using stochastic majorization'. Together they form a unique fingerprint.

Cite this