Browse Prior Art Database

TASK SCHEDULING ON A MULTIPROCESSOR SYSTEM WITH INDEPENDENT MEMORIES

IP.com Disclosure Number: IPCOM000148429D
Original Publication Date: 1976-Mar-31
Included in the Prior Art Database: 2007-Mar-29
Document File: 38 page(s) / 1M

Publishing Venue

Software Patent Institute

Related People

Kafura, Dennis: AUTHOR [+3]

Abstract

Dennis Kafura V. Y. shen*

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

Page 1 of 38

TASK SCHEDULING ON A MULTIPROCESSOR SYSTEM
WITH INDEPENDENT MEMORIES

Dennis Kafura
V. Y. shen*
Technical Report
f 76-5

March, 1976

*V.Y. Shen, Computer Science Department, Purdue University,
West Lafayette, Indiana 47907

This research was supported in part by NSF Grant No. GJ-3157281.

[This page contains 1 picture or other non-text object]

Page 2 of 38

[This page contains 1 picture or other non-text object]

Page 3 of 38

Abstract

    This paper considers a model of a compilting system with several inde- pendent but identical processors, each with a private memory of limited,

and possibly different, storage capacity. The tasks are assumed to have known resource demands expressed as processjtng times and memory requirements. Several scheduling strategies are evaluated by worst-case performance bounds and simulation results. Both preemptive and non-preemptive scheduling are considered. An optimal preemptive algorithm is given to find the shortest schedule for a task set with no precedence constraints.

t

[This page contains 1 picture or other non-text object]

Page 4 of 38

[This page contains 1 picture or other non-text object]

Page 5 of 38

I. INTRODUCTION


This paper analyces a model of computation with processors and memory

as resources. The allocation of memory has the constraint that only fixed (but possibly different) amounts can be allocated during the scheduling pro- cess. The analysis differs from previous investigations which consider only the processors as the resource to be scheduled [3, 6, 9-11, 22, 23 1,

or which consider the memory resource as a contiguous quantity such that
each memory request may be satisfied by allocating the exact amount requested 18, 19, 201. Since the problem of finding tlhe optimal schedule for most interesting models of computation is "polynomial complete" [4, 17, 251,
this paper analyzes heuristic algorithms in terms of their worst-case be- havior except in the case that an optimal algorithm is available. The mea- sure of performance in this investigation is the maximum finishing time
[9, 10, etc. 1 rather than the mean finishing t i m e sometime used [I].

    The model of computation being analyzed consists of m identical, inde- pendent, abstract processors P , P , . . . , P . Associated with the jth pro- m

cessor is a private memory with fixed size denoted by (P 1. Each memory j

is private in the sense that information contained in the j& memory is accessible only by P The memory sizes are fixed since IP1 1 , 1 ~ ~ 1 ,

. . .,

1P I remain constant throughout the execution of a task set. For conven- m

ience, we w i l l index the processors so that IP I 2 I P ~ + ~

j I . The task set,

J, consists of n tasks, {J1,JZ,..,J 1, where the ith task, Ji: (mi, ti), n -

specifies both a memory requirement, mi, and ii time requirement, ti. An

important scheduling parameter is the number of processors wh...