A STOCHASTIC LOAD BALANCING MODEL FOR LOOSELY-COUPLED COMPUTER SYSTEMS
Original Publication Date: 1899-Dec-30
Included in the Prior Art Database: 2007-Apr-12
Software Patent Institute
Ni, Lionel M.: AUTHOR [+2]
A STOCHASTIC LOAD BALANCING MODEL FOR Lionel M. N i
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.
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.
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...