Browse Prior Art Database

Deadlock Free Communication Discipline that is Reducible

IP.com Disclosure Number: IPCOM000105807D
Original Publication Date: 1993-Sep-01
Included in the Prior Art Database: 2005-Mar-20
Document File: 4 page(s) / 137K

Publishing Venue

IBM

Related People

Ekanadham, K: AUTHOR [+2]

Abstract

There are two distinct types of parallelism which can be categorized as Coarse Grained (CG) parallelism and Fine Grained (FG) parallelism. Fine-grained parallelism operates on the instruction level and partitions a putative instruction stream that has a single logical register file and a single memory hierarchy among several processor elements. As such, fine-grained parallelism allows successive instructions to be executed in parallel and requires that the result of such executions conform to a RUBRIC OF SEQUENTIAL CORRECTNESS. Another implication of this is that the memory hierarchy that supports fine-grained parallelism is common to all processor elements that share the same putative instruction stream.

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

Deadlock Free Communication Discipline that is Reducible

      There are two distinct types of parallelism which can be
categorized as Coarse Grained (CG) parallelism and Fine Grained (FG)
parallelism.  Fine-grained parallelism operates on the instruction
level and partitions a putative instruction stream that has a single
logical register file and a single memory hierarchy among several
processor elements.  As such, fine-grained parallelism allows
successive instructions to be executed in parallel and requires that
the result of such executions conform to a RUBRIC OF SEQUENTIAL
CORRECTNESS.  Another implication of this is that the memory
hierarchy that supports fine-grained parallelism is common to all
processor elements that share the same putative instruction stream.

      The basic computational entity within coarse-grained
parallelism is a THREAD which is given a name.  Each THREAD is said
to comprise a sequence of steps (beads) which are one of the
following types:

1.  Compute Step (Using Local Memory/Registers)

2.  Conditional Fork and Thread(Name) Creation

3.  Send Buffer to Name

4.  Wait & Receive Buffer

These threads are called CSR because of the compute-send-receive
aspect of their structure.  The definition of the COMPUTE-STEP
involves a long sequence of instructions that operate within the
context of a local memory which is comprised of private registers and
a private memory hierarchy.  The operation of the SEND-BUFFER and
WAIT&RECEIVE-BUFFER is performed in conjunction with the local memory
associated with the named-THREAD, and different named-THREADS can
have different templates for realizing the structure of the local
memory within the common hardware.  An important parameter of such
coarse-grained parallelism is the ratio of the COMPUTE-STEP time to
the SEND-BUFFER time.  Coarse-grained parallelism usually involves a
distributed memory system in which each CSR is supported by its own
private memory.

DEFINITION OF DATA PARALLELISM

      Let us 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> }

      Let us define a new algorithm &doubleC., such that

               &doubleC.

       sub i &determines.  Q sub i for all i=1,2, ....  , n

      and execute n copies of &doubleC.  in parallel.  This form of
parallelism we shall call DATA PARALLELISM.

      Given a form of DATA PARALLELISM in which all processes have
identical structures, what are the...