Browse Prior Art Database

Paradigm of Parallel Processing Computational Step Size Disclosure Number: IPCOM000104452D
Original Publication Date: 1993-Apr-01
Included in the Prior Art Database: 2005-Mar-19
Document File: 2 page(s) / 99K

Publishing Venue


Related People

Ekanadham, K: AUTHOR [+2]


To use PPP a relationship between computation step time and message passing time must be established. The PPP is adapted to a broader class of computational paradigms for parallel processing by defining the STU (STEP TIME UNIT) more generally and modifying the assignment algorithm appropriately.

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

Paradigm of Parallel Processing Computational Step Size

      To  use PPP a relationship between computation step time and
message passing time  must  be  established.    The  PPP  is adapted
to  a  broader class of computational paradigms for parallel
processing by defining the  STU  (STEP  TIME  UNIT) more   generally
and  modifying  the  assignment  algorithm appropriately.

      PPP  (Paradigm  of   Parallel   Processing)   involves   the
parallelization   of   computational  steps  uses  the  MSIS
methodology of scheduling.

      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 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  the  inputs  for  the instruction and the PE that sets those
inputs.  A  different timing  is  associated with the dependency if
the dependency

      is local/remote.  That is, if the input is set by the i-th PE
then MIN-SLOT(i) may well be different than MIN-SLOT(j) with i not
equal to j. Following the determination of MIN-SLOT(i) the
availability  of  the  decode  slot  on  the i-th PE is determined.
The first available slot on the i-th  PE  which is  greater  than  or
equal  to  MIN-SLOT(i)  is called the SELECT-SLOT(i).   The
instruction is  scheduled  on ...