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

Multisequencing a Single Instruction Stream using the Parameter of Occupancy to Moderate Complexity

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

Publishing Venue

IBM

Related People

Ekanadham, K: AUTHOR [+4]

Abstract

Multisequencing a Single Instruction Stream (MSIS) is a uniprocessor organization in which a set of processing elements (PE) working in concert execute Segments of the instruction stream. The Segments are either P-Segments, normal uniprocessor instruction stream portions, that are processed in the E-MODE of MSIS and produce Z-Segments, or the Z-Segments that are processed in Z-MODE by MSIS. The main difference between E-MODE and Z-MODE is that during E-MODE each PE sees all instructions in the Segment and executes the ones that are assigned to it, but during Z-MODE, a PE only sees the instructions assigned to it.

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

Multisequencing a Single Instruction Stream using the Parameter of Occupancy to Moderate Complexity

      Multisequencing a Single Instruction Stream (MSIS) is a
uniprocessor organization in which a set of processing elements (PE)
working in concert execute Segments of the instruction stream.  The
Segments are either P-Segments, normal uniprocessor instruction
stream portions, that are processed in the E-MODE of MSIS and produce
Z-Segments, or the Z-Segments that are processed in  Z-MODE by MSIS.
The main difference between E-MODE and Z-MODE is that during E-MODE
each PE sees all instructions in the Segment and executes the ones
that are assigned to it, but during Z-MODE, a PE only sees the
instructions assigned to it.

      As all PEs see all instructions in E-MODE, each PE can create
the Z-CODE it will require to re-execute the  Segment as a Z-Segment,
the Z-CODE being stored in the Z-CACHE, and associated with
instructions in the Z-CODE are  S-LISTS  and D-LISTS as appropriate.
An S-LIST instructs the PE, in the Z-MODE, that one or more of the
source registers in an instruction assigned to it is set by another
instruction that is executed on another PE, an S-LIST is a receiving
obligation.  The D-LIST instructs the PE in the Z-MODE as to the
names of PEs that require the values of the register(s) that are
being set by an instruction that is assigned to it.  A D-LIST entry
is a sending obligation.

      The relationship between instructions that set a value and
instructions that use a value can be expressed in terms of a Directed
Acyclic Graph (DAG) where the instructions are  the nodes of the
Graph and the arcs specify the set/use dependencies.

      DETERMINING THE DDI - The DAG can be used to determine the
dependency depth  (DDI) of each instruction.  The DDI corresponds to
the cycle of decode of an instruction when there are more PEs  than
instructions and corresponds to the row index of the matrix that
represents the schedule in such a circumstance.

      The simplest way to compute the DDI of an instruction is  to
retain the DDI of the instruction which last set each of the
registers.  The DDI is then computed recursively using these values
that relate to the registers required as input.  Registers in MSIS
are a generalized concept involving those aspects through which the
execution of an instruction depends on the execution of an earlier
instruction.  Suitable adjustment is made for AGEN DEPENDENCY or
EXECUTION DEPENDENCY in computing the resultant DDI.  The maximum
value of the DDI for any instruction in a P-SEGMENT is the MDT
(Maximum Dependency Time) and this is the smallest value of the
length of the schedule - the makespan.

      OCCUPANCY ASSIGNMENT ALGORITHM (OAA) - An Assignment Algorithm
is a rule that determines the decode time of each instruction within
a P-SEGMENT and assigns that instruction to a decode time slot and
PE.  Typically instructions are examined and assigned in c...