Browse Prior Art Database

Class of Efficient Multiple Processor Dispatching Policies

IP.com Disclosure Number: IPCOM000100464D
Original Publication Date: 1990-Apr-01
Included in the Prior Art Database: 2005-Mar-15
Document File: 3 page(s) / 73K

Publishing Venue

IBM

Related People

Chen, MS: AUTHOR [+2]

Abstract

This article describes two simple scheduling policies for dispatching tasks of a large number of identical jobs in a multiple processor (MP) environment. The policy is asymptotically optimum in that its efficiency approaches optimality as the number of jobs becomes large.

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

Class of Efficient Multiple Processor Dispatching Policies

       This article describes two simple scheduling policies for
dispatching tasks of a large number of identical jobs in a multiple
processor (MP) environment.  The policy is asymptotically optimum in
that its efficiency approaches optimality as the number of jobs
becomes large.

      Each job is a set of tasks that must be executed in sequence.
Each task executes one component, and has a fixed path length and a
delay, which is the mandatory job suspension interval after the
completion of the task. Hence, each task is characterized by four
attributes:  (1) task id, (2) component executed, (3) path length
(denoted as Xi) and (4) delay (denoted as di).  A component is
critical if it allows at most one execution at a time, or
non-critical if it allows any number of simultaneous executions on
different processors.  The path length of a component is the sum of
path lengths of tasks executing the component.  The bottleneck is the
component that has the largest path length among critical components.
 Different tasks may execute the same component, and if two tasks
execute the same critical component, they are said to be dependent.

      The primary performance measure is the MP factor, which is the
ratio of total elapsed time if one processor is used versus if
multiple processors are used.  An upper bound on the MP factor can be
found to be min {m, X/Xb}, where m is the number of processors, X is
the total path length of a job, and Xb is the path length of the
bottleneck component.

      Two policies are disclosed:  the Sequentia...