Abstract

This paper diverges from the traditional load balancing, and introduces a new principle called the on-machine load balance rule. the on-machine load balance rule leads to resource allocations that are better in tolerating uncertainties in the processing times of the tasks allocated to the resources when compared to other resource allocations that are derived using the conventional "across-the-machines" load balancing rule. the on-machine load balance rule calls for the resource allocation algorithms to allocate similarly sized tasks on a machine (in addition to optimizing some primary performance measures such as estimated make span and average response time). the on-machine load balance rule is very different from the usual across-the-machines load balance rule that strives to balance load across resources so that all resources have similar finishing times. We give a mathematical justification for the on-machine load balance rule requiring only liberal assumptions about task processing times. Then we validate with extensive simulations that the resource allocations derived using on-machine load balance rule are indeed more tolerant of uncertain task processing times. © 2010 Elsevier Inc. All rights reserved.

Department(s)

Electrical and Computer Engineering

Keywords and Phrases

Application studies resulting in better multiple-processor systems; Load balancing and task assignment; Measurement, evaluation, modeling, simulation of multiple-processor systems; Resource allocation

International Standard Serial Number (ISSN)

0743-7315

Document Type

Article - Journal

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 2024 Elsevier, All rights reserved.

Publication Date

01 Apr 2011

Download

Full Text Link

Share

 
COinS