Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Metaparallelism - Which Paths Should be Considered

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

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

Metaparallelism - Which Paths Should be Considered

      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.

      The interrelations between the instructions that set values of
registers and the instructions that use those values set.  This
interrelationship can be formulated in terms of a Directed Acyclic
Graph, a DAG.  The nodes of the DAG are instructions and the arcs
represent interrelationships of set/use.

      The paths that can be considered, within a speculative
execution scheme, can be classified as possible paths, probable
paths, or time critical paths.  Given a choice in the sequence of
execution the importance of a path to the timely completion of the
program can be a determining characteristic in path selection.  There
is a way of comparing the time critical aspect of computations in a
fully speculative structure that associates a fixed priority with a
computation based on the virtual speculative structure that emerges
from this computation as a root node.  The priority can be
established using the components of the conditional DAG and directly
reflect the extent to which speculative parallelism beyond this
computation is hampered by delaying this computation.  The priority
is measured in terms of the dependency of subordinate computations on
the root computation in a depth-4 speculative structure.

      Consider the problem of prioritizing the computations that are
part of the speculative tree that emerges from the current machine
state.  The approach to parallelism is to parallelize the speculative
computations and, based on the resolution of the branches, determine
PATH, DAG, and STATE.

      In such a framework a natural form of priorit...