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 - Bayesian Branch Prediction on Speculative Processors

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

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

Metaparallelism - Bayesian Branch Prediction on Speculative Processors

      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 branch at which two alternatives are possible, and a
probability associated with the more probable successor, under what
circumstances would one choose to do both successors?  A processor
which allows for speculation involving both alternatives of a branch
can choose to execute both depending on the probability then extant
for the more probable path and the constant characteristics of the
alternatives as they impact the "relative cost" of doing both.  In
conjunction with the probability, common code, unusable cycles, as
well as the available processing power, play a role in the decision
to execute multiple alternatives of a branch concurrently.

      Given a branch, there are many ways to generate a probability
for the next action/target of that branch.  One approach is the count
the frequency with which it goes to each of its targets, another is
to measure the probabi...