Browse Prior Art Database

MSIS Block Scheduling with Directed Acyclic Graphs

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

Publishing Venue

IBM

Related People

Ekanadham, K: AUTHOR [+6]

Abstract

MSIS (Multisequencing a Single Instruction Stream) is a uniprocessor organization in which a set of processing elements (PEs) 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 52% of the total text.

MSIS Block Scheduling with Directed Acyclic Graphs

       MSIS (Multisequencing a Single Instruction Stream) is a
uniprocessor organization in which a set of processing elements (PEs)
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.

      An MSIS schedule for n PEs is limited by two factors:
o  the number of PEs
o  the speed-up associated with infinite number of PEs, the so-called
Maximum Dependency Time (MDT).

      In schedules generated for small Z-SEGMENTS the performance for
each level of n, where n is the number of PEs, follows one or the
other limitation.  For longer Z-SEGMENTS which can be represented as
repetitions of instructions within a Z-SEGMENT that undergo different
assignments, the performance at 32 PEs stands out as not being
limited by either limitation.

      The constraints on assignment are:
o  The time-slot associated with the assignment of an instruction to
a PE must exceed the MIN_SLOT of the instruction.  The MIN_ SLOT
being defined as the earliest that is later than the time of the
availability of all input to the instruction.  Each timing of
availability being...