Browse Prior Art Database

Metaparallelism - Speculation within Trees

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

Publishing Venue

IBM

Related People

Ekanadham, K: AUTHOR [+3]

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 33% of the total text.

Metaparallelism - Speculation within Trees

      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.

      Given a tree of <2 sup n> - 1 computations with forking
probabilities associated with the branches, the manner of allocating
m processors to computations can be determined in two ways:  the
greatest average depth for a fixed m, or the most efficient depth as
m varies.  Within tree structures, the canonical representation of
path's "as is" orders the paths based on their probabilities and
places paths with higher probability to the left.  This limits the
number of potential assignments that need to be considered.  For any
number of processors, m, that can be assigned to computations within
the tree, the set of assignments range from:

o   A greedy assignment which assigns the processors to the most
    probable path of length m in a m - level tree, to
o   A balanced assignment which assigns the processors to all
    computations of level n or less where m >= <2 sup <n + 1>> - 1 .

The assignment that yields the greatest number of Branch Groups (BGs)
on average can be simply derived from the probabilities of the paths
once these probabilities are ordered by a simple table look-up
operation.  The yields for all lower values of m can be calculated at
the same time.  Thus the choice of speculative assignment can be
based on:

o   assigning a fixed number of processors, or
o   maximizing the efficiency of the assignment.

      A general tree of computations can be illustrated schematically
in the following manner, where O represents a computation to which a
processor has been assigned and X represents an unassigned
computation.  Each symbol (O,X) represen...