Browse Prior Art Database

Metaparallelism - Speculation as Resource Allocation

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

Publishing Venue

IBM

Related People

Ekanadham, K: AUTHOR [+2]

Abstract

Metaparallelism is a process that determines the form of parallelism that is to be used in a specific application. Metaparallelism has two interfaces:

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

Metaparallelism - Speculation as Resource Allocation

      Metaparallelism is a process that determines the form of
parallelism that is to be used in a specific application.
Metaparallelism has two interfaces:

o   Information derived from prior executions.
o   Explicit statements made in the program or compiler output that
    bear on the form of parallelism.

Metaparallelism uses aspects of program behavior as it relates to the
capabilities of the Metaparallel Processor to cope with this behavior
to determine the type of parallelism that is to be pursued.
Metaparallelism employes speculation, that is, allocation of
resources to computations without a guarantee that these computations
are required, in order to complete the application in the faster
time.

The choice of parallelisms that metaparallelism can select from are:

o   Path-oriented forms of parallelism.
o   Path-oriented forms of parallelism with speculation.
o   Computation-oriented parallelism with bifurcation at branches.

o   A set of independent paths that intercommunicate by sending
    messages to each other.
o   A combination of the above.

Metaparallelism employs means at its disposal to alter the form of
parallelism specified by the programmer/compiler at the source level
and to notify the programmer about significant aspects that interfere
with the parallelization of the application.

Speculation can be seen as being resource allocation in two different
ways.

o   From a non-deterministic standpoint, should one do a computation
    which may not be necessary?
o   From a deterministic standpoint, how should a computation be
    done?

The first question can not be answered properly without the second.
Speculation viewed in the context of resource allocation has two
components and the determination of efficiency of speculation is
based on the non-deterministic and deterministic aspects of the
approaches taken, i.e., the speculation.  A programmer can supply his
input to the non-deterministic aspects of the speculation but, the
program behavior dictates often the deterministic aspects.  An
execution will also give rise to posterior probabilities which can be
fed back to the programmer and used by him on subsequent executions,
if they are judged relevant and have a significant impact.

      The subject of speculation is interwoven with the subject of
parallelism, the relationship between speculation and resource
allocation was cast in terms of:

o   Doing computations that may not be necessary,
o   Doing computations with data that may not be valid, or
o   Doing a certain number of repetitions of a computation before the
    actual number of repetitions is known.

In these situations resources have been expended in a probabilistic
manner and the questions as to the efficiency of such a speculative
use of these resources can be investigated only if a more complete
form of speculation is pursued.  Namely, one must first be assured
that...