Browse Prior Art Database

Metaparallelism - Merging Components of a Conditional Directed Acyclic Graph

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

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

Metaparallelism - Merging Components of a Conditional Directed Acyclic Graph

      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 components of the conditional DAG are DAG for instruction
interrelationship that relate to computations.  A computation is a
set of sequential instructions that are between two variable
action/target, TYPE-B, branches.  The DAG for the i computation is
conditional in the sense that the computation being only one of
several targets of a variable branch may not be part of the path.  If
is is part of the path, then this DAG can be simply merged with the
DAGs for the other parts of the DAG to create the overall DAG.  The
DAG for a computation has three components that are interrelated:

o   Place-Holder-On-Entry - This allows instructions within the
    computation to show how they depend on values of register set
    prior to the computation and which register are not modified by
    the computation.

o   DAG between instructions within the computation - This shows
    which instructions within the computation set inputs for other
    instructions in the computation.

o   Place-Holder-On-Exit - This allows instructions within the
    computation to show how they set values of registers that may be
    used by computations that follow this computation and which
    registers are not modified by the c...