Browse Prior Art Database

TASK SCHEDULING ON PROCESSOR OF DIFFERENT SPEEDS

IP.com Disclosure Number: IPCOM000127997D
Original Publication Date: 1976-Dec-31
Included in the Prior Art Database: 2005-Sep-14
Document File: 7 page(s) / 23K

Publishing Venue

Software Patent Institute

Related People

Dennis Kafura: AUTHOR [+4]

Abstract

Many computing systems manufactured recently have lines of processors that are different in execution speeds but otherwise compatible. Examples are the IBM 360/3J0, and the CDC Cyber series. This paper .discusses; strategies to schedule~independent tasks in a configuration that has several compatible.processors whose relative speeds are different. 'The model considered has m processors. Let si be the speed of

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

Page 1 of 7

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

TASK SCHEDULING ON PROCESSOR OF DIFFERENT SPEEDS

Dennis Kafura V. Y. Shen .

Technical Report # 76-4 October, 1975

Task Scheduling on Processors of Diff erent.Speeds

by

D. G. Kafura V. Y. Shen Computer Science Department Computer Sciences Department Iowa State University Purdue University Awes, Iowa 50011 W: Lafayette, Indiana 47907

ABSTRACT

Many computing systems manufactured recently have lines of processors that are different in execution speeds but otherwise compatible. Examples are the IBM 360/3J0, and the CDC Cyber series. This paper .discusses; strategies to schedule~independent tasks in a configuration that has several compatible.processors whose relative speeds are different. 'The model considered has m processors. Let si be the speed of

the ith processor and

(Equation Omitted)

(the first processor being the fastest. Let TL be the schedule completion time of an, arbitrary list of tasks (with arbitrary precedence constraints) and T MIN be the length of the optimal schedule
.for the same set of r tasks, we have established that

(Equation Omitted)

and the bound is the'best possible. Note that the bound reduces to' 2-1/m when the speeds are equal, which is the same. as the bound derived by Graham. If we schedule mutually~ind'ependent taNks according to a largest time-f first (LTF) list, we have

(Equation Omitted)

I. INTRODUCTION

The use of deterministic methods.in analysing models of multiprocessing computer systems has produced numerous interesting results in recent .years. The basic model studied has a collection of identical processors as the single resource to be allocated

3,4 ]. This basic model has been extended in many ways. There now are models of computation that have more than one type of resources to be allocated. Examples are systems with identical

Iowa State University Page 1 Dec 31, 1976

Page 2 of 7

TASK SCHEDULING ON PROCESSOR OF DIFFERENT SPEEDS

processors sharing a common memory C 7,$ ], identical processors each possessing a private memory C 5,6 ', and identical professors sharing an arbitrary number of common resources [ 1,2 ~. This paper returns to the basic model with processors as the only resource.. However, the processors are trot truly identical; they perform the same functions at different speeds. A similar model was also considered in ~ 9,10 3, abet has the additional feature. of preemption: ` A model with processors of different speeds is of practical importance due to the existence of compatible processor lines differing only in their execution speeds.' This model is also equivalent to a single processor providing varying rates of service to tasks in different priority classes.. Formally, the model consists of m independent processors where the speed of the ith processor is denoted by si. The pro- cessors are indexed so that

(Equation Omitted)

, and sl is the fastest processsor. There is a set of n tasks where the ith task, Ti, is repr...