Browse Prior Art Database

Heuristic Models Task Assignment Scheduling in Distributed Systems

IP.com Disclosure Number: IPCOM000131502D
Original Publication Date: 1982-Jun-01
Included in the Prior Art Database: 2005-Nov-11
Document File: 11 page(s) / 39K

Publishing Venue

Software Patent Institute

Related People

Kemal Efe: AUTHOR [+3]

Abstract

University of Leeds

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

Page 1 of 11

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

This record contains textual material that is copyright ©; 1982 by the Institute of Electrical and Electronics Engineers, Inc. All rights reserved. Contact the IEEE Computer Society http://www.computer.org/ (714-821-8380) for copies of the complete work that was the source of this textual material and for all use beyond that as a record from the SPI Database.

Heuristic Models Task Assignment Scheduling in Distributed Systems

Kemal Efe,

University of Leeds

A heuristic approach to task allocation can reduce Saturation in distributed processing by minimizing interprocessor communication under a load-balancing constraint.

When confronted with the need to utilize a remote computer facility or a data base that does not exist in a local computer system, a user looks to distributed processing. Distributed processing not only solves the above problems, it can also increase processing speed by providing facilities for parallel execution. Furthermore, its interconnected set of mini- or microprocessors is flexible, efficient, reliable, modular, and (comparatively) inexpensive.

Distributed processing applications can be found in large networks covering a number o f computing centers and also in small signal-processing systems. When referring to any of these systems in this article, I call the processing elements simply "processors" and use the term "task" for programs or other kinds of code units submitted to a system. Although there are related areas of research in distributed processing environments, including file allocation and processor scheduling, this article concentrates on the problem of task allocation management.

The purpose of task allocation scheduling in a set of interconnected processors is to reduce job turnaround time. This is done by maximizing the utilization of resources while mimimizing any communication between processors. No access conflicts arise from a shared memory (as in a multiple processing system) because every processor is assumed to have its own working area.

The benefits of task allocation scheduling make distributed processing desirable, but several problems must be solved before they can be realized. For example, when the number of processors in a system increases beyond a certain level, throughput decreases. This "saturation effect" can be simply explained: If there are n processors in the system and if each has a processing speed of k, then one would expect the speed of the system to be n x k. In reality, however, a lower processing speed results, caused by such factors as control overheads, communication between processors, unbalanced loading, queueing delays, and the precedence order of the parts of a task assigned to separate processors.

In order to eliminate or minimize saturation, these inhibiting factors must also be eliminated or minimized. First, a fast, dynamic assignment algorithm can be used to attack the control overhead problem. A...