Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

BOUNDS ON LIST SCHEDULING OF UET TASKS WITH RESTRICTED RESOURCE.CONSTRAINTS

IP.com Disclosure Number: IPCOM000128158D
Original Publication Date: 1979-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 7 page(s) / 22K

Publishing Venue

Software Patent Institute

Related People

Joseph Y.T. Leung: AUTHOR [+3]

Abstract

We consider the problem of scheduling a Set [Equation ommitted] of n tasks on a multiprocessor computing system consisting of m identical processors. It is assumed that there is a partial ordering-< specified in T in the formof a directed acyclic graph. That is, for [Equation ommitted] then the execution of T cannot be started until the execution of T has been completed. All tasks require unit execution time. In addition, we assume that there is a set of s resources available and the resources are distinguishable from each other. A task may require at most one resource from the set during its execution. We are interested in obtaining a minimal-length, nonpreemptive schedule for T, where the length of a schedule is the time taken to execute all tasks in T subject to the precedence and resource constraints stated above. The scheduling problem mentioned above is easily seen to be a special case of the general model proposed and studied in [4-6,81. Our interest in studying this special case, rather than the more general model, lies in the recent interest in applying multiprocessor computing system to solve large, sparse system of linear equations in order to reduce the solution time [1,9,10,12,131. one of the methods studied in [1,10,121 involves representing the solution process by a directed acyclic graph, where each node represents an operation of updating a certain variable. There is an edge connecting node p to node q if the operation represented by node q requires the result of the operation of node p. Finally, if two nodes update / the same variable, then they will be treated as using the same resource. In this context, a minimal-length schedule will minimize the time needed to solve the system of linear equations. The interested readers is referred to [1,10,121 for 2

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

Page 1 of 7

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

BOUNDS ON LIST SCHEDULING OF UET TASKS WITH RESTRICTED RESOURCE.CONSTRAINTS

100 0 627 Joseph Y-T. Leung Department of Electrical Engineering and Computer Science Northwestern University No. 79-07-FC-03

July, 1979

*This research was supported in part by the National Science Foundation under Grant MCS-79- 04898.

1. Introduction

We consider the problem of scheduling a Set

(Equation Omitted)

of n tasks

on a multiprocessor computing system consisting of m identical processors. It is assumed that there is a partial ordering-< specified in T in the formof a directed acyclic graph. That is, for

(Equation Omitted)

then the execution of T cannot be started until the execution of T has been completed.

All tasks require unit execution time. In addition, we assume that there is a set of s resources available and the resources are distinguishable from each other. A task may require at most one resource from the set during its execution. We are interested in obtaining a minimal-length, nonpreemptive schedule for T, where the length of a schedule is the time taken to execute all tasks in T subject to the precedence and resource constraints stated above.

The scheduling problem mentioned above is easily seen to be a special case of the general model proposed and studied in [4-6,81. Our interest in studying this special case, rather than the more general model, lies in the recent interest in applying multiprocessor computing system to solve large, sparse system of linear equations in order to reduce the solution time [1,9,10,12,131. one of the methods studied in [1,10,121 involves representing the solution process by a directed acyclic graph, where each node represents an operation of updating a certain variable. There is an edge connecting node p to node q if the operation represented by node q requires the result of the operation of node p. Finally, if two nodes update / the same variable, then they will be treated as using the same resource. In this context, a minimal-length schedule will minimize the time needed to solve the system of linear equations. The interested readers is referred to [1,10,121 for 2

more details.

Northwestern University Page 1 Dec 31, 1979

Page 2 of 7

BOUNDS ON LIST SCHEDULING OF UET TASKS WITH RESTRICTED RESOURCE.CONSTRAINTS

Ullman [111 has shown that the problem of determining a minimal-length, nonpreemptive schedule is NP-complete, even when sagl'and m= 2. Thus, it appears that there is no polynomial-time algorithm for solving this problem. For this reason, we are moved to consider heuristics which are easy to im-plement, and which generate schedules reasonably close to the optimal. A class of scheduling algorithms, called list scheduling, has received wide attention in the literature because of its,easiness in implementation. In this type of scheduling algorithms, a list of tasks is initially constructed according to some mechanisms. At any time a processo...