Browse Prior Art Database

First-Pass Parallelism and Register Management

IP.com Disclosure Number: IPCOM000110852D
Original Publication Date: 1994-Jan-01
Included in the Prior Art Database: 2005-Mar-26
Document File: 4 page(s) / 207K

Publishing Venue

IBM

Related People

Rechtschaffen, R: AUTHOR

Abstract

A single instruction stream offers many different forms of potential parallelism in which instructions can be executed based on a set of conditions that will be resolved subsequently. The manner of the execution of these instructions must be made subject to this subsequent resolution. In the case of LOAD and STORE operations to the memory that are performed by such "conditional" instructions, the issues of the conditionality is fairly easy to handle by pending the stores relative to the condition that will be resolved subsequently. A more difficult task is to coordinate the accessing and the changing of GPRs within such a framework. Parallelism requires that the instructions be encoded and the register access and modification reflect such an encoding.

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

First-Pass Parallelism and Register Management

      A single instruction stream offers many different forms of
potential parallelism in which instructions can be executed based on
a set of conditions that will be resolved subsequently.  The manner
of the execution of these instructions must be made subject to this
subsequent resolution.  In the case of LOAD and STORE operations to
the memory that are performed by such "conditional" instructions, the
issues of the conditionality is fairly easy to handle by pending the
stores relative to the condition that will be resolved subsequently.
A more difficult task is to coordinate the accessing and the changing
of GPRs within such a framework.  Parallelism requires that the
instructions be encoded and the register access and modification
reflect such an encoding.  This is done to preserve the serial
correctness of the execution sequence as well as determine a machine
state commensurate with the subsequent resolution of conditions.

MULTINOMIAL INDEXING - The labelling of an instruction within a
branch group involves the number of branches and the action on the
path to the branch group from the current ROOT GROUP.  For each
branch on the path the label specifies the guess of the branch and
uses n-bits (0,1) if n branches have been bypassed.  A tree with
width 3, allowing three bifurcations at three branches, is shown in
the diagram below.  All leaf node branches are three-digit binary
numbers.  The final instructions are always branches if the width of
the tree is the limiting factor.  Sequence numbers are assigned to
instructions incrementally within branch groups, and the first
instruction in both successor branch groups is one higher than the
sequence number of the bifurcating branch.

      In order to coordinate the use of the registers between
different sections of code running in parallel, a means must exist
for a set/use determination between instructions labelled with
different bit strings and/or different sequence numbers.  Only
instructions with lower sequence numbers can set values for
instructions with a given sequence number.  The multinomial index
relationship that relates to set/use is as follows:

      A j-digit binary labeled instruction with sequence number k,
say, can effect only a instruction with a  sequence number greater
than k and having a m - digit binary label which agrees in the lower
j binary digits.

      Thus instructions labelled '0' can set values for instructions
labelled { '0' , '00' , '000' , '10', '100', '110', '010'} and
instructions labelled '1' can set values for instructions labelled {
'1' , '01' , '001' , '11', '101', '111', '011'}.

ROLE OF A BRANCH IN PARALLELISM - A branch instruction, within a
single instruction stream, can play several roles in the forms of
parallelism that are employed to execute that instruction stream in a
shorter number of cycles.  The branch can delimit branch groups that
can be executed in parallel by...