Browse Prior Art Database

Producer Consumer Synchronization for Single Assignment Languages

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

Publishing Venue

IBM

Related People

Ekanadham, K: AUTHOR [+4]

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

Producer Consumer Synchronization for Single Assignment Languages

       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.

      The role of the E-MODE in MSIS is three-fold:
o  The E-MODE determines the path that is taken in the first
execution of the code.
o  Based on the path, the E-MODE schedules the instructions to the
processor elements.  It is this rational scheduling, based on the
anticipated path taken, that reflects the superiority of MSIS to the
random scheduling that occurs in data-flow designs.
o  The E-MODE gathers and stores information concerning entry points
that allow the parallel code to be entered using the discipline
associated with ownership and flows.

      PCS (Producer-Consumer Synchronization) is defined as a new
language which has many of the characteristics of the Z-CODE in MSIS.
For each instruction it has identified the producer (P) of the inputs
for that instruction and for each instruction it identifies the
consumers (C) for that instruction.  When these instructions are
executed a synchronization (S) between producer and consumer is
required and such a synchronization removes the requirement for
maintenance of conceptual sequence.

      A language is said to be single assignment if any variable is
assigned by only one statement in the language.  For such a language
it is unnecessary to determine that path taken by the program as the
statement that set the variable is uniquely determined.  The
scheduling of the computation is done so as to eliminate the effect
of the presence of both computational options and the CB&E can be
primed so as to use the last correct path taken is entry points are
defined by the E-MODE for both computationa...