Browse Prior Art Database

Fast Algorithm for Scehduling Parallelizable Tasks

IP.com Disclosure Number: IPCOM000105665D
Original Publication Date: 1993-Aug-01
Included in the Prior Art Database: 2005-Mar-20
Document File: 2 page(s) / 69K

Publishing Venue

IBM

Related People

Turek, JJ: AUTHOR [+3]

Abstract

Disclosed is a fast method for approximately solving a multiprocessor scheduling problem for parallellizable (malleable) tasks. Consider a multiprocessor system consisting of P processors, and a set of N tasks which to be scheduled on this system. Assume that each task j memberof {1,...,N} can be allotted an arbitrary number of processors beta sub j memberof {1,...,P}, and that its task execution time t sub j ( beta sub j ) gt 0 is a nonincreasing function of the number of allotted processors. Each of the processors allotted to a task are required to execute that task in unison. That is, these beta sub j processors are all required to start task j at some starting time, say tau sub j. They will then complete task j at some later completion time tau sub j +t sub j ( beta sub j ).

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Fast Algorithm for Scehduling Parallelizable Tasks

      Disclosed is a fast method for approximately solving a
multiprocessor scheduling problem for parallellizable (malleable)
tasks.  Consider a multiprocessor system consisting of P processors,
and a set of N tasks which to be scheduled on this system.  Assume
that each task j memberof {1,...,N}  can be allotted an arbitrary
number of processors beta sub j memberof {1,...,P}, and that its task
execution time t sub j ( beta sub j ) gt 0 is a nonincreasing
function of the number of allotted processors.  Each of the
processors allotted to a task are required to execute that task in
unison.  That is, these beta sub j processors are all required to
start task j at some starting time, say tau sub j.  They will then
complete task j at some later completion time tau sub j +t sub j (
beta sub j ).  A schedule will consist, for each task j memberof
{1,...,N}, of a processor allotment beta sub j, and a starting time
tau sub j.  A schedule is required to be legal in the sense that, for
any time tau, the number of active processors does not exceed the
total number of processors.  In other words,

  sum from <{j vbar tau sub j le tau lt tau sub j + t sub
  j ( beta sub j ) }  >>
  <beta sub j> le P.

An optimal schedule is desired, one for which the overall makespan
given by plex <max> from <1 le j le N> <{  tau sub j + t sub j ( beta
sub j ) }  > is minimized.  In other words, the goal is to minimize
the latest task completion time.

      The new algorithm disclosed here makes use of any algorithm A
that approximately solves the simpler multiprocessor scheduling
problem in which tasks are nonmalleable.  The new algorithm has the
property that for a large class of algorithms A the extension will
guarantee the same worst case performance bounds while increasing the
complexity of A by at most a factor of O(NP).  Specifically, if the
worst case bound for A can be formulated based on the sum of the work
(execution time multiplied by the number processors) of all of the
tasks plus the execution time of the longest task, then the same
bound will apply to the new algorithm.  [1,2,3], among others,
furnish examples.

      The algorithm uses A as a subrouti...