Browse Prior Art Database

Using Modified/Unmodified to Replace Send/Receive in Data Parallelism

IP.com Disclosure Number: IPCOM000106826D
Original Publication Date: 1993-Dec-01
Included in the Prior Art Database: 2005-Mar-21
Document File: 4 page(s) / 144K

Publishing Venue

IBM

Related People

Rechtschaffen, R: AUTHOR

Abstract

The structure of DATA PARALLELISM and the ability to coordinate data set/use, without SEND/RECEIVE and without software locks, by monitoring modified/unmodified status of data that is owned by a single assignment program can be accomplished with virtual processors, <&doubleC.> sub i that are dispatched by a hypervisor, H.

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

Using Modified/Unmodified to Replace Send/Receive in Data Parallelism

      The structure of DATA PARALLELISM and the ability to coordinate
data set/use, without SEND/RECEIVE and without software locks, by
monitoring modified/unmodified status of data that is owned by a
single assignment program can be accomplished with virtual
processors, <&doubleC.> sub i that are dispatched by a hypervisor, H.

      DEFINITION OF DATA PARALLELISM - Consider a datum which is
represented by &doubleP.  and an algorithm &doubleZ.  so that the
result &doubleQ.  is achieved by:

               &doubleZ.:&doubleP.  &determines.  &doubleQ.

      Now we consider a partition of &doubleP.  represented by

           &doubleP.  = { <P sub 1> &cplus.  <P sub 2> &cplus.  <P
sub 3> &cplus.  ...  <&cplus.> <P sub n> }

      and a partition of &doubleQ.  represented by

           &doubleQ.  = { <Q sub 1> &cplus.  <Q sub 2> &cplus.  <Q
sub 3> &cplus.  ...  <&cplus.> <Q sub n> }

      Define a new algorithms <&doubleC.> sub i such that:

               <&doubleC.>sub i

       sub i &determines.  Q sub i for all i=1,2, ....  , n
and execute the n <&doubleC.> sub i programs in parallel.  This form
of parallelism is called DATA PARALLELISM.

      Assume that each of the programs <&doubleC.> sub i is a single
assignment program.  Thus, each of the datum that is owned by
<&doubleC.> sub i, namely <&doubleQ.> sub i is set precisely once and
no other instruction executing on any other processor in the network
can change its value.  If another processor wishes to reference some
datum that is assigned to another processor then a mapping function
either central to the network of processors or within each of the
processors determines the location of the datum and the type of the
datum.  A datum is either Read/Only or Modifiable.

      It is commonly accepted that one means of parallelization
involves the scheduling of work by one process, a hypervisor, for
available processors.  This removes the onus of determining how many
processors are available and how communication between processors can
be optimized.  The resulting system is more portable and also
accommodates a variable run-time environment more easily.  Such a
system can be characterized as a system of virtual processors which
come into being on demand.  Consider a means of extending the concept
of the form of parallelism that was defined as DATA PARALLELIZATION
to systems run under the control of a hypervisor, H that assigns
<&doubleC.> sub i to processors as they are required.  The central
coordination of the H is with respect to <&doubleQ.> sub i. Within
<&doubleQ.> sub i the coordination  is derived from the
modified/unmodified status of a requested datum.

      OPERATION OF THE HYPERVISOR - The operation of H is as follows:

o   A set of <&doubleC.> sub i are assigned to processors and those
    which...