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

MSIS Use of Independent Subgraphs to Determine a Schedule

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

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

MSIS Use of Independent Subgraphs to Determine a Schedule

       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.

      A more computationally intensive scheduling algorithm which
partitions the overall DAG (Directed Acyclic Graph) into dependent
subgraphs can improve the schedule for each value of n - the number
of processing elements.
      Given: A time-labelled directed acyclic graph, G(V,E), with
unique labelling l(v) for each node v, and a set of n processors.
The label of a node v is the sequence number of the instruction that
is represented by v.
      Required: To assign a processor p(v) and time t(v) to each node
in V such that
          (1) for a given time T, the number of nodes having t(v) = T
is less than n,
          (2) if there is a directed edge from node i to node j then
t(j) > t(i), and
          (3) if p(i) = p(j) and l(i) < l(j) then t(i) < t(j).
  Definitions:
            - An independent node in a DAG is one which has no
incoming edges.
            - The dependent subgraph of a node v consists of the set
of nodes in the DAG each of which has...