Browse Prior Art Database

Algorithm for Optimizing Performance of Distributed Systems by Load Balancing and Minimizing Communication Cost

IP.com Disclosure Number: IPCOM000060501D
Original Publication Date: 1986-Apr-01
Included in the Prior Art Database: 2005-Mar-08
Document File: 3 page(s) / 38K

Publishing Venue

IBM

Related People

Kar, G: AUTHOR [+2]

Abstract

The present invention relates to an algorithm wherein processes constituting the software in a distributed system are assigned hierarchically to physical processors of the system to balance the workload among processors and to dynamically relocate the workload under conditions of processor failure to achieve high availability. In accordance with the invention, a process tree is derived by defining a process graph and organizing the graph into a cluster tree TP based on known techniques. Similarly, a processor graph is organized in a cluster tree TR . The figure depicts an instance of such cluster trees. The allocation algorithm is applied on the process and processor cluster trees TP and TR . The algorithm has two arguments, r and R, which are non-leaf nodes of TP and TR, respectively, where r is assignable to R.

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 53% of the total text.

Page 1 of 3

Algorithm for Optimizing Performance of Distributed Systems by Load Balancing and Minimizing Communication Cost

The present invention relates to an algorithm wherein processes constituting the software in a distributed system are assigned hierarchically to physical processors of the system to balance the workload among processors and to dynamically relocate the workload under conditions of processor failure to achieve high availability. In accordance with the invention, a process tree is derived by defining a process graph and organizing the graph into a cluster tree TP based on known techniques. Similarly, a processor graph is organized in a cluster tree TR . The figure depicts an instance of such cluster trees. The allocation algorithm is applied on the process and processor cluster trees TP and TR . The algorithm has two arguments, r and R, which are non-leaf nodes of TP and TR, respectively, where r is assignable to R. Indicating that all children of R are empty, the following condition is initially assumed:

(Image Omitted)

where g is an "ideal" ratio of the assigned workload over the capacity; e represents the tolerance from the ideal ratio; Vi represents the percentage of unfilled capacity of the ith processor cluster child of R; and SV is a set of Vi for all children of R. The allocation algorithm ALLOCATE(r,R) then follows the steps of:
1. If r and R are roots of TP and TR, respectively, check the global workload constraint:

(Image Omitted)

where n is the total number of processes and each process represents a unit workload, and where Mi is the sum of workload capacities of processors belonging to the cluster represented by the ith child of R. If the above inequality is violated, there is no feasible solution and the algorithm terminates; otherwise, continue. 2. Initialize the sets RAi, for i = 1,2,...,n(R), to empty. Set RAi will contain the indices of the process clusters (children of r) that have been assigned to the ith child of R. 3. Repeat until either Pr = { }, or SV { }. Pr is a set of weights in which each weight wi represents the number of processes of the ith child of node r. Accordingly, a. Let i be the child of R with maximum value of Vi
....