Browse Prior Art Database

"Ration Function" That Lets a Parallel Program Adapt Its Processor Requirements to System Load

IP.com Disclosure Number: IPCOM000099381D
Original Publication Date: 1990-Jan-01
Included in the Prior Art Database: 2005-Mar-14
Document File: 3 page(s) / 128K

Publishing Venue

IBM

Related People

Chang, HY: AUTHOR [+2]

Abstract

When a collection of parallel application programs are scheduled on a multiprocessor, the amount of time each program gets to run may well depend of the number of processors the program requests. This disclosure describes a mechanism that makes explicit to each program the relationship between the number of processors it requests and the amount of time it is scheduled to run per unit of elapsed time.

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

"Ration Function" That Lets a Parallel Program Adapt Its Processor Requirements to System Load

       When a collection of parallel application programs are
scheduled on a multiprocessor, the amount of time each program gets
to run may well depend of the number of processors the program
requests.  This disclosure describes a mechanism that makes explicit
to each program the relationship between the number of processors it
requests and the amount of time it is scheduled to run per unit of
elapsed time.

      The problem addressed here is that of allocating the use of a
large parallel processor among a small number of independent jobs
that are themselves parallel application programs.  For the purposes
of this disclosure, a job is an application program that is
structured in such a way that it can make use of multiple processors.
 The size of a job is the number of processors it currently requires,
which may change over time.  While a particular job is running, the
system must give it exclusive use of exactly as many processors as
its size specifies.  A job's ration is a percentage that indicates
the amount of time the job is scheduled to run per unit of elapsed
time.  The sum of the rations of all the jobs in the system will
exceed one if the jobs' sizes allow some of them to run
simultaneously.  The ration the system allocates to a job is likely
to depend on the job's size, because its size determines how well the
job can coexist with other jobs in the system.  If the system makes
explicit to each job the relationship between the job's size and its
ration, the job can choose a size that maximizes the useful work it
can accomplish per unit of elapsed time.

      Disclosed here is the concept of a ration function, a function
the system provides to each job that for every possible job size
gives the fraction of elapsed time the job will actually run.  A
job's ration function encodes information about the system's
scheduling policy and about the other jobs currently in the system.
It lets the job choose and optimal size given its internal
parallelism and efficiency.  To use the function effectively, a job
should maintain an internal work rate function that for each possible
job size gives the rate at which the job can accomplish useful work
while it is running.  The product of a job's ration and work rate
functions then gives the effective rate at which the job can
accomplish useful work for each possible job size.  The job should
simply choose the size that maximizes that product.  To avoid
trashing it must also consider the restructuring costs associated
with a change in size.

      The ration function is most naturally represented as an array
of percentages indexed by job size.  The system can use one of
several possible mechanisms to make the array available to a job it
controls.  The array can be stored in memory that is shared between
the system and the job, it can be returned to the job via a system
call...