Browse Prior Art Database

TASK SCHEDULING ON A MULTIPROCESSOR SYSTEM WITH INDEPENDENT MEMORIES

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

Publishing Venue

Software Patent Institute

Related People

Dennis Kafura: AUTHOR [+4]

Abstract

This paper considers a model of a computing system with several inde-pendent but identical processors, each with a private memory of limited, d and possibly different, storage capacity. The tasks are assumed to have known resource demands expressed as processing times and memory requirements. Several scheduling strategies are evaluated by worst-case performance bounds and simulation results. Both preemptive andl,non-preemptive scheduling are considered. An optimal preemptive algorithm is given to find the shortest schedule for a task set with no precedence constraints.

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

Page 1 of 21

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

TASK SCHEDULING ON A MULTIPROCESSOR SYSTEM WITH INDEPENDENT MEMORIES

by

Dennis Kafura V. Y. Shen*

Technical Report # 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-31572A1.

Abstract

This paper considers a model of a computing system with several inde-pendent but identical processors, each with a private memory of limited, d and possibly different, storage capacity. The tasks are assumed to have known resource demands expressed as processing times and memory requirements. Several scheduling strategies are evaluated by worst-case performance bounds and simulation results. Both preemptive andl,non-preemptive scheduling are considered. An optimal preemptive algorithm is given to find the shortest schedule for a task set with no precedence constraints.

I. INTRODUCTION

This paper analyzes 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-teas. The analysis differs from previous investigations which consider only the processors as the resource to be scheduled [3, 6, 9-11, 22, 23],, or which consider the memory resource as a contiguous quantity such that each memory request may be satisfied by allocating the exact amount requested [8, 19, 20]. Since the problem of finding the optimal schedule for most interesting models of computation is "polynomial complete" [4, 17,
25], this paper analyses heuristic algorithms in t=erms 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.) rather than the mean finishing time sometime used (1]. The model of computation being analyzed consists of m identical, inde- pendent, abstract~processors

(Equation Omitted)

. Associated with the jth pro-cessor is a private memory with fixed size denoted by IP1 1. Each memory is private.in the sense that information contained in the jth memory is accessible only by P J. The memory sizes are-fixed since..

(Equation Omitted)

Iowa State University Page 1 Dec 31, 1976

Page 2 of 21

TASK SCHEDULING ON A MULTIPROCESSOR SYSTEM WITH INDEPENDENT MEMORIES

remain constant throughout the execution of a task set. For conven-ience, we will index the processors so that

(Equation Omitted)

. The task set, J, consists of n tasks,

(Equation Omitted)

where the ith task, Ji: (mi, ti), specifies both a memory requirement, mi, and a time requirement, ti. An important scheduling parameter is the number of processors which can ex-ecute a given task under the memory constraint:. For the ith task the num-ber of such processors will be denoted by ni. The tasks in J are partially ordered by a precedence relation,

that if Ji < J k, then Jk cannot...