Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

A STOCHASTIC LOAD BALANCING MODEL FOR LOOSELY-COUPLED COMPUTER SYSTEMS

IP.com Disclosure Number: IPCOM000148967D
Original Publication Date: 1899-Dec-30
Included in the Prior Art Database: 2007-Apr-12
Document File: 46 page(s) / 1M

Publishing Venue

Software Patent Institute

Related People

Ni, Lionel M.: AUTHOR [+2]

Abstract

A STOCHASTIC LOAD BALANCING MODEL FOR Lionel M. N i Department of Computer Science Michigan State University East Lansing, Michigan 48824 ABSTRACT--To balance the load among multiple processors is of fundamental importance in enhancing the performance of a loosely-coupled multiple processor system (MPS). Optimal stochastic load balancing strategies are studied in this report. Multiple processor systems are classified into four categories according to the processor characteristics, homogeneous versus heterogeneous, and the job environments, single job class versus multiple job classes. Closed-form solutions are derived for scheduling an MPS with single job class. An optimal load balancing algorithm i s developed for an MPS with multiple job classes. The proposed load balancing method is proven globally optimum in the sense that it gives a minimum overall average job response time on a stochastic basis. The stochastic scheduling strategy is easy to implement in an MPS and can be also applied to message routing in packet switched networks.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 8% of the total text.

Page 1 of 46

A STOCHASTIC LOAD BALANCING MODEL FOR

Lionel M. N i

Department of Computer Science

Michigan State University

East Lansing, Michigan 48824

ABSTRACT--To balance the load among multiple processors is of fundamental importance in enhancing the performance of a loosely-coupled multiple processor system (MPS). Optimal stochastic load balancing strategies are studied in this report. Multiple processor systems are classified into four categories according to the processor characteristics, homogeneous versus heterogeneous, and the job environments, single job class versus multiple job classes. Closed-form solutions are derived for scheduling an MPS with single job class. An optimal load balancing algorithm i s developed for an MPS with multiple job classes. The proposed load balancing method is proven globally optimum in the sense that it gives a minimum overall average job response time on a stochastic basis. The stochastic scheduling strategy is easy to implement in an MPS and can be also applied to message routing in packet switched networks.

KEYWORDS :

Multiple Processor System, Load Balancing, Distributed Processing, Stochastic Scheduling, Adaptive Scheduling, M/M/1 Queue,
System Performance, Computer Communications Network.

* Research supported in part by the Division of Engineering Research,

Michigan State University.

[This page contains 1 picture or other non-text object]

Page 2 of 46

[This page contains 1 picture or other non-text object]

Page 3 of 46

-1 -

I. Introduction

    
A loosely coupled Multiple Processor System (MPS) consists of multiple independent processors receiving jobs from a common job scheduler [Ens178, ChKo79, NiHw81, ~wBr811. Such MPS's are considered a kind of distributed computer systems. The motivation to develop MPS is to allow resource sharing and to achieve higher system throughput and availability. The objective of this study is to develop optimal load balancing techniques for achieving the above goals. The system performance of such an MPS is generally indicated by the average job response time.

    In an MPS, the job scheduler is responsible for dispatching incoming jobs among several processors. An arriving job i s routed to one of the processors according to the job scheduling policy and the job characteristics. In this study, the -

                               load of a processor i s characterized by its processing speed and the number of jobs assigned to it. The state of the MPS is indicated by the instantaneous job queue length information. A load balancing strategy used in an MPS is described as either fixed or adaptive depending on whether i t s scheduling decisions are independent of or dependent on the system state.

    Scheduling jobs to processors on a fixed pattern i s classified as fixed policy. A more sophisticated one is the -

                                    stochastic scheduling policy which allocates jobs by fixed probability assignment. In...