Browse Prior Art Database

DISTRIBUTED ALGORITHM FOR THE AVERAGE LOAD OF A MULTICOMPUTER

IP.com Disclosure Number: IPCOM000128478D
Original Publication Date: 1984-Mar-01
Included in the Prior Art Database: 2005-Sep-16

Publishing Venue

Software Patent Institute

Related People

Barak, Amnon: AUTHOR [+4]

Abstract

In this paper we investigate distributed algorithms for the average load of a multicomputer which consists of a cluster of independent computers that are interconnected by a local area communication network. These algorithms are useful when it is desired to balance the load between the nodes of the multicomputer.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 12% of the total text.

Page 1 of 10

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

DISTRIBUTED ALGORITHM FOR THE AVERAGE LOAD OF A MULTICOMPUTER

Amnon Barak1 and Zvi Dresner

CRL-TR-17-84

THE UNIVERSITY OF MICHIGAN COMPUTING RESEARCH LABORATORY

MARCH 1984

Room 1079, East Engineering Building
Ann Arbor, Michigan 48109
USA
Tel: (313) 763-8000

DISTRIBUTED ALGORITHMS FOR THE AVERAGE LOAD OF A MULTICOMPUTER Amnon Barak and Zvi Drezner
March 1984

SUMMARY

In this paper we investigate distributed algorithms for the average load of a multicomputer which consists of a cluster of independent computers that are interconnected by a local area communication network. These algorithms are useful when it is desired to balance the load between the nodes of the multicomputer.

The algorithms that we develop are based on exchange of load messages between the nodes of the multicomputer. Two methods for routing load information are suggested. In the first method, each node sends load messages to a fixed set of prespecified nodes. The second method is based on messages which are sent by each node to a randomly selected node. Based on these information exchanges, we show that each node can find the expected global average of the multicomputer. For each case we give the message exchange algorithm, followed by a proof of convergence to the expected average load.

[ Chapter ] 1. INTRODUCTION

The advent of computer and communication systems has brought with it the opportunities to design multicomputer distributed systems for greater resource sharing, improved performance and reliability. A unique property of distributed operating systems is the possibility for automatic allocation of processor resources to programs, similarly to the allocation of primary memory in traditional operating systems. Automatic allocation allows user programs to be unaware of the amount of resources currently available, and it allows a consistent policy to be applied in order to optimize the allocation throughout the system.

1 On leave from The Hebrew University of Jerusalem, Israel.

University of Michigan Computing Research Laboratory Page 1 Mar 01, 1984

Page 2 of 10

DISTRIBUTED ALGORITHM FOR THE AVERAGE LOAD OF A MULTICOMPUTER

As pointed out by Krueger and Finkel 2, load-balancing is a policy for allocating processor resources. The objective is to assign processes to nodes of the multicomputer in such a way that each node has approximately the same workload. When a process is created, a non- preemptive load balancing algorithm permanently assign it to what appears at that moment to be the best node. The process is not moved even though its run-time characteristics later changes in such a way as to cause the nodes to become very unbalanced. Preemptive load balancing algorithms allow load balancing to occur whenever anomalies appear in the work loads of the nodes. If, in the course of execution, the work loads of the nodes become unbalanced, the process can be migrated to a better node to continue its...