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

Paradigm for Parallel Processing Remote/Local Scheduling

IP.com Disclosure Number: IPCOM000104362D
Original Publication Date: 1993-Apr-01
Included in the Prior Art Database: 2005-Mar-19
Document File: 2 page(s) / 76K

Publishing Venue


Related People

Ekanadham, K: AUTHOR [+3]


MSIS can become a Paradigm for Parallel Processing (PPP) by making the instructions play the role of computational steps. Two novel aspects appear:

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

Paradigm for Parallel Processing Remote/Local Scheduling

      MSIS can become a Paradigm for Parallel Processing (PPP) by
making the  instructions  play  the  role  of  computational steps.
Two novel aspects appear:

o   The extension to the OAA that allows differences in dependency
    timings based on a local/remote distinctions.,
o   The recognition that MSIS is a Paradigm for Parallel Processing
    in which instructions are replaced by computational steps.

      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 a PE  sees  all  instructions  in E-MODE, each PE can create
the Z-CODE it will require to re-execute the  Segment as a Z-Segment,
by  associating  with  the  instructions assigned to it, an S-LISTS
and D-LISTS.  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.
The  D-LIST instructs  the PE in the Z-MODE as to the names of PE
that require the values of the register(s) that are being set  by an
instruction that is assigned to it.

      The  basic  decision  as which PE gets which instructions is
the function of the assignment algorithm.  In  our  case  we shall
employ a variant of the Occupancy Assignment Algorithm (OAA).    For
each  instruction  a  determination as to the earliest time that the
instruction can be assignment on  the i-th   PE  will  be  called
MIN-SLOT(i).  Involved  in  the determination  of  MIN-SLOT(i)  are